./Ultimate.py --spec ../../sv-benchmarks/c/properties/unreach-call.prp --file ../../sv-benchmarks/c/nla-digbench-scaling/prodbin-ll_unwindbound100.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_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/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_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/config/TaipanReach.xml -i ../../sv-benchmarks/c/nla-digbench-scaling/prodbin-ll_unwindbound100.c -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/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_5ea12d34-a747-41d3-91d4-e1fa5410515f/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 d87fab1dc6e9b3b1ef38291e10411689fc961abba4e105f2586cc8da9615d8a6 --- Real Ultimate output --- This is Ultimate 0.3.0-dev-826ab2b [2024-11-14 05:24:57,324 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-14 05:24:57,410 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/config/svcomp-Reach-32bit-Taipan_Default.epf [2024-11-14 05:24:57,416 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-14 05:24:57,417 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-14 05:24:57,454 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-14 05:24:57,457 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-14 05:24:57,457 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-14 05:24:57,458 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-14 05:24:57,458 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-14 05:24:57,459 INFO L153 SettingsManager]: * User list type=DISABLED [2024-11-14 05:24:57,459 INFO L151 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2024-11-14 05:24:57,459 INFO L153 SettingsManager]: * Explicit value domain=true [2024-11-14 05:24:57,459 INFO L153 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2024-11-14 05:24:57,459 INFO L153 SettingsManager]: * Octagon Domain=false [2024-11-14 05:24:57,460 INFO L153 SettingsManager]: * Abstract domain=CompoundDomain [2024-11-14 05:24:57,460 INFO L153 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2024-11-14 05:24:57,460 INFO L153 SettingsManager]: * Use the RCFG-of-the-future interface=true [2024-11-14 05:24:57,460 INFO L153 SettingsManager]: * Interval Domain=false [2024-11-14 05:24:57,460 INFO L151 SettingsManager]: Preferences of Sifa differ from their defaults: [2024-11-14 05:24:57,460 INFO L153 SettingsManager]: * Call Summarizer=TopInputCallSummarizer [2024-11-14 05:24:57,460 INFO L153 SettingsManager]: * Simplification Technique=POLY_PAC [2024-11-14 05:24:57,462 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-14 05:24:57,462 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-14 05:24:57,462 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-14 05:24:57,462 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-14 05:24:57,462 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-14 05:24:57,462 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-14 05:24:57,462 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-14 05:24:57,463 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-14 05:24:57,463 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-14 05:24:57,463 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-14 05:24:57,463 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-14 05:24:57,463 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-14 05:24:57,464 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-14 05:24:57,464 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-14 05:24:57,464 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-14 05:24:57,464 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-14 05:24:57,464 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2024-11-14 05:24:57,464 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-14 05:24:57,465 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-14 05:24:57,465 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-14 05:24:57,465 INFO L153 SettingsManager]: * Trace refinement strategy=SIFA_TAIPAN [2024-11-14 05:24:57,465 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-14 05:24:57,465 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-14 05:24:57,465 INFO L153 SettingsManager]: * Trace refinement exception blacklist=NONE [2024-11-14 05:24:57,465 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-14 05:24:57,465 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_5ea12d34-a747-41d3-91d4-e1fa5410515f/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 -> d87fab1dc6e9b3b1ef38291e10411689fc961abba4e105f2586cc8da9615d8a6 [2024-11-14 05:24:57,851 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-14 05:24:57,864 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-14 05:24:57,867 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-14 05:24:57,869 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-14 05:24:57,870 INFO L274 PluginConnector]: CDTParser initialized [2024-11-14 05:24:57,873 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/../../sv-benchmarks/c/nla-digbench-scaling/prodbin-ll_unwindbound100.c Unable to find full path for "g++" [2024-11-14 05:24:59,920 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-14 05:25:00,227 INFO L384 CDTParser]: Found 1 translation units. [2024-11-14 05:25:00,228 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/sv-benchmarks/c/nla-digbench-scaling/prodbin-ll_unwindbound100.c [2024-11-14 05:25:00,237 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/data/49c5fc7d7/e02632e14dd94700b86b87c5e58aacfb/FLAG2e7395e5a [2024-11-14 05:25:00,254 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/data/49c5fc7d7/e02632e14dd94700b86b87c5e58aacfb [2024-11-14 05:25:00,257 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-14 05:25:00,259 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-14 05:25:00,260 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-14 05:25:00,260 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-14 05:25:00,266 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-14 05:25:00,267 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 14.11 05:25:00" (1/1) ... [2024-11-14 05:25:00,268 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@3eb3a107 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 05:25:00, skipping insertion in model container [2024-11-14 05:25:00,268 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 14.11 05:25:00" (1/1) ... [2024-11-14 05:25:00,284 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-14 05:25:00,468 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_5ea12d34-a747-41d3-91d4-e1fa5410515f/sv-benchmarks/c/nla-digbench-scaling/prodbin-ll_unwindbound100.c[1263,1276] [2024-11-14 05:25:00,492 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-14 05:25:00,504 INFO L200 MainTranslator]: Completed pre-run [2024-11-14 05:25:00,519 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_5ea12d34-a747-41d3-91d4-e1fa5410515f/sv-benchmarks/c/nla-digbench-scaling/prodbin-ll_unwindbound100.c[1263,1276] [2024-11-14 05:25:00,528 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-14 05:25:00,548 INFO L204 MainTranslator]: Completed translation [2024-11-14 05:25:00,549 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 05:25:00 WrapperNode [2024-11-14 05:25:00,549 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-14 05:25:00,550 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-14 05:25:00,550 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-14 05:25:00,551 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-14 05:25:00,558 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 05:25:00" (1/1) ... [2024-11-14 05:25:00,565 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 05:25:00" (1/1) ... [2024-11-14 05:25:00,582 INFO L138 Inliner]: procedures = 14, calls = 10, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 48 [2024-11-14 05:25:00,583 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-14 05:25:00,584 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-14 05:25:00,584 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-14 05:25:00,584 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-14 05:25:00,591 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 05:25:00" (1/1) ... [2024-11-14 05:25:00,592 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 05:25:00" (1/1) ... [2024-11-14 05:25:00,593 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 05:25:00" (1/1) ... [2024-11-14 05:25:00,593 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 05:25:00" (1/1) ... [2024-11-14 05:25:00,601 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 05:25:00" (1/1) ... [2024-11-14 05:25:00,604 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 05:25:00" (1/1) ... [2024-11-14 05:25:00,608 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 05:25:00" (1/1) ... [2024-11-14 05:25:00,609 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 05:25:00" (1/1) ... [2024-11-14 05:25:00,611 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-14 05:25:00,614 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-14 05:25:00,614 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-14 05:25:00,614 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-14 05:25:00,615 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 05:25:00" (1/1) ... [2024-11-14 05:25:00,628 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2024-11-14 05:25:00,645 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 05:25:00,665 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2024-11-14 05:25:00,671 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2024-11-14 05:25:00,704 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-14 05:25:00,704 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2024-11-14 05:25:00,704 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-14 05:25:00,705 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-14 05:25:00,705 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-14 05:25:00,706 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-14 05:25:00,795 INFO L238 CfgBuilder]: Building ICFG [2024-11-14 05:25:00,798 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-14 05:25:00,977 INFO L? ?]: Removed 7 outVars from TransFormulas that were not future-live. [2024-11-14 05:25:00,977 INFO L287 CfgBuilder]: Performing block encoding [2024-11-14 05:25:01,053 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-14 05:25:01,054 INFO L316 CfgBuilder]: Removed 1 assume(true) statements. [2024-11-14 05:25:01,054 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 14.11 05:25:01 BoogieIcfgContainer [2024-11-14 05:25:01,054 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-14 05:25:01,057 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-14 05:25:01,057 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-14 05:25:01,063 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-14 05:25:01,064 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 14.11 05:25:00" (1/3) ... [2024-11-14 05:25:01,065 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@21aa1371 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 14.11 05:25:01, skipping insertion in model container [2024-11-14 05:25:01,065 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 05:25:00" (2/3) ... [2024-11-14 05:25:01,065 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@21aa1371 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 14.11 05:25:01, skipping insertion in model container [2024-11-14 05:25:01,065 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 14.11 05:25:01" (3/3) ... [2024-11-14 05:25:01,067 INFO L112 eAbstractionObserver]: Analyzing ICFG prodbin-ll_unwindbound100.c [2024-11-14 05:25:01,087 INFO L217 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-14 05:25:01,090 INFO L154 ceAbstractionStarter]: Applying trace abstraction to ICFG prodbin-ll_unwindbound100.c that has 2 procedures, 14 locations, 1 initial locations, 1 loop locations, and 1 error locations. [2024-11-14 05:25:01,177 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-14 05:25:01,196 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;@25edb93a, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-14 05:25:01,197 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-14 05:25:01,203 INFO L276 IsEmpty]: Start isEmpty. Operand has 14 states, 9 states have (on average 1.5555555555555556) internal successors, (14), 10 states have internal predecessors, (14), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-14 05:25:01,211 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 7 [2024-11-14 05:25:01,212 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 05:25:01,212 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1] [2024-11-14 05:25:01,213 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 05:25:01,222 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 05:25:01,223 INFO L85 PathProgramCache]: Analyzing trace with hash -1571732168, now seen corresponding path program 1 times [2024-11-14 05:25:01,234 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 05:25:01,234 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [352913750] [2024-11-14 05:25:01,235 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 05:25:01,235 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 05:25:01,333 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 05:25:01,392 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 05:25:01,392 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 05:25:01,392 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [352913750] [2024-11-14 05:25:01,396 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [352913750] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 05:25:01,397 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 05:25:01,397 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-11-14 05:25:01,399 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1679646511] [2024-11-14 05:25:01,399 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 05:25:01,403 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-11-14 05:25:01,404 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 05:25:01,428 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-11-14 05:25:01,429 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-14 05:25:01,434 INFO L87 Difference]: Start difference. First operand has 14 states, 9 states have (on average 1.5555555555555556) internal successors, (14), 10 states have internal predecessors, (14), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Second operand has 2 states, 2 states have (on average 2.5) internal successors, (5), 2 states have internal predecessors, (5), 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 05:25:01,483 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 05:25:01,484 INFO L93 Difference]: Finished difference Result 27 states and 37 transitions. [2024-11-14 05:25:01,486 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-14 05:25:01,487 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 2.5) internal successors, (5), 2 states have internal predecessors, (5), 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 6 [2024-11-14 05:25:01,488 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 05:25:01,494 INFO L225 Difference]: With dead ends: 27 [2024-11-14 05:25:01,495 INFO L226 Difference]: Without dead ends: 12 [2024-11-14 05:25:01,498 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 05:25:01,501 INFO L432 NwaCegarLoop]: 13 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, 13 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 05:25:01,502 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 13 Invalid, 3 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 3 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-14 05:25:01,523 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 12 states. [2024-11-14 05:25:01,536 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 12 to 12. [2024-11-14 05:25:01,538 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 12 states, 8 states have (on average 1.375) internal successors, (11), 9 states have internal predecessors, (11), 2 states have call successors, (2), 1 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 05:25:01,542 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 12 states to 12 states and 14 transitions. [2024-11-14 05:25:01,544 INFO L78 Accepts]: Start accepts. Automaton has 12 states and 14 transitions. Word has length 6 [2024-11-14 05:25:01,544 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 05:25:01,544 INFO L471 AbstractCegarLoop]: Abstraction has 12 states and 14 transitions. [2024-11-14 05:25:01,544 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 2.5) internal successors, (5), 2 states have internal predecessors, (5), 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 05:25:01,544 INFO L276 IsEmpty]: Start isEmpty. Operand 12 states and 14 transitions. [2024-11-14 05:25:01,545 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 8 [2024-11-14 05:25:01,545 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 05:25:01,545 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2024-11-14 05:25:01,545 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-14 05:25:01,546 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 05:25:01,546 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 05:25:01,546 INFO L85 PathProgramCache]: Analyzing trace with hash -2085425866, now seen corresponding path program 1 times [2024-11-14 05:25:01,546 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 05:25:01,547 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [282003968] [2024-11-14 05:25:01,547 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 05:25:01,547 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 05:25:01,563 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 05:25:01,643 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 05:25:01,643 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 05:25:01,644 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [282003968] [2024-11-14 05:25:01,644 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [282003968] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 05:25:01,644 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 05:25:01,644 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2024-11-14 05:25:01,644 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1821940674] [2024-11-14 05:25:01,644 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 05:25:01,645 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-11-14 05:25:01,645 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 05:25:01,646 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-11-14 05:25:01,646 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-14 05:25:01,647 INFO L87 Difference]: Start difference. First operand 12 states and 14 transitions. Second operand has 4 states, 4 states have (on average 1.5) 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 05:25:01,693 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 05:25:01,693 INFO L93 Difference]: Finished difference Result 21 states and 23 transitions. [2024-11-14 05:25:01,694 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-11-14 05:25:01,694 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 1.5) 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 05:25:01,695 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 05:25:01,695 INFO L225 Difference]: With dead ends: 21 [2024-11-14 05:25:01,695 INFO L226 Difference]: Without dead ends: 14 [2024-11-14 05:25:01,696 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 05:25:01,697 INFO L432 NwaCegarLoop]: 10 mSDtfsCounter, 0 mSDsluCounter, 19 mSDsCounter, 0 mSdLazyCounter, 12 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 29 SdHoareTripleChecker+Invalid, 12 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 12 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-14 05:25:01,697 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 29 Invalid, 12 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 12 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-14 05:25:01,704 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 14 states. [2024-11-14 05:25:01,708 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 14 to 14. [2024-11-14 05:25:01,708 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 14 states, 10 states have (on average 1.3) internal successors, (13), 11 states have internal predecessors, (13), 2 states have call successors, (2), 1 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 05:25:01,709 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 14 states to 14 states and 16 transitions. [2024-11-14 05:25:01,709 INFO L78 Accepts]: Start accepts. Automaton has 14 states and 16 transitions. Word has length 7 [2024-11-14 05:25:01,709 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 05:25:01,709 INFO L471 AbstractCegarLoop]: Abstraction has 14 states and 16 transitions. [2024-11-14 05:25:01,710 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 1.5) 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 05:25:01,710 INFO L276 IsEmpty]: Start isEmpty. Operand 14 states and 16 transitions. [2024-11-14 05:25:01,710 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 8 [2024-11-14 05:25:01,710 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 05:25:01,710 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2024-11-14 05:25:01,711 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-11-14 05:25:01,711 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 05:25:01,711 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 05:25:01,712 INFO L85 PathProgramCache]: Analyzing trace with hash -2083638406, now seen corresponding path program 1 times [2024-11-14 05:25:01,712 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 05:25:01,712 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2050728045] [2024-11-14 05:25:01,712 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 05:25:01,712 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 05:25:01,750 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 05:25:01,752 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2121291377] [2024-11-14 05:25:01,752 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 05:25:01,753 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 05:25:01,753 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 05:25:01,756 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 05:25:01,759 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-11-14 05:25:01,824 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 05:25:01,827 INFO L255 TraceCheckSpWp]: Trace formula consists of 48 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-11-14 05:25:01,836 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 05:25:02,030 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 05:25:02,031 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-14 05:25:02,031 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 05:25:02,031 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2050728045] [2024-11-14 05:25:02,032 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-14 05:25:02,034 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2121291377] [2024-11-14 05:25:02,034 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2121291377] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 05:25:02,035 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 05:25:02,035 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2024-11-14 05:25:02,036 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [170076931] [2024-11-14 05:25:02,036 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 05:25:02,036 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-14 05:25:02,036 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 05:25:02,037 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-14 05:25:02,037 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-14 05:25:02,037 INFO L87 Difference]: Start difference. First operand 14 states and 16 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 05:25:02,105 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 05:25:02,105 INFO L93 Difference]: Finished difference Result 22 states and 25 transitions. [2024-11-14 05:25:02,106 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-14 05:25:02,106 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 05:25:02,106 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 05:25:02,107 INFO L225 Difference]: With dead ends: 22 [2024-11-14 05:25:02,107 INFO L226 Difference]: Without dead ends: 20 [2024-11-14 05:25:02,107 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 3 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 05:25:02,108 INFO L432 NwaCegarLoop]: 8 mSDtfsCounter, 3 mSDsluCounter, 23 mSDsCounter, 0 mSdLazyCounter, 24 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 31 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.0s IncrementalHoareTripleChecker+Time [2024-11-14 05:25:02,109 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 31 Invalid, 24 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 24 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-14 05:25:02,110 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 20 states. [2024-11-14 05:25:02,114 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 20 to 19. [2024-11-14 05:25:02,114 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 19 states, 13 states have (on average 1.2307692307692308) internal successors, (16), 15 states have internal predecessors, (16), 3 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-14 05:25:02,115 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 19 states to 19 states and 21 transitions. [2024-11-14 05:25:02,115 INFO L78 Accepts]: Start accepts. Automaton has 19 states and 21 transitions. Word has length 7 [2024-11-14 05:25:02,116 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 05:25:02,116 INFO L471 AbstractCegarLoop]: Abstraction has 19 states and 21 transitions. [2024-11-14 05:25:02,116 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 05:25:02,116 INFO L276 IsEmpty]: Start isEmpty. Operand 19 states and 21 transitions. [2024-11-14 05:25:02,116 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 14 [2024-11-14 05:25:02,116 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 05:25:02,117 INFO L215 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 05:25:02,139 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2024-11-14 05:25:02,317 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 05:25:02,317 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 05:25:02,318 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 05:25:02,318 INFO L85 PathProgramCache]: Analyzing trace with hash 1858335025, now seen corresponding path program 1 times [2024-11-14 05:25:02,318 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 05:25:02,318 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2136177747] [2024-11-14 05:25:02,318 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 05:25:02,319 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 05:25:02,346 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 05:25:02,525 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 05:25:02,525 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 05:25:02,525 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2136177747] [2024-11-14 05:25:02,525 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2136177747] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 05:25:02,525 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 05:25:02,525 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2024-11-14 05:25:02,525 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [238162851] [2024-11-14 05:25:02,525 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 05:25:02,526 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2024-11-14 05:25:02,526 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 05:25:02,526 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2024-11-14 05:25:02,526 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-11-14 05:25:02,527 INFO L87 Difference]: Start difference. First operand 19 states and 21 transitions. Second operand has 3 states, 3 states have (on average 3.3333333333333335) internal successors, (10), 3 states have internal predecessors, (10), 2 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 05:25:02,542 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 05:25:02,542 INFO L93 Difference]: Finished difference Result 27 states and 29 transitions. [2024-11-14 05:25:02,543 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2024-11-14 05:25:02,543 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 3.3333333333333335) internal successors, (10), 3 states have internal predecessors, (10), 2 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 13 [2024-11-14 05:25:02,543 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 05:25:02,544 INFO L225 Difference]: With dead ends: 27 [2024-11-14 05:25:02,544 INFO L226 Difference]: Without dead ends: 20 [2024-11-14 05:25:02,544 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-11-14 05:25:02,545 INFO L432 NwaCegarLoop]: 12 mSDtfsCounter, 0 mSDsluCounter, 11 mSDsCounter, 0 mSdLazyCounter, 4 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 23 SdHoareTripleChecker+Invalid, 4 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 4 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-14 05:25:02,546 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 23 Invalid, 4 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 4 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-14 05:25:02,547 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 20 states. [2024-11-14 05:25:02,550 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 20 to 20. [2024-11-14 05:25:02,550 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 20 states, 14 states have (on average 1.2142857142857142) internal successors, (17), 15 states have internal predecessors, (17), 3 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-14 05:25:02,551 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 20 states to 20 states and 22 transitions. [2024-11-14 05:25:02,551 INFO L78 Accepts]: Start accepts. Automaton has 20 states and 22 transitions. Word has length 13 [2024-11-14 05:25:02,551 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 05:25:02,552 INFO L471 AbstractCegarLoop]: Abstraction has 20 states and 22 transitions. [2024-11-14 05:25:02,552 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 3.3333333333333335) internal successors, (10), 3 states have internal predecessors, (10), 2 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 05:25:02,552 INFO L276 IsEmpty]: Start isEmpty. Operand 20 states and 22 transitions. [2024-11-14 05:25:02,553 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2024-11-14 05:25:02,553 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 05:25:02,553 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 05:25:02,553 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2024-11-14 05:25:02,553 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 05:25:02,554 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 05:25:02,554 INFO L85 PathProgramCache]: Analyzing trace with hash 1646896634, now seen corresponding path program 1 times [2024-11-14 05:25:02,554 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 05:25:02,554 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1468044471] [2024-11-14 05:25:02,554 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 05:25:02,555 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 05:25:02,573 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 05:25:02,698 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 05:25:02,698 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 05:25:02,699 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1468044471] [2024-11-14 05:25:02,699 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1468044471] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 05:25:02,699 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [490537891] [2024-11-14 05:25:02,699 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 05:25:02,699 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 05:25:02,699 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 05:25:02,702 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 05:25:02,703 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-11-14 05:25:02,789 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 05:25:02,790 INFO L255 TraceCheckSpWp]: Trace formula consists of 68 conjuncts, 5 conjuncts are in the unsatisfiable core [2024-11-14 05:25:02,792 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 05:25:02,844 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 05:25:02,845 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 05:25:02,928 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 05:25:02,928 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [490537891] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 05:25:02,928 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1758441789] [2024-11-14 05:25:02,953 INFO L159 IcfgInterpreter]: Started Sifa with 12 locations of interest [2024-11-14 05:25:02,953 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 05:25:02,956 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 05:25:02,962 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 05:25:02,962 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 05:25:04,970 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 63 for LOIs [2024-11-14 05:25:05,151 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 05:25:08,312 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '376#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0))' at error location [2024-11-14 05:25:08,312 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 05:25:08,312 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-14 05:25:08,312 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 4, 5] total 8 [2024-11-14 05:25:08,312 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [930214602] [2024-11-14 05:25:08,313 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-14 05:25:08,313 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-11-14 05:25:08,313 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 05:25:08,314 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-11-14 05:25:08,316 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=51, Invalid=255, Unknown=0, NotChecked=0, Total=306 [2024-11-14 05:25:08,317 INFO L87 Difference]: Start difference. First operand 20 states and 22 transitions. Second operand has 8 states, 8 states have (on average 2.625) internal successors, (21), 8 states have internal predecessors, (21), 3 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-14 05:25:08,480 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 05:25:08,480 INFO L93 Difference]: Finished difference Result 51 states and 57 transitions. [2024-11-14 05:25:08,481 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-14 05:25:08,482 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 2.625) internal successors, (21), 8 states have internal predecessors, (21), 3 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 15 [2024-11-14 05:25:08,482 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 05:25:08,483 INFO L225 Difference]: With dead ends: 51 [2024-11-14 05:25:08,483 INFO L226 Difference]: Without dead ends: 44 [2024-11-14 05:25:08,483 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 51 GetRequests, 32 SyntacticMatches, 0 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 1 DeprecatedPredicates, 100 ImplicationChecksByTransitivity, 3.3s TimeCoverageRelationStatistics Valid=71, Invalid=349, Unknown=0, NotChecked=0, Total=420 [2024-11-14 05:25:08,484 INFO L432 NwaCegarLoop]: 10 mSDtfsCounter, 25 mSDsluCounter, 37 mSDsCounter, 0 mSdLazyCounter, 31 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 25 SdHoareTripleChecker+Valid, 47 SdHoareTripleChecker+Invalid, 34 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 31 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-14 05:25:08,488 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [25 Valid, 47 Invalid, 34 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 31 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-14 05:25:08,489 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 44 states. [2024-11-14 05:25:08,500 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 44 to 40. [2024-11-14 05:25:08,500 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 40 states, 28 states have (on average 1.25) internal successors, (35), 31 states have internal predecessors, (35), 7 states have call successors, (7), 4 states have call predecessors, (7), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2024-11-14 05:25:08,503 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 40 states to 40 states and 46 transitions. [2024-11-14 05:25:08,503 INFO L78 Accepts]: Start accepts. Automaton has 40 states and 46 transitions. Word has length 15 [2024-11-14 05:25:08,503 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 05:25:08,503 INFO L471 AbstractCegarLoop]: Abstraction has 40 states and 46 transitions. [2024-11-14 05:25:08,504 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 2.625) internal successors, (21), 8 states have internal predecessors, (21), 3 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-14 05:25:08,504 INFO L276 IsEmpty]: Start isEmpty. Operand 40 states and 46 transitions. [2024-11-14 05:25:08,506 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2024-11-14 05:25:08,506 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 05:25:08,507 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 05:25:08,533 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2024-11-14 05:25:08,707 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 05:25:08,708 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 05:25:08,708 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 05:25:08,708 INFO L85 PathProgramCache]: Analyzing trace with hash 1648684094, now seen corresponding path program 1 times [2024-11-14 05:25:08,708 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 05:25:08,708 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1843277444] [2024-11-14 05:25:08,708 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 05:25:08,709 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 05:25:08,752 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 05:25:08,753 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [436992038] [2024-11-14 05:25:08,754 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 05:25:08,754 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 05:25:08,754 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 05:25:08,761 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 05:25:08,763 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-11-14 05:25:08,838 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 05:25:08,840 INFO L255 TraceCheckSpWp]: Trace formula consists of 68 conjuncts, 20 conjuncts are in the unsatisfiable core [2024-11-14 05:25:08,844 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 05:25:10,371 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 1 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 05:25:10,372 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 05:25:13,189 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 1 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 05:25:13,189 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 05:25:13,189 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1843277444] [2024-11-14 05:25:13,189 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-14 05:25:13,190 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [436992038] [2024-11-14 05:25:13,190 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [436992038] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 05:25:13,190 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1471768842] [2024-11-14 05:25:13,193 INFO L159 IcfgInterpreter]: Started Sifa with 11 locations of interest [2024-11-14 05:25:13,193 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 05:25:13,193 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 05:25:13,193 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 05:25:13,193 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 05:25:14,235 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 39 for LOIs [2024-11-14 05:25:14,279 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 05:25:15,617 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '622#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (<= ~counter~0 100))' at error location [2024-11-14 05:25:15,617 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 05:25:15,618 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-14 05:25:15,618 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 9] total 12 [2024-11-14 05:25:15,618 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1641553525] [2024-11-14 05:25:15,618 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-14 05:25:15,619 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2024-11-14 05:25:15,619 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 05:25:15,620 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2024-11-14 05:25:15,620 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=69, Invalid=351, Unknown=0, NotChecked=0, Total=420 [2024-11-14 05:25:15,620 INFO L87 Difference]: Start difference. First operand 40 states and 46 transitions. Second operand has 12 states, 12 states have (on average 1.6666666666666667) internal successors, (20), 9 states have internal predecessors, (20), 4 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-14 05:25:17,798 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 05:25:22,597 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 05:25:22,597 INFO L93 Difference]: Finished difference Result 56 states and 62 transitions. [2024-11-14 05:25:22,597 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2024-11-14 05:25:22,598 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 1.6666666666666667) internal successors, (20), 9 states have internal predecessors, (20), 4 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 15 [2024-11-14 05:25:22,598 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 05:25:22,600 INFO L225 Difference]: With dead ends: 56 [2024-11-14 05:25:22,600 INFO L226 Difference]: Without dead ends: 50 [2024-11-14 05:25:22,600 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 46 GetRequests, 22 SyntacticMatches, 3 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 1 DeprecatedPredicates, 96 ImplicationChecksByTransitivity, 6.0s TimeCoverageRelationStatistics Valid=83, Invalid=423, Unknown=0, NotChecked=0, Total=506 [2024-11-14 05:25:22,602 INFO L432 NwaCegarLoop]: 10 mSDtfsCounter, 5 mSDsluCounter, 46 mSDsCounter, 0 mSdLazyCounter, 55 mSolverCounterSat, 7 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 3.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 56 SdHoareTripleChecker+Invalid, 63 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 55 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 3.5s IncrementalHoareTripleChecker+Time [2024-11-14 05:25:22,602 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 56 Invalid, 63 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 55 Invalid, 1 Unknown, 0 Unchecked, 3.5s Time] [2024-11-14 05:25:22,603 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 50 states. [2024-11-14 05:25:22,612 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 50 to 46. [2024-11-14 05:25:22,612 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 46 states, 33 states have (on average 1.1515151515151516) internal successors, (38), 35 states have internal predecessors, (38), 7 states have call successors, (7), 6 states have call predecessors, (7), 5 states have return successors, (5), 4 states have call predecessors, (5), 5 states have call successors, (5) [2024-11-14 05:25:22,613 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 46 states to 46 states and 50 transitions. [2024-11-14 05:25:22,613 INFO L78 Accepts]: Start accepts. Automaton has 46 states and 50 transitions. Word has length 15 [2024-11-14 05:25:22,614 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 05:25:22,614 INFO L471 AbstractCegarLoop]: Abstraction has 46 states and 50 transitions. [2024-11-14 05:25:22,614 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 1.6666666666666667) internal successors, (20), 9 states have internal predecessors, (20), 4 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-14 05:25:22,614 INFO L276 IsEmpty]: Start isEmpty. Operand 46 states and 50 transitions. [2024-11-14 05:25:22,615 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2024-11-14 05:25:22,615 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 05:25:22,615 INFO L215 NwaCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1] [2024-11-14 05:25:22,639 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2024-11-14 05:25:22,816 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 05:25:22,816 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 05:25:22,817 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 05:25:22,817 INFO L85 PathProgramCache]: Analyzing trace with hash 395708149, now seen corresponding path program 1 times [2024-11-14 05:25:22,817 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 05:25:22,817 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1514087162] [2024-11-14 05:25:22,817 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 05:25:22,818 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 05:25:22,860 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 05:25:22,862 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1395394671] [2024-11-14 05:25:22,863 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 05:25:22,863 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 05:25:22,863 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 05:25:22,865 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 05:25:22,868 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-11-14 05:25:22,927 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 05:25:22,928 INFO L255 TraceCheckSpWp]: Trace formula consists of 79 conjuncts, 10 conjuncts are in the unsatisfiable core [2024-11-14 05:25:22,930 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 05:25:23,004 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 7 proven. 1 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-14 05:25:23,004 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 05:25:23,098 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 7 proven. 1 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-14 05:25:23,098 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 05:25:23,098 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1514087162] [2024-11-14 05:25:23,098 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-14 05:25:23,098 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1395394671] [2024-11-14 05:25:23,098 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1395394671] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 05:25:23,098 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [2012009604] [2024-11-14 05:25:23,100 INFO L159 IcfgInterpreter]: Started Sifa with 12 locations of interest [2024-11-14 05:25:23,100 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 05:25:23,101 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 05:25:23,103 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 05:25:23,103 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 05:25:23,911 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 41 for LOIs [2024-11-14 05:25:23,955 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 05:25:24,491 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '919#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (<= ~counter~0 100))' at error location [2024-11-14 05:25:24,491 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 05:25:24,491 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-14 05:25:24,491 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 10 [2024-11-14 05:25:24,491 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [454803807] [2024-11-14 05:25:24,492 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-14 05:25:24,492 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-11-14 05:25:24,493 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 05:25:24,494 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-11-14 05:25:24,494 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=61, Invalid=281, Unknown=0, NotChecked=0, Total=342 [2024-11-14 05:25:24,494 INFO L87 Difference]: Start difference. First operand 46 states and 50 transitions. Second operand has 10 states, 9 states have (on average 1.8888888888888888) internal successors, (17), 7 states have internal predecessors, (17), 2 states have call successors, (2), 2 states have call predecessors, (2), 2 states have return successors, (3), 3 states have call predecessors, (3), 1 states have call successors, (3) [2024-11-14 05:25:24,588 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 05:25:24,589 INFO L93 Difference]: Finished difference Result 53 states and 56 transitions. [2024-11-14 05:25:24,589 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2024-11-14 05:25:24,589 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 9 states have (on average 1.8888888888888888) internal successors, (17), 7 states have internal predecessors, (17), 2 states have call successors, (2), 2 states have call predecessors, (2), 2 states have return successors, (3), 3 states have call predecessors, (3), 1 states have call successors, (3) Word has length 21 [2024-11-14 05:25:24,592 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 05:25:24,593 INFO L225 Difference]: With dead ends: 53 [2024-11-14 05:25:24,593 INFO L226 Difference]: Without dead ends: 43 [2024-11-14 05:25:24,594 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 62 GetRequests, 42 SyntacticMatches, 2 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 72 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=68, Invalid=312, Unknown=0, NotChecked=0, Total=380 [2024-11-14 05:25:24,595 INFO L432 NwaCegarLoop]: 9 mSDtfsCounter, 8 mSDsluCounter, 34 mSDsCounter, 0 mSdLazyCounter, 48 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 43 SdHoareTripleChecker+Invalid, 50 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 48 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-14 05:25:24,595 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 43 Invalid, 50 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 48 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-14 05:25:24,599 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 43 states. [2024-11-14 05:25:24,612 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 43 to 43. [2024-11-14 05:25:24,613 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 43 states, 31 states have (on average 1.064516129032258) internal successors, (33), 33 states have internal predecessors, (33), 6 states have call successors, (6), 5 states have call predecessors, (6), 5 states have return successors, (5), 4 states have call predecessors, (5), 5 states have call successors, (5) [2024-11-14 05:25:24,615 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 43 states to 43 states and 44 transitions. [2024-11-14 05:25:24,615 INFO L78 Accepts]: Start accepts. Automaton has 43 states and 44 transitions. Word has length 21 [2024-11-14 05:25:24,616 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 05:25:24,618 INFO L471 AbstractCegarLoop]: Abstraction has 43 states and 44 transitions. [2024-11-14 05:25:24,618 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 9 states have (on average 1.8888888888888888) internal successors, (17), 7 states have internal predecessors, (17), 2 states have call successors, (2), 2 states have call predecessors, (2), 2 states have return successors, (3), 3 states have call predecessors, (3), 1 states have call successors, (3) [2024-11-14 05:25:24,618 INFO L276 IsEmpty]: Start isEmpty. Operand 43 states and 44 transitions. [2024-11-14 05:25:24,619 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 40 [2024-11-14 05:25:24,619 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 05:25:24,619 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1] [2024-11-14 05:25:24,637 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2024-11-14 05:25:24,820 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable6 [2024-11-14 05:25:24,820 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 05:25:24,820 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 05:25:24,821 INFO L85 PathProgramCache]: Analyzing trace with hash 1940633670, now seen corresponding path program 2 times [2024-11-14 05:25:24,821 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 05:25:24,821 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [488702361] [2024-11-14 05:25:24,821 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 05:25:24,821 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 05:25:24,861 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 05:25:25,181 INFO L134 CoverageAnalysis]: Checked inductivity of 64 backedges. 8 proven. 32 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-14 05:25:25,182 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 05:25:25,182 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [488702361] [2024-11-14 05:25:25,182 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [488702361] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 05:25:25,182 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [600755522] [2024-11-14 05:25:25,183 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-14 05:25:25,183 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 05:25:25,183 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 05:25:25,185 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 05:25:25,188 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2024-11-14 05:25:25,263 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2024-11-14 05:25:25,264 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-14 05:25:25,265 INFO L255 TraceCheckSpWp]: Trace formula consists of 128 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-14 05:25:25,267 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 05:25:25,323 INFO L134 CoverageAnalysis]: Checked inductivity of 64 backedges. 8 proven. 56 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 05:25:25,323 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 05:25:25,452 INFO L134 CoverageAnalysis]: Checked inductivity of 64 backedges. 8 proven. 32 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-14 05:25:25,453 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [600755522] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 05:25:25,453 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1955509197] [2024-11-14 05:25:25,457 INFO L159 IcfgInterpreter]: Started Sifa with 12 locations of interest [2024-11-14 05:25:25,457 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 05:25:25,457 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 05:25:25,458 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 05:25:25,458 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 05:25:26,353 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 63 for LOIs [2024-11-14 05:25:26,421 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 05:25:27,131 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1315#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0))' at error location [2024-11-14 05:25:27,131 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 05:25:27,131 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-14 05:25:27,131 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 7, 8] total 14 [2024-11-14 05:25:27,131 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [17717909] [2024-11-14 05:25:27,131 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-14 05:25:27,132 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2024-11-14 05:25:27,132 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 05:25:27,133 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2024-11-14 05:25:27,133 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=97, Invalid=409, Unknown=0, NotChecked=0, Total=506 [2024-11-14 05:25:27,133 INFO L87 Difference]: Start difference. First operand 43 states and 44 transitions. Second operand has 14 states, 14 states have (on average 3.4285714285714284) internal successors, (48), 14 states have internal predecessors, (48), 9 states have call successors, (13), 6 states have call predecessors, (13), 5 states have return successors, (12), 8 states have call predecessors, (12), 8 states have call successors, (12) [2024-11-14 05:25:27,401 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 05:25:27,402 INFO L93 Difference]: Finished difference Result 103 states and 109 transitions. [2024-11-14 05:25:27,402 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2024-11-14 05:25:27,402 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 3.4285714285714284) internal successors, (48), 14 states have internal predecessors, (48), 9 states have call successors, (13), 6 states have call predecessors, (13), 5 states have return successors, (12), 8 states have call predecessors, (12), 8 states have call successors, (12) Word has length 39 [2024-11-14 05:25:27,403 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 05:25:27,404 INFO L225 Difference]: With dead ends: 103 [2024-11-14 05:25:27,404 INFO L226 Difference]: Without dead ends: 96 [2024-11-14 05:25:27,405 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 132 GetRequests, 102 SyntacticMatches, 0 SemanticMatches, 30 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 250 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=210, Invalid=782, Unknown=0, NotChecked=0, Total=992 [2024-11-14 05:25:27,406 INFO L432 NwaCegarLoop]: 9 mSDtfsCounter, 48 mSDsluCounter, 70 mSDsCounter, 0 mSdLazyCounter, 62 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 48 SdHoareTripleChecker+Valid, 79 SdHoareTripleChecker+Invalid, 66 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 62 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-14 05:25:27,406 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [48 Valid, 79 Invalid, 66 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 62 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-14 05:25:27,407 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 96 states. [2024-11-14 05:25:27,418 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 96 to 86. [2024-11-14 05:25:27,419 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 86 states, 64 states have (on average 1.109375) internal successors, (71), 65 states have internal predecessors, (71), 11 states have call successors, (11), 10 states have call predecessors, (11), 10 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2024-11-14 05:25:27,420 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 86 states to 86 states and 92 transitions. [2024-11-14 05:25:27,420 INFO L78 Accepts]: Start accepts. Automaton has 86 states and 92 transitions. Word has length 39 [2024-11-14 05:25:27,421 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 05:25:27,421 INFO L471 AbstractCegarLoop]: Abstraction has 86 states and 92 transitions. [2024-11-14 05:25:27,421 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 3.4285714285714284) internal successors, (48), 14 states have internal predecessors, (48), 9 states have call successors, (13), 6 states have call predecessors, (13), 5 states have return successors, (12), 8 states have call predecessors, (12), 8 states have call successors, (12) [2024-11-14 05:25:27,421 INFO L276 IsEmpty]: Start isEmpty. Operand 86 states and 92 transitions. [2024-11-14 05:25:27,422 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 40 [2024-11-14 05:25:27,422 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 05:25:27,422 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 5, 5, 4, 4, 4, 4, 1, 1, 1] [2024-11-14 05:25:27,442 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2024-11-14 05:25:27,622 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable7 [2024-11-14 05:25:27,622 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 05:25:27,623 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 05:25:27,624 INFO L85 PathProgramCache]: Analyzing trace with hash 1942421130, now seen corresponding path program 2 times [2024-11-14 05:25:27,624 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 05:25:27,624 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [74227283] [2024-11-14 05:25:27,624 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 05:25:27,624 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 05:25:27,731 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 05:25:27,733 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [52106021] [2024-11-14 05:25:27,733 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-14 05:25:27,733 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 05:25:27,733 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 05:25:27,738 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 05:25:27,741 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2024-11-14 05:25:27,886 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2024-11-14 05:25:27,886 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-14 05:25:27,887 INFO L255 TraceCheckSpWp]: Trace formula consists of 128 conjuncts, 44 conjuncts are in the unsatisfiable core [2024-11-14 05:25:27,892 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 05:25:28,956 INFO L134 CoverageAnalysis]: Checked inductivity of 68 backedges. 14 proven. 39 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2024-11-14 05:25:28,956 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 05:25:33,448 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 05:25:33,448 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [74227283] [2024-11-14 05:25:33,448 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-14 05:25:33,449 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [52106021] [2024-11-14 05:25:33,449 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [52106021] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 05:25:33,449 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [523661293] [2024-11-14 05:25:33,451 INFO L159 IcfgInterpreter]: Started Sifa with 11 locations of interest [2024-11-14 05:25:33,451 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 05:25:33,451 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 05:25:33,451 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 05:25:33,451 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 05:25:34,073 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 39 for LOIs [2024-11-14 05:25:34,102 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 05:25:35,428 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1798#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (<= ~counter~0 100))' at error location [2024-11-14 05:25:35,428 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 05:25:35,428 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-14 05:25:35,428 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12] total 12 [2024-11-14 05:25:35,428 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [440085690] [2024-11-14 05:25:35,428 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-14 05:25:35,429 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2024-11-14 05:25:35,429 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 05:25:35,432 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2024-11-14 05:25:35,433 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=95, Invalid=555, Unknown=0, NotChecked=0, Total=650 [2024-11-14 05:25:35,433 INFO L87 Difference]: Start difference. First operand 86 states and 92 transitions. Second operand has 12 states, 12 states have (on average 2.0) internal successors, (24), 10 states have internal predecessors, (24), 5 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2024-11-14 05:25:35,730 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 05:25:35,730 INFO L93 Difference]: Finished difference Result 88 states and 93 transitions. [2024-11-14 05:25:35,731 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2024-11-14 05:25:35,731 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 2.0) internal successors, (24), 10 states have internal predecessors, (24), 5 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) Word has length 39 [2024-11-14 05:25:35,731 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 05:25:35,733 INFO L225 Difference]: With dead ends: 88 [2024-11-14 05:25:35,733 INFO L226 Difference]: Without dead ends: 86 [2024-11-14 05:25:35,734 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 94 GetRequests, 65 SyntacticMatches, 4 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 117 ImplicationChecksByTransitivity, 3.8s TimeCoverageRelationStatistics Valid=102, Invalid=600, Unknown=0, NotChecked=0, Total=702 [2024-11-14 05:25:35,735 INFO L432 NwaCegarLoop]: 21 mSDtfsCounter, 3 mSDsluCounter, 156 mSDsCounter, 0 mSdLazyCounter, 149 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 177 SdHoareTripleChecker+Invalid, 151 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 149 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-11-14 05:25:35,735 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 177 Invalid, 151 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 149 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-11-14 05:25:35,736 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 86 states. [2024-11-14 05:25:35,750 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 86 to 86. [2024-11-14 05:25:35,750 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 86 states, 64 states have (on average 1.09375) internal successors, (70), 65 states have internal predecessors, (70), 11 states have call successors, (11), 10 states have call predecessors, (11), 10 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2024-11-14 05:25:35,751 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 86 states to 86 states and 91 transitions. [2024-11-14 05:25:35,751 INFO L78 Accepts]: Start accepts. Automaton has 86 states and 91 transitions. Word has length 39 [2024-11-14 05:25:35,752 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 05:25:35,752 INFO L471 AbstractCegarLoop]: Abstraction has 86 states and 91 transitions. [2024-11-14 05:25:35,752 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 2.0) internal successors, (24), 10 states have internal predecessors, (24), 5 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2024-11-14 05:25:35,752 INFO L276 IsEmpty]: Start isEmpty. Operand 86 states and 91 transitions. [2024-11-14 05:25:35,753 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 48 [2024-11-14 05:25:35,753 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 05:25:35,754 INFO L215 NwaCegarLoop]: trace histogram [6, 6, 6, 6, 5, 5, 5, 5, 1, 1, 1] [2024-11-14 05:25:35,759 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2024-11-14 05:25:35,954 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,7 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 05:25:35,954 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 05:25:35,955 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 05:25:35,955 INFO L85 PathProgramCache]: Analyzing trace with hash 1653188430, now seen corresponding path program 3 times [2024-11-14 05:25:35,955 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 05:25:35,955 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1412119488] [2024-11-14 05:25:35,955 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 05:25:35,955 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 05:25:36,091 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 05:25:36,096 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1706942719] [2024-11-14 05:25:36,099 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-14 05:25:36,099 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 05:25:36,099 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 05:25:36,101 INFO L229 MonitoredProcess]: Starting monitored process 8 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 05:25:36,103 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2024-11-14 05:25:36,798 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-14 05:25:36,798 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-14 05:25:36,800 INFO L255 TraceCheckSpWp]: Trace formula consists of 148 conjuncts, 66 conjuncts are in the unsatisfiable core [2024-11-14 05:25:36,805 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 05:26:32,350 INFO L134 CoverageAnalysis]: Checked inductivity of 105 backedges. 5 proven. 60 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2024-11-14 05:26:32,350 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 05:26:56,697 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 05:26:56,697 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1412119488] [2024-11-14 05:26:56,697 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-14 05:26:56,697 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1706942719] [2024-11-14 05:26:56,697 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1706942719] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 05:26:56,697 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1282741921] [2024-11-14 05:26:56,699 INFO L159 IcfgInterpreter]: Started Sifa with 11 locations of interest [2024-11-14 05:26:56,699 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 05:26:56,699 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 05:26:56,700 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 05:26:56,700 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 05:26:57,133 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 39 for LOIs [2024-11-14 05:26:57,158 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 05:26:59,660 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '2350#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (<= ~counter~0 100))' at error location [2024-11-14 05:26:59,660 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 05:26:59,660 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-14 05:26:59,660 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13] total 13 [2024-11-14 05:26:59,660 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [475908366] [2024-11-14 05:26:59,660 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-14 05:26:59,661 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2024-11-14 05:26:59,661 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 05:26:59,661 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2024-11-14 05:26:59,662 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=168, Invalid=1018, Unknown=4, NotChecked=0, Total=1190 [2024-11-14 05:26:59,662 INFO L87 Difference]: Start difference. First operand 86 states and 91 transitions. Second operand has 13 states, 13 states have (on average 1.8461538461538463) internal successors, (24), 10 states have internal predecessors, (24), 6 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2024-11-14 05:27:04,260 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [0] [2024-11-14 05:27:06,686 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [0] [2024-11-14 05:27:07,194 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 05:27:07,194 INFO L93 Difference]: Finished difference Result 88 states and 92 transitions. [2024-11-14 05:27:07,194 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2024-11-14 05:27:07,195 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 1.8461538461538463) internal successors, (24), 10 states have internal predecessors, (24), 6 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) Word has length 47 [2024-11-14 05:27:07,195 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 05:27:07,196 INFO L225 Difference]: With dead ends: 88 [2024-11-14 05:27:07,196 INFO L226 Difference]: Without dead ends: 86 [2024-11-14 05:27:07,197 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 134 GetRequests, 97 SyntacticMatches, 3 SemanticMatches, 34 ConstructedPredicates, 0 IntricatePredicates, 1 DeprecatedPredicates, 251 ImplicationChecksByTransitivity, 29.9s TimeCoverageRelationStatistics Valid=176, Invalid=1080, Unknown=4, NotChecked=0, Total=1260 [2024-11-14 05:27:07,198 INFO L432 NwaCegarLoop]: 22 mSDtfsCounter, 6 mSDsluCounter, 172 mSDsCounter, 0 mSdLazyCounter, 154 mSolverCounterSat, 11 mSolverCounterUnsat, 2 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 6.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 194 SdHoareTripleChecker+Invalid, 167 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 154 IncrementalHoareTripleChecker+Invalid, 2 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 7.3s IncrementalHoareTripleChecker+Time [2024-11-14 05:27:07,198 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 194 Invalid, 167 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 154 Invalid, 2 Unknown, 0 Unchecked, 7.3s Time] [2024-11-14 05:27:07,199 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 86 states. [2024-11-14 05:27:07,247 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 86 to 86. [2024-11-14 05:27:07,248 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 86 states, 64 states have (on average 1.078125) internal successors, (69), 65 states have internal predecessors, (69), 11 states have call successors, (11), 10 states have call predecessors, (11), 10 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2024-11-14 05:27:07,249 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 86 states to 86 states and 90 transitions. [2024-11-14 05:27:07,249 INFO L78 Accepts]: Start accepts. Automaton has 86 states and 90 transitions. Word has length 47 [2024-11-14 05:27:07,249 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 05:27:07,250 INFO L471 AbstractCegarLoop]: Abstraction has 86 states and 90 transitions. [2024-11-14 05:27:07,250 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 1.8461538461538463) internal successors, (24), 10 states have internal predecessors, (24), 6 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2024-11-14 05:27:07,250 INFO L276 IsEmpty]: Start isEmpty. Operand 86 states and 90 transitions. [2024-11-14 05:27:07,251 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 56 [2024-11-14 05:27:07,251 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 05:27:07,252 INFO L215 NwaCegarLoop]: trace histogram [7, 7, 7, 7, 6, 6, 6, 6, 1, 1, 1] [2024-11-14 05:27:07,271 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2024-11-14 05:27:07,452 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 8 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2024-11-14 05:27:07,452 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 05:27:07,453 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 05:27:07,453 INFO L85 PathProgramCache]: Analyzing trace with hash -594981870, now seen corresponding path program 4 times [2024-11-14 05:27:07,453 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 05:27:07,453 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [512005194] [2024-11-14 05:27:07,453 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 05:27:07,453 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 05:27:07,523 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 05:27:07,525 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [61575648] [2024-11-14 05:27:07,525 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2024-11-14 05:27:07,525 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 05:27:07,526 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 05:27:07,528 INFO L229 MonitoredProcess]: Starting monitored process 9 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 05:27:07,536 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2024-11-14 05:27:07,934 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 05:27:07,935 INFO L255 TraceCheckSpWp]: Trace formula consists of 168 conjuncts, 57 conjuncts are in the unsatisfiable core [2024-11-14 05:27:07,941 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 05:27:19,377 INFO L134 CoverageAnalysis]: Checked inductivity of 150 backedges. 33 proven. 84 refuted. 0 times theorem prover too weak. 33 trivial. 0 not checked. [2024-11-14 05:27:19,377 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 05:27:29,595 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 05:27:29,595 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [512005194] [2024-11-14 05:27:29,595 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-14 05:27:29,595 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [61575648] [2024-11-14 05:27:29,595 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [61575648] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 05:27:29,595 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [879831756] [2024-11-14 05:27:29,597 INFO L159 IcfgInterpreter]: Started Sifa with 11 locations of interest [2024-11-14 05:27:29,598 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 05:27:29,598 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 05:27:29,598 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 05:27:29,598 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 05:27:30,115 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 39 for LOIs [2024-11-14 05:27:30,151 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 05:27:32,901 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '2851#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (<= ~counter~0 100))' at error location [2024-11-14 05:27:32,901 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 05:27:32,901 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-14 05:27:32,901 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15] total 15 [2024-11-14 05:27:32,901 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2026369896] [2024-11-14 05:27:32,901 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-14 05:27:32,902 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2024-11-14 05:27:32,902 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 05:27:32,903 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2024-11-14 05:27:32,903 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=122, Invalid=808, Unknown=0, NotChecked=0, Total=930 [2024-11-14 05:27:32,903 INFO L87 Difference]: Start difference. First operand 86 states and 90 transitions. Second operand has 15 states, 15 states have (on average 2.0) internal successors, (30), 12 states have internal predecessors, (30), 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 05:27:34,867 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 05:27:34,867 INFO L93 Difference]: Finished difference Result 88 states and 91 transitions. [2024-11-14 05:27:34,868 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2024-11-14 05:27:34,868 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 15 states have (on average 2.0) internal successors, (30), 12 states have internal predecessors, (30), 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) Word has length 55 [2024-11-14 05:27:34,868 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 05:27:34,869 INFO L225 Difference]: With dead ends: 88 [2024-11-14 05:27:34,869 INFO L226 Difference]: Without dead ends: 86 [2024-11-14 05:27:34,870 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 126 GetRequests, 96 SyntacticMatches, 0 SemanticMatches, 30 ConstructedPredicates, 0 IntricatePredicates, 1 DeprecatedPredicates, 170 ImplicationChecksByTransitivity, 11.8s TimeCoverageRelationStatistics Valid=130, Invalid=862, Unknown=0, NotChecked=0, Total=992 [2024-11-14 05:27:34,871 INFO L432 NwaCegarLoop]: 27 mSDtfsCounter, 3 mSDsluCounter, 306 mSDsCounter, 0 mSdLazyCounter, 266 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 333 SdHoareTripleChecker+Invalid, 267 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 266 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.8s IncrementalHoareTripleChecker+Time [2024-11-14 05:27:34,871 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 333 Invalid, 267 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 266 Invalid, 0 Unknown, 0 Unchecked, 1.8s Time] [2024-11-14 05:27:34,872 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 86 states. [2024-11-14 05:27:34,915 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 86 to 86. [2024-11-14 05:27:34,915 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 86 states, 64 states have (on average 1.0625) internal successors, (68), 65 states have internal predecessors, (68), 11 states have call successors, (11), 10 states have call predecessors, (11), 10 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2024-11-14 05:27:34,916 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 86 states to 86 states and 89 transitions. [2024-11-14 05:27:34,916 INFO L78 Accepts]: Start accepts. Automaton has 86 states and 89 transitions. Word has length 55 [2024-11-14 05:27:34,917 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 05:27:34,917 INFO L471 AbstractCegarLoop]: Abstraction has 86 states and 89 transitions. [2024-11-14 05:27:34,917 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 2.0) internal successors, (30), 12 states have internal predecessors, (30), 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 05:27:34,917 INFO L276 IsEmpty]: Start isEmpty. Operand 86 states and 89 transitions. [2024-11-14 05:27:34,918 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 64 [2024-11-14 05:27:34,918 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 05:27:34,918 INFO L215 NwaCegarLoop]: trace histogram [8, 8, 8, 8, 7, 7, 7, 7, 1, 1, 1] [2024-11-14 05:27:34,938 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2024-11-14 05:27:35,119 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2024-11-14 05:27:35,119 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 05:27:35,119 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 05:27:35,119 INFO L85 PathProgramCache]: Analyzing trace with hash 1124723926, now seen corresponding path program 5 times [2024-11-14 05:27:35,119 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 05:27:35,119 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [184365426] [2024-11-14 05:27:35,119 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 05:27:35,120 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 05:27:35,227 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 05:27:35,229 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [410770707] [2024-11-14 05:27:35,230 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-14 05:27:35,230 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 05:27:35,230 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 05:27:35,232 INFO L229 MonitoredProcess]: Starting monitored process 10 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 05:27:35,236 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2024-11-14 05:27:35,603 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 8 check-sat command(s) [2024-11-14 05:27:35,603 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-14 05:27:35,606 INFO L255 TraceCheckSpWp]: Trace formula consists of 188 conjuncts, 53 conjuncts are in the unsatisfiable core [2024-11-14 05:27:35,612 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 05:27:40,865 INFO L134 CoverageAnalysis]: Checked inductivity of 203 backedges. 42 proven. 107 refuted. 0 times theorem prover too weak. 54 trivial. 0 not checked. [2024-11-14 05:27:40,865 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 05:27:51,367 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 05:27:51,367 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [184365426] [2024-11-14 05:27:51,367 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-14 05:27:51,367 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [410770707] [2024-11-14 05:27:51,367 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [410770707] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 05:27:51,367 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [32993803] [2024-11-14 05:27:51,369 INFO L159 IcfgInterpreter]: Started Sifa with 11 locations of interest [2024-11-14 05:27:51,369 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 05:27:51,369 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 05:27:51,369 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 05:27:51,370 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 05:27:51,819 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 39 for LOIs [2024-11-14 05:27:51,853 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 05:27:55,032 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '3400#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (<= ~counter~0 100))' at error location [2024-11-14 05:27:55,032 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 05:27:55,032 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-14 05:27:55,033 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15] total 15 [2024-11-14 05:27:55,033 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2015859274] [2024-11-14 05:27:55,033 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-14 05:27:55,033 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2024-11-14 05:27:55,033 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 05:27:55,034 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2024-11-14 05:27:55,034 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=119, Invalid=751, Unknown=0, NotChecked=0, Total=870 [2024-11-14 05:27:55,034 INFO L87 Difference]: Start difference. First operand 86 states and 89 transitions. Second operand has 15 states, 15 states have (on average 2.2) internal successors, (33), 13 states have internal predecessors, (33), 8 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2024-11-14 05:27:56,637 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 05:27:56,637 INFO L93 Difference]: Finished difference Result 88 states and 90 transitions. [2024-11-14 05:27:56,638 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2024-11-14 05:27:56,638 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 15 states have (on average 2.2) internal successors, (33), 13 states have internal predecessors, (33), 8 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) Word has length 63 [2024-11-14 05:27:56,639 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 05:27:56,640 INFO L225 Difference]: With dead ends: 88 [2024-11-14 05:27:56,640 INFO L226 Difference]: Without dead ends: 86 [2024-11-14 05:27:56,640 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 150 GetRequests, 118 SyntacticMatches, 3 SemanticMatches, 29 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 129 ImplicationChecksByTransitivity, 9.6s TimeCoverageRelationStatistics Valid=126, Invalid=804, Unknown=0, NotChecked=0, Total=930 [2024-11-14 05:27:56,641 INFO L432 NwaCegarLoop]: 30 mSDtfsCounter, 3 mSDsluCounter, 312 mSDsCounter, 0 mSdLazyCounter, 277 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 342 SdHoareTripleChecker+Invalid, 278 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 277 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.4s IncrementalHoareTripleChecker+Time [2024-11-14 05:27:56,641 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 342 Invalid, 278 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 277 Invalid, 0 Unknown, 0 Unchecked, 1.4s Time] [2024-11-14 05:27:56,642 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 86 states. [2024-11-14 05:27:56,684 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 86 to 86. [2024-11-14 05:27:56,684 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 86 states, 64 states have (on average 1.046875) internal successors, (67), 65 states have internal predecessors, (67), 11 states have call successors, (11), 10 states have call predecessors, (11), 10 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2024-11-14 05:27:56,685 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 86 states to 86 states and 88 transitions. [2024-11-14 05:27:56,685 INFO L78 Accepts]: Start accepts. Automaton has 86 states and 88 transitions. Word has length 63 [2024-11-14 05:27:56,686 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 05:27:56,686 INFO L471 AbstractCegarLoop]: Abstraction has 86 states and 88 transitions. [2024-11-14 05:27:56,686 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 2.2) internal successors, (33), 13 states have internal predecessors, (33), 8 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2024-11-14 05:27:56,686 INFO L276 IsEmpty]: Start isEmpty. Operand 86 states and 88 transitions. [2024-11-14 05:27:56,687 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 72 [2024-11-14 05:27:56,687 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 05:27:56,687 INFO L215 NwaCegarLoop]: trace histogram [9, 9, 9, 9, 8, 8, 8, 8, 1, 1, 1] [2024-11-14 05:27:56,704 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2024-11-14 05:27:56,891 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable11 [2024-11-14 05:27:56,891 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 05:27:56,891 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 05:27:56,892 INFO L85 PathProgramCache]: Analyzing trace with hash 1934592410, now seen corresponding path program 6 times [2024-11-14 05:27:56,892 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 05:27:56,892 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1145007736] [2024-11-14 05:27:56,892 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 05:27:56,892 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 05:27:56,975 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 05:27:56,978 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [319231948] [2024-11-14 05:27:56,978 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-14 05:27:56,978 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 05:27:56,978 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 05:27:56,981 INFO L229 MonitoredProcess]: Starting monitored process 11 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 05:27:56,983 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2024-11-14 05:27:57,811 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-14 05:27:57,811 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-14 05:27:57,815 INFO L255 TraceCheckSpWp]: Trace formula consists of 208 conjuncts, 65 conjuncts are in the unsatisfiable core [2024-11-14 05:27:57,822 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 05:28:11,745 WARN L286 SmtUtils]: Spent 5.79s on a formula simplification that was a NOOP. DAG size: 73 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-14 05:28:23,826 WARN L286 SmtUtils]: Spent 5.80s on a formula simplification that was a NOOP. DAG size: 110 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-14 05:29:07,895 WARN L286 SmtUtils]: Spent 13.60s on a formula simplification that was a NOOP. DAG size: 218 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-14 05:29:25,330 INFO L134 CoverageAnalysis]: Checked inductivity of 264 backedges. 55 proven. 142 refuted. 0 times theorem prover too weak. 67 trivial. 0 not checked. [2024-11-14 05:29:25,330 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 05:29:36,163 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 05:29:36,163 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1145007736] [2024-11-14 05:29:36,164 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-14 05:29:36,164 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [319231948] [2024-11-14 05:29:36,164 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [319231948] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 05:29:36,164 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [818660750] [2024-11-14 05:29:36,165 INFO L159 IcfgInterpreter]: Started Sifa with 11 locations of interest [2024-11-14 05:29:36,165 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 05:29:36,165 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 05:29:36,166 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 05:29:36,166 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 05:29:36,571 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 39 for LOIs [2024-11-14 05:29:36,604 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 05:29:40,030 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '3950#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (<= ~counter~0 100))' at error location [2024-11-14 05:29:40,030 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 05:29:40,030 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-14 05:29:40,030 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17] total 17 [2024-11-14 05:29:40,030 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [687771516] [2024-11-14 05:29:40,030 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-14 05:29:40,031 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2024-11-14 05:29:40,031 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 05:29:40,031 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2024-11-14 05:29:40,032 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=123, Invalid=868, Unknown=1, NotChecked=0, Total=992 [2024-11-14 05:29:40,032 INFO L87 Difference]: Start difference. First operand 86 states and 88 transitions. Second operand has 17 states, 17 states have (on average 2.1176470588235294) internal successors, (36), 14 states have internal predecessors, (36), 9 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2024-11-14 05:29:49,541 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.86s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [0] [2024-11-14 05:29:52,397 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.65s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [0] [2024-11-14 05:29:54,089 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.69s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [0] [2024-11-14 05:29:56,176 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [0] [2024-11-14 05:29:58,616 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [0] [2024-11-14 05:30:00,051 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.43s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [0] [2024-11-14 05:30:00,124 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 05:30:00,124 INFO L93 Difference]: Finished difference Result 88 states and 89 transitions. [2024-11-14 05:30:00,125 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2024-11-14 05:30:00,125 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 17 states have (on average 2.1176470588235294) internal successors, (36), 14 states have internal predecessors, (36), 9 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) Word has length 71 [2024-11-14 05:30:00,125 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 05:30:00,126 INFO L225 Difference]: With dead ends: 88 [2024-11-14 05:30:00,126 INFO L226 Difference]: Without dead ends: 86 [2024-11-14 05:30:00,127 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 158 GetRequests, 126 SyntacticMatches, 1 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 155 ImplicationChecksByTransitivity, 46.4s TimeCoverageRelationStatistics Valid=131, Invalid=924, Unknown=1, NotChecked=0, Total=1056 [2024-11-14 05:30:00,127 INFO L432 NwaCegarLoop]: 33 mSDtfsCounter, 4 mSDsluCounter, 358 mSDsCounter, 0 mSdLazyCounter, 297 mSolverCounterSat, 2 mSolverCounterUnsat, 2 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 19.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 391 SdHoareTripleChecker+Invalid, 301 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 297 IncrementalHoareTripleChecker+Invalid, 2 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 19.9s IncrementalHoareTripleChecker+Time [2024-11-14 05:30:00,132 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [5 Valid, 391 Invalid, 301 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 297 Invalid, 2 Unknown, 0 Unchecked, 19.9s Time] [2024-11-14 05:30:00,132 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 86 states. [2024-11-14 05:30:00,190 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 86 to 86. [2024-11-14 05:30:00,190 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 86 states, 64 states have (on average 1.03125) internal successors, (66), 65 states have internal predecessors, (66), 11 states have call successors, (11), 10 states have call predecessors, (11), 10 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2024-11-14 05:30:00,191 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 86 states to 86 states and 87 transitions. [2024-11-14 05:30:00,191 INFO L78 Accepts]: Start accepts. Automaton has 86 states and 87 transitions. Word has length 71 [2024-11-14 05:30:00,192 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 05:30:00,192 INFO L471 AbstractCegarLoop]: Abstraction has 86 states and 87 transitions. [2024-11-14 05:30:00,192 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 17 states have (on average 2.1176470588235294) internal successors, (36), 14 states have internal predecessors, (36), 9 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2024-11-14 05:30:00,192 INFO L276 IsEmpty]: Start isEmpty. Operand 86 states and 87 transitions. [2024-11-14 05:30:00,193 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 80 [2024-11-14 05:30:00,193 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 05:30:00,193 INFO L215 NwaCegarLoop]: trace histogram [10, 10, 10, 10, 9, 9, 9, 9, 1, 1, 1] [2024-11-14 05:30:00,214 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Ended with exit code 0 [2024-11-14 05:30:00,393 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable12,11 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 05:30:00,394 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 05:30:00,394 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 05:30:00,395 INFO L85 PathProgramCache]: Analyzing trace with hash -962715042, now seen corresponding path program 7 times [2024-11-14 05:30:00,395 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 05:30:00,395 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1910045650] [2024-11-14 05:30:00,395 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 05:30:00,395 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 05:30:00,509 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 05:30:00,511 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1111899502] [2024-11-14 05:30:00,511 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2024-11-14 05:30:00,511 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 05:30:00,511 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 05:30:00,513 INFO L229 MonitoredProcess]: Starting monitored process 12 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 05:30:00,517 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2024-11-14 05:30:01,870 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 05:30:01,873 INFO L255 TraceCheckSpWp]: Trace formula consists of 228 conjuncts, 68 conjuncts are in the unsatisfiable core [2024-11-14 05:30:01,877 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 05:30:11,153 INFO L134 CoverageAnalysis]: Checked inductivity of 333 backedges. 69 proven. 174 refuted. 0 times theorem prover too weak. 90 trivial. 0 not checked. [2024-11-14 05:30:11,153 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 05:30:26,582 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 05:30:26,582 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1910045650] [2024-11-14 05:30:26,582 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-14 05:30:26,582 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1111899502] [2024-11-14 05:30:26,582 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1111899502] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 05:30:26,582 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1719800343] [2024-11-14 05:30:26,584 INFO L159 IcfgInterpreter]: Started Sifa with 11 locations of interest [2024-11-14 05:30:26,584 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 05:30:26,584 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 05:30:26,584 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 05:30:26,584 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 05:30:26,966 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 39 for LOIs [2024-11-14 05:30:27,000 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 05:30:30,986 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '4550#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (<= ~counter~0 100))' at error location [2024-11-14 05:30:30,986 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 05:30:30,986 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-14 05:30:30,986 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17] total 17 [2024-11-14 05:30:30,986 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [72573739] [2024-11-14 05:30:30,986 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-14 05:30:30,986 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2024-11-14 05:30:30,986 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 05:30:30,987 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2024-11-14 05:30:30,987 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=157, Invalid=1032, Unknown=1, NotChecked=0, Total=1190 [2024-11-14 05:30:30,988 INFO L87 Difference]: Start difference. First operand 86 states and 87 transitions. Second operand has 17 states, 17 states have (on average 2.2941176470588234) internal successors, (39), 15 states have internal predecessors, (39), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2024-11-14 05:30:40,991 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 05:30:40,991 INFO L93 Difference]: Finished difference Result 94 states and 95 transitions. [2024-11-14 05:30:40,992 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2024-11-14 05:30:40,992 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 17 states have (on average 2.2941176470588234) internal successors, (39), 15 states have internal predecessors, (39), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) Word has length 79 [2024-11-14 05:30:40,992 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 05:30:40,993 INFO L225 Difference]: With dead ends: 94 [2024-11-14 05:30:40,993 INFO L226 Difference]: Without dead ends: 92 [2024-11-14 05:30:40,994 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 191 GetRequests, 147 SyntacticMatches, 1 SemanticMatches, 43 ConstructedPredicates, 0 IntricatePredicates, 1 DeprecatedPredicates, 317 ImplicationChecksByTransitivity, 22.8s TimeCoverageRelationStatistics Valid=257, Invalid=1722, Unknown=1, NotChecked=0, Total=1980 [2024-11-14 05:30:40,995 INFO L432 NwaCegarLoop]: 33 mSDtfsCounter, 5 mSDsluCounter, 422 mSDsCounter, 0 mSdLazyCounter, 350 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 455 SdHoareTripleChecker+Invalid, 354 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 350 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 4.3s IncrementalHoareTripleChecker+Time [2024-11-14 05:30:40,997 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 455 Invalid, 354 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 350 Invalid, 0 Unknown, 0 Unchecked, 4.3s Time] [2024-11-14 05:30:40,998 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 92 states. [2024-11-14 05:30:41,074 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 92 to 91. [2024-11-14 05:30:41,074 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 91 states, 67 states have (on average 1.0298507462686568) internal successors, (69), 69 states have internal predecessors, (69), 12 states have call successors, (12), 11 states have call predecessors, (12), 11 states have return successors, (11), 10 states have call predecessors, (11), 11 states have call successors, (11) [2024-11-14 05:30:41,075 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 91 states to 91 states and 92 transitions. [2024-11-14 05:30:41,076 INFO L78 Accepts]: Start accepts. Automaton has 91 states and 92 transitions. Word has length 79 [2024-11-14 05:30:41,076 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 05:30:41,076 INFO L471 AbstractCegarLoop]: Abstraction has 91 states and 92 transitions. [2024-11-14 05:30:41,076 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 17 states have (on average 2.2941176470588234) internal successors, (39), 15 states have internal predecessors, (39), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2024-11-14 05:30:41,077 INFO L276 IsEmpty]: Start isEmpty. Operand 91 states and 92 transitions. [2024-11-14 05:30:41,077 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 88 [2024-11-14 05:30:41,077 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 05:30:41,078 INFO L215 NwaCegarLoop]: trace histogram [11, 11, 10, 10, 10, 10, 10, 10, 1, 1, 1, 1, 1] [2024-11-14 05:30:41,102 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Ended with exit code 0 [2024-11-14 05:30:41,278 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable13,12 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 05:30:41,278 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 05:30:41,279 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 05:30:41,279 INFO L85 PathProgramCache]: Analyzing trace with hash 303984862, now seen corresponding path program 3 times [2024-11-14 05:30:41,279 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 05:30:41,279 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1225337322] [2024-11-14 05:30:41,279 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 05:30:41,279 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 05:30:41,332 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 05:30:42,649 INFO L134 CoverageAnalysis]: Checked inductivity of 400 backedges. 20 proven. 200 refuted. 0 times theorem prover too weak. 180 trivial. 0 not checked. [2024-11-14 05:30:42,650 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 05:30:42,650 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1225337322] [2024-11-14 05:30:42,650 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1225337322] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 05:30:42,650 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1697367950] [2024-11-14 05:30:42,650 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-14 05:30:42,650 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 05:30:42,650 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 05:30:42,655 INFO L229 MonitoredProcess]: Starting monitored process 13 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 05:30:42,656 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2024-11-14 05:30:42,837 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-14 05:30:42,837 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-14 05:30:42,839 INFO L255 TraceCheckSpWp]: Trace formula consists of 248 conjuncts, 23 conjuncts are in the unsatisfiable core [2024-11-14 05:30:42,840 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 05:30:43,462 INFO L134 CoverageAnalysis]: Checked inductivity of 400 backedges. 20 proven. 380 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 05:30:43,462 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 05:30:45,337 INFO L134 CoverageAnalysis]: Checked inductivity of 400 backedges. 20 proven. 200 refuted. 0 times theorem prover too weak. 180 trivial. 0 not checked. [2024-11-14 05:30:45,337 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1697367950] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 05:30:45,338 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [347916720] [2024-11-14 05:30:45,339 INFO L159 IcfgInterpreter]: Started Sifa with 12 locations of interest [2024-11-14 05:30:45,339 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 05:30:45,339 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 05:30:45,340 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 05:30:45,340 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 05:30:45,734 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 63 for LOIs [2024-11-14 05:30:45,810 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 05:30:49,006 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '5396#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0))' at error location [2024-11-14 05:30:49,007 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 05:30:49,007 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-14 05:30:49,007 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 13, 14] total 26 [2024-11-14 05:30:49,007 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1756986807] [2024-11-14 05:30:49,007 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-14 05:30:49,008 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 26 states [2024-11-14 05:30:49,008 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 05:30:49,009 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2024-11-14 05:30:49,010 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=312, Invalid=948, Unknown=0, NotChecked=0, Total=1260 [2024-11-14 05:30:49,011 INFO L87 Difference]: Start difference. First operand 91 states and 92 transitions. Second operand has 26 states, 26 states have (on average 3.923076923076923) internal successors, (102), 26 states have internal predecessors, (102), 21 states have call successors, (31), 12 states have call predecessors, (31), 11 states have return successors, (30), 20 states have call predecessors, (30), 20 states have call successors, (30) [2024-11-14 05:30:51,935 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 05:30:51,935 INFO L93 Difference]: Finished difference Result 211 states and 223 transitions. [2024-11-14 05:30:51,935 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 46 states. [2024-11-14 05:30:51,935 INFO L78 Accepts]: Start accepts. Automaton has has 26 states, 26 states have (on average 3.923076923076923) internal successors, (102), 26 states have internal predecessors, (102), 21 states have call successors, (31), 12 states have call predecessors, (31), 11 states have return successors, (30), 20 states have call predecessors, (30), 20 states have call successors, (30) Word has length 87 [2024-11-14 05:30:51,936 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 05:30:51,937 INFO L225 Difference]: With dead ends: 211 [2024-11-14 05:30:51,937 INFO L226 Difference]: Without dead ends: 204 [2024-11-14 05:30:51,938 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 294 GetRequests, 239 SyntacticMatches, 0 SemanticMatches, 55 ConstructedPredicates, 0 IntricatePredicates, 1 DeprecatedPredicates, 775 ImplicationChecksByTransitivity, 7.3s TimeCoverageRelationStatistics Valid=827, Invalid=2365, Unknown=0, NotChecked=0, Total=3192 [2024-11-14 05:30:51,939 INFO L432 NwaCegarLoop]: 9 mSDtfsCounter, 109 mSDsluCounter, 122 mSDsCounter, 0 mSdLazyCounter, 122 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 109 SdHoareTripleChecker+Valid, 131 SdHoareTripleChecker+Invalid, 131 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 122 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.7s IncrementalHoareTripleChecker+Time [2024-11-14 05:30:51,939 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [109 Valid, 131 Invalid, 131 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 122 Invalid, 0 Unknown, 0 Unchecked, 0.7s Time] [2024-11-14 05:30:51,940 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 204 states. [2024-11-14 05:30:52,000 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 204 to 182. [2024-11-14 05:30:52,000 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 182 states, 136 states have (on average 1.0955882352941178) internal successors, (149), 137 states have internal predecessors, (149), 23 states have call successors, (23), 22 states have call predecessors, (23), 22 states have return successors, (22), 22 states have call predecessors, (22), 22 states have call successors, (22) [2024-11-14 05:30:52,002 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 182 states to 182 states and 194 transitions. [2024-11-14 05:30:52,002 INFO L78 Accepts]: Start accepts. Automaton has 182 states and 194 transitions. Word has length 87 [2024-11-14 05:30:52,002 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 05:30:52,002 INFO L471 AbstractCegarLoop]: Abstraction has 182 states and 194 transitions. [2024-11-14 05:30:52,003 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 26 states, 26 states have (on average 3.923076923076923) internal successors, (102), 26 states have internal predecessors, (102), 21 states have call successors, (31), 12 states have call predecessors, (31), 11 states have return successors, (30), 20 states have call predecessors, (30), 20 states have call successors, (30) [2024-11-14 05:30:52,003 INFO L276 IsEmpty]: Start isEmpty. Operand 182 states and 194 transitions. [2024-11-14 05:30:52,003 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 88 [2024-11-14 05:30:52,003 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 05:30:52,003 INFO L215 NwaCegarLoop]: trace histogram [11, 11, 11, 11, 10, 10, 10, 10, 1, 1, 1] [2024-11-14 05:30:52,019 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Ended with exit code 0 [2024-11-14 05:30:52,204 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable14,13 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 05:30:52,204 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 05:30:52,204 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 05:30:52,204 INFO L85 PathProgramCache]: Analyzing trace with hash 305772322, now seen corresponding path program 8 times [2024-11-14 05:30:52,204 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 05:30:52,204 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1454598728] [2024-11-14 05:30:52,204 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 05:30:52,205 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 05:30:52,566 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 05:30:52,568 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [356120819] [2024-11-14 05:30:52,570 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-14 05:30:52,571 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 05:30:52,571 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 05:30:52,573 INFO L229 MonitoredProcess]: Starting monitored process 14 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 05:30:52,577 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2024-11-14 05:30:53,562 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 11 check-sat command(s) [2024-11-14 05:30:53,563 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-14 05:30:53,565 INFO L255 TraceCheckSpWp]: Trace formula consists of 248 conjuncts, 58 conjuncts are in the unsatisfiable core [2024-11-14 05:30:53,570 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 05:31:01,376 INFO L134 CoverageAnalysis]: Checked inductivity of 410 backedges. 80 proven. 213 refuted. 0 times theorem prover too weak. 117 trivial. 0 not checked. [2024-11-14 05:31:01,376 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 05:31:13,190 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 05:31:13,190 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1454598728] [2024-11-14 05:31:13,190 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-14 05:31:13,190 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [356120819] [2024-11-14 05:31:13,190 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [356120819] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 05:31:13,190 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [491411631] [2024-11-14 05:31:13,192 INFO L159 IcfgInterpreter]: Started Sifa with 11 locations of interest [2024-11-14 05:31:13,192 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 05:31:13,192 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 05:31:13,192 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 05:31:13,193 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 05:31:13,570 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 39 for LOIs [2024-11-14 05:31:13,608 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 05:31:17,998 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '6354#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (<= ~counter~0 100))' at error location [2024-11-14 05:31:17,998 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 05:31:17,998 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-14 05:31:17,998 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18] total 18 [2024-11-14 05:31:17,999 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [697965260] [2024-11-14 05:31:17,999 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-14 05:31:17,999 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2024-11-14 05:31:17,999 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 05:31:18,000 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2024-11-14 05:31:18,000 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=152, Invalid=839, Unknown=1, NotChecked=0, Total=992 [2024-11-14 05:31:18,000 INFO L87 Difference]: Start difference. First operand 182 states and 194 transitions. Second operand has 18 states, 18 states have (on average 2.3333333333333335) internal successors, (42), 16 states have internal predecessors, (42), 11 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2024-11-14 05:31:43,349 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 05:31:43,350 INFO L93 Difference]: Finished difference Result 184 states and 195 transitions. [2024-11-14 05:31:43,350 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2024-11-14 05:31:43,350 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 18 states have (on average 2.3333333333333335) internal successors, (42), 16 states have internal predecessors, (42), 11 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) Word has length 87 [2024-11-14 05:31:43,350 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 05:31:43,351 INFO L225 Difference]: With dead ends: 184 [2024-11-14 05:31:43,351 INFO L226 Difference]: Without dead ends: 182 [2024-11-14 05:31:43,352 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 200 GetRequests, 156 SyntacticMatches, 3 SemanticMatches, 41 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 388 ImplicationChecksByTransitivity, 40.4s TimeCoverageRelationStatistics Valid=316, Invalid=1488, Unknown=2, NotChecked=0, Total=1806 [2024-11-14 05:31:43,353 INFO L432 NwaCegarLoop]: 19 mSDtfsCounter, 19 mSDsluCounter, 176 mSDsCounter, 0 mSdLazyCounter, 145 mSolverCounterSat, 18 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 20 SdHoareTripleChecker+Valid, 195 SdHoareTripleChecker+Invalid, 163 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 18 IncrementalHoareTripleChecker+Valid, 145 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.2s IncrementalHoareTripleChecker+Time [2024-11-14 05:31:43,353 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [20 Valid, 195 Invalid, 163 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [18 Valid, 145 Invalid, 0 Unknown, 0 Unchecked, 2.2s Time] [2024-11-14 05:31:43,353 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 182 states. [2024-11-14 05:31:43,415 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 182 to 182. [2024-11-14 05:31:43,416 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 182 states, 136 states have (on average 1.088235294117647) internal successors, (148), 137 states have internal predecessors, (148), 23 states have call successors, (23), 22 states have call predecessors, (23), 22 states have return successors, (22), 22 states have call predecessors, (22), 22 states have call successors, (22) [2024-11-14 05:31:43,417 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 182 states to 182 states and 193 transitions. [2024-11-14 05:31:43,417 INFO L78 Accepts]: Start accepts. Automaton has 182 states and 193 transitions. Word has length 87 [2024-11-14 05:31:43,418 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 05:31:43,418 INFO L471 AbstractCegarLoop]: Abstraction has 182 states and 193 transitions. [2024-11-14 05:31:43,418 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 18 states, 18 states have (on average 2.3333333333333335) internal successors, (42), 16 states have internal predecessors, (42), 11 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2024-11-14 05:31:43,418 INFO L276 IsEmpty]: Start isEmpty. Operand 182 states and 193 transitions. [2024-11-14 05:31:43,419 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 96 [2024-11-14 05:31:43,419 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 05:31:43,419 INFO L215 NwaCegarLoop]: trace histogram [12, 12, 12, 12, 11, 11, 11, 11, 1, 1, 1] [2024-11-14 05:31:43,434 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Forceful destruction successful, exit code 0 [2024-11-14 05:31:43,619 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable15 [2024-11-14 05:31:43,619 INFO L396 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 05:31:43,620 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 05:31:43,620 INFO L85 PathProgramCache]: Analyzing trace with hash -1486469146, now seen corresponding path program 9 times [2024-11-14 05:31:43,620 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 05:31:43,620 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [960742762] [2024-11-14 05:31:43,620 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 05:31:43,620 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 05:31:43,853 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 05:31:43,856 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [108098218] [2024-11-14 05:31:43,856 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-14 05:31:43,856 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 05:31:43,856 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 05:31:43,858 INFO L229 MonitoredProcess]: Starting monitored process 15 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 05:31:43,861 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2024-11-14 05:31:46,595 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-14 05:31:46,595 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-14 05:31:46,598 INFO L255 TraceCheckSpWp]: Trace formula consists of 268 conjuncts, 72 conjuncts are in the unsatisfiable core [2024-11-14 05:31:46,603 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 05:31:56,017 INFO L134 CoverageAnalysis]: Checked inductivity of 495 backedges. 91 proven. 256 refuted. 0 times theorem prover too weak. 148 trivial. 0 not checked. [2024-11-14 05:31:56,017 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 05:32:04,474 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 05:32:04,474 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [960742762] [2024-11-14 05:32:04,474 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-14 05:32:04,474 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [108098218] [2024-11-14 05:32:04,474 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [108098218] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 05:32:04,474 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1003636245] [2024-11-14 05:32:04,476 INFO L159 IcfgInterpreter]: Started Sifa with 11 locations of interest [2024-11-14 05:32:04,476 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 05:32:04,476 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 05:32:04,476 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 05:32:04,476 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 05:32:04,837 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 39 for LOIs [2024-11-14 05:32:04,867 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 05:32:09,016 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '7285#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (<= ~counter~0 100))' at error location [2024-11-14 05:32:09,016 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 05:32:09,017 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-14 05:32:09,017 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19] total 19 [2024-11-14 05:32:09,017 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1498102303] [2024-11-14 05:32:09,017 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-14 05:32:09,017 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2024-11-14 05:32:09,017 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 05:32:09,018 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2024-11-14 05:32:09,018 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=144, Invalid=978, Unknown=0, NotChecked=0, Total=1122 [2024-11-14 05:32:09,018 INFO L87 Difference]: Start difference. First operand 182 states and 193 transitions. Second operand has 19 states, 19 states have (on average 2.3684210526315788) internal successors, (45), 17 states have internal predecessors, (45), 12 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2024-11-14 05:32:26,618 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 05:32:26,618 INFO L93 Difference]: Finished difference Result 184 states and 194 transitions. [2024-11-14 05:32:26,618 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2024-11-14 05:32:26,619 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 19 states have (on average 2.3684210526315788) internal successors, (45), 17 states have internal predecessors, (45), 12 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) Word has length 95 [2024-11-14 05:32:26,619 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 05:32:26,620 INFO L225 Difference]: With dead ends: 184 [2024-11-14 05:32:26,620 INFO L226 Difference]: Without dead ends: 182 [2024-11-14 05:32:26,621 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 217 GetRequests, 170 SyntacticMatches, 3 SemanticMatches, 44 ConstructedPredicates, 0 IntricatePredicates, 1 DeprecatedPredicates, 363 ImplicationChecksByTransitivity, 25.2s TimeCoverageRelationStatistics Valid=267, Invalid=1803, Unknown=0, NotChecked=0, Total=2070 [2024-11-14 05:32:26,623 INFO L432 NwaCegarLoop]: 33 mSDtfsCounter, 9 mSDsluCounter, 400 mSDsCounter, 0 mSdLazyCounter, 325 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 5.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 433 SdHoareTripleChecker+Invalid, 333 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 325 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 5.7s IncrementalHoareTripleChecker+Time [2024-11-14 05:32:26,623 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 433 Invalid, 333 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 325 Invalid, 0 Unknown, 0 Unchecked, 5.7s Time] [2024-11-14 05:32:26,624 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 182 states. [2024-11-14 05:32:26,687 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 182 to 182. [2024-11-14 05:32:26,687 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 182 states, 136 states have (on average 1.0808823529411764) internal successors, (147), 137 states have internal predecessors, (147), 23 states have call successors, (23), 22 states have call predecessors, (23), 22 states have return successors, (22), 22 states have call predecessors, (22), 22 states have call successors, (22) [2024-11-14 05:32:26,688 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 182 states to 182 states and 192 transitions. [2024-11-14 05:32:26,689 INFO L78 Accepts]: Start accepts. Automaton has 182 states and 192 transitions. Word has length 95 [2024-11-14 05:32:26,689 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 05:32:26,689 INFO L471 AbstractCegarLoop]: Abstraction has 182 states and 192 transitions. [2024-11-14 05:32:26,689 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 19 states have (on average 2.3684210526315788) internal successors, (45), 17 states have internal predecessors, (45), 12 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2024-11-14 05:32:26,689 INFO L276 IsEmpty]: Start isEmpty. Operand 182 states and 192 transitions. [2024-11-14 05:32:26,690 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 104 [2024-11-14 05:32:26,690 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 05:32:26,691 INFO L215 NwaCegarLoop]: trace histogram [13, 13, 13, 13, 12, 12, 12, 12, 1, 1, 1] [2024-11-14 05:32:26,710 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Ended with exit code 0 [2024-11-14 05:32:26,891 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 15 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable16 [2024-11-14 05:32:26,891 INFO L396 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 05:32:26,892 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 05:32:26,892 INFO L85 PathProgramCache]: Analyzing trace with hash 1399313578, now seen corresponding path program 10 times [2024-11-14 05:32:26,892 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 05:32:26,892 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2081967399] [2024-11-14 05:32:26,892 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 05:32:26,892 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 05:32:27,079 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 05:32:27,086 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [659354735] [2024-11-14 05:32:27,087 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2024-11-14 05:32:27,087 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 05:32:27,087 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 05:32:27,089 INFO L229 MonitoredProcess]: Starting monitored process 16 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 05:32:27,092 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2024-11-14 05:32:27,728 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 05:32:27,730 INFO L255 TraceCheckSpWp]: Trace formula consists of 288 conjuncts, 62 conjuncts are in the unsatisfiable core [2024-11-14 05:32:27,735 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 05:32:35,638 INFO L134 CoverageAnalysis]: Checked inductivity of 588 backedges. 56 proven. 301 refuted. 0 times theorem prover too weak. 231 trivial. 0 not checked. [2024-11-14 05:32:35,638 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 05:32:40,274 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 05:32:40,274 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2081967399] [2024-11-14 05:32:40,274 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-14 05:32:40,274 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [659354735] [2024-11-14 05:32:40,274 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [659354735] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 05:32:40,274 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1491971092] [2024-11-14 05:32:40,276 INFO L159 IcfgInterpreter]: Started Sifa with 11 locations of interest [2024-11-14 05:32:40,276 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 05:32:40,276 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 05:32:40,276 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 05:32:40,276 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 05:32:40,676 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 39 for LOIs [2024-11-14 05:32:40,704 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 05:32:43,496 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '8217#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (<= ~counter~0 100))' at error location [2024-11-14 05:32:43,496 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 05:32:43,496 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-14 05:32:43,496 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [20] total 20 [2024-11-14 05:32:43,496 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [116005201] [2024-11-14 05:32:43,496 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-14 05:32:43,497 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2024-11-14 05:32:43,497 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 05:32:43,497 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2024-11-14 05:32:43,498 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=100, Invalid=830, Unknown=0, NotChecked=0, Total=930 [2024-11-14 05:32:43,498 INFO L87 Difference]: Start difference. First operand 182 states and 192 transitions. Second operand has 20 states, 20 states have (on average 2.4) internal successors, (48), 18 states have internal predecessors, (48), 13 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2024-11-14 05:32:56,638 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 05:32:56,638 INFO L93 Difference]: Finished difference Result 184 states and 193 transitions. [2024-11-14 05:32:56,638 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2024-11-14 05:32:56,638 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 20 states have (on average 2.4) internal successors, (48), 18 states have internal predecessors, (48), 13 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) Word has length 103 [2024-11-14 05:32:56,639 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 05:32:56,640 INFO L225 Difference]: With dead ends: 184 [2024-11-14 05:32:56,640 INFO L226 Difference]: Without dead ends: 182 [2024-11-14 05:32:56,641 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 226 GetRequests, 182 SyntacticMatches, 2 SemanticMatches, 42 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 326 ImplicationChecksByTransitivity, 18.9s TimeCoverageRelationStatistics Valid=218, Invalid=1674, Unknown=0, NotChecked=0, Total=1892 [2024-11-14 05:32:56,642 INFO L432 NwaCegarLoop]: 33 mSDtfsCounter, 11 mSDsluCounter, 396 mSDsCounter, 0 mSdLazyCounter, 324 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 3.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 429 SdHoareTripleChecker+Invalid, 332 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 324 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 3.6s IncrementalHoareTripleChecker+Time [2024-11-14 05:32:56,642 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [12 Valid, 429 Invalid, 332 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 324 Invalid, 0 Unknown, 0 Unchecked, 3.6s Time] [2024-11-14 05:32:56,643 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 182 states. [2024-11-14 05:32:56,706 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 182 to 182. [2024-11-14 05:32:56,707 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 182 states, 136 states have (on average 1.0735294117647058) internal successors, (146), 137 states have internal predecessors, (146), 23 states have call successors, (23), 22 states have call predecessors, (23), 22 states have return successors, (22), 22 states have call predecessors, (22), 22 states have call successors, (22) [2024-11-14 05:32:56,707 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 182 states to 182 states and 191 transitions. [2024-11-14 05:32:56,708 INFO L78 Accepts]: Start accepts. Automaton has 182 states and 191 transitions. Word has length 103 [2024-11-14 05:32:56,708 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 05:32:56,708 INFO L471 AbstractCegarLoop]: Abstraction has 182 states and 191 transitions. [2024-11-14 05:32:56,708 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 20 states have (on average 2.4) internal successors, (48), 18 states have internal predecessors, (48), 13 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2024-11-14 05:32:56,708 INFO L276 IsEmpty]: Start isEmpty. Operand 182 states and 191 transitions. [2024-11-14 05:32:56,709 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 112 [2024-11-14 05:32:56,709 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 05:32:56,709 INFO L215 NwaCegarLoop]: trace histogram [14, 14, 14, 14, 13, 13, 13, 13, 1, 1, 1] [2024-11-14 05:32:56,723 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Ended with exit code 0 [2024-11-14 05:32:56,909 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 16 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable17 [2024-11-14 05:32:56,909 INFO L396 AbstractCegarLoop]: === Iteration 19 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 05:32:56,909 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 05:32:56,910 INFO L85 PathProgramCache]: Analyzing trace with hash 1602379118, now seen corresponding path program 11 times [2024-11-14 05:32:56,910 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 05:32:56,910 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [612992371] [2024-11-14 05:32:56,910 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 05:32:56,910 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 05:32:57,062 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 05:32:57,065 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [599635964] [2024-11-14 05:32:57,065 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-14 05:32:57,065 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 05:32:57,066 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 05:32:57,067 INFO L229 MonitoredProcess]: Starting monitored process 17 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 05:32:57,070 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2024-11-14 05:32:59,278 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 14 check-sat command(s) [2024-11-14 05:32:59,278 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-14 05:32:59,282 INFO L255 TraceCheckSpWp]: Trace formula consists of 308 conjuncts, 77 conjuncts are in the unsatisfiable core [2024-11-14 05:32:59,287 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 05:33:08,707 INFO L134 CoverageAnalysis]: Checked inductivity of 689 backedges. 130 proven. 355 refuted. 0 times theorem prover too weak. 204 trivial. 0 not checked. [2024-11-14 05:33:08,707 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 05:33:26,373 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 05:33:26,374 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [612992371] [2024-11-14 05:33:26,374 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-14 05:33:26,374 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [599635964] [2024-11-14 05:33:26,374 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [599635964] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 05:33:26,374 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [177543738] [2024-11-14 05:33:26,376 INFO L159 IcfgInterpreter]: Started Sifa with 11 locations of interest [2024-11-14 05:33:26,376 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 05:33:26,376 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 05:33:26,376 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 05:33:26,376 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 05:33:26,751 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 39 for LOIs [2024-11-14 05:33:26,780 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 05:33:30,331 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '9254#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (<= ~counter~0 100))' at error location [2024-11-14 05:33:30,331 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 05:33:30,331 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-14 05:33:30,332 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [21] total 21 [2024-11-14 05:33:30,332 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1655654210] [2024-11-14 05:33:30,332 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-14 05:33:30,332 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2024-11-14 05:33:30,332 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 05:33:30,333 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2024-11-14 05:33:30,333 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=246, Invalid=1235, Unknown=1, NotChecked=0, Total=1482 [2024-11-14 05:33:30,334 INFO L87 Difference]: Start difference. First operand 182 states and 191 transitions. Second operand has 21 states, 21 states have (on average 2.4285714285714284) internal successors, (51), 19 states have internal predecessors, (51), 14 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2024-11-14 05:34:13,764 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 05:34:13,764 INFO L93 Difference]: Finished difference Result 184 states and 192 transitions. [2024-11-14 05:34:13,764 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2024-11-14 05:34:13,765 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 21 states have (on average 2.4285714285714284) internal successors, (51), 19 states have internal predecessors, (51), 14 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) Word has length 111 [2024-11-14 05:34:13,765 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 05:34:13,766 INFO L225 Difference]: With dead ends: 184 [2024-11-14 05:34:13,766 INFO L226 Difference]: Without dead ends: 182 [2024-11-14 05:34:13,767 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 267 GetRequests, 213 SyntacticMatches, 3 SemanticMatches, 51 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 540 ImplicationChecksByTransitivity, 59.7s TimeCoverageRelationStatistics Valid=519, Invalid=2234, Unknown=3, NotChecked=0, Total=2756 [2024-11-14 05:34:13,768 INFO L432 NwaCegarLoop]: 24 mSDtfsCounter, 20 mSDsluCounter, 206 mSDsCounter, 0 mSdLazyCounter, 174 mSolverCounterSat, 22 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 3.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 21 SdHoareTripleChecker+Valid, 230 SdHoareTripleChecker+Invalid, 196 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 22 IncrementalHoareTripleChecker+Valid, 174 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 3.6s IncrementalHoareTripleChecker+Time [2024-11-14 05:34:13,768 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [21 Valid, 230 Invalid, 196 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [22 Valid, 174 Invalid, 0 Unknown, 0 Unchecked, 3.6s Time] [2024-11-14 05:34:13,769 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 182 states. [2024-11-14 05:34:13,849 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 182 to 182. [2024-11-14 05:34:13,849 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 182 states, 136 states have (on average 1.0661764705882353) internal successors, (145), 137 states have internal predecessors, (145), 23 states have call successors, (23), 22 states have call predecessors, (23), 22 states have return successors, (22), 22 states have call predecessors, (22), 22 states have call successors, (22) [2024-11-14 05:34:13,850 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 182 states to 182 states and 190 transitions. [2024-11-14 05:34:13,851 INFO L78 Accepts]: Start accepts. Automaton has 182 states and 190 transitions. Word has length 111 [2024-11-14 05:34:13,851 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 05:34:13,851 INFO L471 AbstractCegarLoop]: Abstraction has 182 states and 190 transitions. [2024-11-14 05:34:13,851 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 21 states have (on average 2.4285714285714284) internal successors, (51), 19 states have internal predecessors, (51), 14 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2024-11-14 05:34:13,851 INFO L276 IsEmpty]: Start isEmpty. Operand 182 states and 190 transitions. [2024-11-14 05:34:13,853 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 120 [2024-11-14 05:34:13,853 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 05:34:13,853 INFO L215 NwaCegarLoop]: trace histogram [15, 15, 15, 15, 14, 14, 14, 14, 1, 1, 1] [2024-11-14 05:34:13,863 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Ended with exit code 0 [2024-11-14 05:34:14,053 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable18,17 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 05:34:14,054 INFO L396 AbstractCegarLoop]: === Iteration 20 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 05:34:14,054 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 05:34:14,054 INFO L85 PathProgramCache]: Analyzing trace with hash -1862671822, now seen corresponding path program 12 times [2024-11-14 05:34:14,054 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 05:34:14,054 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [929251402] [2024-11-14 05:34:14,055 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 05:34:14,055 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 05:34:14,296 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 05:34:14,298 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1695450340] [2024-11-14 05:34:14,298 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-14 05:34:14,298 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 05:34:14,299 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 05:34:14,304 INFO L229 MonitoredProcess]: Starting monitored process 18 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 05:34:14,307 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Waiting until timeout for monitored process [2024-11-14 05:34:18,220 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-14 05:34:18,220 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-14 05:34:18,225 INFO L255 TraceCheckSpWp]: Trace formula consists of 328 conjuncts, 77 conjuncts are in the unsatisfiable core [2024-11-14 05:34:18,233 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 05:34:31,498 INFO L134 CoverageAnalysis]: Checked inductivity of 798 backedges. 98 proven. 408 refuted. 0 times theorem prover too weak. 292 trivial. 0 not checked. [2024-11-14 05:34:31,498 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 05:34:45,524 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 05:34:45,524 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [929251402] [2024-11-14 05:34:45,525 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-14 05:34:45,525 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1695450340] [2024-11-14 05:34:45,525 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1695450340] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 05:34:45,525 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1873018603] [2024-11-14 05:34:45,526 INFO L159 IcfgInterpreter]: Started Sifa with 11 locations of interest [2024-11-14 05:34:45,526 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 05:34:45,527 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 05:34:45,527 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 05:34:45,527 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 05:34:45,972 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 39 for LOIs [2024-11-14 05:34:46,006 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 05:34:49,579 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '10266#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (<= ~counter~0 100))' at error location [2024-11-14 05:34:49,579 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 05:34:49,579 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-14 05:34:49,579 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [22] total 22 [2024-11-14 05:34:49,579 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1077376560] [2024-11-14 05:34:49,579 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-14 05:34:49,580 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2024-11-14 05:34:49,580 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 05:34:49,582 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2024-11-14 05:34:49,582 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=165, Invalid=1167, Unknown=0, NotChecked=0, Total=1332 [2024-11-14 05:34:49,582 INFO L87 Difference]: Start difference. First operand 182 states and 190 transitions. Second operand has 22 states, 22 states have (on average 2.4545454545454546) internal successors, (54), 20 states have internal predecessors, (54), 15 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (14), 14 states have call predecessors, (14), 14 states have call successors, (14) [2024-11-14 05:35:11,649 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.08s for a HTC check with result VALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 05:35:12,811 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.11s for a HTC check with result VALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 05:35:34,159 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 05:35:34,159 INFO L93 Difference]: Finished difference Result 184 states and 191 transitions. [2024-11-14 05:35:34,160 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2024-11-14 05:35:34,160 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 22 states have (on average 2.4545454545454546) internal successors, (54), 20 states have internal predecessors, (54), 15 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (14), 14 states have call predecessors, (14), 14 states have call successors, (14) Word has length 119 [2024-11-14 05:35:34,161 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 05:35:34,162 INFO L225 Difference]: With dead ends: 184 [2024-11-14 05:35:34,162 INFO L226 Difference]: Without dead ends: 182 [2024-11-14 05:35:34,163 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 268 GetRequests, 216 SyntacticMatches, 2 SemanticMatches, 50 ConstructedPredicates, 0 IntricatePredicates, 1 DeprecatedPredicates, 478 ImplicationChecksByTransitivity, 48.5s TimeCoverageRelationStatistics Valid=346, Invalid=2305, Unknown=1, NotChecked=0, Total=2652 [2024-11-14 05:35:34,164 INFO L432 NwaCegarLoop]: 36 mSDtfsCounter, 13 mSDsluCounter, 480 mSDsCounter, 0 mSdLazyCounter, 377 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 11.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 516 SdHoareTripleChecker+Invalid, 388 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 377 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 11.4s IncrementalHoareTripleChecker+Time [2024-11-14 05:35:34,164 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [14 Valid, 516 Invalid, 388 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 377 Invalid, 0 Unknown, 0 Unchecked, 11.4s Time] [2024-11-14 05:35:34,165 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 182 states. [2024-11-14 05:35:34,263 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 182 to 182. [2024-11-14 05:35:34,264 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 182 states, 136 states have (on average 1.0588235294117647) internal successors, (144), 137 states have internal predecessors, (144), 23 states have call successors, (23), 22 states have call predecessors, (23), 22 states have return successors, (22), 22 states have call predecessors, (22), 22 states have call successors, (22) [2024-11-14 05:35:34,264 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 182 states to 182 states and 189 transitions. [2024-11-14 05:35:34,265 INFO L78 Accepts]: Start accepts. Automaton has 182 states and 189 transitions. Word has length 119 [2024-11-14 05:35:34,265 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 05:35:34,265 INFO L471 AbstractCegarLoop]: Abstraction has 182 states and 189 transitions. [2024-11-14 05:35:34,265 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 22 states have (on average 2.4545454545454546) internal successors, (54), 20 states have internal predecessors, (54), 15 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (14), 14 states have call predecessors, (14), 14 states have call successors, (14) [2024-11-14 05:35:34,265 INFO L276 IsEmpty]: Start isEmpty. Operand 182 states and 189 transitions. [2024-11-14 05:35:34,267 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 128 [2024-11-14 05:35:34,267 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 05:35:34,267 INFO L215 NwaCegarLoop]: trace histogram [16, 16, 16, 16, 15, 15, 15, 15, 1, 1, 1] [2024-11-14 05:35:34,299 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Ended with exit code 0 [2024-11-14 05:35:34,467 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable19,18 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 05:35:34,467 INFO L396 AbstractCegarLoop]: === Iteration 21 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 05:35:34,468 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 05:35:34,468 INFO L85 PathProgramCache]: Analyzing trace with hash 689070838, now seen corresponding path program 13 times [2024-11-14 05:35:34,468 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 05:35:34,468 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [394223124] [2024-11-14 05:35:34,468 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 05:35:34,468 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 05:35:34,761 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 05:35:34,764 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2047111892] [2024-11-14 05:35:34,764 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2024-11-14 05:35:34,764 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 05:35:34,765 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 05:35:34,768 INFO L229 MonitoredProcess]: Starting monitored process 19 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 05:35:34,771 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Waiting until timeout for monitored process [2024-11-14 05:35:38,270 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 05:35:38,274 INFO L255 TraceCheckSpWp]: Trace formula consists of 348 conjuncts, 85 conjuncts are in the unsatisfiable core [2024-11-14 05:35:38,283 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 05:35:50,051 INFO L134 CoverageAnalysis]: Checked inductivity of 915 backedges. 135 proven. 468 refuted. 0 times theorem prover too weak. 312 trivial. 0 not checked. [2024-11-14 05:35:50,051 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 05:36:03,253 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 05:36:03,253 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [394223124] [2024-11-14 05:36:03,253 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-14 05:36:03,253 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2047111892] [2024-11-14 05:36:03,253 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2047111892] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 05:36:03,253 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1390291073] [2024-11-14 05:36:03,255 INFO L159 IcfgInterpreter]: Started Sifa with 11 locations of interest [2024-11-14 05:36:03,255 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 05:36:03,255 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 05:36:03,255 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 05:36:03,255 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 05:36:03,741 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 39 for LOIs [2024-11-14 05:36:03,790 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 05:36:08,708 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '11333#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (<= ~counter~0 100))' at error location [2024-11-14 05:36:08,708 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 05:36:08,708 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-14 05:36:08,708 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [23] total 23 [2024-11-14 05:36:08,709 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1353861892] [2024-11-14 05:36:08,709 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-14 05:36:08,709 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2024-11-14 05:36:08,709 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 05:36:08,710 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2024-11-14 05:36:08,710 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=219, Invalid=1341, Unknown=0, NotChecked=0, Total=1560 [2024-11-14 05:36:08,710 INFO L87 Difference]: Start difference. First operand 182 states and 189 transitions. Second operand has 23 states, 23 states have (on average 2.4782608695652173) internal successors, (57), 21 states have internal predecessors, (57), 16 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (15), 15 states have call predecessors, (15), 15 states have call successors, (15) [2024-11-14 05:36:22,668 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 05:36:32,870 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 05:37:01,437 WARN L286 SmtUtils]: Spent 5.77s on a formula simplification. DAG size of input: 121 DAG size of output: 57 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-14 05:37:20,983 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 05:37:20,983 INFO L93 Difference]: Finished difference Result 184 states and 190 transitions. [2024-11-14 05:37:20,984 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2024-11-14 05:37:20,984 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 23 states have (on average 2.4782608695652173) internal successors, (57), 21 states have internal predecessors, (57), 16 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (15), 15 states have call predecessors, (15), 15 states have call successors, (15) Word has length 127 [2024-11-14 05:37:20,984 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 05:37:20,985 INFO L225 Difference]: With dead ends: 184 [2024-11-14 05:37:20,985 INFO L226 Difference]: Without dead ends: 182 [2024-11-14 05:37:20,986 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 295 GetRequests, 239 SyntacticMatches, 1 SemanticMatches, 55 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 588 ImplicationChecksByTransitivity, 78.9s TimeCoverageRelationStatistics Valid=497, Invalid=2692, Unknown=3, NotChecked=0, Total=3192 [2024-11-14 05:37:20,988 INFO L432 NwaCegarLoop]: 33 mSDtfsCounter, 18 mSDsluCounter, 383 mSDsCounter, 0 mSdLazyCounter, 297 mSolverCounterSat, 16 mSolverCounterUnsat, 2 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 11.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 19 SdHoareTripleChecker+Valid, 416 SdHoareTripleChecker+Invalid, 315 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 16 IncrementalHoareTripleChecker+Valid, 297 IncrementalHoareTripleChecker+Invalid, 2 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 11.7s IncrementalHoareTripleChecker+Time [2024-11-14 05:37:20,988 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [19 Valid, 416 Invalid, 315 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [16 Valid, 297 Invalid, 2 Unknown, 0 Unchecked, 11.7s Time] [2024-11-14 05:37:20,989 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 182 states. [2024-11-14 05:37:21,099 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 182 to 182. [2024-11-14 05:37:21,100 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 182 states, 136 states have (on average 1.0514705882352942) internal successors, (143), 137 states have internal predecessors, (143), 23 states have call successors, (23), 22 states have call predecessors, (23), 22 states have return successors, (22), 22 states have call predecessors, (22), 22 states have call successors, (22) [2024-11-14 05:37:21,101 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 182 states to 182 states and 188 transitions. [2024-11-14 05:37:21,101 INFO L78 Accepts]: Start accepts. Automaton has 182 states and 188 transitions. Word has length 127 [2024-11-14 05:37:21,101 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 05:37:21,101 INFO L471 AbstractCegarLoop]: Abstraction has 182 states and 188 transitions. [2024-11-14 05:37:21,102 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 23 states have (on average 2.4782608695652173) internal successors, (57), 21 states have internal predecessors, (57), 16 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (15), 15 states have call predecessors, (15), 15 states have call successors, (15) [2024-11-14 05:37:21,102 INFO L276 IsEmpty]: Start isEmpty. Operand 182 states and 188 transitions. [2024-11-14 05:37:21,103 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 136 [2024-11-14 05:37:21,103 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 05:37:21,103 INFO L215 NwaCegarLoop]: trace histogram [17, 17, 17, 17, 16, 16, 16, 16, 1, 1, 1] [2024-11-14 05:37:21,141 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Ended with exit code 0 [2024-11-14 05:37:21,304 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable20,19 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 05:37:21,304 INFO L396 AbstractCegarLoop]: === Iteration 22 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 05:37:21,304 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 05:37:21,304 INFO L85 PathProgramCache]: Analyzing trace with hash -451944518, now seen corresponding path program 14 times [2024-11-14 05:37:21,304 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 05:37:21,304 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1581118189] [2024-11-14 05:37:21,305 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 05:37:21,305 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 05:37:26,153 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 05:37:26,156 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1757571324] [2024-11-14 05:37:26,157 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-14 05:37:26,157 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 05:37:26,157 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 05:37:26,160 INFO L229 MonitoredProcess]: Starting monitored process 20 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 05:37:26,165 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Waiting until timeout for monitored process [2024-11-14 05:37:28,934 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 17 check-sat command(s) [2024-11-14 05:37:28,934 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-14 05:37:28,939 INFO L255 TraceCheckSpWp]: Trace formula consists of 368 conjuncts, 66 conjuncts are in the unsatisfiable core [2024-11-14 05:37:28,950 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 05:37:36,235 INFO L134 CoverageAnalysis]: Checked inductivity of 1040 backedges. 76 proven. 529 refuted. 0 times theorem prover too weak. 435 trivial. 0 not checked. [2024-11-14 05:37:36,235 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 05:37:43,574 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 05:37:43,574 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1581118189] [2024-11-14 05:37:43,574 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-14 05:37:43,575 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1757571324] [2024-11-14 05:37:43,575 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1757571324] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 05:37:43,575 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1596166581] [2024-11-14 05:37:43,576 INFO L159 IcfgInterpreter]: Started Sifa with 11 locations of interest [2024-11-14 05:37:43,576 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 05:37:43,577 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 05:37:43,577 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 05:37:43,577 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 05:37:44,135 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 39 for LOIs [2024-11-14 05:37:44,173 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 05:37:48,332 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '12375#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (<= ~counter~0 100))' at error location [2024-11-14 05:37:48,332 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 05:37:48,333 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-14 05:37:48,333 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [24] total 24 [2024-11-14 05:37:48,333 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1817654911] [2024-11-14 05:37:48,333 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-14 05:37:48,333 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 24 states [2024-11-14 05:37:48,333 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 05:37:48,334 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2024-11-14 05:37:48,334 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=186, Invalid=1073, Unknown=1, NotChecked=0, Total=1260 [2024-11-14 05:37:48,334 INFO L87 Difference]: Start difference. First operand 182 states and 188 transitions. Second operand has 24 states, 24 states have (on average 2.5) internal successors, (60), 22 states have internal predecessors, (60), 17 states have call successors, (17), 2 states have call predecessors, (17), 2 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2024-11-14 05:38:19,295 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 05:38:19,295 INFO L93 Difference]: Finished difference Result 184 states and 189 transitions. [2024-11-14 05:38:19,296 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2024-11-14 05:38:19,296 INFO L78 Accepts]: Start accepts. Automaton has has 24 states, 24 states have (on average 2.5) internal successors, (60), 22 states have internal predecessors, (60), 17 states have call successors, (17), 2 states have call predecessors, (17), 2 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) Word has length 135 [2024-11-14 05:38:19,297 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 05:38:19,298 INFO L225 Difference]: With dead ends: 184 [2024-11-14 05:38:19,298 INFO L226 Difference]: Without dead ends: 182 [2024-11-14 05:38:19,301 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 294 GetRequests, 241 SyntacticMatches, 2 SemanticMatches, 51 ConstructedPredicates, 0 IntricatePredicates, 1 DeprecatedPredicates, 595 ImplicationChecksByTransitivity, 38.9s TimeCoverageRelationStatistics Valid=488, Invalid=2267, Unknown=1, NotChecked=0, Total=2756 [2024-11-14 05:38:19,305 INFO L432 NwaCegarLoop]: 21 mSDtfsCounter, 27 mSDsluCounter, 196 mSDsCounter, 0 mSdLazyCounter, 177 mSolverCounterSat, 24 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 28 SdHoareTripleChecker+Valid, 217 SdHoareTripleChecker+Invalid, 201 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 24 IncrementalHoareTripleChecker+Valid, 177 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 4.9s IncrementalHoareTripleChecker+Time [2024-11-14 05:38:19,306 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [28 Valid, 217 Invalid, 201 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [24 Valid, 177 Invalid, 0 Unknown, 0 Unchecked, 4.9s Time] [2024-11-14 05:38:19,307 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 182 states. [2024-11-14 05:38:19,418 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 182 to 182. [2024-11-14 05:38:19,418 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 182 states, 136 states have (on average 1.0441176470588236) internal successors, (142), 137 states have internal predecessors, (142), 23 states have call successors, (23), 22 states have call predecessors, (23), 22 states have return successors, (22), 22 states have call predecessors, (22), 22 states have call successors, (22) [2024-11-14 05:38:19,420 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 182 states to 182 states and 187 transitions. [2024-11-14 05:38:19,421 INFO L78 Accepts]: Start accepts. Automaton has 182 states and 187 transitions. Word has length 135 [2024-11-14 05:38:19,421 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 05:38:19,421 INFO L471 AbstractCegarLoop]: Abstraction has 182 states and 187 transitions. [2024-11-14 05:38:19,421 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 24 states, 24 states have (on average 2.5) internal successors, (60), 22 states have internal predecessors, (60), 17 states have call successors, (17), 2 states have call predecessors, (17), 2 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2024-11-14 05:38:19,422 INFO L276 IsEmpty]: Start isEmpty. Operand 182 states and 187 transitions. [2024-11-14 05:38:19,423 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 144 [2024-11-14 05:38:19,423 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 05:38:19,423 INFO L215 NwaCegarLoop]: trace histogram [18, 18, 18, 18, 17, 17, 17, 17, 1, 1, 1] [2024-11-14 05:38:19,454 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Ended with exit code 0 [2024-11-14 05:38:19,623 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable21,20 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 05:38:19,624 INFO L396 AbstractCegarLoop]: === Iteration 23 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 05:38:19,624 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 05:38:19,624 INFO L85 PathProgramCache]: Analyzing trace with hash -29992834, now seen corresponding path program 15 times [2024-11-14 05:38:19,624 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 05:38:19,624 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [908195070] [2024-11-14 05:38:19,625 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 05:38:19,625 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 05:38:20,610 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 05:38:20,613 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1207276145] [2024-11-14 05:38:20,614 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-14 05:38:20,614 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 05:38:20,614 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 05:38:20,616 INFO L229 MonitoredProcess]: Starting monitored process 21 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 05:38:20,619 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5ea12d34-a747-41d3-91d4-e1fa5410515f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Waiting until timeout for monitored process [2024-11-14 05:38:23,793 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-14 05:38:23,794 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-14 05:38:23,798 INFO L255 TraceCheckSpWp]: Trace formula consists of 388 conjuncts, 91 conjuncts are in the unsatisfiable core [2024-11-14 05:38:23,807 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 05:39:33,377 WARN L286 SmtUtils]: Spent 8.68s on a formula simplification. DAG size of input: 491 DAG size of output: 454 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate)