./Ultimate.py --spec ../../sv-benchmarks/c/properties/unreach-call.prp --file ../../sv-benchmarks/c/nla-digbench-scaling/hard-ll_unwindbound50.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 826ab2ba Calling Ultimate with: /usr/bin/java -Dosgi.configuration.area=/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E/plugins/org.eclipse.equinox.launcher_1.6.800.v20240513-1750.jar -data @noDefault -ultimatedata /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E/config/TaipanReach.xml -i ../../sv-benchmarks/c/nla-digbench-scaling/hard-ll_unwindbound50.c -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E/config/svcomp-Reach-32bit-Taipan_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(G ! call(reach_error())) ) --witnessprinter.graph.data.producer Taipan --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash aefc568e9b7c922872a103ac050823e614044aea4bac2f22f2c586f3247176b4 --- Real Ultimate output --- This is Ultimate 0.3.0-dev-826ab2b [2024-11-14 02:42:56,718 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-14 02:42:56,814 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E/config/svcomp-Reach-32bit-Taipan_Default.epf [2024-11-14 02:42:56,822 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-14 02:42:56,822 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-14 02:42:56,856 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-14 02:42:56,856 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-14 02:42:56,856 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-14 02:42:56,857 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-14 02:42:56,857 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-14 02:42:56,857 INFO L153 SettingsManager]: * User list type=DISABLED [2024-11-14 02:42:56,857 INFO L151 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2024-11-14 02:42:56,857 INFO L153 SettingsManager]: * Explicit value domain=true [2024-11-14 02:42:56,857 INFO L153 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2024-11-14 02:42:56,857 INFO L153 SettingsManager]: * Octagon Domain=false [2024-11-14 02:42:56,858 INFO L153 SettingsManager]: * Abstract domain=CompoundDomain [2024-11-14 02:42:56,858 INFO L153 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2024-11-14 02:42:56,858 INFO L153 SettingsManager]: * Use the RCFG-of-the-future interface=true [2024-11-14 02:42:56,858 INFO L153 SettingsManager]: * Interval Domain=false [2024-11-14 02:42:56,858 INFO L151 SettingsManager]: Preferences of Sifa differ from their defaults: [2024-11-14 02:42:56,858 INFO L153 SettingsManager]: * Call Summarizer=TopInputCallSummarizer [2024-11-14 02:42:56,858 INFO L153 SettingsManager]: * Simplification Technique=POLY_PAC [2024-11-14 02:42:56,859 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-14 02:42:56,859 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-14 02:42:56,859 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-14 02:42:56,859 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-14 02:42:56,859 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-14 02:42:56,859 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-14 02:42:56,859 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-14 02:42:56,859 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-14 02:42:56,859 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-14 02:42:56,860 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-14 02:42:56,860 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-14 02:42:56,860 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-14 02:42:56,860 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-14 02:42:56,860 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-14 02:42:56,860 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-14 02:42:56,860 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-14 02:42:56,860 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2024-11-14 02:42:56,861 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-14 02:42:56,861 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-14 02:42:56,861 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-14 02:42:56,861 INFO L153 SettingsManager]: * Trace refinement strategy=SIFA_TAIPAN [2024-11-14 02:42:56,861 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-14 02:42:56,862 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-14 02:42:56,862 INFO L153 SettingsManager]: * Trace refinement exception blacklist=NONE [2024-11-14 02:42:56,862 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-14 02:42:56,862 INFO L153 SettingsManager]: * Abstract interpretation Mode=USE_PREDICATES Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Entry function -> main Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness directory -> /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Write witness besides input file -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data specification -> CHECK( init(main()), LTL(G ! call(reach_error())) ) Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data producer -> Taipan Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data architecture -> 32bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> aefc568e9b7c922872a103ac050823e614044aea4bac2f22f2c586f3247176b4 [2024-11-14 02:42:57,186 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-14 02:42:57,196 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-14 02:42:57,198 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-14 02:42:57,200 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-14 02:42:57,200 INFO L274 PluginConnector]: CDTParser initialized [2024-11-14 02:42:57,201 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E/../../sv-benchmarks/c/nla-digbench-scaling/hard-ll_unwindbound50.c Unable to find full path for "g++" [2024-11-14 02:42:59,060 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-14 02:42:59,338 INFO L384 CDTParser]: Found 1 translation units. [2024-11-14 02:42:59,339 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/sv-benchmarks/c/nla-digbench-scaling/hard-ll_unwindbound50.c [2024-11-14 02:42:59,349 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E/data/8fae36ae6/aec0da1f5ce642ad82018c6632a51f5b/FLAG65c36a757 [2024-11-14 02:42:59,381 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E/data/8fae36ae6/aec0da1f5ce642ad82018c6632a51f5b [2024-11-14 02:42:59,385 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-14 02:42:59,387 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-14 02:42:59,390 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-14 02:42:59,391 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-14 02:42:59,396 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-14 02:42:59,397 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 14.11 02:42:59" (1/1) ... [2024-11-14 02:42:59,399 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@3b2b8f42 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:42:59, skipping insertion in model container [2024-11-14 02:42:59,400 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 14.11 02:42:59" (1/1) ... [2024-11-14 02:42:59,420 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-14 02:42:59,605 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/sv-benchmarks/c/nla-digbench-scaling/hard-ll_unwindbound50.c[538,551] [2024-11-14 02:42:59,642 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-14 02:42:59,663 INFO L200 MainTranslator]: Completed pre-run [2024-11-14 02:42:59,675 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/sv-benchmarks/c/nla-digbench-scaling/hard-ll_unwindbound50.c[538,551] [2024-11-14 02:42:59,691 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-14 02:42:59,706 INFO L204 MainTranslator]: Completed translation [2024-11-14 02:42:59,707 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:42:59 WrapperNode [2024-11-14 02:42:59,707 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-14 02:42:59,708 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-14 02:42:59,708 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-14 02:42:59,708 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-14 02:42:59,717 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:42:59" (1/1) ... [2024-11-14 02:42:59,724 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:42:59" (1/1) ... [2024-11-14 02:42:59,751 INFO L138 Inliner]: procedures = 14, calls = 15, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 64 [2024-11-14 02:42:59,752 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-14 02:42:59,753 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-14 02:42:59,753 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-14 02:42:59,754 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-14 02:42:59,763 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:42:59" (1/1) ... [2024-11-14 02:42:59,764 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:42:59" (1/1) ... [2024-11-14 02:42:59,770 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:42:59" (1/1) ... [2024-11-14 02:42:59,770 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:42:59" (1/1) ... [2024-11-14 02:42:59,774 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:42:59" (1/1) ... [2024-11-14 02:42:59,785 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:42:59" (1/1) ... [2024-11-14 02:42:59,786 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:42:59" (1/1) ... [2024-11-14 02:42:59,787 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:42:59" (1/1) ... [2024-11-14 02:42:59,788 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-14 02:42:59,793 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-14 02:42:59,793 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-14 02:42:59,793 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-14 02:42:59,794 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:42:59" (1/1) ... [2024-11-14 02:42:59,804 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2024-11-14 02:42:59,820 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 02:42:59,835 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2024-11-14 02:42:59,841 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2024-11-14 02:42:59,874 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-14 02:42:59,875 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2024-11-14 02:42:59,875 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-14 02:42:59,875 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-14 02:42:59,875 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-14 02:42:59,876 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-14 02:42:59,961 INFO L238 CfgBuilder]: Building ICFG [2024-11-14 02:42:59,963 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-14 02:43:00,169 INFO L? ?]: Removed 7 outVars from TransFormulas that were not future-live. [2024-11-14 02:43:00,169 INFO L287 CfgBuilder]: Performing block encoding [2024-11-14 02:43:00,262 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-14 02:43:00,262 INFO L316 CfgBuilder]: Removed 2 assume(true) statements. [2024-11-14 02:43:00,262 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 14.11 02:43:00 BoogieIcfgContainer [2024-11-14 02:43:00,263 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-14 02:43:00,265 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-14 02:43:00,265 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-14 02:43:00,271 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-14 02:43:00,271 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 14.11 02:42:59" (1/3) ... [2024-11-14 02:43:00,272 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@b13319a and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 14.11 02:43:00, skipping insertion in model container [2024-11-14 02:43:00,272 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:42:59" (2/3) ... [2024-11-14 02:43:00,272 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@b13319a and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 14.11 02:43:00, skipping insertion in model container [2024-11-14 02:43:00,273 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 14.11 02:43:00" (3/3) ... [2024-11-14 02:43:00,274 INFO L112 eAbstractionObserver]: Analyzing ICFG hard-ll_unwindbound50.c [2024-11-14 02:43:00,292 INFO L217 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-14 02:43:00,293 INFO L154 ceAbstractionStarter]: Applying trace abstraction to ICFG hard-ll_unwindbound50.c that has 2 procedures, 22 locations, 1 initial locations, 2 loop locations, and 1 error locations. [2024-11-14 02:43:00,374 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-14 02:43:00,392 INFO L333 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=FPandBP, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mAutomataTypeConcurrency=FINITE_AUTOMATA, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=LoopHeads, mDumpOnlyReuseAutomata=false, mLimitTraceHistogram=0, mErrorLocTimeLimit=0, mLimitPathProgramCount=0, mCollectInterpolantStatistics=true, mHeuristicEmptinessCheck=false, mHeuristicEmptinessCheckAStarHeuristic=ZERO, mHeuristicEmptinessCheckAStarHeuristicRandomSeed=1337, mHeuristicEmptinessCheckSmtFeatureScoringMethod=DAGSIZE, mSMTFeatureExtraction=false, mSMTFeatureExtractionDumpPath=., mOverrideInterpolantAutomaton=false, mMcrInterpolantMethod=WP, mPorIndependenceSettings=[Lde.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings;@1dd402e7, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-14 02:43:00,393 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-14 02:43:00,399 INFO L276 IsEmpty]: Start isEmpty. Operand has 22 states, 12 states have (on average 1.6666666666666667) internal successors, (20), 13 states have internal predecessors, (20), 7 states have call successors, (7), 1 states have call predecessors, (7), 1 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2024-11-14 02:43:00,407 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 8 [2024-11-14 02:43:00,408 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 02:43:00,409 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2024-11-14 02:43:00,410 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 02:43:00,415 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 02:43:00,416 INFO L85 PathProgramCache]: Analyzing trace with hash -1654084864, now seen corresponding path program 1 times [2024-11-14 02:43:00,425 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 02:43:00,426 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1415092120] [2024-11-14 02:43:00,426 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:43:00,427 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 02:43:00,530 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 02:43:00,597 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 02:43:00,597 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 02:43:00,598 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1415092120] [2024-11-14 02:43:00,601 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1415092120] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 02:43:00,601 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 02:43:00,601 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-11-14 02:43:00,603 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [990674839] [2024-11-14 02:43:00,604 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 02:43:00,608 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-11-14 02:43:00,609 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 02:43:00,634 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-11-14 02:43:00,635 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-14 02:43:00,637 INFO L87 Difference]: Start difference. First operand has 22 states, 12 states have (on average 1.6666666666666667) internal successors, (20), 13 states have internal predecessors, (20), 7 states have call successors, (7), 1 states have call predecessors, (7), 1 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) Second operand has 2 states, 2 states have (on average 3.0) internal successors, (6), 2 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-14 02:43:00,674 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 02:43:00,675 INFO L93 Difference]: Finished difference Result 43 states and 74 transitions. [2024-11-14 02:43:00,676 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-14 02:43:00,677 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 3.0) internal successors, (6), 2 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 7 [2024-11-14 02:43:00,677 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 02:43:00,684 INFO L225 Difference]: With dead ends: 43 [2024-11-14 02:43:00,684 INFO L226 Difference]: Without dead ends: 20 [2024-11-14 02:43:00,687 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-14 02:43:00,691 INFO L432 NwaCegarLoop]: 28 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 3 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 28 SdHoareTripleChecker+Invalid, 3 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 3 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-14 02:43:00,691 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 28 Invalid, 3 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 3 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-14 02:43:00,707 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 20 states. [2024-11-14 02:43:00,721 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 20 to 20. [2024-11-14 02:43:00,722 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 20 states, 11 states have (on average 1.4545454545454546) internal successors, (16), 12 states have internal predecessors, (16), 7 states have call successors, (7), 1 states have call predecessors, (7), 1 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-14 02:43:00,726 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 20 states to 20 states and 29 transitions. [2024-11-14 02:43:00,728 INFO L78 Accepts]: Start accepts. Automaton has 20 states and 29 transitions. Word has length 7 [2024-11-14 02:43:00,728 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 02:43:00,728 INFO L471 AbstractCegarLoop]: Abstraction has 20 states and 29 transitions. [2024-11-14 02:43:00,729 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 3.0) internal successors, (6), 2 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-14 02:43:00,729 INFO L276 IsEmpty]: Start isEmpty. Operand 20 states and 29 transitions. [2024-11-14 02:43:00,730 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 8 [2024-11-14 02:43:00,730 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 02:43:00,730 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2024-11-14 02:43:00,730 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-14 02:43:00,731 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 02:43:00,731 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 02:43:00,731 INFO L85 PathProgramCache]: Analyzing trace with hash -2115219753, now seen corresponding path program 1 times [2024-11-14 02:43:00,731 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 02:43:00,732 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1050342385] [2024-11-14 02:43:00,732 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:43:00,732 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 02:43:00,751 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 02:43:00,924 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 02:43:00,924 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 02:43:00,924 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1050342385] [2024-11-14 02:43:00,924 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1050342385] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 02:43:00,924 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 02:43:00,925 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2024-11-14 02:43:00,925 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1750954257] [2024-11-14 02:43:00,925 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 02:43:00,926 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-14 02:43:00,926 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 02:43:00,927 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-14 02:43:00,927 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-14 02:43:00,927 INFO L87 Difference]: Start difference. First operand 20 states and 29 transitions. Second operand has 5 states, 5 states have (on average 1.2) internal successors, (6), 3 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-14 02:43:01,032 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 02:43:01,032 INFO L93 Difference]: Finished difference Result 33 states and 46 transitions. [2024-11-14 02:43:01,033 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-14 02:43:01,033 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.2) internal successors, (6), 3 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 7 [2024-11-14 02:43:01,033 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 02:43:01,034 INFO L225 Difference]: With dead ends: 33 [2024-11-14 02:43:01,034 INFO L226 Difference]: Without dead ends: 31 [2024-11-14 02:43:01,035 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-14 02:43:01,036 INFO L432 NwaCegarLoop]: 24 mSDtfsCounter, 10 mSDsluCounter, 58 mSDsCounter, 0 mSdLazyCounter, 24 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 16 SdHoareTripleChecker+Valid, 82 SdHoareTripleChecker+Invalid, 24 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 24 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-14 02:43:01,036 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [16 Valid, 82 Invalid, 24 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 24 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-14 02:43:01,037 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 31 states. [2024-11-14 02:43:01,052 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 31 to 24. [2024-11-14 02:43:01,052 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 24 states, 14 states have (on average 1.3571428571428572) internal successors, (19), 15 states have internal predecessors, (19), 7 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-14 02:43:01,053 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 32 transitions. [2024-11-14 02:43:01,054 INFO L78 Accepts]: Start accepts. Automaton has 24 states and 32 transitions. Word has length 7 [2024-11-14 02:43:01,054 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 02:43:01,054 INFO L471 AbstractCegarLoop]: Abstraction has 24 states and 32 transitions. [2024-11-14 02:43:01,054 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.2) internal successors, (6), 3 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-14 02:43:01,054 INFO L276 IsEmpty]: Start isEmpty. Operand 24 states and 32 transitions. [2024-11-14 02:43:01,055 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 10 [2024-11-14 02:43:01,055 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 02:43:01,055 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 02:43:01,055 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-11-14 02:43:01,057 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 02:43:01,063 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 02:43:01,063 INFO L85 PathProgramCache]: Analyzing trace with hash 174216846, now seen corresponding path program 1 times [2024-11-14 02:43:01,063 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 02:43:01,063 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [777326917] [2024-11-14 02:43:01,063 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:43:01,063 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 02:43:01,103 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 02:43:01,220 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 02:43:01,223 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 02:43:01,223 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [777326917] [2024-11-14 02:43:01,223 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [777326917] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 02:43:01,223 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 02:43:01,223 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2024-11-14 02:43:01,223 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1585880211] [2024-11-14 02:43:01,223 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 02:43:01,223 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-11-14 02:43:01,224 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 02:43:01,224 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-11-14 02:43:01,224 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-14 02:43:01,224 INFO L87 Difference]: Start difference. First operand 24 states and 32 transitions. Second operand has 4 states, 4 states have (on average 2.0) internal successors, (8), 3 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-14 02:43:01,256 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 02:43:01,256 INFO L93 Difference]: Finished difference Result 39 states and 52 transitions. [2024-11-14 02:43:01,257 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-11-14 02:43:01,257 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 2.0) internal successors, (8), 3 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 9 [2024-11-14 02:43:01,257 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 02:43:01,257 INFO L225 Difference]: With dead ends: 39 [2024-11-14 02:43:01,258 INFO L226 Difference]: Without dead ends: 26 [2024-11-14 02:43:01,258 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-14 02:43:01,259 INFO L432 NwaCegarLoop]: 25 mSDtfsCounter, 0 mSDsluCounter, 48 mSDsCounter, 0 mSdLazyCounter, 13 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 73 SdHoareTripleChecker+Invalid, 13 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 13 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-14 02:43:01,259 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 73 Invalid, 13 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 13 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-14 02:43:01,260 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 26 states. [2024-11-14 02:43:01,264 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 26 to 26. [2024-11-14 02:43:01,265 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 26 states, 16 states have (on average 1.3125) internal successors, (21), 17 states have internal predecessors, (21), 7 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-14 02:43:01,266 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 34 transitions. [2024-11-14 02:43:01,266 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 34 transitions. Word has length 9 [2024-11-14 02:43:01,266 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 02:43:01,266 INFO L471 AbstractCegarLoop]: Abstraction has 26 states and 34 transitions. [2024-11-14 02:43:01,266 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 2.0) internal successors, (8), 3 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-14 02:43:01,266 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 34 transitions. [2024-11-14 02:43:01,267 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2024-11-14 02:43:01,267 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 02:43:01,267 INFO L215 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 02:43:01,267 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2024-11-14 02:43:01,267 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 02:43:01,267 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 02:43:01,268 INFO L85 PathProgramCache]: Analyzing trace with hash 1872131942, now seen corresponding path program 1 times [2024-11-14 02:43:01,268 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 02:43:01,268 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1872685696] [2024-11-14 02:43:01,268 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:43:01,268 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 02:43:01,280 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 02:43:01,430 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 02:43:01,430 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 02:43:01,430 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1872685696] [2024-11-14 02:43:01,430 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1872685696] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 02:43:01,431 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 02:43:01,431 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-14 02:43:01,431 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [407874354] [2024-11-14 02:43:01,431 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 02:43:01,431 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-14 02:43:01,431 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 02:43:01,432 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-14 02:43:01,432 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-14 02:43:01,432 INFO L87 Difference]: Start difference. First operand 26 states and 34 transitions. Second operand has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 states have internal predecessors, (9), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-14 02:43:01,507 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 02:43:01,507 INFO L93 Difference]: Finished difference Result 39 states and 51 transitions. [2024-11-14 02:43:01,508 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-14 02:43:01,508 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 states have internal predecessors, (9), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 12 [2024-11-14 02:43:01,508 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 02:43:01,509 INFO L225 Difference]: With dead ends: 39 [2024-11-14 02:43:01,509 INFO L226 Difference]: Without dead ends: 37 [2024-11-14 02:43:01,510 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-14 02:43:01,511 INFO L432 NwaCegarLoop]: 25 mSDtfsCounter, 10 mSDsluCounter, 58 mSDsCounter, 0 mSdLazyCounter, 31 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 15 SdHoareTripleChecker+Valid, 83 SdHoareTripleChecker+Invalid, 31 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 31 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-14 02:43:01,512 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [15 Valid, 83 Invalid, 31 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 31 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-14 02:43:01,512 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 37 states. [2024-11-14 02:43:01,519 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 37 to 30. [2024-11-14 02:43:01,519 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 30 states, 19 states have (on average 1.263157894736842) internal successors, (24), 20 states have internal predecessors, (24), 7 states have call successors, (7), 3 states have call predecessors, (7), 3 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-14 02:43:01,520 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 30 states to 30 states and 37 transitions. [2024-11-14 02:43:01,520 INFO L78 Accepts]: Start accepts. Automaton has 30 states and 37 transitions. Word has length 12 [2024-11-14 02:43:01,520 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 02:43:01,521 INFO L471 AbstractCegarLoop]: Abstraction has 30 states and 37 transitions. [2024-11-14 02:43:01,521 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 states have internal predecessors, (9), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-14 02:43:01,521 INFO L276 IsEmpty]: Start isEmpty. Operand 30 states and 37 transitions. [2024-11-14 02:43:01,521 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2024-11-14 02:43:01,521 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 02:43:01,521 INFO L215 NwaCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 02:43:01,522 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2024-11-14 02:43:01,522 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 02:43:01,522 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 02:43:01,522 INFO L85 PathProgramCache]: Analyzing trace with hash -1306040329, now seen corresponding path program 1 times [2024-11-14 02:43:01,522 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 02:43:01,522 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2035963317] [2024-11-14 02:43:01,523 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:43:01,523 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 02:43:01,547 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 02:43:01,549 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [820348738] [2024-11-14 02:43:01,552 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:43:01,552 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 02:43:01,552 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 02:43:01,555 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 02:43:01,557 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-11-14 02:43:01,631 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 02:43:01,637 INFO L255 TraceCheckSpWp]: Trace formula consists of 64 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-14 02:43:01,645 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 02:43:01,796 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-14 02:43:01,796 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-14 02:43:01,796 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 02:43:01,796 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2035963317] [2024-11-14 02:43:01,797 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-14 02:43:01,797 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [820348738] [2024-11-14 02:43:01,797 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [820348738] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 02:43:01,797 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 02:43:01,797 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-14 02:43:01,798 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1315259268] [2024-11-14 02:43:01,798 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 02:43:01,798 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-14 02:43:01,798 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 02:43:01,801 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-14 02:43:01,801 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-14 02:43:01,801 INFO L87 Difference]: Start difference. First operand 30 states and 37 transitions. Second operand has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 states have internal predecessors, (9), 1 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-14 02:43:01,923 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 02:43:01,924 INFO L93 Difference]: Finished difference Result 58 states and 78 transitions. [2024-11-14 02:43:01,924 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-14 02:43:01,924 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 states have internal predecessors, (9), 1 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 17 [2024-11-14 02:43:01,925 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 02:43:01,925 INFO L225 Difference]: With dead ends: 58 [2024-11-14 02:43:01,926 INFO L226 Difference]: Without dead ends: 44 [2024-11-14 02:43:01,926 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 17 GetRequests, 13 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-14 02:43:01,927 INFO L432 NwaCegarLoop]: 23 mSDtfsCounter, 7 mSDsluCounter, 59 mSDsCounter, 0 mSdLazyCounter, 41 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 82 SdHoareTripleChecker+Invalid, 44 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 41 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-14 02:43:01,927 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 82 Invalid, 44 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 41 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-14 02:43:01,930 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 44 states. [2024-11-14 02:43:01,944 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 44 to 44. [2024-11-14 02:43:01,949 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 44 states, 26 states have (on average 1.2692307692307692) internal successors, (33), 28 states have internal predecessors, (33), 13 states have call successors, (13), 4 states have call predecessors, (13), 4 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2024-11-14 02:43:01,950 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 44 states to 44 states and 57 transitions. [2024-11-14 02:43:01,950 INFO L78 Accepts]: Start accepts. Automaton has 44 states and 57 transitions. Word has length 17 [2024-11-14 02:43:01,950 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 02:43:01,950 INFO L471 AbstractCegarLoop]: Abstraction has 44 states and 57 transitions. [2024-11-14 02:43:01,950 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 states have internal predecessors, (9), 1 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-14 02:43:01,950 INFO L276 IsEmpty]: Start isEmpty. Operand 44 states and 57 transitions. [2024-11-14 02:43:01,951 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2024-11-14 02:43:01,951 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 02:43:01,951 INFO L215 NwaCegarLoop]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 02:43:01,975 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2024-11-14 02:43:02,158 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 02:43:02,158 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 02:43:02,158 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 02:43:02,159 INFO L85 PathProgramCache]: Analyzing trace with hash -507918445, now seen corresponding path program 1 times [2024-11-14 02:43:02,159 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 02:43:02,159 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1677890927] [2024-11-14 02:43:02,159 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:43:02,159 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 02:43:02,188 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 02:43:02,329 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-11-14 02:43:02,329 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 02:43:02,329 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1677890927] [2024-11-14 02:43:02,330 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1677890927] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 02:43:02,330 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 02:43:02,330 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2024-11-14 02:43:02,330 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1179624011] [2024-11-14 02:43:02,330 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 02:43:02,330 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-14 02:43:02,331 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 02:43:02,331 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-14 02:43:02,331 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-14 02:43:02,331 INFO L87 Difference]: Start difference. First operand 44 states and 57 transitions. Second operand has 6 states, 6 states have (on average 2.0) internal successors, (12), 6 states have internal predecessors, (12), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2024-11-14 02:43:02,416 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 02:43:02,417 INFO L93 Difference]: Finished difference Result 63 states and 72 transitions. [2024-11-14 02:43:02,418 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-14 02:43:02,418 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.0) internal successors, (12), 6 states have internal predecessors, (12), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) Word has length 25 [2024-11-14 02:43:02,418 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 02:43:02,419 INFO L225 Difference]: With dead ends: 63 [2024-11-14 02:43:02,419 INFO L226 Difference]: Without dead ends: 56 [2024-11-14 02:43:02,419 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-14 02:43:02,420 INFO L432 NwaCegarLoop]: 23 mSDtfsCounter, 7 mSDsluCounter, 79 mSDsCounter, 0 mSdLazyCounter, 41 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 102 SdHoareTripleChecker+Invalid, 41 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 41 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-14 02:43:02,420 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 102 Invalid, 41 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 41 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-14 02:43:02,421 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 56 states. [2024-11-14 02:43:02,437 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 56 to 55. [2024-11-14 02:43:02,437 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 55 states, 35 states have (on average 1.1714285714285715) internal successors, (41), 36 states have internal predecessors, (41), 12 states have call successors, (12), 7 states have call predecessors, (12), 7 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2024-11-14 02:43:02,438 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 55 states to 55 states and 64 transitions. [2024-11-14 02:43:02,438 INFO L78 Accepts]: Start accepts. Automaton has 55 states and 64 transitions. Word has length 25 [2024-11-14 02:43:02,438 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 02:43:02,439 INFO L471 AbstractCegarLoop]: Abstraction has 55 states and 64 transitions. [2024-11-14 02:43:02,439 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.0) internal successors, (12), 6 states have internal predecessors, (12), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2024-11-14 02:43:02,439 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 64 transitions. [2024-11-14 02:43:02,441 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2024-11-14 02:43:02,442 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 02:43:02,442 INFO L215 NwaCegarLoop]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 02:43:02,442 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5 [2024-11-14 02:43:02,442 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 02:43:02,443 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 02:43:02,443 INFO L85 PathProgramCache]: Analyzing trace with hash -506190567, now seen corresponding path program 1 times [2024-11-14 02:43:02,443 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 02:43:02,443 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1267721078] [2024-11-14 02:43:02,443 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:43:02,443 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 02:43:02,463 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 02:43:02,465 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1177693310] [2024-11-14 02:43:02,465 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:43:02,466 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 02:43:02,466 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 02:43:02,468 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 02:43:02,470 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-11-14 02:43:02,525 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 02:43:02,526 INFO L255 TraceCheckSpWp]: Trace formula consists of 79 conjuncts, 15 conjuncts are in the unsatisfiable core [2024-11-14 02:43:02,528 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 02:43:02,670 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 5 proven. 7 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2024-11-14 02:43:02,670 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 02:43:02,904 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 5 proven. 7 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2024-11-14 02:43:02,904 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 02:43:02,904 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1267721078] [2024-11-14 02:43:02,904 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-14 02:43:02,904 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1177693310] [2024-11-14 02:43:02,904 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1177693310] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 02:43:02,904 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [510158439] [2024-11-14 02:43:02,922 INFO L159 IcfgInterpreter]: Started Sifa with 16 locations of interest [2024-11-14 02:43:02,922 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 02:43:02,925 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 02:43:02,929 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 02:43:02,930 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 02:43:03,672 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 10 for LOIs [2024-11-14 02:43:03,689 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 02:43:04,584 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSifa [510158439] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 02:43:04,584 INFO L185 FreeRefinementEngine]: Found 1 perfect and 2 imperfect interpolant sequences. [2024-11-14 02:43:04,585 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [7, 7] total 18 [2024-11-14 02:43:04,585 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1428144858] [2024-11-14 02:43:04,586 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 02:43:04,586 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-11-14 02:43:04,586 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 02:43:04,587 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-11-14 02:43:04,588 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=64, Invalid=242, Unknown=0, NotChecked=0, Total=306 [2024-11-14 02:43:04,588 INFO L87 Difference]: Start difference. First operand 55 states and 64 transitions. Second operand has 10 states, 9 states have (on average 1.2222222222222223) internal successors, (11), 9 states have internal predecessors, (11), 2 states have call successors, (4), 1 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2024-11-14 02:43:04,916 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 02:43:04,916 INFO L93 Difference]: Finished difference Result 61 states and 69 transitions. [2024-11-14 02:43:04,917 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-14 02:43:04,917 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 9 states have (on average 1.2222222222222223) internal successors, (11), 9 states have internal predecessors, (11), 2 states have call successors, (4), 1 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) Word has length 25 [2024-11-14 02:43:04,917 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 02:43:04,918 INFO L225 Difference]: With dead ends: 61 [2024-11-14 02:43:04,918 INFO L226 Difference]: Without dead ends: 59 [2024-11-14 02:43:04,919 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 73 GetRequests, 56 SyntacticMatches, 1 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 66 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=64, Invalid=242, Unknown=0, NotChecked=0, Total=306 [2024-11-14 02:43:04,919 INFO L432 NwaCegarLoop]: 13 mSDtfsCounter, 0 mSDsluCounter, 54 mSDsCounter, 0 mSdLazyCounter, 145 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 67 SdHoareTripleChecker+Invalid, 146 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 145 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-11-14 02:43:04,920 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [2 Valid, 67 Invalid, 146 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 145 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-11-14 02:43:04,921 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 59 states. [2024-11-14 02:43:04,938 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 59 to 59. [2024-11-14 02:43:04,939 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 59 states, 38 states have (on average 1.1578947368421053) internal successors, (44), 39 states have internal predecessors, (44), 12 states have call successors, (12), 8 states have call predecessors, (12), 8 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2024-11-14 02:43:04,940 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 59 states to 59 states and 67 transitions. [2024-11-14 02:43:04,940 INFO L78 Accepts]: Start accepts. Automaton has 59 states and 67 transitions. Word has length 25 [2024-11-14 02:43:04,941 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 02:43:04,941 INFO L471 AbstractCegarLoop]: Abstraction has 59 states and 67 transitions. [2024-11-14 02:43:04,941 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 9 states have (on average 1.2222222222222223) internal successors, (11), 9 states have internal predecessors, (11), 2 states have call successors, (4), 1 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2024-11-14 02:43:04,941 INFO L276 IsEmpty]: Start isEmpty. Operand 59 states and 67 transitions. [2024-11-14 02:43:04,942 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2024-11-14 02:43:04,942 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 02:43:04,942 INFO L215 NwaCegarLoop]: trace histogram [4, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 02:43:04,967 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2024-11-14 02:43:05,146 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable6 [2024-11-14 02:43:05,146 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 02:43:05,147 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 02:43:05,147 INFO L85 PathProgramCache]: Analyzing trace with hash -1960004552, now seen corresponding path program 1 times [2024-11-14 02:43:05,147 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 02:43:05,147 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [464187000] [2024-11-14 02:43:05,147 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:43:05,147 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 02:43:05,168 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 02:43:05,317 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 6 proven. 2 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-11-14 02:43:05,317 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 02:43:05,317 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [464187000] [2024-11-14 02:43:05,317 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [464187000] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 02:43:05,318 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1068416445] [2024-11-14 02:43:05,318 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:43:05,318 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 02:43:05,318 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 02:43:05,320 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 02:43:05,323 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-11-14 02:43:05,389 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 02:43:05,390 INFO L255 TraceCheckSpWp]: Trace formula consists of 88 conjuncts, 5 conjuncts are in the unsatisfiable core [2024-11-14 02:43:05,394 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 02:43:05,468 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 6 proven. 2 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-11-14 02:43:05,468 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 02:43:05,542 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 6 proven. 2 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-11-14 02:43:05,543 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1068416445] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 02:43:05,543 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [523639949] [2024-11-14 02:43:05,549 INFO L159 IcfgInterpreter]: Started Sifa with 16 locations of interest [2024-11-14 02:43:05,550 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 02:43:05,550 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 02:43:05,550 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 02:43:05,550 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 02:43:07,253 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2024-11-14 02:43:07,259 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 02:43:12,271 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1352#(= |__VERIFIER_assert_#in~cond| 0)' at error location [2024-11-14 02:43:12,272 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 02:43:12,272 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-14 02:43:12,272 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 4, 5] total 10 [2024-11-14 02:43:12,272 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2104759458] [2024-11-14 02:43:12,273 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-14 02:43:12,273 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-11-14 02:43:12,273 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 02:43:12,274 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-11-14 02:43:12,274 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=76, Invalid=386, Unknown=0, NotChecked=0, Total=462 [2024-11-14 02:43:12,275 INFO L87 Difference]: Start difference. First operand 59 states and 67 transitions. Second operand has 10 states, 10 states have (on average 2.6) internal successors, (26), 10 states have internal predecessors, (26), 3 states have call successors, (10), 3 states have call predecessors, (10), 2 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) [2024-11-14 02:43:12,510 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 02:43:12,511 INFO L93 Difference]: Finished difference Result 124 states and 147 transitions. [2024-11-14 02:43:12,511 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-14 02:43:12,512 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 2.6) internal successors, (26), 10 states have internal predecessors, (26), 3 states have call successors, (10), 3 states have call predecessors, (10), 2 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) Word has length 27 [2024-11-14 02:43:12,512 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 02:43:12,513 INFO L225 Difference]: With dead ends: 124 [2024-11-14 02:43:12,513 INFO L226 Difference]: Without dead ends: 111 [2024-11-14 02:43:12,514 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 87 GetRequests, 65 SyntacticMatches, 0 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 129 ImplicationChecksByTransitivity, 5.1s TimeCoverageRelationStatistics Valid=89, Invalid=463, Unknown=0, NotChecked=0, Total=552 [2024-11-14 02:43:12,515 INFO L432 NwaCegarLoop]: 24 mSDtfsCounter, 52 mSDsluCounter, 88 mSDsCounter, 0 mSdLazyCounter, 85 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 52 SdHoareTripleChecker+Valid, 112 SdHoareTripleChecker+Invalid, 99 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 85 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-14 02:43:12,515 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [52 Valid, 112 Invalid, 99 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 85 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-14 02:43:12,516 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 111 states. [2024-11-14 02:43:12,550 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 111 to 106. [2024-11-14 02:43:12,550 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 106 states, 67 states have (on average 1.1791044776119404) internal successors, (79), 70 states have internal predecessors, (79), 24 states have call successors, (24), 14 states have call predecessors, (24), 14 states have return successors, (21), 21 states have call predecessors, (21), 21 states have call successors, (21) [2024-11-14 02:43:12,555 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 106 states to 106 states and 124 transitions. [2024-11-14 02:43:12,556 INFO L78 Accepts]: Start accepts. Automaton has 106 states and 124 transitions. Word has length 27 [2024-11-14 02:43:12,556 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 02:43:12,556 INFO L471 AbstractCegarLoop]: Abstraction has 106 states and 124 transitions. [2024-11-14 02:43:12,556 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 2.6) internal successors, (26), 10 states have internal predecessors, (26), 3 states have call successors, (10), 3 states have call predecessors, (10), 2 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) [2024-11-14 02:43:12,556 INFO L276 IsEmpty]: Start isEmpty. Operand 106 states and 124 transitions. [2024-11-14 02:43:12,557 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2024-11-14 02:43:12,557 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 02:43:12,557 INFO L215 NwaCegarLoop]: trace histogram [6, 5, 5, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1] [2024-11-14 02:43:12,582 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2024-11-14 02:43:12,758 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable7 [2024-11-14 02:43:12,758 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 02:43:12,758 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 02:43:12,759 INFO L85 PathProgramCache]: Analyzing trace with hash 448166817, now seen corresponding path program 1 times [2024-11-14 02:43:12,759 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 02:43:12,759 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [202889188] [2024-11-14 02:43:12,759 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:43:12,759 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 02:43:12,776 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 02:43:12,777 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [36385105] [2024-11-14 02:43:12,777 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:43:12,777 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 02:43:12,777 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 02:43:12,780 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 02:43:12,781 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-11-14 02:43:12,844 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 02:43:12,848 INFO L255 TraceCheckSpWp]: Trace formula consists of 101 conjuncts, 23 conjuncts are in the unsatisfiable core [2024-11-14 02:43:12,850 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 02:43:13,037 INFO L134 CoverageAnalysis]: Checked inductivity of 55 backedges. 9 proven. 18 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2024-11-14 02:43:13,037 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 02:43:13,225 INFO L134 CoverageAnalysis]: Checked inductivity of 55 backedges. 12 proven. 13 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2024-11-14 02:43:13,225 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 02:43:13,225 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [202889188] [2024-11-14 02:43:13,225 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-14 02:43:13,225 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [36385105] [2024-11-14 02:43:13,226 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [36385105] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 02:43:13,226 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1018089731] [2024-11-14 02:43:13,228 INFO L159 IcfgInterpreter]: Started Sifa with 13 locations of interest [2024-11-14 02:43:13,228 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 02:43:13,228 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 02:43:13,229 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 02:43:13,229 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 02:43:14,493 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2024-11-14 02:43:14,499 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 02:43:18,094 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1943#(= |__VERIFIER_assert_#in~cond| 0)' at error location [2024-11-14 02:43:18,094 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 02:43:18,094 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-14 02:43:18,094 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 7] total 13 [2024-11-14 02:43:18,094 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1745207607] [2024-11-14 02:43:18,095 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-14 02:43:18,095 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2024-11-14 02:43:18,095 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 02:43:18,095 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2024-11-14 02:43:18,096 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=65, Invalid=315, Unknown=0, NotChecked=0, Total=380 [2024-11-14 02:43:18,096 INFO L87 Difference]: Start difference. First operand 106 states and 124 transitions. Second operand has 13 states, 13 states have (on average 1.9230769230769231) internal successors, (25), 11 states have internal predecessors, (25), 5 states have call successors, (11), 3 states have call predecessors, (11), 2 states have return successors, (9), 3 states have call predecessors, (9), 5 states have call successors, (9) [2024-11-14 02:43:18,359 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 02:43:18,359 INFO L93 Difference]: Finished difference Result 150 states and 182 transitions. [2024-11-14 02:43:18,360 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-14 02:43:18,360 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 1.9230769230769231) internal successors, (25), 11 states have internal predecessors, (25), 5 states have call successors, (11), 3 states have call predecessors, (11), 2 states have return successors, (9), 3 states have call predecessors, (9), 5 states have call successors, (9) Word has length 35 [2024-11-14 02:43:18,360 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 02:43:18,363 INFO L225 Difference]: With dead ends: 150 [2024-11-14 02:43:18,363 INFO L226 Difference]: Without dead ends: 130 [2024-11-14 02:43:18,366 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 104 GetRequests, 85 SyntacticMatches, 0 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 73 ImplicationChecksByTransitivity, 3.7s TimeCoverageRelationStatistics Valid=73, Invalid=347, Unknown=0, NotChecked=0, Total=420 [2024-11-14 02:43:18,367 INFO L432 NwaCegarLoop]: 29 mSDtfsCounter, 32 mSDsluCounter, 109 mSDsCounter, 0 mSdLazyCounter, 155 mSolverCounterSat, 24 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 47 SdHoareTripleChecker+Valid, 138 SdHoareTripleChecker+Invalid, 179 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 24 IncrementalHoareTripleChecker+Valid, 155 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-14 02:43:18,367 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [47 Valid, 138 Invalid, 179 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [24 Valid, 155 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-14 02:43:18,368 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 130 states. [2024-11-14 02:43:18,402 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 130 to 128. [2024-11-14 02:43:18,402 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 128 states, 81 states have (on average 1.1604938271604939) internal successors, (94), 86 states have internal predecessors, (94), 29 states have call successors, (29), 17 states have call predecessors, (29), 17 states have return successors, (25), 24 states have call predecessors, (25), 25 states have call successors, (25) [2024-11-14 02:43:18,406 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 128 states to 128 states and 148 transitions. [2024-11-14 02:43:18,406 INFO L78 Accepts]: Start accepts. Automaton has 128 states and 148 transitions. Word has length 35 [2024-11-14 02:43:18,409 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 02:43:18,409 INFO L471 AbstractCegarLoop]: Abstraction has 128 states and 148 transitions. [2024-11-14 02:43:18,409 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 1.9230769230769231) internal successors, (25), 11 states have internal predecessors, (25), 5 states have call successors, (11), 3 states have call predecessors, (11), 2 states have return successors, (9), 3 states have call predecessors, (9), 5 states have call successors, (9) [2024-11-14 02:43:18,410 INFO L276 IsEmpty]: Start isEmpty. Operand 128 states and 148 transitions. [2024-11-14 02:43:18,410 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2024-11-14 02:43:18,410 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 02:43:18,410 INFO L215 NwaCegarLoop]: trace histogram [6, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 02:43:18,431 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2024-11-14 02:43:18,615 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 02:43:18,616 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 02:43:18,616 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 02:43:18,616 INFO L85 PathProgramCache]: Analyzing trace with hash -938277045, now seen corresponding path program 1 times [2024-11-14 02:43:18,616 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 02:43:18,617 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [353982414] [2024-11-14 02:43:18,617 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:43:18,617 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 02:43:18,631 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 02:43:18,632 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2113897028] [2024-11-14 02:43:18,632 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:43:18,632 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 02:43:18,632 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 02:43:18,634 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 02:43:18,639 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2024-11-14 02:43:18,685 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 02:43:18,685 INFO L255 TraceCheckSpWp]: Trace formula consists of 99 conjuncts, 15 conjuncts are in the unsatisfiable core [2024-11-14 02:43:18,687 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 02:43:18,802 INFO L134 CoverageAnalysis]: Checked inductivity of 50 backedges. 9 proven. 13 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2024-11-14 02:43:18,802 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 02:43:18,968 INFO L134 CoverageAnalysis]: Checked inductivity of 50 backedges. 9 proven. 13 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2024-11-14 02:43:18,968 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 02:43:18,969 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [353982414] [2024-11-14 02:43:18,969 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-14 02:43:18,969 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2113897028] [2024-11-14 02:43:18,969 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2113897028] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 02:43:18,969 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1488434382] [2024-11-14 02:43:18,971 INFO L159 IcfgInterpreter]: Started Sifa with 19 locations of interest [2024-11-14 02:43:18,971 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 02:43:18,971 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 02:43:18,972 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 02:43:18,972 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 02:43:19,245 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 48 for LOIs [2024-11-14 02:43:19,277 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 02:43:20,369 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSifa [1488434382] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 02:43:20,369 INFO L185 FreeRefinementEngine]: Found 1 perfect and 2 imperfect interpolant sequences. [2024-11-14 02:43:20,369 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [10] imperfect sequences [7, 7] total 19 [2024-11-14 02:43:20,369 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1782424259] [2024-11-14 02:43:20,370 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 02:43:20,370 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2024-11-14 02:43:20,370 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 02:43:20,371 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2024-11-14 02:43:20,371 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=70, Invalid=272, Unknown=0, NotChecked=0, Total=342 [2024-11-14 02:43:20,372 INFO L87 Difference]: Start difference. First operand 128 states and 148 transitions. Second operand has 11 states, 10 states have (on average 1.2) internal successors, (12), 10 states have internal predecessors, (12), 3 states have call successors, (6), 1 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2024-11-14 02:43:20,619 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 02:43:20,619 INFO L93 Difference]: Finished difference Result 130 states and 149 transitions. [2024-11-14 02:43:20,619 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2024-11-14 02:43:20,620 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 10 states have (on average 1.2) internal successors, (12), 10 states have internal predecessors, (12), 3 states have call successors, (6), 1 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 36 [2024-11-14 02:43:20,620 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 02:43:20,622 INFO L225 Difference]: With dead ends: 130 [2024-11-14 02:43:20,622 INFO L226 Difference]: Without dead ends: 109 [2024-11-14 02:43:20,623 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 106 GetRequests, 78 SyntacticMatches, 11 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 187 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=70, Invalid=272, Unknown=0, NotChecked=0, Total=342 [2024-11-14 02:43:20,623 INFO L432 NwaCegarLoop]: 12 mSDtfsCounter, 0 mSDsluCounter, 38 mSDsCounter, 0 mSdLazyCounter, 164 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1 SdHoareTripleChecker+Valid, 50 SdHoareTripleChecker+Invalid, 165 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 164 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-14 02:43:20,624 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [1 Valid, 50 Invalid, 165 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 164 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-14 02:43:20,624 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 109 states. [2024-11-14 02:43:20,639 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 109 to 109. [2024-11-14 02:43:20,640 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 109 states, 69 states have (on average 1.1594202898550725) internal successors, (80), 73 states have internal predecessors, (80), 25 states have call successors, (25), 14 states have call predecessors, (25), 14 states have return successors, (22), 21 states have call predecessors, (22), 22 states have call successors, (22) [2024-11-14 02:43:20,641 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 109 states to 109 states and 127 transitions. [2024-11-14 02:43:20,641 INFO L78 Accepts]: Start accepts. Automaton has 109 states and 127 transitions. Word has length 36 [2024-11-14 02:43:20,642 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 02:43:20,642 INFO L471 AbstractCegarLoop]: Abstraction has 109 states and 127 transitions. [2024-11-14 02:43:20,642 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 10 states have (on average 1.2) internal successors, (12), 10 states have internal predecessors, (12), 3 states have call successors, (6), 1 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2024-11-14 02:43:20,642 INFO L276 IsEmpty]: Start isEmpty. Operand 109 states and 127 transitions. [2024-11-14 02:43:20,643 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2024-11-14 02:43:20,643 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 02:43:20,643 INFO L215 NwaCegarLoop]: trace histogram [7, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 02:43:20,667 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2024-11-14 02:43:20,843 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 02:43:20,844 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 02:43:20,844 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 02:43:20,844 INFO L85 PathProgramCache]: Analyzing trace with hash -721972931, now seen corresponding path program 1 times [2024-11-14 02:43:20,844 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 02:43:20,844 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1885193579] [2024-11-14 02:43:20,845 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:43:20,845 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 02:43:20,858 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 02:43:20,992 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 12 proven. 6 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2024-11-14 02:43:20,993 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 02:43:20,993 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1885193579] [2024-11-14 02:43:20,993 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1885193579] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 02:43:20,993 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [638971843] [2024-11-14 02:43:20,993 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:43:20,993 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 02:43:20,993 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 02:43:20,995 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 02:43:20,997 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2024-11-14 02:43:21,062 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 02:43:21,063 INFO L255 TraceCheckSpWp]: Trace formula consists of 116 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-14 02:43:21,065 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 02:43:21,158 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 12 proven. 42 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-14 02:43:21,159 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 02:43:21,253 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 12 proven. 6 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2024-11-14 02:43:21,253 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [638971843] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 02:43:21,254 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [666663350] [2024-11-14 02:43:21,256 INFO L159 IcfgInterpreter]: Started Sifa with 16 locations of interest [2024-11-14 02:43:21,256 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 02:43:21,256 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 02:43:21,256 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 02:43:21,257 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 02:43:22,195 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2024-11-14 02:43:22,199 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 02:43:26,208 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '3257#(= |__VERIFIER_assert_#in~cond| 0)' at error location [2024-11-14 02:43:26,208 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 02:43:26,208 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-14 02:43:26,208 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 5, 6] total 12 [2024-11-14 02:43:26,209 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [497429176] [2024-11-14 02:43:26,209 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-14 02:43:26,209 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2024-11-14 02:43:26,209 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 02:43:26,210 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2024-11-14 02:43:26,210 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=86, Invalid=465, Unknown=1, NotChecked=0, Total=552 [2024-11-14 02:43:26,210 INFO L87 Difference]: Start difference. First operand 109 states and 127 transitions. Second operand has 12 states, 12 states have (on average 2.75) internal successors, (33), 12 states have internal predecessors, (33), 5 states have call successors, (19), 4 states have call predecessors, (19), 3 states have return successors, (18), 4 states have call predecessors, (18), 4 states have call successors, (18) [2024-11-14 02:43:26,499 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 02:43:26,500 INFO L93 Difference]: Finished difference Result 192 states and 225 transitions. [2024-11-14 02:43:26,500 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2024-11-14 02:43:26,500 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 2.75) internal successors, (33), 12 states have internal predecessors, (33), 5 states have call successors, (19), 4 states have call predecessors, (19), 3 states have return successors, (18), 4 states have call predecessors, (18), 4 states have call successors, (18) Word has length 43 [2024-11-14 02:43:26,501 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 02:43:26,502 INFO L225 Difference]: With dead ends: 192 [2024-11-14 02:43:26,502 INFO L226 Difference]: Without dead ends: 177 [2024-11-14 02:43:26,503 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 137 GetRequests, 112 SyntacticMatches, 0 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 167 ImplicationChecksByTransitivity, 4.1s TimeCoverageRelationStatistics Valid=105, Invalid=596, Unknown=1, NotChecked=0, Total=702 [2024-11-14 02:43:26,504 INFO L432 NwaCegarLoop]: 23 mSDtfsCounter, 69 mSDsluCounter, 130 mSDsCounter, 0 mSdLazyCounter, 141 mSolverCounterSat, 12 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 69 SdHoareTripleChecker+Valid, 153 SdHoareTripleChecker+Invalid, 153 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 141 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-14 02:43:26,504 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [69 Valid, 153 Invalid, 153 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 141 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-14 02:43:26,507 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 177 states. [2024-11-14 02:43:26,527 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 177 to 170. [2024-11-14 02:43:26,528 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 170 states, 109 states have (on average 1.146788990825688) internal successors, (125), 114 states have internal predecessors, (125), 38 states have call successors, (38), 22 states have call predecessors, (38), 22 states have return successors, (35), 33 states have call predecessors, (35), 35 states have call successors, (35) [2024-11-14 02:43:26,529 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 170 states to 170 states and 198 transitions. [2024-11-14 02:43:26,530 INFO L78 Accepts]: Start accepts. Automaton has 170 states and 198 transitions. Word has length 43 [2024-11-14 02:43:26,530 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 02:43:26,530 INFO L471 AbstractCegarLoop]: Abstraction has 170 states and 198 transitions. [2024-11-14 02:43:26,530 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 2.75) internal successors, (33), 12 states have internal predecessors, (33), 5 states have call successors, (19), 4 states have call predecessors, (19), 3 states have return successors, (18), 4 states have call predecessors, (18), 4 states have call successors, (18) [2024-11-14 02:43:26,531 INFO L276 IsEmpty]: Start isEmpty. Operand 170 states and 198 transitions. [2024-11-14 02:43:26,531 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2024-11-14 02:43:26,531 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 02:43:26,532 INFO L215 NwaCegarLoop]: trace histogram [7, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 02:43:26,553 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2024-11-14 02:43:26,732 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,7 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 02:43:26,732 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 02:43:26,732 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 02:43:26,733 INFO L85 PathProgramCache]: Analyzing trace with hash -720245053, now seen corresponding path program 1 times [2024-11-14 02:43:26,733 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 02:43:26,733 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [273150605] [2024-11-14 02:43:26,733 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:43:26,733 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 02:43:26,747 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 02:43:26,747 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [95801037] [2024-11-14 02:43:26,748 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:43:26,748 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 02:43:26,748 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 02:43:26,750 INFO L229 MonitoredProcess]: Starting monitored process 8 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 02:43:26,753 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2024-11-14 02:43:26,812 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 02:43:26,814 INFO L255 TraceCheckSpWp]: Trace formula consists of 116 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-14 02:43:26,816 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 02:43:26,928 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 12 proven. 0 refuted. 0 times theorem prover too weak. 66 trivial. 0 not checked. [2024-11-14 02:43:26,928 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-14 02:43:26,929 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 02:43:26,929 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [273150605] [2024-11-14 02:43:26,929 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-14 02:43:26,929 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [95801037] [2024-11-14 02:43:26,929 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [95801037] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 02:43:26,929 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 02:43:26,929 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-14 02:43:26,929 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1163088466] [2024-11-14 02:43:26,929 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 02:43:26,929 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-14 02:43:26,929 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 02:43:26,930 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-14 02:43:26,930 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-14 02:43:26,930 INFO L87 Difference]: Start difference. First operand 170 states and 198 transitions. Second operand has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 1 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2024-11-14 02:43:27,018 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 02:43:27,019 INFO L93 Difference]: Finished difference Result 192 states and 224 transitions. [2024-11-14 02:43:27,019 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-14 02:43:27,019 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 1 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) Word has length 43 [2024-11-14 02:43:27,020 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 02:43:27,021 INFO L225 Difference]: With dead ends: 192 [2024-11-14 02:43:27,021 INFO L226 Difference]: Without dead ends: 190 [2024-11-14 02:43:27,022 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 43 GetRequests, 39 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-14 02:43:27,026 INFO L432 NwaCegarLoop]: 24 mSDtfsCounter, 6 mSDsluCounter, 58 mSDsCounter, 0 mSdLazyCounter, 39 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 9 SdHoareTripleChecker+Valid, 82 SdHoareTripleChecker+Invalid, 42 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 39 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-14 02:43:27,026 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [9 Valid, 82 Invalid, 42 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 39 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-14 02:43:27,027 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 190 states. [2024-11-14 02:43:27,052 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 190 to 187. [2024-11-14 02:43:27,053 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 187 states, 120 states have (on average 1.1416666666666666) internal successors, (137), 126 states have internal predecessors, (137), 41 states have call successors, (41), 25 states have call predecessors, (41), 25 states have return successors, (38), 35 states have call predecessors, (38), 38 states have call successors, (38) [2024-11-14 02:43:27,055 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 187 states to 187 states and 216 transitions. [2024-11-14 02:43:27,055 INFO L78 Accepts]: Start accepts. Automaton has 187 states and 216 transitions. Word has length 43 [2024-11-14 02:43:27,055 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 02:43:27,056 INFO L471 AbstractCegarLoop]: Abstraction has 187 states and 216 transitions. [2024-11-14 02:43:27,056 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 1 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2024-11-14 02:43:27,056 INFO L276 IsEmpty]: Start isEmpty. Operand 187 states and 216 transitions. [2024-11-14 02:43:27,057 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 57 [2024-11-14 02:43:27,057 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 02:43:27,058 INFO L215 NwaCegarLoop]: trace histogram [9, 8, 8, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 02:43:27,073 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2024-11-14 02:43:27,261 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11,8 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 02:43:27,262 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 02:43:27,262 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 02:43:27,262 INFO L85 PathProgramCache]: Analyzing trace with hash -1991197863, now seen corresponding path program 1 times [2024-11-14 02:43:27,262 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 02:43:27,262 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [782078756] [2024-11-14 02:43:27,262 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:43:27,262 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 02:43:27,288 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 02:43:27,292 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2040381232] [2024-11-14 02:43:27,293 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:43:27,293 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 02:43:27,293 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 02:43:27,299 INFO L229 MonitoredProcess]: Starting monitored process 9 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 02:43:27,310 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2024-11-14 02:43:27,368 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 02:43:27,369 INFO L255 TraceCheckSpWp]: Trace formula consists of 145 conjuncts, 30 conjuncts are in the unsatisfiable core [2024-11-14 02:43:27,374 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 02:43:27,947 INFO L134 CoverageAnalysis]: Checked inductivity of 137 backedges. 15 proven. 31 refuted. 0 times theorem prover too weak. 91 trivial. 0 not checked. [2024-11-14 02:43:27,947 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 02:43:31,191 INFO L134 CoverageAnalysis]: Checked inductivity of 137 backedges. 15 proven. 31 refuted. 0 times theorem prover too weak. 91 trivial. 0 not checked. [2024-11-14 02:43:31,191 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 02:43:31,191 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [782078756] [2024-11-14 02:43:31,191 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-14 02:43:31,191 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2040381232] [2024-11-14 02:43:31,191 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2040381232] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 02:43:31,192 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1735864708] [2024-11-14 02:43:31,194 INFO L159 IcfgInterpreter]: Started Sifa with 18 locations of interest [2024-11-14 02:43:31,195 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 02:43:31,196 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 02:43:31,196 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 02:43:31,196 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 02:43:32,916 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2024-11-14 02:43:32,920 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 02:43:42,151 WARN L286 SmtUtils]: Spent 7.81s on a formula simplification. DAG size of input: 83 DAG size of output: 79 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-14 02:43:44,553 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '4913#(= |__VERIFIER_assert_#in~cond| 0)' at error location [2024-11-14 02:43:44,554 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 02:43:44,554 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-14 02:43:44,554 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 15 [2024-11-14 02:43:44,554 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1762567888] [2024-11-14 02:43:44,554 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-14 02:43:44,554 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2024-11-14 02:43:44,555 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 02:43:44,555 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2024-11-14 02:43:44,556 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=77, Invalid=572, Unknown=1, NotChecked=0, Total=650 [2024-11-14 02:43:44,556 INFO L87 Difference]: Start difference. First operand 187 states and 216 transitions. Second operand has 15 states, 15 states have (on average 2.466666666666667) internal successors, (37), 13 states have internal predecessors, (37), 7 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (16), 4 states have call predecessors, (16), 5 states have call successors, (16) [2024-11-14 02:43:45,858 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 02:43:45,858 INFO L93 Difference]: Finished difference Result 230 states and 260 transitions. [2024-11-14 02:43:45,858 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2024-11-14 02:43:45,859 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 15 states have (on average 2.466666666666667) internal successors, (37), 13 states have internal predecessors, (37), 7 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (16), 4 states have call predecessors, (16), 5 states have call successors, (16) Word has length 56 [2024-11-14 02:43:45,859 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 02:43:45,861 INFO L225 Difference]: With dead ends: 230 [2024-11-14 02:43:45,861 INFO L226 Difference]: Without dead ends: 228 [2024-11-14 02:43:45,861 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 170 GetRequests, 140 SyntacticMatches, 2 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 150 ImplicationChecksByTransitivity, 12.7s TimeCoverageRelationStatistics Valid=108, Invalid=761, Unknown=1, NotChecked=0, Total=870 [2024-11-14 02:43:45,862 INFO L432 NwaCegarLoop]: 29 mSDtfsCounter, 35 mSDsluCounter, 184 mSDsCounter, 0 mSdLazyCounter, 195 mSolverCounterSat, 63 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 38 SdHoareTripleChecker+Valid, 213 SdHoareTripleChecker+Invalid, 258 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 63 IncrementalHoareTripleChecker+Valid, 195 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2024-11-14 02:43:45,862 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [38 Valid, 213 Invalid, 258 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [63 Valid, 195 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2024-11-14 02:43:45,863 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 228 states. [2024-11-14 02:43:45,909 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 228 to 220. [2024-11-14 02:43:45,910 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 220 states, 145 states have (on average 1.1241379310344828) internal successors, (163), 152 states have internal predecessors, (163), 42 states have call successors, (42), 32 states have call predecessors, (42), 32 states have return successors, (39), 35 states have call predecessors, (39), 39 states have call successors, (39) [2024-11-14 02:43:45,911 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 220 states to 220 states and 244 transitions. [2024-11-14 02:43:45,911 INFO L78 Accepts]: Start accepts. Automaton has 220 states and 244 transitions. Word has length 56 [2024-11-14 02:43:45,912 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 02:43:45,912 INFO L471 AbstractCegarLoop]: Abstraction has 220 states and 244 transitions. [2024-11-14 02:43:45,912 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 2.466666666666667) internal successors, (37), 13 states have internal predecessors, (37), 7 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (16), 4 states have call predecessors, (16), 5 states have call successors, (16) [2024-11-14 02:43:45,912 INFO L276 IsEmpty]: Start isEmpty. Operand 220 states and 244 transitions. [2024-11-14 02:43:45,913 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 68 [2024-11-14 02:43:45,913 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 02:43:45,913 INFO L215 NwaCegarLoop]: trace histogram [11, 10, 10, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 02:43:45,934 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2024-11-14 02:43:46,113 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable12,9 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 02:43:46,114 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 02:43:46,114 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 02:43:46,114 INFO L85 PathProgramCache]: Analyzing trace with hash -563738357, now seen corresponding path program 1 times [2024-11-14 02:43:46,114 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 02:43:46,114 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [774518131] [2024-11-14 02:43:46,115 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:43:46,115 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 02:43:46,149 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 02:43:46,150 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1783358788] [2024-11-14 02:43:46,151 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:43:46,151 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 02:43:46,151 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 02:43:46,156 INFO L229 MonitoredProcess]: Starting monitored process 10 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 02:43:46,158 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2024-11-14 02:43:46,228 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 02:43:46,230 INFO L255 TraceCheckSpWp]: Trace formula consists of 165 conjuncts, 26 conjuncts are in the unsatisfiable core [2024-11-14 02:43:46,232 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 02:43:46,778 INFO L134 CoverageAnalysis]: Checked inductivity of 211 backedges. 19 proven. 39 refuted. 0 times theorem prover too weak. 153 trivial. 0 not checked. [2024-11-14 02:43:46,778 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 02:43:47,505 INFO L134 CoverageAnalysis]: Checked inductivity of 211 backedges. 22 proven. 36 refuted. 0 times theorem prover too weak. 153 trivial. 0 not checked. [2024-11-14 02:43:47,505 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 02:43:47,506 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [774518131] [2024-11-14 02:43:47,506 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-14 02:43:47,507 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1783358788] [2024-11-14 02:43:47,507 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1783358788] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 02:43:47,507 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1058700000] [2024-11-14 02:43:47,509 INFO L159 IcfgInterpreter]: Started Sifa with 19 locations of interest [2024-11-14 02:43:47,512 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 02:43:47,512 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 02:43:47,513 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 02:43:47,513 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 02:43:49,334 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2024-11-14 02:43:49,338 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 02:44:06,183 WARN L286 SmtUtils]: Spent 14.97s on a formula simplification. DAG size of input: 83 DAG size of output: 79 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-14 02:44:08,601 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '6049#(= |__VERIFIER_assert_#in~cond| 0)' at error location [2024-11-14 02:44:08,601 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 02:44:08,601 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-14 02:44:08,602 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 17 [2024-11-14 02:44:08,602 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1146197338] [2024-11-14 02:44:08,602 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-14 02:44:08,602 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2024-11-14 02:44:08,602 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 02:44:08,603 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2024-11-14 02:44:08,603 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=105, Invalid=706, Unknown=1, NotChecked=0, Total=812 [2024-11-14 02:44:08,604 INFO L87 Difference]: Start difference. First operand 220 states and 244 transitions. Second operand has 17 states, 15 states have (on average 2.6) internal successors, (39), 15 states have internal predecessors, (39), 9 states have call successors, (22), 3 states have call predecessors, (22), 2 states have return successors, (20), 6 states have call predecessors, (20), 7 states have call successors, (20) [2024-11-14 02:44:09,176 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 02:44:09,177 INFO L93 Difference]: Finished difference Result 244 states and 272 transitions. [2024-11-14 02:44:09,177 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2024-11-14 02:44:09,178 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 15 states have (on average 2.6) internal successors, (39), 15 states have internal predecessors, (39), 9 states have call successors, (22), 3 states have call predecessors, (22), 2 states have return successors, (20), 6 states have call predecessors, (20), 7 states have call successors, (20) Word has length 67 [2024-11-14 02:44:09,178 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 02:44:09,180 INFO L225 Difference]: With dead ends: 244 [2024-11-14 02:44:09,180 INFO L226 Difference]: Without dead ends: 240 [2024-11-14 02:44:09,181 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 202 GetRequests, 170 SyntacticMatches, 2 SemanticMatches, 30 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 197 ImplicationChecksByTransitivity, 19.7s TimeCoverageRelationStatistics Valid=127, Invalid=864, Unknown=1, NotChecked=0, Total=992 [2024-11-14 02:44:09,181 INFO L432 NwaCegarLoop]: 30 mSDtfsCounter, 11 mSDsluCounter, 200 mSDsCounter, 0 mSdLazyCounter, 221 mSolverCounterSat, 17 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 15 SdHoareTripleChecker+Valid, 230 SdHoareTripleChecker+Invalid, 238 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 17 IncrementalHoareTripleChecker+Valid, 221 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2024-11-14 02:44:09,182 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [15 Valid, 230 Invalid, 238 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [17 Valid, 221 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2024-11-14 02:44:09,183 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 240 states. [2024-11-14 02:44:09,231 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 240 to 218. [2024-11-14 02:44:09,232 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 218 states, 145 states have (on average 1.1241379310344828) internal successors, (163), 148 states have internal predecessors, (163), 41 states have call successors, (41), 32 states have call predecessors, (41), 31 states have return successors, (38), 37 states have call predecessors, (38), 38 states have call successors, (38) [2024-11-14 02:44:09,233 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 218 states to 218 states and 242 transitions. [2024-11-14 02:44:09,233 INFO L78 Accepts]: Start accepts. Automaton has 218 states and 242 transitions. Word has length 67 [2024-11-14 02:44:09,234 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 02:44:09,234 INFO L471 AbstractCegarLoop]: Abstraction has 218 states and 242 transitions. [2024-11-14 02:44:09,234 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 15 states have (on average 2.6) internal successors, (39), 15 states have internal predecessors, (39), 9 states have call successors, (22), 3 states have call predecessors, (22), 2 states have return successors, (20), 6 states have call predecessors, (20), 7 states have call successors, (20) [2024-11-14 02:44:09,234 INFO L276 IsEmpty]: Start isEmpty. Operand 218 states and 242 transitions. [2024-11-14 02:44:09,235 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 73 [2024-11-14 02:44:09,235 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 02:44:09,236 INFO L215 NwaCegarLoop]: trace histogram [12, 11, 11, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 02:44:09,253 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2024-11-14 02:44:09,436 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2024-11-14 02:44:09,436 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 02:44:09,437 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 02:44:09,437 INFO L85 PathProgramCache]: Analyzing trace with hash -1251052430, now seen corresponding path program 1 times [2024-11-14 02:44:09,437 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 02:44:09,437 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [451013903] [2024-11-14 02:44:09,437 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:44:09,437 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 02:44:09,488 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 02:44:10,076 INFO L134 CoverageAnalysis]: Checked inductivity of 253 backedges. 22 proven. 11 refuted. 0 times theorem prover too weak. 220 trivial. 0 not checked. [2024-11-14 02:44:10,077 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 02:44:10,077 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [451013903] [2024-11-14 02:44:10,077 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [451013903] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 02:44:10,077 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2146785171] [2024-11-14 02:44:10,077 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:44:10,077 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 02:44:10,077 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 02:44:10,080 INFO L229 MonitoredProcess]: Starting monitored process 11 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 02:44:10,083 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2024-11-14 02:44:10,159 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 02:44:10,166 INFO L255 TraceCheckSpWp]: Trace formula consists of 174 conjuncts, 22 conjuncts are in the unsatisfiable core [2024-11-14 02:44:10,172 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 02:44:10,526 INFO L134 CoverageAnalysis]: Checked inductivity of 253 backedges. 21 proven. 42 refuted. 0 times theorem prover too weak. 190 trivial. 0 not checked. [2024-11-14 02:44:10,526 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 02:44:11,112 INFO L134 CoverageAnalysis]: Checked inductivity of 253 backedges. 21 proven. 42 refuted. 0 times theorem prover too weak. 190 trivial. 0 not checked. [2024-11-14 02:44:11,112 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2146785171] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 02:44:11,112 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [2107974049] [2024-11-14 02:44:11,115 INFO L159 IcfgInterpreter]: Started Sifa with 20 locations of interest [2024-11-14 02:44:11,115 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 02:44:11,115 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 02:44:11,116 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 02:44:11,116 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 02:44:12,837 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2024-11-14 02:44:12,840 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 02:44:20,518 WARN L286 SmtUtils]: Spent 6.38s on a formula simplification. DAG size of input: 83 DAG size of output: 79 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-14 02:44:21,042 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '7228#(= |__VERIFIER_assert_#in~cond| 0)' at error location [2024-11-14 02:44:21,042 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 02:44:21,042 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-14 02:44:21,043 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 9, 8] total 14 [2024-11-14 02:44:21,043 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [532037375] [2024-11-14 02:44:21,043 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-14 02:44:21,043 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2024-11-14 02:44:21,044 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 02:44:21,044 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2024-11-14 02:44:21,045 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=73, Invalid=577, Unknown=0, NotChecked=0, Total=650 [2024-11-14 02:44:21,045 INFO L87 Difference]: Start difference. First operand 218 states and 242 transitions. Second operand has 14 states, 14 states have (on average 3.0714285714285716) internal successors, (43), 13 states have internal predecessors, (43), 6 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (23), 4 states have call predecessors, (23), 6 states have call successors, (23) [2024-11-14 02:44:21,349 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 02:44:21,349 INFO L93 Difference]: Finished difference Result 224 states and 248 transitions. [2024-11-14 02:44:21,349 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-14 02:44:21,349 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 3.0714285714285716) internal successors, (43), 13 states have internal predecessors, (43), 6 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (23), 4 states have call predecessors, (23), 6 states have call successors, (23) Word has length 72 [2024-11-14 02:44:21,350 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 02:44:21,351 INFO L225 Difference]: With dead ends: 224 [2024-11-14 02:44:21,351 INFO L226 Difference]: Without dead ends: 196 [2024-11-14 02:44:21,352 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 222 GetRequests, 191 SyntacticMatches, 6 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 168 ImplicationChecksByTransitivity, 8.5s TimeCoverageRelationStatistics Valid=81, Invalid=621, Unknown=0, NotChecked=0, Total=702 [2024-11-14 02:44:21,353 INFO L432 NwaCegarLoop]: 25 mSDtfsCounter, 3 mSDsluCounter, 187 mSDsCounter, 0 mSdLazyCounter, 230 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 212 SdHoareTripleChecker+Invalid, 231 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 230 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-14 02:44:21,353 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 212 Invalid, 231 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 230 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-14 02:44:21,354 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 196 states. [2024-11-14 02:44:21,394 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 196 to 196. [2024-11-14 02:44:21,395 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 196 states, 130 states have (on average 1.1307692307692307) internal successors, (147), 133 states have internal predecessors, (147), 37 states have call successors, (37), 29 states have call predecessors, (37), 28 states have return successors, (34), 33 states have call predecessors, (34), 34 states have call successors, (34) [2024-11-14 02:44:21,396 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 196 states to 196 states and 218 transitions. [2024-11-14 02:44:21,397 INFO L78 Accepts]: Start accepts. Automaton has 196 states and 218 transitions. Word has length 72 [2024-11-14 02:44:21,397 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 02:44:21,397 INFO L471 AbstractCegarLoop]: Abstraction has 196 states and 218 transitions. [2024-11-14 02:44:21,398 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 3.0714285714285716) internal successors, (43), 13 states have internal predecessors, (43), 6 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (23), 4 states have call predecessors, (23), 6 states have call successors, (23) [2024-11-14 02:44:21,398 INFO L276 IsEmpty]: Start isEmpty. Operand 196 states and 218 transitions. [2024-11-14 02:44:21,399 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 78 [2024-11-14 02:44:21,399 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 02:44:21,399 INFO L215 NwaCegarLoop]: trace histogram [13, 12, 12, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 02:44:21,417 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2024-11-14 02:44:21,603 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2024-11-14 02:44:21,604 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 02:44:21,604 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 02:44:21,604 INFO L85 PathProgramCache]: Analyzing trace with hash -80055546, now seen corresponding path program 1 times [2024-11-14 02:44:21,604 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 02:44:21,604 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1427172294] [2024-11-14 02:44:21,604 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:44:21,604 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 02:44:21,617 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 02:44:21,727 INFO L134 CoverageAnalysis]: Checked inductivity of 306 backedges. 30 proven. 12 refuted. 0 times theorem prover too weak. 264 trivial. 0 not checked. [2024-11-14 02:44:21,727 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 02:44:21,727 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1427172294] [2024-11-14 02:44:21,728 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1427172294] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 02:44:21,728 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [451136663] [2024-11-14 02:44:21,728 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:44:21,728 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 02:44:21,728 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 02:44:21,730 INFO L229 MonitoredProcess]: Starting monitored process 12 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 02:44:21,733 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2024-11-14 02:44:21,809 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 02:44:21,811 INFO L255 TraceCheckSpWp]: Trace formula consists of 182 conjuncts, 4 conjuncts are in the unsatisfiable core [2024-11-14 02:44:21,813 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 02:44:21,879 INFO L134 CoverageAnalysis]: Checked inductivity of 306 backedges. 84 proven. 0 refuted. 0 times theorem prover too weak. 222 trivial. 0 not checked. [2024-11-14 02:44:21,880 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-14 02:44:21,880 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [451136663] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 02:44:21,880 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-14 02:44:21,880 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [5] total 6 [2024-11-14 02:44:21,880 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2119387442] [2024-11-14 02:44:21,881 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 02:44:21,881 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-14 02:44:21,881 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 02:44:21,882 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-14 02:44:21,882 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=17, Unknown=0, NotChecked=0, Total=30 [2024-11-14 02:44:21,882 INFO L87 Difference]: Start difference. First operand 196 states and 218 transitions. Second operand has 5 states, 5 states have (on average 4.2) internal successors, (21), 5 states have internal predecessors, (21), 4 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2024-11-14 02:44:22,009 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 02:44:22,010 INFO L93 Difference]: Finished difference Result 217 states and 240 transitions. [2024-11-14 02:44:22,010 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-14 02:44:22,010 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 4.2) internal successors, (21), 5 states have internal predecessors, (21), 4 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) Word has length 77 [2024-11-14 02:44:22,011 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 02:44:22,012 INFO L225 Difference]: With dead ends: 217 [2024-11-14 02:44:22,012 INFO L226 Difference]: Without dead ends: 187 [2024-11-14 02:44:22,013 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 81 GetRequests, 77 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=13, Invalid=17, Unknown=0, NotChecked=0, Total=30 [2024-11-14 02:44:22,014 INFO L432 NwaCegarLoop]: 43 mSDtfsCounter, 11 mSDsluCounter, 51 mSDsCounter, 0 mSdLazyCounter, 29 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 18 SdHoareTripleChecker+Valid, 94 SdHoareTripleChecker+Invalid, 36 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 29 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-14 02:44:22,014 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [18 Valid, 94 Invalid, 36 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 29 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-14 02:44:22,015 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 187 states. [2024-11-14 02:44:22,063 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 187 to 182. [2024-11-14 02:44:22,064 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 182 states, 122 states have (on average 1.098360655737705) internal successors, (134), 124 states have internal predecessors, (134), 33 states have call successors, (33), 26 states have call predecessors, (33), 26 states have return successors, (32), 31 states have call predecessors, (32), 32 states have call successors, (32) [2024-11-14 02:44:22,065 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 182 states to 182 states and 199 transitions. [2024-11-14 02:44:22,065 INFO L78 Accepts]: Start accepts. Automaton has 182 states and 199 transitions. Word has length 77 [2024-11-14 02:44:22,066 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 02:44:22,066 INFO L471 AbstractCegarLoop]: Abstraction has 182 states and 199 transitions. [2024-11-14 02:44:22,066 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 4.2) internal successors, (21), 5 states have internal predecessors, (21), 4 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2024-11-14 02:44:22,066 INFO L276 IsEmpty]: Start isEmpty. Operand 182 states and 199 transitions. [2024-11-14 02:44:22,067 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 80 [2024-11-14 02:44:22,067 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 02:44:22,067 INFO L215 NwaCegarLoop]: trace histogram [13, 12, 12, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1] [2024-11-14 02:44:22,088 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Ended with exit code 0 [2024-11-14 02:44:22,271 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable15 [2024-11-14 02:44:22,271 INFO L396 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 02:44:22,272 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 02:44:22,272 INFO L85 PathProgramCache]: Analyzing trace with hash 998412302, now seen corresponding path program 2 times [2024-11-14 02:44:22,272 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 02:44:22,272 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [951438517] [2024-11-14 02:44:22,272 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:44:22,272 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 02:44:22,316 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 02:44:22,319 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [974459579] [2024-11-14 02:44:22,319 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-14 02:44:22,319 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 02:44:22,319 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 02:44:22,322 INFO L229 MonitoredProcess]: Starting monitored process 13 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 02:44:22,323 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2024-11-14 02:44:22,403 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2024-11-14 02:44:22,403 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-14 02:44:22,405 INFO L255 TraceCheckSpWp]: Trace formula consists of 122 conjuncts, 32 conjuncts are in the unsatisfiable core [2024-11-14 02:44:22,408 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 02:44:22,891 INFO L134 CoverageAnalysis]: Checked inductivity of 310 backedges. 41 proven. 38 refuted. 0 times theorem prover too weak. 231 trivial. 0 not checked. [2024-11-14 02:44:22,891 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 02:44:24,440 INFO L134 CoverageAnalysis]: Checked inductivity of 310 backedges. 41 proven. 32 refuted. 0 times theorem prover too weak. 237 trivial. 0 not checked. [2024-11-14 02:44:24,440 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 02:44:24,440 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [951438517] [2024-11-14 02:44:24,440 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-14 02:44:24,440 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [974459579] [2024-11-14 02:44:24,440 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [974459579] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 02:44:24,440 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [389839994] [2024-11-14 02:44:24,442 INFO L159 IcfgInterpreter]: Started Sifa with 18 locations of interest [2024-11-14 02:44:24,442 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 02:44:24,443 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 02:44:24,443 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 02:44:24,443 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 02:44:25,696 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2024-11-14 02:44:25,699 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 02:44:45,035 WARN L286 SmtUtils]: Spent 14.59s on a formula simplification. DAG size of input: 83 DAG size of output: 79 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-14 02:44:47,484 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '9235#(= |__VERIFIER_assert_#in~cond| 0)' at error location [2024-11-14 02:44:47,484 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 02:44:47,484 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-14 02:44:47,484 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 9] total 17 [2024-11-14 02:44:47,484 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [48633784] [2024-11-14 02:44:47,484 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-14 02:44:47,485 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2024-11-14 02:44:47,485 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 02:44:47,485 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2024-11-14 02:44:47,486 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=90, Invalid=664, Unknown=2, NotChecked=0, Total=756 [2024-11-14 02:44:47,486 INFO L87 Difference]: Start difference. First operand 182 states and 199 transitions. Second operand has 17 states, 17 states have (on average 2.411764705882353) internal successors, (41), 16 states have internal predecessors, (41), 9 states have call successors, (23), 3 states have call predecessors, (23), 2 states have return successors, (21), 7 states have call predecessors, (21), 9 states have call successors, (21) [2024-11-14 02:44:48,409 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 02:44:48,409 INFO L93 Difference]: Finished difference Result 193 states and 212 transitions. [2024-11-14 02:44:48,410 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2024-11-14 02:44:48,410 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 17 states have (on average 2.411764705882353) internal successors, (41), 16 states have internal predecessors, (41), 9 states have call successors, (23), 3 states have call predecessors, (23), 2 states have return successors, (21), 7 states have call predecessors, (21), 9 states have call successors, (21) Word has length 79 [2024-11-14 02:44:48,410 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 02:44:48,412 INFO L225 Difference]: With dead ends: 193 [2024-11-14 02:44:48,412 INFO L226 Difference]: Without dead ends: 191 [2024-11-14 02:44:48,413 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 237 GetRequests, 206 SyntacticMatches, 3 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 184 ImplicationChecksByTransitivity, 22.6s TimeCoverageRelationStatistics Valid=108, Invalid=760, Unknown=2, NotChecked=0, Total=870 [2024-11-14 02:44:48,414 INFO L432 NwaCegarLoop]: 34 mSDtfsCounter, 21 mSDsluCounter, 164 mSDsCounter, 0 mSdLazyCounter, 204 mSolverCounterSat, 31 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 29 SdHoareTripleChecker+Valid, 198 SdHoareTripleChecker+Invalid, 235 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 31 IncrementalHoareTripleChecker+Valid, 204 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2024-11-14 02:44:48,414 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [29 Valid, 198 Invalid, 235 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [31 Valid, 204 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2024-11-14 02:44:48,415 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 191 states. [2024-11-14 02:44:48,461 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 191 to 188. [2024-11-14 02:44:48,462 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 188 states, 125 states have (on average 1.088) internal successors, (136), 128 states have internal predecessors, (136), 35 states have call successors, (35), 27 states have call predecessors, (35), 27 states have return successors, (34), 32 states have call predecessors, (34), 34 states have call successors, (34) [2024-11-14 02:44:48,463 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 188 states to 188 states and 205 transitions. [2024-11-14 02:44:48,464 INFO L78 Accepts]: Start accepts. Automaton has 188 states and 205 transitions. Word has length 79 [2024-11-14 02:44:48,464 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 02:44:48,464 INFO L471 AbstractCegarLoop]: Abstraction has 188 states and 205 transitions. [2024-11-14 02:44:48,464 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 17 states have (on average 2.411764705882353) internal successors, (41), 16 states have internal predecessors, (41), 9 states have call successors, (23), 3 states have call predecessors, (23), 2 states have return successors, (21), 7 states have call predecessors, (21), 9 states have call successors, (21) [2024-11-14 02:44:48,465 INFO L276 IsEmpty]: Start isEmpty. Operand 188 states and 205 transitions. [2024-11-14 02:44:48,466 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 88 [2024-11-14 02:44:48,466 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 02:44:48,466 INFO L215 NwaCegarLoop]: trace histogram [14, 13, 13, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1] [2024-11-14 02:44:48,482 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Forceful destruction successful, exit code 0 [2024-11-14 02:44:48,666 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable16 [2024-11-14 02:44:48,666 INFO L396 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 02:44:48,667 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 02:44:48,667 INFO L85 PathProgramCache]: Analyzing trace with hash -240712403, now seen corresponding path program 3 times [2024-11-14 02:44:48,667 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 02:44:48,667 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [430657847] [2024-11-14 02:44:48,667 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:44:48,667 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 02:44:48,714 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 02:44:48,716 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [364254406] [2024-11-14 02:44:48,716 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-14 02:44:48,716 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 02:44:48,716 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 02:44:48,718 INFO L229 MonitoredProcess]: Starting monitored process 14 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 02:44:48,722 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89110ef7-ba53-44ea-a5a3-ecb65a8e4fef/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2024-11-14 02:44:48,839 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-14 02:44:48,839 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-14 02:44:48,841 INFO L255 TraceCheckSpWp]: Trace formula consists of 211 conjuncts, 45 conjuncts are in the unsatisfiable core [2024-11-14 02:44:48,844 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 02:44:50,389 INFO L134 CoverageAnalysis]: Checked inductivity of 367 backedges. 72 proven. 49 refuted. 0 times theorem prover too weak. 246 trivial. 0 not checked. [2024-11-14 02:44:50,389 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 02:52:53,555 WARN L286 SmtUtils]: Spent 5.37s on a formula simplification that was a NOOP. DAG size: 9 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2024-11-14 02:53:05,200 WARN L286 SmtUtils]: Spent 5.11s on a formula simplification that was a NOOP. DAG size: 17 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2024-11-14 02:57:48,984 WARN L672 sPolynomialRelations]: Constructing 64(two to the power of 6 dual juncts.