./Ultimate.py --spec ../../sv-benchmarks/c/properties/unreach-call.prp --file ../../sv-benchmarks/c/nla-digbench-scaling/cohencu-ll_unwindbound50.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 9bd2c7ff Calling Ultimate with: /usr/lib/jvm/java-1.11.0-openjdk-amd64/bin/java -Dosgi.configuration.area=/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/config/TaipanReach.xml -i ../../sv-benchmarks/c/nla-digbench-scaling/cohencu-ll_unwindbound50.c -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/config/svcomp-Reach-32bit-Taipan_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ --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 cb55eb0e5d7c4df3b95a55b83f19894edf68e79ccb0eab5e69a8aa23c994caed --- Real Ultimate output --- This is Ultimate 0.2.3-dev-9bd2c7f [2023-11-19 05:02:34,399 INFO L188 SettingsManager]: Resetting all preferences to default values... [2023-11-19 05:02:34,509 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/config/svcomp-Reach-32bit-Taipan_Default.epf [2023-11-19 05:02:34,519 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2023-11-19 05:02:34,521 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2023-11-19 05:02:34,562 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2023-11-19 05:02:34,563 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2023-11-19 05:02:34,564 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2023-11-19 05:02:34,565 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2023-11-19 05:02:34,570 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2023-11-19 05:02:34,570 INFO L153 SettingsManager]: * User list type=DISABLED [2023-11-19 05:02:34,572 INFO L151 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2023-11-19 05:02:34,572 INFO L153 SettingsManager]: * Explicit value domain=true [2023-11-19 05:02:34,574 INFO L153 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2023-11-19 05:02:34,574 INFO L153 SettingsManager]: * Octagon Domain=false [2023-11-19 05:02:34,575 INFO L153 SettingsManager]: * Abstract domain=CompoundDomain [2023-11-19 05:02:34,575 INFO L153 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2023-11-19 05:02:34,576 INFO L153 SettingsManager]: * Use the RCFG-of-the-future interface=true [2023-11-19 05:02:34,576 INFO L153 SettingsManager]: * Interval Domain=false [2023-11-19 05:02:34,577 INFO L151 SettingsManager]: Preferences of Sifa differ from their defaults: [2023-11-19 05:02:34,577 INFO L153 SettingsManager]: * Call Summarizer=TopInputCallSummarizer [2023-11-19 05:02:34,578 INFO L153 SettingsManager]: * Simplification Technique=POLY_PAC [2023-11-19 05:02:34,579 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2023-11-19 05:02:34,580 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2023-11-19 05:02:34,580 INFO L153 SettingsManager]: * sizeof long=4 [2023-11-19 05:02:34,581 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2023-11-19 05:02:34,581 INFO L153 SettingsManager]: * sizeof POINTER=4 [2023-11-19 05:02:34,582 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2023-11-19 05:02:34,582 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2023-11-19 05:02:34,582 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2023-11-19 05:02:34,584 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2023-11-19 05:02:34,613 INFO L153 SettingsManager]: * sizeof long double=12 [2023-11-19 05:02:34,614 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2023-11-19 05:02:34,614 INFO L153 SettingsManager]: * Use constant arrays=true [2023-11-19 05:02:34,614 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2023-11-19 05:02:34,615 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2023-11-19 05:02:34,615 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-11-19 05:02:34,616 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2023-11-19 05:02:34,617 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2023-11-19 05:02:34,617 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2023-11-19 05:02:34,618 INFO L153 SettingsManager]: * Trace refinement strategy=SIFA_TAIPAN [2023-11-19 05:02:34,618 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2023-11-19 05:02:34,619 INFO L153 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2023-11-19 05:02:34,619 INFO L153 SettingsManager]: * Trace refinement exception blacklist=NONE [2023-11-19 05:02:34,620 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2023-11-19 05:02:34,620 INFO L153 SettingsManager]: * Abstract interpretation Mode=USE_PREDICATES WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release 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_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ 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 -> cb55eb0e5d7c4df3b95a55b83f19894edf68e79ccb0eab5e69a8aa23c994caed [2023-11-19 05:02:34,939 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2023-11-19 05:02:34,970 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2023-11-19 05:02:34,973 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2023-11-19 05:02:34,974 INFO L270 PluginConnector]: Initializing CDTParser... [2023-11-19 05:02:34,975 INFO L274 PluginConnector]: CDTParser initialized [2023-11-19 05:02:34,977 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/../../sv-benchmarks/c/nla-digbench-scaling/cohencu-ll_unwindbound50.c [2023-11-19 05:02:37,984 INFO L533 CDTParser]: Created temporary CDT project at NULL [2023-11-19 05:02:38,232 INFO L384 CDTParser]: Found 1 translation units. [2023-11-19 05:02:38,233 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/sv-benchmarks/c/nla-digbench-scaling/cohencu-ll_unwindbound50.c [2023-11-19 05:02:38,242 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/data/209b3c0c7/5a4b3ef8f39d42d4b6465b9d613b18d5/FLAGa8c12fea2 [2023-11-19 05:02:38,259 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/data/209b3c0c7/5a4b3ef8f39d42d4b6465b9d613b18d5 [2023-11-19 05:02:38,266 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2023-11-19 05:02:38,268 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2023-11-19 05:02:38,274 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2023-11-19 05:02:38,274 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2023-11-19 05:02:38,280 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2023-11-19 05:02:38,280 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 19.11 05:02:38" (1/1) ... [2023-11-19 05:02:38,282 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@4584347a and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 05:02:38, skipping insertion in model container [2023-11-19 05:02:38,282 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 19.11 05:02:38" (1/1) ... [2023-11-19 05:02:38,308 INFO L177 MainTranslator]: Built tables and reachable declarations [2023-11-19 05:02:38,479 WARN L240 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_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/sv-benchmarks/c/nla-digbench-scaling/cohencu-ll_unwindbound50.c[588,601] [2023-11-19 05:02:38,503 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-19 05:02:38,513 INFO L202 MainTranslator]: Completed pre-run [2023-11-19 05:02:38,526 WARN L240 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_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/sv-benchmarks/c/nla-digbench-scaling/cohencu-ll_unwindbound50.c[588,601] [2023-11-19 05:02:38,539 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-19 05:02:38,561 INFO L206 MainTranslator]: Completed translation [2023-11-19 05:02:38,562 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 05:02:38 WrapperNode [2023-11-19 05:02:38,562 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2023-11-19 05:02:38,564 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2023-11-19 05:02:38,564 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2023-11-19 05:02:38,564 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2023-11-19 05:02:38,572 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 05:02:38" (1/1) ... [2023-11-19 05:02:38,579 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 05:02:38" (1/1) ... [2023-11-19 05:02:38,604 INFO L138 Inliner]: procedures = 14, calls = 18, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 49 [2023-11-19 05:02:38,604 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2023-11-19 05:02:38,605 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2023-11-19 05:02:38,605 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2023-11-19 05:02:38,606 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2023-11-19 05:02:38,615 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 05:02:38" (1/1) ... [2023-11-19 05:02:38,615 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 05:02:38" (1/1) ... [2023-11-19 05:02:38,617 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 05:02:38" (1/1) ... [2023-11-19 05:02:38,618 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 05:02:38" (1/1) ... [2023-11-19 05:02:38,621 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 05:02:38" (1/1) ... [2023-11-19 05:02:38,625 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 05:02:38" (1/1) ... [2023-11-19 05:02:38,626 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 05:02:38" (1/1) ... [2023-11-19 05:02:38,627 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 05:02:38" (1/1) ... [2023-11-19 05:02:38,628 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2023-11-19 05:02:38,629 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2023-11-19 05:02:38,630 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2023-11-19 05:02:38,630 INFO L274 PluginConnector]: RCFGBuilder initialized [2023-11-19 05:02:38,631 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 05:02:38" (1/1) ... [2023-11-19 05:02:38,639 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-11-19 05:02:38,668 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 05:02:38,679 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2023-11-19 05:02:38,714 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2023-11-19 05:02:38,733 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2023-11-19 05:02:38,733 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2023-11-19 05:02:38,734 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2023-11-19 05:02:38,734 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2023-11-19 05:02:38,734 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2023-11-19 05:02:38,734 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2023-11-19 05:02:38,814 INFO L236 CfgBuilder]: Building ICFG [2023-11-19 05:02:38,816 INFO L262 CfgBuilder]: Building CFG for each procedure with an implementation [2023-11-19 05:02:39,080 INFO L277 CfgBuilder]: Performing block encoding [2023-11-19 05:02:39,098 INFO L297 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2023-11-19 05:02:39,098 INFO L302 CfgBuilder]: Removed 1 assume(true) statements. [2023-11-19 05:02:39,103 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 19.11 05:02:39 BoogieIcfgContainer [2023-11-19 05:02:39,103 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2023-11-19 05:02:39,107 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2023-11-19 05:02:39,107 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2023-11-19 05:02:39,110 INFO L274 PluginConnector]: TraceAbstraction initialized [2023-11-19 05:02:39,110 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 19.11 05:02:38" (1/3) ... [2023-11-19 05:02:39,111 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@44243e63 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 19.11 05:02:39, skipping insertion in model container [2023-11-19 05:02:39,111 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 05:02:38" (2/3) ... [2023-11-19 05:02:39,112 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@44243e63 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 19.11 05:02:39, skipping insertion in model container [2023-11-19 05:02:39,112 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 19.11 05:02:39" (3/3) ... [2023-11-19 05:02:39,113 INFO L112 eAbstractionObserver]: Analyzing ICFG cohencu-ll_unwindbound50.c [2023-11-19 05:02:39,133 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2023-11-19 05:02:39,133 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2023-11-19 05:02:39,194 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-11-19 05:02:39,200 INFO L357 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, mHoare=true, 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;@6b737fd7, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2023-11-19 05:02:39,201 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2023-11-19 05:02:39,205 INFO L276 IsEmpty]: Start isEmpty. Operand has 23 states, 9 states have (on average 1.5555555555555556) internal successors, (14), 10 states have internal predecessors, (14), 11 states have call successors, (11), 1 states have call predecessors, (11), 1 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2023-11-19 05:02:39,212 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 7 [2023-11-19 05:02:39,212 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 05:02:39,213 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1] [2023-11-19 05:02:39,213 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 05:02:39,218 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 05:02:39,219 INFO L85 PathProgramCache]: Analyzing trace with hash -1379524608, now seen corresponding path program 1 times [2023-11-19 05:02:39,229 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 05:02:39,230 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [483780919] [2023-11-19 05:02:39,230 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 05:02:39,230 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 05:02:39,328 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 05:02:39,418 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-19 05:02:39,418 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 05:02:39,419 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [483780919] [2023-11-19 05:02:39,420 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [483780919] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-19 05:02:39,420 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-19 05:02:39,421 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2023-11-19 05:02:39,422 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1347447746] [2023-11-19 05:02:39,439 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-19 05:02:39,444 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2023-11-19 05:02:39,445 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 05:02:39,474 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2023-11-19 05:02:39,476 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2023-11-19 05:02:39,478 INFO L87 Difference]: Start difference. First operand has 23 states, 9 states have (on average 1.5555555555555556) internal successors, (14), 10 states have internal predecessors, (14), 11 states have call successors, (11), 1 states have call predecessors, (11), 1 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) 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) [2023-11-19 05:02:39,518 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 05:02:39,519 INFO L93 Difference]: Finished difference Result 45 states and 82 transitions. [2023-11-19 05:02:39,520 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2023-11-19 05:02:39,521 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 [2023-11-19 05:02:39,522 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 05:02:39,528 INFO L225 Difference]: With dead ends: 45 [2023-11-19 05:02:39,528 INFO L226 Difference]: Without dead ends: 21 [2023-11-19 05:02:39,532 INFO L412 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 [2023-11-19 05:02:39,535 INFO L413 NwaCegarLoop]: 32 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 2 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 32 SdHoareTripleChecker+Invalid, 2 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 2 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-11-19 05:02:39,536 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 32 Invalid, 2 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 2 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-11-19 05:02:39,554 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 21 states. [2023-11-19 05:02:39,584 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 21 to 21. [2023-11-19 05:02:39,585 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 21 states, 8 states have (on average 1.375) internal successors, (11), 9 states have internal predecessors, (11), 11 states have call successors, (11), 1 states have call predecessors, (11), 1 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2023-11-19 05:02:39,587 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 21 states to 21 states and 32 transitions. [2023-11-19 05:02:39,588 INFO L78 Accepts]: Start accepts. Automaton has 21 states and 32 transitions. Word has length 6 [2023-11-19 05:02:39,588 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 05:02:39,588 INFO L495 AbstractCegarLoop]: Abstraction has 21 states and 32 transitions. [2023-11-19 05:02:39,589 INFO L496 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) [2023-11-19 05:02:39,589 INFO L276 IsEmpty]: Start isEmpty. Operand 21 states and 32 transitions. [2023-11-19 05:02:39,590 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 8 [2023-11-19 05:02:39,590 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 05:02:39,590 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2023-11-19 05:02:39,590 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2023-11-19 05:02:39,591 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 05:02:39,591 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 05:02:39,592 INFO L85 PathProgramCache]: Analyzing trace with hash -345068235, now seen corresponding path program 1 times [2023-11-19 05:02:39,592 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 05:02:39,592 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [800572650] [2023-11-19 05:02:39,592 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 05:02:39,593 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 05:02:39,611 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 05:02:39,704 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-19 05:02:39,704 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 05:02:39,704 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [800572650] [2023-11-19 05:02:39,705 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [800572650] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-19 05:02:39,705 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-19 05:02:39,705 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2023-11-19 05:02:39,705 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1908106656] [2023-11-19 05:02:39,705 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-19 05:02:39,707 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2023-11-19 05:02:39,707 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 05:02:39,708 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2023-11-19 05:02:39,708 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2023-11-19 05:02:39,708 INFO L87 Difference]: Start difference. First operand 21 states and 32 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) [2023-11-19 05:02:39,740 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 05:02:39,740 INFO L93 Difference]: Finished difference Result 35 states and 51 transitions. [2023-11-19 05:02:39,744 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2023-11-19 05:02:39,745 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 [2023-11-19 05:02:39,745 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 05:02:39,746 INFO L225 Difference]: With dead ends: 35 [2023-11-19 05:02:39,746 INFO L226 Difference]: Without dead ends: 23 [2023-11-19 05:02:39,747 INFO L412 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 [2023-11-19 05:02:39,749 INFO L413 NwaCegarLoop]: 29 mSDtfsCounter, 0 mSDsluCounter, 57 mSDsCounter, 0 mSdLazyCounter, 9 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 86 SdHoareTripleChecker+Invalid, 9 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 9 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-11-19 05:02:39,750 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 86 Invalid, 9 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 9 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-11-19 05:02:39,751 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 23 states. [2023-11-19 05:02:39,758 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 23 to 23. [2023-11-19 05:02:39,761 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 23 states, 10 states have (on average 1.3) internal successors, (13), 11 states have internal predecessors, (13), 11 states have call successors, (11), 1 states have call predecessors, (11), 1 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2023-11-19 05:02:39,771 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 23 states to 23 states and 34 transitions. [2023-11-19 05:02:39,772 INFO L78 Accepts]: Start accepts. Automaton has 23 states and 34 transitions. Word has length 7 [2023-11-19 05:02:39,772 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 05:02:39,772 INFO L495 AbstractCegarLoop]: Abstraction has 23 states and 34 transitions. [2023-11-19 05:02:39,773 INFO L496 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) [2023-11-19 05:02:39,773 INFO L276 IsEmpty]: Start isEmpty. Operand 23 states and 34 transitions. [2023-11-19 05:02:39,773 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 8 [2023-11-19 05:02:39,773 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 05:02:39,774 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2023-11-19 05:02:39,774 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2023-11-19 05:02:39,774 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 05:02:39,775 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 05:02:39,775 INFO L85 PathProgramCache]: Analyzing trace with hash -343519103, now seen corresponding path program 1 times [2023-11-19 05:02:39,775 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 05:02:39,776 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1492974898] [2023-11-19 05:02:39,776 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 05:02:39,776 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 05:02:39,790 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 05:02:40,060 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-19 05:02:40,061 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 05:02:40,061 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1492974898] [2023-11-19 05:02:40,061 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1492974898] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-19 05:02:40,061 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-19 05:02:40,062 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2023-11-19 05:02:40,062 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1987274375] [2023-11-19 05:02:40,062 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-19 05:02:40,062 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-11-19 05:02:40,063 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 05:02:40,063 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-11-19 05:02:40,064 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2023-11-19 05:02:40,064 INFO L87 Difference]: Start difference. First operand 23 states and 34 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) [2023-11-19 05:02:40,193 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 05:02:40,193 INFO L93 Difference]: Finished difference Result 29 states and 39 transitions. [2023-11-19 05:02:40,193 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-11-19 05:02:40,194 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 [2023-11-19 05:02:40,194 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 05:02:40,195 INFO L225 Difference]: With dead ends: 29 [2023-11-19 05:02:40,195 INFO L226 Difference]: Without dead ends: 27 [2023-11-19 05:02:40,196 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2023-11-19 05:02:40,197 INFO L413 NwaCegarLoop]: 25 mSDtfsCounter, 8 mSDsluCounter, 52 mSDsCounter, 0 mSdLazyCounter, 31 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 18 SdHoareTripleChecker+Valid, 77 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 [2023-11-19 05:02:40,198 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [18 Valid, 77 Invalid, 34 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 31 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-19 05:02:40,199 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 27 states. [2023-11-19 05:02:40,212 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 27 to 27. [2023-11-19 05:02:40,212 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 27 states, 13 states have (on average 1.2307692307692308) internal successors, (16), 14 states have internal predecessors, (16), 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) [2023-11-19 05:02:40,213 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 27 states to 27 states and 37 transitions. [2023-11-19 05:02:40,214 INFO L78 Accepts]: Start accepts. Automaton has 27 states and 37 transitions. Word has length 7 [2023-11-19 05:02:40,214 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 05:02:40,214 INFO L495 AbstractCegarLoop]: Abstraction has 27 states and 37 transitions. [2023-11-19 05:02:40,214 INFO L496 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) [2023-11-19 05:02:40,215 INFO L276 IsEmpty]: Start isEmpty. Operand 27 states and 37 transitions. [2023-11-19 05:02:40,215 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2023-11-19 05:02:40,215 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 05:02:40,216 INFO L195 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-19 05:02:40,216 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2023-11-19 05:02:40,216 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 05:02:40,217 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 05:02:40,217 INFO L85 PathProgramCache]: Analyzing trace with hash -875596316, now seen corresponding path program 1 times [2023-11-19 05:02:40,217 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 05:02:40,217 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1894901278] [2023-11-19 05:02:40,218 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 05:02:40,218 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 05:02:40,232 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-19 05:02:40,233 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [22294348] [2023-11-19 05:02:40,233 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 05:02:40,233 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 05:02:40,233 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 05:02:40,245 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 05:02:40,257 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2023-11-19 05:02:40,328 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 05:02:40,331 INFO L262 TraceCheckSpWp]: Trace formula consists of 56 conjuncts, 7 conjunts are in the unsatisfiable core [2023-11-19 05:02:40,337 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-19 05:02:40,455 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-19 05:02:40,455 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-11-19 05:02:40,455 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 05:02:40,456 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1894901278] [2023-11-19 05:02:40,456 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-19 05:02:40,456 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [22294348] [2023-11-19 05:02:40,456 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [22294348] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-19 05:02:40,457 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-19 05:02:40,457 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2023-11-19 05:02:40,457 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [668590852] [2023-11-19 05:02:40,458 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-19 05:02:40,458 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-11-19 05:02:40,458 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 05:02:40,459 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-11-19 05:02:40,460 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2023-11-19 05:02:40,460 INFO L87 Difference]: Start difference. First operand 27 states and 37 transitions. Second operand has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 states have internal predecessors, (9), 1 states have call successors, (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) [2023-11-19 05:02:40,575 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 05:02:40,575 INFO L93 Difference]: Finished difference Result 45 states and 65 transitions. [2023-11-19 05:02:40,575 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2023-11-19 05:02:40,576 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 states have internal predecessors, (9), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 12 [2023-11-19 05:02:40,576 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 05:02:40,577 INFO L225 Difference]: With dead ends: 45 [2023-11-19 05:02:40,577 INFO L226 Difference]: Without dead ends: 43 [2023-11-19 05:02:40,578 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 12 GetRequests, 8 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2023-11-19 05:02:40,580 INFO L413 NwaCegarLoop]: 31 mSDtfsCounter, 6 mSDsluCounter, 75 mSDsCounter, 0 mSdLazyCounter, 34 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 15 SdHoareTripleChecker+Valid, 106 SdHoareTripleChecker+Invalid, 34 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 34 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-19 05:02:40,580 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [15 Valid, 106 Invalid, 34 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 34 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-19 05:02:40,582 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 43 states. [2023-11-19 05:02:40,601 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 43 to 33. [2023-11-19 05:02:40,606 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 33 states, 16 states have (on average 1.1875) internal successors, (19), 18 states have internal predecessors, (19), 13 states have call successors, (13), 3 states have call predecessors, (13), 3 states have return successors, (12), 11 states have call predecessors, (12), 12 states have call successors, (12) [2023-11-19 05:02:40,614 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 33 states to 33 states and 44 transitions. [2023-11-19 05:02:40,614 INFO L78 Accepts]: Start accepts. Automaton has 33 states and 44 transitions. Word has length 12 [2023-11-19 05:02:40,614 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 05:02:40,614 INFO L495 AbstractCegarLoop]: Abstraction has 33 states and 44 transitions. [2023-11-19 05:02:40,615 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 states have internal predecessors, (9), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2023-11-19 05:02:40,615 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 44 transitions. [2023-11-19 05:02:40,615 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2023-11-19 05:02:40,616 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 05:02:40,616 INFO L195 NwaCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-19 05:02:40,639 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2023-11-19 05:02:40,837 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 05:02:40,838 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 05:02:40,838 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 05:02:40,838 INFO L85 PathProgramCache]: Analyzing trace with hash 2105691681, now seen corresponding path program 1 times [2023-11-19 05:02:40,838 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 05:02:40,839 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2043651823] [2023-11-19 05:02:40,839 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 05:02:40,839 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 05:02:40,869 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-19 05:02:40,873 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [146116574] [2023-11-19 05:02:40,873 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 05:02:40,873 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 05:02:40,874 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 05:02:40,875 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 05:02:40,901 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2023-11-19 05:02:40,929 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 05:02:40,930 INFO L262 TraceCheckSpWp]: Trace formula consists of 65 conjuncts, 7 conjunts are in the unsatisfiable core [2023-11-19 05:02:40,932 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-19 05:02:40,999 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2023-11-19 05:02:40,999 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-11-19 05:02:40,999 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 05:02:41,000 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2043651823] [2023-11-19 05:02:41,000 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-19 05:02:41,000 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [146116574] [2023-11-19 05:02:41,001 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [146116574] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-19 05:02:41,001 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-19 05:02:41,001 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2023-11-19 05:02:41,001 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [62947450] [2023-11-19 05:02:41,002 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-19 05:02:41,002 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-11-19 05:02:41,002 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 05:02:41,003 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-11-19 05:02:41,003 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2023-11-19 05:02:41,004 INFO L87 Difference]: Start difference. First operand 33 states and 44 transitions. Second operand has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 states have internal predecessors, (9), 1 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2023-11-19 05:02:41,076 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 05:02:41,076 INFO L93 Difference]: Finished difference Result 49 states and 68 transitions. [2023-11-19 05:02:41,076 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2023-11-19 05:02:41,077 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 states have internal predecessors, (9), 1 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 17 [2023-11-19 05:02:41,077 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 05:02:41,083 INFO L225 Difference]: With dead ends: 49 [2023-11-19 05:02:41,083 INFO L226 Difference]: Without dead ends: 47 [2023-11-19 05:02:41,084 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 17 GetRequests, 13 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2023-11-19 05:02:41,085 INFO L413 NwaCegarLoop]: 34 mSDtfsCounter, 6 mSDsluCounter, 81 mSDsCounter, 0 mSdLazyCounter, 38 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 115 SdHoareTripleChecker+Invalid, 39 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 38 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-11-19 05:02:41,085 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [14 Valid, 115 Invalid, 39 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 38 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-11-19 05:02:41,087 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2023-11-19 05:02:41,107 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 43. [2023-11-19 05:02:41,107 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 43 states, 20 states have (on average 1.2) internal successors, (24), 22 states have internal predecessors, (24), 18 states have call successors, (18), 4 states have call predecessors, (18), 4 states have return successors, (17), 16 states have call predecessors, (17), 17 states have call successors, (17) [2023-11-19 05:02:41,109 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 43 states to 43 states and 59 transitions. [2023-11-19 05:02:41,109 INFO L78 Accepts]: Start accepts. Automaton has 43 states and 59 transitions. Word has length 17 [2023-11-19 05:02:41,110 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 05:02:41,110 INFO L495 AbstractCegarLoop]: Abstraction has 43 states and 59 transitions. [2023-11-19 05:02:41,110 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 states have internal predecessors, (9), 1 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2023-11-19 05:02:41,111 INFO L276 IsEmpty]: Start isEmpty. Operand 43 states and 59 transitions. [2023-11-19 05:02:41,112 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2023-11-19 05:02:41,112 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 05:02:41,113 INFO L195 NwaCegarLoop]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-19 05:02:41,142 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2023-11-19 05:02:41,337 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 05:02:41,338 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 05:02:41,338 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 05:02:41,338 INFO L85 PathProgramCache]: Analyzing trace with hash 168504260, now seen corresponding path program 1 times [2023-11-19 05:02:41,339 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 05:02:41,339 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [37398973] [2023-11-19 05:02:41,339 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 05:02:41,339 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 05:02:41,349 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-19 05:02:41,350 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [895447040] [2023-11-19 05:02:41,352 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 05:02:41,352 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 05:02:41,352 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 05:02:41,357 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 05:02:41,367 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2023-11-19 05:02:41,412 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 05:02:41,413 INFO L262 TraceCheckSpWp]: Trace formula consists of 74 conjuncts, 9 conjunts are in the unsatisfiable core [2023-11-19 05:02:41,417 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-19 05:02:41,559 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2023-11-19 05:02:41,559 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-11-19 05:02:41,560 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 05:02:41,560 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [37398973] [2023-11-19 05:02:41,560 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-19 05:02:41,560 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [895447040] [2023-11-19 05:02:41,560 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [895447040] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-19 05:02:41,563 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-19 05:02:41,563 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2023-11-19 05:02:41,563 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1769142963] [2023-11-19 05:02:41,563 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-19 05:02:41,564 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-11-19 05:02:41,564 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 05:02:41,565 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-11-19 05:02:41,565 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2023-11-19 05:02:41,565 INFO L87 Difference]: Start difference. First operand 43 states and 59 transitions. Second operand has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 states have internal predecessors, (9), 1 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2023-11-19 05:02:41,696 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 05:02:41,697 INFO L93 Difference]: Finished difference Result 57 states and 74 transitions. [2023-11-19 05:02:41,697 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2023-11-19 05:02:41,697 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 states have internal predecessors, (9), 1 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) Word has length 22 [2023-11-19 05:02:41,698 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 05:02:41,701 INFO L225 Difference]: With dead ends: 57 [2023-11-19 05:02:41,701 INFO L226 Difference]: Without dead ends: 45 [2023-11-19 05:02:41,702 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 22 GetRequests, 18 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2023-11-19 05:02:41,705 INFO L413 NwaCegarLoop]: 31 mSDtfsCounter, 6 mSDsluCounter, 76 mSDsCounter, 0 mSdLazyCounter, 44 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 107 SdHoareTripleChecker+Invalid, 50 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 44 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-19 05:02:41,708 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [13 Valid, 107 Invalid, 50 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 44 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-19 05:02:41,713 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 45 states. [2023-11-19 05:02:41,731 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 45 to 45. [2023-11-19 05:02:41,732 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 45 states, 23 states have (on average 1.1304347826086956) internal successors, (26), 24 states have internal predecessors, (26), 16 states have call successors, (16), 5 states have call predecessors, (16), 5 states have return successors, (15), 15 states have call predecessors, (15), 15 states have call successors, (15) [2023-11-19 05:02:41,737 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 45 states to 45 states and 57 transitions. [2023-11-19 05:02:41,737 INFO L78 Accepts]: Start accepts. Automaton has 45 states and 57 transitions. Word has length 22 [2023-11-19 05:02:41,738 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 05:02:41,738 INFO L495 AbstractCegarLoop]: Abstraction has 45 states and 57 transitions. [2023-11-19 05:02:41,738 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 states have internal predecessors, (9), 1 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2023-11-19 05:02:41,738 INFO L276 IsEmpty]: Start isEmpty. Operand 45 states and 57 transitions. [2023-11-19 05:02:41,740 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2023-11-19 05:02:41,740 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 05:02:41,741 INFO L195 NwaCegarLoop]: trace histogram [7, 6, 6, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-19 05:02:41,767 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2023-11-19 05:02:41,951 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 05:02:41,951 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 05:02:41,952 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 05:02:41,952 INFO L85 PathProgramCache]: Analyzing trace with hash 1666200982, now seen corresponding path program 1 times [2023-11-19 05:02:41,952 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 05:02:41,952 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1701065451] [2023-11-19 05:02:41,952 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 05:02:41,952 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 05:02:41,964 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-19 05:02:41,965 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1155862839] [2023-11-19 05:02:41,965 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 05:02:41,965 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 05:02:41,965 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 05:02:41,966 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 05:02:41,991 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2023-11-19 05:02:42,026 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 05:02:42,027 INFO L262 TraceCheckSpWp]: Trace formula consists of 115 conjuncts, 5 conjunts are in the unsatisfiable core [2023-11-19 05:02:42,030 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-19 05:02:42,091 INFO L134 CoverageAnalysis]: Checked inductivity of 74 backedges. 30 proven. 2 refuted. 0 times theorem prover too weak. 42 trivial. 0 not checked. [2023-11-19 05:02:42,091 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-19 05:02:42,150 INFO L134 CoverageAnalysis]: Checked inductivity of 74 backedges. 12 proven. 2 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2023-11-19 05:02:42,151 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 05:02:42,151 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1701065451] [2023-11-19 05:02:42,151 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-19 05:02:42,151 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1155862839] [2023-11-19 05:02:42,151 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1155862839] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-19 05:02:42,151 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1072660593] [2023-11-19 05:02:42,172 INFO L159 IcfgInterpreter]: Started Sifa with 17 locations of interest [2023-11-19 05:02:42,172 INFO L166 IcfgInterpreter]: Building call graph [2023-11-19 05:02:42,175 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-19 05:02:42,181 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-19 05:02:42,181 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-19 05:02:44,519 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 6 for LOIs [2023-11-19 05:02:44,525 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-19 05:02:44,925 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1152#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-19 05:02:44,925 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-19 05:02:44,926 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-19 05:02:44,926 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 5] total 8 [2023-11-19 05:02:44,926 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1967695119] [2023-11-19 05:02:44,926 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-19 05:02:44,927 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2023-11-19 05:02:44,927 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 05:02:44,928 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2023-11-19 05:02:44,928 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=59, Invalid=181, Unknown=0, NotChecked=0, Total=240 [2023-11-19 05:02:44,928 INFO L87 Difference]: Start difference. First operand 45 states and 57 transitions. Second operand has 8 states, 8 states have (on average 2.875) internal successors, (23), 8 states have internal predecessors, (23), 3 states have call successors, (13), 3 states have call predecessors, (13), 3 states have return successors, (12), 3 states have call predecessors, (12), 3 states have call successors, (12) [2023-11-19 05:02:45,121 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 05:02:45,121 INFO L93 Difference]: Finished difference Result 115 states and 150 transitions. [2023-11-19 05:02:45,121 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2023-11-19 05:02:45,122 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 2.875) internal successors, (23), 8 states have internal predecessors, (23), 3 states have call successors, (13), 3 states have call predecessors, (13), 3 states have return successors, (12), 3 states have call predecessors, (12), 3 states have call successors, (12) Word has length 40 [2023-11-19 05:02:45,122 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 05:02:45,124 INFO L225 Difference]: With dead ends: 115 [2023-11-19 05:02:45,124 INFO L226 Difference]: Without dead ends: 99 [2023-11-19 05:02:45,125 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 121 GetRequests, 103 SyntacticMatches, 1 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 102 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=82, Invalid=260, Unknown=0, NotChecked=0, Total=342 [2023-11-19 05:02:45,126 INFO L413 NwaCegarLoop]: 29 mSDtfsCounter, 57 mSDsluCounter, 103 mSDsCounter, 0 mSdLazyCounter, 71 mSolverCounterSat, 17 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 57 SdHoareTripleChecker+Valid, 132 SdHoareTripleChecker+Invalid, 88 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 17 IncrementalHoareTripleChecker+Valid, 71 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-19 05:02:45,126 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [57 Valid, 132 Invalid, 88 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [17 Valid, 71 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-19 05:02:45,127 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 99 states. [2023-11-19 05:02:45,150 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 99 to 95. [2023-11-19 05:02:45,151 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 95 states, 46 states have (on average 1.1521739130434783) internal successors, (53), 49 states have internal predecessors, (53), 38 states have call successors, (38), 10 states have call predecessors, (38), 10 states have return successors, (35), 35 states have call predecessors, (35), 35 states have call successors, (35) [2023-11-19 05:02:45,153 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 95 states to 95 states and 126 transitions. [2023-11-19 05:02:45,153 INFO L78 Accepts]: Start accepts. Automaton has 95 states and 126 transitions. Word has length 40 [2023-11-19 05:02:45,153 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 05:02:45,153 INFO L495 AbstractCegarLoop]: Abstraction has 95 states and 126 transitions. [2023-11-19 05:02:45,154 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 2.875) internal successors, (23), 8 states have internal predecessors, (23), 3 states have call successors, (13), 3 states have call predecessors, (13), 3 states have return successors, (12), 3 states have call predecessors, (12), 3 states have call successors, (12) [2023-11-19 05:02:45,154 INFO L276 IsEmpty]: Start isEmpty. Operand 95 states and 126 transitions. [2023-11-19 05:02:45,155 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2023-11-19 05:02:45,155 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 05:02:45,155 INFO L195 NwaCegarLoop]: trace histogram [7, 6, 6, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-19 05:02:45,182 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2023-11-19 05:02:45,379 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 05:02:45,379 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 05:02:45,379 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 05:02:45,379 INFO L85 PathProgramCache]: Analyzing trace with hash -2136650998, now seen corresponding path program 1 times [2023-11-19 05:02:45,380 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 05:02:45,380 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [158392561] [2023-11-19 05:02:45,380 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 05:02:45,380 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 05:02:45,391 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-19 05:02:45,391 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1588839070] [2023-11-19 05:02:45,391 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 05:02:45,392 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 05:02:45,392 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 05:02:45,393 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 05:02:45,417 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2023-11-19 05:02:45,463 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 05:02:45,464 INFO L262 TraceCheckSpWp]: Trace formula consists of 115 conjuncts, 23 conjunts are in the unsatisfiable core [2023-11-19 05:02:45,468 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-19 05:02:45,575 INFO L134 CoverageAnalysis]: Checked inductivity of 76 backedges. 11 proven. 20 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2023-11-19 05:02:45,576 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-19 05:02:45,727 INFO L134 CoverageAnalysis]: Checked inductivity of 76 backedges. 14 proven. 17 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2023-11-19 05:02:45,727 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 05:02:45,728 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [158392561] [2023-11-19 05:02:45,728 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-19 05:02:45,728 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1588839070] [2023-11-19 05:02:45,728 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1588839070] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-19 05:02:45,728 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [2118171507] [2023-11-19 05:02:45,731 INFO L159 IcfgInterpreter]: Started Sifa with 15 locations of interest [2023-11-19 05:02:45,731 INFO L166 IcfgInterpreter]: Building call graph [2023-11-19 05:02:45,732 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-19 05:02:45,732 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-19 05:02:45,732 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-19 05:02:47,260 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 6 for LOIs [2023-11-19 05:02:47,265 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-19 05:02:47,734 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1737#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-19 05:02:47,735 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-19 05:02:47,735 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-19 05:02:47,735 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 13 [2023-11-19 05:02:47,735 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1651669355] [2023-11-19 05:02:47,735 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-19 05:02:47,736 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2023-11-19 05:02:47,736 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 05:02:47,737 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2023-11-19 05:02:47,737 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=82, Invalid=338, Unknown=0, NotChecked=0, Total=420 [2023-11-19 05:02:47,737 INFO L87 Difference]: Start difference. First operand 95 states and 126 transitions. Second operand has 13 states, 13 states have (on average 1.9230769230769231) internal successors, (25), 11 states have internal predecessors, (25), 5 states have call successors, (14), 3 states have call predecessors, (14), 2 states have return successors, (12), 4 states have call predecessors, (12), 5 states have call successors, (12) [2023-11-19 05:02:48,062 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 05:02:48,062 INFO L93 Difference]: Finished difference Result 113 states and 142 transitions. [2023-11-19 05:02:48,063 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2023-11-19 05:02:48,063 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 1.9230769230769231) internal successors, (25), 11 states have internal predecessors, (25), 5 states have call successors, (14), 3 states have call predecessors, (14), 2 states have return successors, (12), 4 states have call predecessors, (12), 5 states have call successors, (12) Word has length 40 [2023-11-19 05:02:48,063 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 05:02:48,067 INFO L225 Difference]: With dead ends: 113 [2023-11-19 05:02:48,067 INFO L226 Difference]: Without dead ends: 111 [2023-11-19 05:02:48,068 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 122 GetRequests, 97 SyntacticMatches, 2 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 168 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=114, Invalid=486, Unknown=0, NotChecked=0, Total=600 [2023-11-19 05:02:48,070 INFO L413 NwaCegarLoop]: 23 mSDtfsCounter, 25 mSDsluCounter, 106 mSDsCounter, 0 mSdLazyCounter, 200 mSolverCounterSat, 53 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 25 SdHoareTripleChecker+Valid, 129 SdHoareTripleChecker+Invalid, 253 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 53 IncrementalHoareTripleChecker+Valid, 200 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-11-19 05:02:48,070 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [25 Valid, 129 Invalid, 253 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [53 Valid, 200 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-11-19 05:02:48,071 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 111 states. [2023-11-19 05:02:48,122 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 111 to 111. [2023-11-19 05:02:48,122 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 111 states, 58 states have (on average 1.1206896551724137) internal successors, (65), 61 states have internal predecessors, (65), 38 states have call successors, (38), 14 states have call predecessors, (38), 14 states have return successors, (35), 35 states have call predecessors, (35), 35 states have call successors, (35) [2023-11-19 05:02:48,124 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 111 states to 111 states and 138 transitions. [2023-11-19 05:02:48,124 INFO L78 Accepts]: Start accepts. Automaton has 111 states and 138 transitions. Word has length 40 [2023-11-19 05:02:48,126 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 05:02:48,126 INFO L495 AbstractCegarLoop]: Abstraction has 111 states and 138 transitions. [2023-11-19 05:02:48,126 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 1.9230769230769231) internal successors, (25), 11 states have internal predecessors, (25), 5 states have call successors, (14), 3 states have call predecessors, (14), 2 states have return successors, (12), 4 states have call predecessors, (12), 5 states have call successors, (12) [2023-11-19 05:02:48,126 INFO L276 IsEmpty]: Start isEmpty. Operand 111 states and 138 transitions. [2023-11-19 05:02:48,127 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 46 [2023-11-19 05:02:48,127 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 05:02:48,128 INFO L195 NwaCegarLoop]: trace histogram [8, 7, 7, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-19 05:02:48,149 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2023-11-19 05:02:48,348 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 05:02:48,348 INFO L420 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 05:02:48,349 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 05:02:48,349 INFO L85 PathProgramCache]: Analyzing trace with hash 1054982331, now seen corresponding path program 2 times [2023-11-19 05:02:48,349 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 05:02:48,349 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1322921860] [2023-11-19 05:02:48,349 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 05:02:48,349 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 05:02:48,358 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-19 05:02:48,359 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [271974543] [2023-11-19 05:02:48,359 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-11-19 05:02:48,359 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 05:02:48,359 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 05:02:48,362 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 05:02:48,368 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2023-11-19 05:02:48,420 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 2 check-sat command(s) [2023-11-19 05:02:48,420 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-19 05:02:48,421 INFO L262 TraceCheckSpWp]: Trace formula consists of 79 conjuncts, 16 conjunts are in the unsatisfiable core [2023-11-19 05:02:48,424 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-19 05:02:48,505 INFO L134 CoverageAnalysis]: Checked inductivity of 103 backedges. 14 proven. 5 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2023-11-19 05:02:48,505 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-19 05:02:48,588 INFO L134 CoverageAnalysis]: Checked inductivity of 103 backedges. 14 proven. 5 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2023-11-19 05:02:48,588 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 05:02:48,588 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1322921860] [2023-11-19 05:02:48,589 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-19 05:02:48,589 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [271974543] [2023-11-19 05:02:48,589 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [271974543] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-19 05:02:48,589 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [862519880] [2023-11-19 05:02:48,592 INFO L159 IcfgInterpreter]: Started Sifa with 15 locations of interest [2023-11-19 05:02:48,592 INFO L166 IcfgInterpreter]: Building call graph [2023-11-19 05:02:48,592 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-19 05:02:48,592 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-19 05:02:48,593 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-19 05:02:49,926 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 6 for LOIs [2023-11-19 05:02:49,933 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-19 05:02:50,376 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '2365#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-19 05:02:50,376 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-19 05:02:50,376 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-19 05:02:50,376 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 10 [2023-11-19 05:02:50,377 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1477148355] [2023-11-19 05:02:50,377 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-19 05:02:50,377 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2023-11-19 05:02:50,377 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 05:02:50,378 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2023-11-19 05:02:50,378 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=60, Invalid=246, Unknown=0, NotChecked=0, Total=306 [2023-11-19 05:02:50,379 INFO L87 Difference]: Start difference. First operand 111 states and 138 transitions. Second operand has 10 states, 10 states have (on average 2.0) internal successors, (20), 8 states have internal predecessors, (20), 4 states have call successors, (16), 3 states have call predecessors, (16), 1 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) [2023-11-19 05:02:50,540 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 05:02:50,541 INFO L93 Difference]: Finished difference Result 117 states and 143 transitions. [2023-11-19 05:02:50,541 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2023-11-19 05:02:50,542 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 2.0) internal successors, (20), 8 states have internal predecessors, (20), 4 states have call successors, (16), 3 states have call predecessors, (16), 1 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) Word has length 45 [2023-11-19 05:02:50,542 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 05:02:50,546 INFO L225 Difference]: With dead ends: 117 [2023-11-19 05:02:50,546 INFO L226 Difference]: Without dead ends: 115 [2023-11-19 05:02:50,547 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 134 GetRequests, 115 SyntacticMatches, 2 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 91 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=66, Invalid=276, Unknown=0, NotChecked=0, Total=342 [2023-11-19 05:02:50,550 INFO L413 NwaCegarLoop]: 39 mSDtfsCounter, 8 mSDsluCounter, 173 mSDsCounter, 0 mSdLazyCounter, 97 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 16 SdHoareTripleChecker+Valid, 212 SdHoareTripleChecker+Invalid, 108 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 97 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-19 05:02:50,550 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [16 Valid, 212 Invalid, 108 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 97 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-19 05:02:50,552 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 115 states. [2023-11-19 05:02:50,603 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 115 to 115. [2023-11-19 05:02:50,605 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 115 states, 61 states have (on average 1.1147540983606556) internal successors, (68), 64 states have internal predecessors, (68), 38 states have call successors, (38), 15 states have call predecessors, (38), 15 states have return successors, (35), 35 states have call predecessors, (35), 35 states have call successors, (35) [2023-11-19 05:02:50,609 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 115 states to 115 states and 141 transitions. [2023-11-19 05:02:50,609 INFO L78 Accepts]: Start accepts. Automaton has 115 states and 141 transitions. Word has length 45 [2023-11-19 05:02:50,610 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 05:02:50,610 INFO L495 AbstractCegarLoop]: Abstraction has 115 states and 141 transitions. [2023-11-19 05:02:50,611 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 2.0) internal successors, (20), 8 states have internal predecessors, (20), 4 states have call successors, (16), 3 states have call predecessors, (16), 1 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) [2023-11-19 05:02:50,611 INFO L276 IsEmpty]: Start isEmpty. Operand 115 states and 141 transitions. [2023-11-19 05:02:50,618 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2023-11-19 05:02:50,620 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 05:02:50,620 INFO L195 NwaCegarLoop]: trace histogram [9, 8, 8, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1] [2023-11-19 05:02:50,642 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2023-11-19 05:02:50,838 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,7 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 05:02:50,839 INFO L420 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 05:02:50,839 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 05:02:50,839 INFO L85 PathProgramCache]: Analyzing trace with hash -615691926, now seen corresponding path program 3 times [2023-11-19 05:02:50,840 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 05:02:50,840 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [363655952] [2023-11-19 05:02:50,840 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 05:02:50,840 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 05:02:50,848 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-19 05:02:50,849 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1362797146] [2023-11-19 05:02:50,849 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2023-11-19 05:02:50,849 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 05:02:50,849 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 05:02:50,850 INFO L229 MonitoredProcess]: Starting monitored process 8 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 05:02:50,873 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2023-11-19 05:02:50,914 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2023-11-19 05:02:50,915 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-19 05:02:50,916 INFO L262 TraceCheckSpWp]: Trace formula consists of 133 conjuncts, 19 conjunts are in the unsatisfiable core [2023-11-19 05:02:50,918 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-19 05:02:51,039 INFO L134 CoverageAnalysis]: Checked inductivity of 134 backedges. 16 proven. 6 refuted. 0 times theorem prover too weak. 112 trivial. 0 not checked. [2023-11-19 05:02:51,040 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-19 05:02:51,178 INFO L134 CoverageAnalysis]: Checked inductivity of 134 backedges. 16 proven. 6 refuted. 0 times theorem prover too weak. 112 trivial. 0 not checked. [2023-11-19 05:02:51,179 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 05:02:51,179 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [363655952] [2023-11-19 05:02:51,179 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-19 05:02:51,179 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1362797146] [2023-11-19 05:02:51,179 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1362797146] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-19 05:02:51,179 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1600585711] [2023-11-19 05:02:51,181 INFO L159 IcfgInterpreter]: Started Sifa with 15 locations of interest [2023-11-19 05:02:51,182 INFO L166 IcfgInterpreter]: Building call graph [2023-11-19 05:02:51,182 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-19 05:02:51,182 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-19 05:02:51,182 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-19 05:02:52,433 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 6 for LOIs [2023-11-19 05:02:52,440 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-19 05:02:52,849 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '3025#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-19 05:02:52,849 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-19 05:02:52,849 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-19 05:02:52,849 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 8 [2023-11-19 05:02:52,849 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1843881704] [2023-11-19 05:02:52,849 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-19 05:02:52,850 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2023-11-19 05:02:52,850 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 05:02:52,851 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2023-11-19 05:02:52,851 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=53, Invalid=187, Unknown=0, NotChecked=0, Total=240 [2023-11-19 05:02:52,851 INFO L87 Difference]: Start difference. First operand 115 states and 141 transitions. Second operand has 8 states, 8 states have (on average 2.25) internal successors, (18), 7 states have internal predecessors, (18), 4 states have call successors, (18), 2 states have call predecessors, (18), 1 states have return successors, (16), 4 states have call predecessors, (16), 4 states have call successors, (16) [2023-11-19 05:02:53,085 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 05:02:53,085 INFO L93 Difference]: Finished difference Result 141 states and 163 transitions. [2023-11-19 05:02:53,086 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2023-11-19 05:02:53,086 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 2.25) internal successors, (18), 7 states have internal predecessors, (18), 4 states have call successors, (18), 2 states have call predecessors, (18), 1 states have return successors, (16), 4 states have call predecessors, (16), 4 states have call successors, (16) Word has length 50 [2023-11-19 05:02:53,086 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 05:02:53,088 INFO L225 Difference]: With dead ends: 141 [2023-11-19 05:02:53,088 INFO L226 Difference]: Without dead ends: 130 [2023-11-19 05:02:53,089 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 150 GetRequests, 130 SyntacticMatches, 4 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 73 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=66, Invalid=240, Unknown=0, NotChecked=0, Total=306 [2023-11-19 05:02:53,089 INFO L413 NwaCegarLoop]: 31 mSDtfsCounter, 12 mSDsluCounter, 110 mSDsCounter, 0 mSdLazyCounter, 79 mSolverCounterSat, 38 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 19 SdHoareTripleChecker+Valid, 141 SdHoareTripleChecker+Invalid, 117 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 38 IncrementalHoareTripleChecker+Valid, 79 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-11-19 05:02:53,090 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [19 Valid, 141 Invalid, 117 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [38 Valid, 79 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-11-19 05:02:53,090 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 130 states. [2023-11-19 05:02:53,114 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 130 to 130. [2023-11-19 05:02:53,115 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 130 states, 79 states have (on average 1.0886075949367089) internal successors, (86), 82 states have internal predecessors, (86), 29 states have call successors, (29), 21 states have call predecessors, (29), 21 states have return successors, (26), 26 states have call predecessors, (26), 26 states have call successors, (26) [2023-11-19 05:02:53,116 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 130 states to 130 states and 141 transitions. [2023-11-19 05:02:53,117 INFO L78 Accepts]: Start accepts. Automaton has 130 states and 141 transitions. Word has length 50 [2023-11-19 05:02:53,117 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 05:02:53,117 INFO L495 AbstractCegarLoop]: Abstraction has 130 states and 141 transitions. [2023-11-19 05:02:53,117 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 2.25) internal successors, (18), 7 states have internal predecessors, (18), 4 states have call successors, (18), 2 states have call predecessors, (18), 1 states have return successors, (16), 4 states have call predecessors, (16), 4 states have call successors, (16) [2023-11-19 05:02:53,118 INFO L276 IsEmpty]: Start isEmpty. Operand 130 states and 141 transitions. [2023-11-19 05:02:53,119 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 67 [2023-11-19 05:02:53,119 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 05:02:53,119 INFO L195 NwaCegarLoop]: trace histogram [12, 11, 11, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-19 05:02:53,144 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2023-11-19 05:02:53,337 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 8 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2023-11-19 05:02:53,337 INFO L420 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 05:02:53,338 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 05:02:53,338 INFO L85 PathProgramCache]: Analyzing trace with hash -1733391679, now seen corresponding path program 1 times [2023-11-19 05:02:53,338 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 05:02:53,338 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [884532834] [2023-11-19 05:02:53,338 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 05:02:53,338 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 05:02:53,346 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-19 05:02:53,347 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [443615702] [2023-11-19 05:02:53,347 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 05:02:53,347 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 05:02:53,347 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 05:02:53,348 INFO L229 MonitoredProcess]: Starting monitored process 9 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 05:02:53,352 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2023-11-19 05:02:53,415 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 05:02:53,416 INFO L262 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 29 conjunts are in the unsatisfiable core [2023-11-19 05:02:53,419 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-19 05:02:53,782 INFO L134 CoverageAnalysis]: Checked inductivity of 250 backedges. 21 proven. 39 refuted. 0 times theorem prover too weak. 190 trivial. 0 not checked. [2023-11-19 05:02:53,782 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-19 05:02:54,032 INFO L134 CoverageAnalysis]: Checked inductivity of 250 backedges. 24 proven. 36 refuted. 0 times theorem prover too weak. 190 trivial. 0 not checked. [2023-11-19 05:02:54,032 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 05:02:54,032 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [884532834] [2023-11-19 05:02:54,033 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-19 05:02:54,033 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [443615702] [2023-11-19 05:02:54,033 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [443615702] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-19 05:02:54,033 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [629759448] [2023-11-19 05:02:54,035 INFO L159 IcfgInterpreter]: Started Sifa with 17 locations of interest [2023-11-19 05:02:54,036 INFO L166 IcfgInterpreter]: Building call graph [2023-11-19 05:02:54,036 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-19 05:02:54,036 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-19 05:02:54,036 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-19 05:02:55,363 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 6 for LOIs [2023-11-19 05:02:55,368 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-19 05:02:55,994 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '3831#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-19 05:02:55,995 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-19 05:02:55,995 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-19 05:02:55,995 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 8] total 14 [2023-11-19 05:02:55,995 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1533897568] [2023-11-19 05:02:55,995 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-19 05:02:55,996 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2023-11-19 05:02:55,996 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 05:02:55,997 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2023-11-19 05:02:55,997 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=85, Invalid=377, Unknown=0, NotChecked=0, Total=462 [2023-11-19 05:02:55,997 INFO L87 Difference]: Start difference. First operand 130 states and 141 transitions. Second operand has 14 states, 12 states have (on average 2.25) internal successors, (27), 12 states have internal predecessors, (27), 7 states have call successors, (24), 3 states have call predecessors, (24), 2 states have return successors, (22), 6 states have call predecessors, (22), 7 states have call successors, (22) [2023-11-19 05:02:56,332 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 05:02:56,332 INFO L93 Difference]: Finished difference Result 146 states and 158 transitions. [2023-11-19 05:02:56,333 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2023-11-19 05:02:56,333 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 12 states have (on average 2.25) internal successors, (27), 12 states have internal predecessors, (27), 7 states have call successors, (24), 3 states have call predecessors, (24), 2 states have return successors, (22), 6 states have call predecessors, (22), 7 states have call successors, (22) Word has length 66 [2023-11-19 05:02:56,334 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 05:02:56,336 INFO L225 Difference]: With dead ends: 146 [2023-11-19 05:02:56,336 INFO L226 Difference]: Without dead ends: 142 [2023-11-19 05:02:56,337 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 202 GetRequests, 175 SyntacticMatches, 2 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 184 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=129, Invalid=573, Unknown=0, NotChecked=0, Total=702 [2023-11-19 05:02:56,338 INFO L413 NwaCegarLoop]: 20 mSDtfsCounter, 22 mSDsluCounter, 88 mSDsCounter, 0 mSdLazyCounter, 131 mSolverCounterSat, 34 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 23 SdHoareTripleChecker+Valid, 108 SdHoareTripleChecker+Invalid, 165 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 34 IncrementalHoareTripleChecker+Valid, 131 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-11-19 05:02:56,338 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [23 Valid, 108 Invalid, 165 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [34 Valid, 131 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-11-19 05:02:56,339 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 142 states. [2023-11-19 05:02:56,376 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 142 to 142. [2023-11-19 05:02:56,377 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 142 states, 87 states have (on average 1.0689655172413792) internal successors, (93), 90 states have internal predecessors, (93), 31 states have call successors, (31), 24 states have call predecessors, (31), 23 states have return successors, (28), 27 states have call predecessors, (28), 28 states have call successors, (28) [2023-11-19 05:02:56,378 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 142 states to 142 states and 152 transitions. [2023-11-19 05:02:56,378 INFO L78 Accepts]: Start accepts. Automaton has 142 states and 152 transitions. Word has length 66 [2023-11-19 05:02:56,378 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 05:02:56,379 INFO L495 AbstractCegarLoop]: Abstraction has 142 states and 152 transitions. [2023-11-19 05:02:56,379 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 12 states have (on average 2.25) internal successors, (27), 12 states have internal predecessors, (27), 7 states have call successors, (24), 3 states have call predecessors, (24), 2 states have return successors, (22), 6 states have call predecessors, (22), 7 states have call successors, (22) [2023-11-19 05:02:56,379 INFO L276 IsEmpty]: Start isEmpty. Operand 142 states and 152 transitions. [2023-11-19 05:02:56,380 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 72 [2023-11-19 05:02:56,380 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 05:02:56,380 INFO L195 NwaCegarLoop]: trace histogram [13, 12, 12, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-19 05:02:56,406 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2023-11-19 05:02:56,590 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,9 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 05:02:56,591 INFO L420 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 05:02:56,591 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 05:02:56,591 INFO L85 PathProgramCache]: Analyzing trace with hash 2124427812, now seen corresponding path program 1 times [2023-11-19 05:02:56,591 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 05:02:56,591 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1208663041] [2023-11-19 05:02:56,591 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 05:02:56,591 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 05:02:56,605 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-19 05:02:56,611 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1716079744] [2023-11-19 05:02:56,611 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 05:02:56,611 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 05:02:56,611 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 05:02:56,612 INFO L229 MonitoredProcess]: Starting monitored process 10 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 05:02:56,636 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2023-11-19 05:02:56,680 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 05:02:56,682 INFO L262 TraceCheckSpWp]: Trace formula consists of 170 conjuncts, 27 conjunts are in the unsatisfiable core [2023-11-19 05:02:56,685 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-19 05:02:57,023 INFO L134 CoverageAnalysis]: Checked inductivity of 296 backedges. 23 proven. 42 refuted. 0 times theorem prover too weak. 231 trivial. 0 not checked. [2023-11-19 05:02:57,023 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-19 05:02:57,341 INFO L134 CoverageAnalysis]: Checked inductivity of 296 backedges. 23 proven. 42 refuted. 0 times theorem prover too weak. 231 trivial. 0 not checked. [2023-11-19 05:02:57,341 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 05:02:57,342 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1208663041] [2023-11-19 05:02:57,342 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-19 05:02:57,342 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1716079744] [2023-11-19 05:02:57,342 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1716079744] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-19 05:02:57,342 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1785964098] [2023-11-19 05:02:57,344 INFO L159 IcfgInterpreter]: Started Sifa with 18 locations of interest [2023-11-19 05:02:57,344 INFO L166 IcfgInterpreter]: Building call graph [2023-11-19 05:02:57,345 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-19 05:02:57,345 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-19 05:02:57,345 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-19 05:02:58,380 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 6 for LOIs [2023-11-19 05:02:58,385 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-19 05:02:58,845 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '4693#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-19 05:02:58,845 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-19 05:02:58,845 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-19 05:02:58,845 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 15 [2023-11-19 05:02:58,846 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1925322115] [2023-11-19 05:02:58,846 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-19 05:02:58,846 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2023-11-19 05:02:58,846 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 05:02:58,847 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2023-11-19 05:02:58,849 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=94, Invalid=412, Unknown=0, NotChecked=0, Total=506 [2023-11-19 05:02:58,850 INFO L87 Difference]: Start difference. First operand 142 states and 152 transitions. Second operand has 15 states, 13 states have (on average 2.076923076923077) internal successors, (27), 13 states have internal predecessors, (27), 7 states have call successors, (26), 3 states have call predecessors, (26), 2 states have return successors, (24), 6 states have call predecessors, (24), 7 states have call successors, (24) [2023-11-19 05:02:59,362 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 05:02:59,362 INFO L93 Difference]: Finished difference Result 162 states and 179 transitions. [2023-11-19 05:02:59,363 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2023-11-19 05:02:59,363 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 13 states have (on average 2.076923076923077) internal successors, (27), 13 states have internal predecessors, (27), 7 states have call successors, (26), 3 states have call predecessors, (26), 2 states have return successors, (24), 6 states have call predecessors, (24), 7 states have call successors, (24) Word has length 71 [2023-11-19 05:02:59,363 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 05:02:59,364 INFO L225 Difference]: With dead ends: 162 [2023-11-19 05:02:59,365 INFO L226 Difference]: Without dead ends: 133 [2023-11-19 05:02:59,366 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 217 GetRequests, 188 SyntacticMatches, 2 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 221 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=154, Invalid=658, Unknown=0, NotChecked=0, Total=812 [2023-11-19 05:02:59,367 INFO L413 NwaCegarLoop]: 20 mSDtfsCounter, 16 mSDsluCounter, 190 mSDsCounter, 0 mSdLazyCounter, 263 mSolverCounterSat, 22 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 21 SdHoareTripleChecker+Valid, 210 SdHoareTripleChecker+Invalid, 285 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 22 IncrementalHoareTripleChecker+Valid, 263 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2023-11-19 05:02:59,367 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [21 Valid, 210 Invalid, 285 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [22 Valid, 263 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2023-11-19 05:02:59,368 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 133 states. [2023-11-19 05:02:59,407 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 133 to 132. [2023-11-19 05:02:59,408 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 132 states, 80 states have (on average 1.05) internal successors, (84), 82 states have internal predecessors, (84), 30 states have call successors, (30), 21 states have call predecessors, (30), 21 states have return successors, (29), 28 states have call predecessors, (29), 29 states have call successors, (29) [2023-11-19 05:02:59,409 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 132 states to 132 states and 143 transitions. [2023-11-19 05:02:59,409 INFO L78 Accepts]: Start accepts. Automaton has 132 states and 143 transitions. Word has length 71 [2023-11-19 05:02:59,409 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 05:02:59,409 INFO L495 AbstractCegarLoop]: Abstraction has 132 states and 143 transitions. [2023-11-19 05:02:59,410 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 13 states have (on average 2.076923076923077) internal successors, (27), 13 states have internal predecessors, (27), 7 states have call successors, (26), 3 states have call predecessors, (26), 2 states have return successors, (24), 6 states have call predecessors, (24), 7 states have call successors, (24) [2023-11-19 05:02:59,410 INFO L276 IsEmpty]: Start isEmpty. Operand 132 states and 143 transitions. [2023-11-19 05:02:59,411 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 74 [2023-11-19 05:02:59,411 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 05:02:59,411 INFO L195 NwaCegarLoop]: trace histogram [13, 12, 12, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1] [2023-11-19 05:02:59,436 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2023-11-19 05:02:59,631 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable11 [2023-11-19 05:02:59,631 INFO L420 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 05:02:59,631 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 05:02:59,631 INFO L85 PathProgramCache]: Analyzing trace with hash -1181636523, now seen corresponding path program 4 times [2023-11-19 05:02:59,632 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 05:02:59,632 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [127751830] [2023-11-19 05:02:59,632 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 05:02:59,632 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 05:02:59,644 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-19 05:02:59,645 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2017879281] [2023-11-19 05:02:59,645 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2023-11-19 05:02:59,651 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 05:02:59,652 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 05:02:59,653 INFO L229 MonitoredProcess]: Starting monitored process 11 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 05:02:59,656 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2023-11-19 05:02:59,710 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 05:02:59,711 INFO L262 TraceCheckSpWp]: Trace formula consists of 183 conjuncts, 31 conjunts are in the unsatisfiable core [2023-11-19 05:02:59,714 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-19 05:02:59,875 INFO L134 CoverageAnalysis]: Checked inductivity of 306 backedges. 23 proven. 52 refuted. 0 times theorem prover too weak. 231 trivial. 0 not checked. [2023-11-19 05:02:59,876 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-19 05:03:00,071 INFO L134 CoverageAnalysis]: Checked inductivity of 306 backedges. 23 proven. 52 refuted. 0 times theorem prover too weak. 231 trivial. 0 not checked. [2023-11-19 05:03:00,071 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 05:03:00,071 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [127751830] [2023-11-19 05:03:00,071 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-19 05:03:00,071 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2017879281] [2023-11-19 05:03:00,071 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2017879281] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-19 05:03:00,072 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1169536816] [2023-11-19 05:03:00,073 INFO L159 IcfgInterpreter]: Started Sifa with 15 locations of interest [2023-11-19 05:03:00,074 INFO L166 IcfgInterpreter]: Building call graph [2023-11-19 05:03:00,074 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-19 05:03:00,074 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-19 05:03:00,074 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-19 05:03:00,979 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 6 for LOIs [2023-11-19 05:03:00,983 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-19 05:03:01,435 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '5581#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-19 05:03:01,436 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-19 05:03:01,436 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-19 05:03:01,436 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 15 [2023-11-19 05:03:01,436 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1805335082] [2023-11-19 05:03:01,436 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-19 05:03:01,436 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2023-11-19 05:03:01,437 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 05:03:01,437 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2023-11-19 05:03:01,437 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=91, Invalid=415, Unknown=0, NotChecked=0, Total=506 [2023-11-19 05:03:01,438 INFO L87 Difference]: Start difference. First operand 132 states and 143 transitions. Second operand has 15 states, 15 states have (on average 2.066666666666667) internal successors, (31), 13 states have internal predecessors, (31), 7 states have call successors, (26), 3 states have call predecessors, (26), 2 states have return successors, (24), 6 states have call predecessors, (24), 7 states have call successors, (24) [2023-11-19 05:03:02,826 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.04s for a HTC check with result VALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-11-19 05:03:03,071 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 05:03:03,071 INFO L93 Difference]: Finished difference Result 138 states and 148 transitions. [2023-11-19 05:03:03,074 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2023-11-19 05:03:03,075 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 15 states have (on average 2.066666666666667) internal successors, (31), 13 states have internal predecessors, (31), 7 states have call successors, (26), 3 states have call predecessors, (26), 2 states have return successors, (24), 6 states have call predecessors, (24), 7 states have call successors, (24) Word has length 73 [2023-11-19 05:03:03,075 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 05:03:03,076 INFO L225 Difference]: With dead ends: 138 [2023-11-19 05:03:03,077 INFO L226 Difference]: Without dead ends: 136 [2023-11-19 05:03:03,077 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 222 GetRequests, 193 SyntacticMatches, 3 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 219 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=133, Invalid=623, Unknown=0, NotChecked=0, Total=756 [2023-11-19 05:03:03,078 INFO L413 NwaCegarLoop]: 27 mSDtfsCounter, 28 mSDsluCounter, 152 mSDsCounter, 0 mSdLazyCounter, 224 mSolverCounterSat, 45 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 28 SdHoareTripleChecker+Valid, 179 SdHoareTripleChecker+Invalid, 269 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 45 IncrementalHoareTripleChecker+Valid, 224 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.5s IncrementalHoareTripleChecker+Time [2023-11-19 05:03:03,078 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [28 Valid, 179 Invalid, 269 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [45 Valid, 224 Invalid, 0 Unknown, 0 Unchecked, 1.5s Time] [2023-11-19 05:03:03,079 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 136 states. [2023-11-19 05:03:03,122 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 136 to 136. [2023-11-19 05:03:03,123 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 136 states, 83 states have (on average 1.036144578313253) internal successors, (86), 85 states have internal predecessors, (86), 30 states have call successors, (30), 22 states have call predecessors, (30), 22 states have return successors, (29), 28 states have call predecessors, (29), 29 states have call successors, (29) [2023-11-19 05:03:03,124 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 136 states to 136 states and 145 transitions. [2023-11-19 05:03:03,124 INFO L78 Accepts]: Start accepts. Automaton has 136 states and 145 transitions. Word has length 73 [2023-11-19 05:03:03,124 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 05:03:03,125 INFO L495 AbstractCegarLoop]: Abstraction has 136 states and 145 transitions. [2023-11-19 05:03:03,125 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 2.066666666666667) internal successors, (31), 13 states have internal predecessors, (31), 7 states have call successors, (26), 3 states have call predecessors, (26), 2 states have return successors, (24), 6 states have call predecessors, (24), 7 states have call successors, (24) [2023-11-19 05:03:03,125 INFO L276 IsEmpty]: Start isEmpty. Operand 136 states and 145 transitions. [2023-11-19 05:03:03,126 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 125 [2023-11-19 05:03:03,127 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 05:03:03,127 INFO L195 NwaCegarLoop]: trace histogram [22, 21, 21, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1] [2023-11-19 05:03:03,143 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2023-11-19 05:03:03,338 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2023-11-19 05:03:03,339 INFO L420 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 05:03:03,339 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 05:03:03,339 INFO L85 PathProgramCache]: Analyzing trace with hash -1753860344, now seen corresponding path program 2 times [2023-11-19 05:03:03,339 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 05:03:03,339 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1891776966] [2023-11-19 05:03:03,339 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 05:03:03,339 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 05:03:03,369 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-19 05:03:03,369 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [982288217] [2023-11-19 05:03:03,369 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-11-19 05:03:03,370 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 05:03:03,370 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 05:03:03,371 INFO L229 MonitoredProcess]: Starting monitored process 12 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 05:03:03,390 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2023-11-19 05:03:03,546 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 10 check-sat command(s) [2023-11-19 05:03:03,546 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-19 05:03:03,548 INFO L262 TraceCheckSpWp]: Trace formula consists of 265 conjuncts, 11 conjunts are in the unsatisfiable core [2023-11-19 05:03:03,552 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-19 05:03:03,717 INFO L134 CoverageAnalysis]: Checked inductivity of 938 backedges. 120 proven. 656 refuted. 0 times theorem prover too weak. 162 trivial. 0 not checked. [2023-11-19 05:03:03,718 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-19 05:03:03,889 INFO L134 CoverageAnalysis]: Checked inductivity of 938 backedges. 42 proven. 56 refuted. 0 times theorem prover too weak. 840 trivial. 0 not checked. [2023-11-19 05:03:03,890 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 05:03:03,890 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1891776966] [2023-11-19 05:03:03,890 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-19 05:03:03,890 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [982288217] [2023-11-19 05:03:03,890 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [982288217] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-19 05:03:03,890 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1460345812] [2023-11-19 05:03:03,894 INFO L159 IcfgInterpreter]: Started Sifa with 17 locations of interest [2023-11-19 05:03:03,894 INFO L166 IcfgInterpreter]: Building call graph [2023-11-19 05:03:03,895 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-19 05:03:03,895 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-19 05:03:03,896 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-19 05:03:04,882 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 6 for LOIs [2023-11-19 05:03:04,886 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-19 05:03:05,277 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '6739#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-19 05:03:05,277 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-19 05:03:05,277 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-19 05:03:05,278 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 8] total 14 [2023-11-19 05:03:05,278 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1604503672] [2023-11-19 05:03:05,278 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-19 05:03:05,279 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2023-11-19 05:03:05,279 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 05:03:05,280 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2023-11-19 05:03:05,280 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=128, Invalid=334, Unknown=0, NotChecked=0, Total=462 [2023-11-19 05:03:05,280 INFO L87 Difference]: Start difference. First operand 136 states and 145 transitions. Second operand has 14 states, 14 states have (on average 3.5714285714285716) internal successors, (50), 14 states have internal predecessors, (50), 9 states have call successors, (43), 6 states have call predecessors, (43), 6 states have return successors, (42), 9 states have call predecessors, (42), 9 states have call successors, (42) [2023-11-19 05:03:05,769 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 05:03:05,769 INFO L93 Difference]: Finished difference Result 376 states and 391 transitions. [2023-11-19 05:03:05,769 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2023-11-19 05:03:05,770 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 3.5714285714285716) internal successors, (50), 14 states have internal predecessors, (50), 9 states have call successors, (43), 6 states have call predecessors, (43), 6 states have return successors, (42), 9 states have call predecessors, (42), 9 states have call successors, (42) Word has length 124 [2023-11-19 05:03:05,770 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 05:03:05,772 INFO L225 Difference]: With dead ends: 376 [2023-11-19 05:03:05,772 INFO L226 Difference]: Without dead ends: 353 [2023-11-19 05:03:05,773 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 379 GetRequests, 346 SyntacticMatches, 4 SemanticMatches, 29 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 351 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=250, Invalid=680, Unknown=0, NotChecked=0, Total=930 [2023-11-19 05:03:05,773 INFO L413 NwaCegarLoop]: 23 mSDtfsCounter, 105 mSDsluCounter, 103 mSDsCounter, 0 mSdLazyCounter, 153 mSolverCounterSat, 31 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 105 SdHoareTripleChecker+Valid, 126 SdHoareTripleChecker+Invalid, 184 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 31 IncrementalHoareTripleChecker+Valid, 153 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-11-19 05:03:05,773 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [105 Valid, 126 Invalid, 184 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [31 Valid, 153 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-11-19 05:03:05,774 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 353 states. [2023-11-19 05:03:05,869 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 353 to 311. [2023-11-19 05:03:05,870 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 311 states, 195 states have (on average 1.041025641025641) internal successors, (203), 201 states have internal predecessors, (203), 62 states have call successors, (62), 54 states have call predecessors, (62), 53 states have return successors, (60), 55 states have call predecessors, (60), 60 states have call successors, (60) [2023-11-19 05:03:05,873 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 311 states to 311 states and 325 transitions. [2023-11-19 05:03:05,873 INFO L78 Accepts]: Start accepts. Automaton has 311 states and 325 transitions. Word has length 124 [2023-11-19 05:03:05,873 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 05:03:05,873 INFO L495 AbstractCegarLoop]: Abstraction has 311 states and 325 transitions. [2023-11-19 05:03:05,874 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 3.5714285714285716) internal successors, (50), 14 states have internal predecessors, (50), 9 states have call successors, (43), 6 states have call predecessors, (43), 6 states have return successors, (42), 9 states have call predecessors, (42), 9 states have call successors, (42) [2023-11-19 05:03:05,874 INFO L276 IsEmpty]: Start isEmpty. Operand 311 states and 325 transitions. [2023-11-19 05:03:05,876 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 156 [2023-11-19 05:03:05,876 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 05:03:05,876 INFO L195 NwaCegarLoop]: trace histogram [28, 27, 27, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-19 05:03:05,896 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2023-11-19 05:03:06,094 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable13,12 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 05:03:06,095 INFO L420 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 05:03:06,095 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 05:03:06,095 INFO L85 PathProgramCache]: Analyzing trace with hash 460751474, now seen corresponding path program 2 times [2023-11-19 05:03:06,095 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 05:03:06,095 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [748960799] [2023-11-19 05:03:06,095 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 05:03:06,095 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 05:03:06,104 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-19 05:03:06,105 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1708329460] [2023-11-19 05:03:06,105 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-11-19 05:03:06,105 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 05:03:06,105 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 05:03:06,106 INFO L229 MonitoredProcess]: Starting monitored process 13 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 05:03:06,110 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2023-11-19 05:03:06,207 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2023-11-19 05:03:06,207 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-19 05:03:06,208 INFO L262 TraceCheckSpWp]: Trace formula consists of 171 conjuncts, 42 conjunts are in the unsatisfiable core [2023-11-19 05:03:06,214 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-19 05:03:07,137 INFO L134 CoverageAnalysis]: Checked inductivity of 1538 backedges. 341 proven. 46 refuted. 0 times theorem prover too weak. 1151 trivial. 0 not checked. [2023-11-19 05:03:07,137 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-19 05:03:07,948 INFO L134 CoverageAnalysis]: Checked inductivity of 1538 backedges. 215 proven. 24 refuted. 0 times theorem prover too weak. 1299 trivial. 0 not checked. [2023-11-19 05:03:07,948 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 05:03:07,948 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [748960799] [2023-11-19 05:03:07,948 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-19 05:03:07,949 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1708329460] [2023-11-19 05:03:07,949 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1708329460] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-19 05:03:07,949 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [592717245] [2023-11-19 05:03:07,951 INFO L159 IcfgInterpreter]: Started Sifa with 18 locations of interest [2023-11-19 05:03:07,951 INFO L166 IcfgInterpreter]: Building call graph [2023-11-19 05:03:07,951 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-19 05:03:07,952 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-19 05:03:07,952 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-19 05:03:08,921 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 6 for LOIs [2023-11-19 05:03:08,926 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-19 05:03:09,681 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '8668#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-19 05:03:09,682 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-19 05:03:09,682 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-19 05:03:09,682 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 9] total 17 [2023-11-19 05:03:09,682 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [436256068] [2023-11-19 05:03:09,682 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-19 05:03:09,683 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2023-11-19 05:03:09,683 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 05:03:09,684 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2023-11-19 05:03:09,684 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=110, Invalid=490, Unknown=0, NotChecked=0, Total=600 [2023-11-19 05:03:09,685 INFO L87 Difference]: Start difference. First operand 311 states and 325 transitions. Second operand has 17 states, 13 states have (on average 2.4615384615384617) internal successors, (32), 13 states have internal predecessors, (32), 9 states have call successors, (31), 3 states have call predecessors, (31), 2 states have return successors, (31), 8 states have call predecessors, (31), 9 states have call successors, (31) [2023-11-19 05:03:11,516 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 05:03:11,516 INFO L93 Difference]: Finished difference Result 318 states and 331 transitions. [2023-11-19 05:03:11,517 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2023-11-19 05:03:11,517 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 13 states have (on average 2.4615384615384617) internal successors, (32), 13 states have internal predecessors, (32), 9 states have call successors, (31), 3 states have call predecessors, (31), 2 states have return successors, (31), 8 states have call predecessors, (31), 9 states have call successors, (31) Word has length 155 [2023-11-19 05:03:11,518 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 05:03:11,519 INFO L225 Difference]: With dead ends: 318 [2023-11-19 05:03:11,520 INFO L226 Difference]: Without dead ends: 292 [2023-11-19 05:03:11,520 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 467 GetRequests, 434 SyntacticMatches, 6 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 302 ImplicationChecksByTransitivity, 2.0s TimeCoverageRelationStatistics Valid=150, Invalid=662, Unknown=0, NotChecked=0, Total=812 [2023-11-19 05:03:11,521 INFO L413 NwaCegarLoop]: 22 mSDtfsCounter, 18 mSDsluCounter, 135 mSDsCounter, 0 mSdLazyCounter, 184 mSolverCounterSat, 22 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 21 SdHoareTripleChecker+Valid, 157 SdHoareTripleChecker+Invalid, 206 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 22 IncrementalHoareTripleChecker+Valid, 184 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.0s IncrementalHoareTripleChecker+Time [2023-11-19 05:03:11,521 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [21 Valid, 157 Invalid, 206 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [22 Valid, 184 Invalid, 0 Unknown, 0 Unchecked, 1.0s Time] [2023-11-19 05:03:11,522 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 292 states. [2023-11-19 05:03:11,624 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 292 to 292. [2023-11-19 05:03:11,624 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 292 states, 187 states have (on average 1.0106951871657754) internal successors, (189), 188 states have internal predecessors, (189), 53 states have call successors, (53), 51 states have call predecessors, (53), 51 states have return successors, (52), 52 states have call predecessors, (52), 52 states have call successors, (52) [2023-11-19 05:03:11,626 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 292 states to 292 states and 294 transitions. [2023-11-19 05:03:11,626 INFO L78 Accepts]: Start accepts. Automaton has 292 states and 294 transitions. Word has length 155 [2023-11-19 05:03:11,627 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 05:03:11,627 INFO L495 AbstractCegarLoop]: Abstraction has 292 states and 294 transitions. [2023-11-19 05:03:11,627 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 13 states have (on average 2.4615384615384617) internal successors, (32), 13 states have internal predecessors, (32), 9 states have call successors, (31), 3 states have call predecessors, (31), 2 states have return successors, (31), 8 states have call predecessors, (31), 9 states have call successors, (31) [2023-11-19 05:03:11,627 INFO L276 IsEmpty]: Start isEmpty. Operand 292 states and 294 transitions. [2023-11-19 05:03:11,631 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 293 [2023-11-19 05:03:11,631 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 05:03:11,632 INFO L195 NwaCegarLoop]: trace histogram [52, 51, 51, 11, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 1, 1, 1, 1, 1, 1, 1] [2023-11-19 05:03:11,638 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Forceful destruction successful, exit code 0 [2023-11-19 05:03:11,837 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2023-11-19 05:03:11,837 INFO L420 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 05:03:11,837 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 05:03:11,838 INFO L85 PathProgramCache]: Analyzing trace with hash -141720852, now seen corresponding path program 3 times [2023-11-19 05:03:11,838 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 05:03:11,838 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [697023016] [2023-11-19 05:03:11,838 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 05:03:11,838 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 05:03:11,853 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-19 05:03:11,853 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1651943927] [2023-11-19 05:03:11,853 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2023-11-19 05:03:11,854 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 05:03:11,854 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 05:03:11,855 INFO L229 MonitoredProcess]: Starting monitored process 14 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 05:03:11,861 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2023-11-19 05:03:11,991 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2023-11-19 05:03:11,991 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-19 05:03:11,994 INFO L262 TraceCheckSpWp]: Trace formula consists of 646 conjuncts, 23 conjunts are in the unsatisfiable core [2023-11-19 05:03:12,001 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-19 05:03:12,369 INFO L134 CoverageAnalysis]: Checked inductivity of 5582 backedges. 300 proven. 4880 refuted. 0 times theorem prover too weak. 402 trivial. 0 not checked. [2023-11-19 05:03:12,369 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-19 05:03:12,819 INFO L134 CoverageAnalysis]: Checked inductivity of 5582 backedges. 102 proven. 380 refuted. 0 times theorem prover too weak. 5100 trivial. 0 not checked. [2023-11-19 05:03:12,819 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 05:03:12,820 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [697023016] [2023-11-19 05:03:12,820 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-19 05:03:12,820 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1651943927] [2023-11-19 05:03:12,820 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1651943927] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-19 05:03:12,820 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [846051720] [2023-11-19 05:03:12,822 INFO L159 IcfgInterpreter]: Started Sifa with 17 locations of interest [2023-11-19 05:03:12,822 INFO L166 IcfgInterpreter]: Building call graph [2023-11-19 05:03:12,823 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-19 05:03:12,823 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-19 05:03:12,823 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-19 05:03:13,714 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 6 for LOIs [2023-11-19 05:03:13,718 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-19 05:03:14,250 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '11310#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-19 05:03:14,250 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-19 05:03:14,250 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-19 05:03:14,251 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 14] total 26 [2023-11-19 05:03:14,251 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2077487888] [2023-11-19 05:03:14,251 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-19 05:03:14,252 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 26 states [2023-11-19 05:03:14,252 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 05:03:14,253 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2023-11-19 05:03:14,254 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=374, Invalid=748, Unknown=0, NotChecked=0, Total=1122 [2023-11-19 05:03:14,254 INFO L87 Difference]: Start difference. First operand 292 states and 294 transitions. Second operand has 26 states, 26 states have (on average 4.0) internal successors, (104), 26 states have internal predecessors, (104), 21 states have call successors, (103), 12 states have call predecessors, (103), 12 states have return successors, (102), 21 states have call predecessors, (102), 21 states have call successors, (102) [2023-11-19 05:03:15,308 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 05:03:15,309 INFO L93 Difference]: Finished difference Result 641 states and 655 transitions. [2023-11-19 05:03:15,309 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 46 states. [2023-11-19 05:03:15,310 INFO L78 Accepts]: Start accepts. Automaton has has 26 states, 26 states have (on average 4.0) internal successors, (104), 26 states have internal predecessors, (104), 21 states have call successors, (103), 12 states have call predecessors, (103), 12 states have return successors, (102), 21 states have call predecessors, (102), 21 states have call successors, (102) Word has length 292 [2023-11-19 05:03:15,311 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 05:03:15,314 INFO L225 Difference]: With dead ends: 641 [2023-11-19 05:03:15,314 INFO L226 Difference]: Without dead ends: 628 [2023-11-19 05:03:15,316 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 895 GetRequests, 832 SyntacticMatches, 10 SemanticMatches, 53 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1200 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=910, Invalid=2060, Unknown=0, NotChecked=0, Total=2970 [2023-11-19 05:03:15,317 INFO L413 NwaCegarLoop]: 22 mSDtfsCounter, 128 mSDsluCounter, 151 mSDsCounter, 0 mSdLazyCounter, 262 mSolverCounterSat, 56 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 128 SdHoareTripleChecker+Valid, 173 SdHoareTripleChecker+Invalid, 318 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 56 IncrementalHoareTripleChecker+Valid, 262 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2023-11-19 05:03:15,317 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [128 Valid, 173 Invalid, 318 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [56 Valid, 262 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2023-11-19 05:03:15,320 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 628 states. [2023-11-19 05:03:15,598 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 628 to 628. [2023-11-19 05:03:15,599 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 628 states, 403 states have (on average 1.0049627791563276) internal successors, (405), 404 states have internal predecessors, (405), 113 states have call successors, (113), 111 states have call predecessors, (113), 111 states have return successors, (112), 112 states have call predecessors, (112), 112 states have call successors, (112) [2023-11-19 05:03:15,603 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 628 states to 628 states and 630 transitions. [2023-11-19 05:03:15,603 INFO L78 Accepts]: Start accepts. Automaton has 628 states and 630 transitions. Word has length 292 [2023-11-19 05:03:15,604 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 05:03:15,604 INFO L495 AbstractCegarLoop]: Abstraction has 628 states and 630 transitions. [2023-11-19 05:03:15,604 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 26 states, 26 states have (on average 4.0) internal successors, (104), 26 states have internal predecessors, (104), 21 states have call successors, (103), 12 states have call predecessors, (103), 12 states have return successors, (102), 21 states have call predecessors, (102), 21 states have call successors, (102) [2023-11-19 05:03:15,605 INFO L276 IsEmpty]: Start isEmpty. Operand 628 states and 630 transitions. [2023-11-19 05:03:15,621 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 629 [2023-11-19 05:03:15,621 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 05:03:15,622 INFO L195 NwaCegarLoop]: trace histogram [112, 111, 111, 23, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 1, 1, 1, 1, 1, 1, 1] [2023-11-19 05:03:15,647 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Forceful destruction successful, exit code 0 [2023-11-19 05:03:15,834 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable15 [2023-11-19 05:03:15,835 INFO L420 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 05:03:15,835 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 05:03:15,835 INFO L85 PathProgramCache]: Analyzing trace with hash -1785250124, now seen corresponding path program 4 times [2023-11-19 05:03:15,835 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 05:03:15,835 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1724482290] [2023-11-19 05:03:15,835 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 05:03:15,835 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 05:03:15,864 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-19 05:03:15,865 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1886944346] [2023-11-19 05:03:15,865 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2023-11-19 05:03:15,865 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 05:03:15,865 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 05:03:15,866 INFO L229 MonitoredProcess]: Starting monitored process 15 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 05:03:15,890 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2023-11-19 05:03:16,135 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 05:03:16,141 INFO L262 TraceCheckSpWp]: Trace formula consists of 1354 conjuncts, 47 conjunts are in the unsatisfiable core [2023-11-19 05:03:16,164 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-19 05:03:17,093 INFO L134 CoverageAnalysis]: Checked inductivity of 26534 backedges. 660 proven. 24992 refuted. 0 times theorem prover too weak. 882 trivial. 0 not checked. [2023-11-19 05:03:17,093 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-19 05:03:18,368 INFO L134 CoverageAnalysis]: Checked inductivity of 26534 backedges. 222 proven. 1892 refuted. 0 times theorem prover too weak. 24420 trivial. 0 not checked. [2023-11-19 05:03:18,368 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 05:03:18,369 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1724482290] [2023-11-19 05:03:18,369 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-19 05:03:18,369 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1886944346] [2023-11-19 05:03:18,369 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1886944346] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-19 05:03:18,369 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1406777929] [2023-11-19 05:03:18,372 INFO L159 IcfgInterpreter]: Started Sifa with 17 locations of interest [2023-11-19 05:03:18,372 INFO L166 IcfgInterpreter]: Building call graph [2023-11-19 05:03:18,373 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-19 05:03:18,373 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-19 05:03:18,373 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-19 05:03:19,278 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 6 for LOIs [2023-11-19 05:03:19,283 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-19 05:03:20,217 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '16940#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-19 05:03:20,217 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-19 05:03:20,218 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-19 05:03:20,218 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [25, 26] total 50 [2023-11-19 05:03:20,218 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [532548958] [2023-11-19 05:03:20,218 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-19 05:03:20,220 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 50 states [2023-11-19 05:03:20,220 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 05:03:20,222 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 50 interpolants. [2023-11-19 05:03:20,224 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1298, Invalid=2008, Unknown=0, NotChecked=0, Total=3306 [2023-11-19 05:03:20,225 INFO L87 Difference]: Start difference. First operand 628 states and 630 transitions. Second operand has 50 states, 50 states have (on average 4.24) internal successors, (212), 50 states have internal predecessors, (212), 45 states have call successors, (223), 24 states have call predecessors, (223), 24 states have return successors, (222), 45 states have call predecessors, (222), 45 states have call successors, (222) [2023-11-19 05:03:23,232 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 05:03:23,233 INFO L93 Difference]: Finished difference Result 1313 states and 1339 transitions. [2023-11-19 05:03:23,233 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 94 states. [2023-11-19 05:03:23,234 INFO L78 Accepts]: Start accepts. Automaton has has 50 states, 50 states have (on average 4.24) internal successors, (212), 50 states have internal predecessors, (212), 45 states have call successors, (223), 24 states have call predecessors, (223), 24 states have return successors, (222), 45 states have call predecessors, (222), 45 states have call successors, (222) Word has length 628 [2023-11-19 05:03:23,236 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 05:03:23,243 INFO L225 Difference]: With dead ends: 1313 [2023-11-19 05:03:23,243 INFO L226 Difference]: Without dead ends: 1300 [2023-11-19 05:03:23,248 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 1927 GetRequests, 1804 SyntacticMatches, 22 SemanticMatches, 101 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4302 ImplicationChecksByTransitivity, 3.0s TimeCoverageRelationStatistics Valid=3526, Invalid=6980, Unknown=0, NotChecked=0, Total=10506 [2023-11-19 05:03:23,249 INFO L413 NwaCegarLoop]: 22 mSDtfsCounter, 332 mSDsluCounter, 260 mSDsCounter, 0 mSdLazyCounter, 553 mSolverCounterSat, 236 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 332 SdHoareTripleChecker+Valid, 282 SdHoareTripleChecker+Invalid, 789 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 236 IncrementalHoareTripleChecker+Valid, 553 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.9s IncrementalHoareTripleChecker+Time [2023-11-19 05:03:23,249 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [332 Valid, 282 Invalid, 789 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [236 Valid, 553 Invalid, 0 Unknown, 0 Unchecked, 0.9s Time] [2023-11-19 05:03:23,251 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1300 states. [2023-11-19 05:03:23,706 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1300 to 1300. [2023-11-19 05:03:23,708 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1300 states, 835 states have (on average 1.0023952095808384) internal successors, (837), 836 states have internal predecessors, (837), 233 states have call successors, (233), 231 states have call predecessors, (233), 231 states have return successors, (232), 232 states have call predecessors, (232), 232 states have call successors, (232) [2023-11-19 05:03:23,715 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1300 states to 1300 states and 1302 transitions. [2023-11-19 05:03:23,715 INFO L78 Accepts]: Start accepts. Automaton has 1300 states and 1302 transitions. Word has length 628 [2023-11-19 05:03:23,716 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 05:03:23,717 INFO L495 AbstractCegarLoop]: Abstraction has 1300 states and 1302 transitions. [2023-11-19 05:03:23,717 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 50 states, 50 states have (on average 4.24) internal successors, (212), 50 states have internal predecessors, (212), 45 states have call successors, (223), 24 states have call predecessors, (223), 24 states have return successors, (222), 45 states have call predecessors, (222), 45 states have call successors, (222) [2023-11-19 05:03:23,718 INFO L276 IsEmpty]: Start isEmpty. Operand 1300 states and 1302 transitions. [2023-11-19 05:03:23,798 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1301 [2023-11-19 05:03:23,798 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 05:03:23,799 INFO L195 NwaCegarLoop]: trace histogram [232, 231, 231, 47, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 1, 1, 1, 1, 1, 1, 1] [2023-11-19 05:03:23,825 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Forceful destruction successful, exit code 0 [2023-11-19 05:03:24,020 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 15 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable16 [2023-11-19 05:03:24,021 INFO L420 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 05:03:24,021 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 05:03:24,021 INFO L85 PathProgramCache]: Analyzing trace with hash -997767612, now seen corresponding path program 5 times [2023-11-19 05:03:24,021 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 05:03:24,021 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [986582730] [2023-11-19 05:03:24,021 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 05:03:24,022 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 05:03:24,083 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-19 05:03:24,084 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [757824270] [2023-11-19 05:03:24,084 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-11-19 05:03:24,084 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 05:03:24,084 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 05:03:24,085 INFO L229 MonitoredProcess]: Starting monitored process 16 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 05:03:24,105 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_737fb500-dc7b-4fca-88c7-5e32c3edcc3e/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2023-11-19 05:03:26,838 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 162 check-sat command(s) [2023-11-19 05:03:26,838 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-19 05:03:26,856 INFO L262 TraceCheckSpWp]: Trace formula consists of 2761 conjuncts, 95 conjunts are in the unsatisfiable core [2023-11-19 05:03:26,885 INFO L285 TraceCheckSpWp]: Computing forward predicates...