./Ultimate.py --spec ../../sv-benchmarks/c/properties/unreach-call.prp --file ../../sv-benchmarks/c/nla-digbench-scaling/hard2_unwindbound5.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 0e0057cc Calling Ultimate with: /usr/lib/jvm/java-11-openjdk-amd64/bin/java -Dosgi.configuration.area=/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/config/TaipanReach.xml -i ../../sv-benchmarks/c/nla-digbench-scaling/hard2_unwindbound5.c -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/config/svcomp-Reach-32bit-Taipan_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh --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 5f094e7ea34d2025ab25ab51a4a0b06d8f845826c76dbd06e91f3d4a761fa19b --- Real Ultimate output --- This is Ultimate 0.2.4-dev-0e0057c [2023-12-02 18:01:39,021 INFO L188 SettingsManager]: Resetting all preferences to default values... [2023-12-02 18:01:39,089 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/config/svcomp-Reach-32bit-Taipan_Default.epf [2023-12-02 18:01:39,093 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2023-12-02 18:01:39,094 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2023-12-02 18:01:39,119 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2023-12-02 18:01:39,120 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2023-12-02 18:01:39,121 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2023-12-02 18:01:39,121 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2023-12-02 18:01:39,122 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2023-12-02 18:01:39,122 INFO L153 SettingsManager]: * User list type=DISABLED [2023-12-02 18:01:39,123 INFO L151 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2023-12-02 18:01:39,124 INFO L153 SettingsManager]: * Explicit value domain=true [2023-12-02 18:01:39,124 INFO L153 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2023-12-02 18:01:39,125 INFO L153 SettingsManager]: * Octagon Domain=false [2023-12-02 18:01:39,125 INFO L153 SettingsManager]: * Abstract domain=CompoundDomain [2023-12-02 18:01:39,126 INFO L153 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2023-12-02 18:01:39,126 INFO L153 SettingsManager]: * Use the RCFG-of-the-future interface=true [2023-12-02 18:01:39,127 INFO L153 SettingsManager]: * Interval Domain=false [2023-12-02 18:01:39,127 INFO L151 SettingsManager]: Preferences of Sifa differ from their defaults: [2023-12-02 18:01:39,128 INFO L153 SettingsManager]: * Call Summarizer=TopInputCallSummarizer [2023-12-02 18:01:39,128 INFO L153 SettingsManager]: * Simplification Technique=POLY_PAC [2023-12-02 18:01:39,129 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2023-12-02 18:01:39,130 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2023-12-02 18:01:39,130 INFO L153 SettingsManager]: * sizeof long=4 [2023-12-02 18:01:39,131 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2023-12-02 18:01:39,131 INFO L153 SettingsManager]: * sizeof POINTER=4 [2023-12-02 18:01:39,131 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2023-12-02 18:01:39,132 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2023-12-02 18:01:39,132 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2023-12-02 18:01:39,133 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2023-12-02 18:01:39,133 INFO L153 SettingsManager]: * sizeof long double=12 [2023-12-02 18:01:39,133 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2023-12-02 18:01:39,134 INFO L153 SettingsManager]: * Use constant arrays=true [2023-12-02 18:01:39,134 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2023-12-02 18:01:39,134 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2023-12-02 18:01:39,134 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2023-12-02 18:01:39,135 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-12-02 18:01:39,135 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2023-12-02 18:01:39,135 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2023-12-02 18:01:39,135 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2023-12-02 18:01:39,136 INFO L153 SettingsManager]: * Trace refinement strategy=SIFA_TAIPAN [2023-12-02 18:01:39,136 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2023-12-02 18:01:39,136 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2023-12-02 18:01:39,136 INFO L153 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2023-12-02 18:01:39,137 INFO L153 SettingsManager]: * Trace refinement exception blacklist=NONE [2023-12-02 18:01:39,137 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2023-12-02 18:01:39,137 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_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/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_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh 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 -> 5f094e7ea34d2025ab25ab51a4a0b06d8f845826c76dbd06e91f3d4a761fa19b [2023-12-02 18:01:39,343 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2023-12-02 18:01:39,363 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2023-12-02 18:01:39,365 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2023-12-02 18:01:39,367 INFO L270 PluginConnector]: Initializing CDTParser... [2023-12-02 18:01:39,367 INFO L274 PluginConnector]: CDTParser initialized [2023-12-02 18:01:39,368 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/../../sv-benchmarks/c/nla-digbench-scaling/hard2_unwindbound5.c [2023-12-02 18:01:42,086 INFO L533 CDTParser]: Created temporary CDT project at NULL [2023-12-02 18:01:42,240 INFO L384 CDTParser]: Found 1 translation units. [2023-12-02 18:01:42,241 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/sv-benchmarks/c/nla-digbench-scaling/hard2_unwindbound5.c [2023-12-02 18:01:42,246 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/data/7559dd6ec/a2b7c1791cdb409eafe5b7b189738cab/FLAG30a764b30 [2023-12-02 18:01:42,258 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/data/7559dd6ec/a2b7c1791cdb409eafe5b7b189738cab [2023-12-02 18:01:42,261 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2023-12-02 18:01:42,263 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2023-12-02 18:01:42,264 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2023-12-02 18:01:42,264 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2023-12-02 18:01:42,269 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2023-12-02 18:01:42,270 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 02.12 06:01:42" (1/1) ... [2023-12-02 18:01:42,271 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@1ec0a62b and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 06:01:42, skipping insertion in model container [2023-12-02 18:01:42,271 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 02.12 06:01:42" (1/1) ... [2023-12-02 18:01:42,294 INFO L177 MainTranslator]: Built tables and reachable declarations [2023-12-02 18:01:42,446 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_bb488dd9-c770-4879-a233-8b6251207c70/sv-benchmarks/c/nla-digbench-scaling/hard2_unwindbound5.c[526,539] [2023-12-02 18:01:42,463 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-12-02 18:01:42,473 INFO L202 MainTranslator]: Completed pre-run [2023-12-02 18:01:42,487 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_bb488dd9-c770-4879-a233-8b6251207c70/sv-benchmarks/c/nla-digbench-scaling/hard2_unwindbound5.c[526,539] [2023-12-02 18:01:42,493 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-12-02 18:01:42,508 INFO L206 MainTranslator]: Completed translation [2023-12-02 18:01:42,508 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 06:01:42 WrapperNode [2023-12-02 18:01:42,508 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2023-12-02 18:01:42,509 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2023-12-02 18:01:42,509 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2023-12-02 18:01:42,510 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2023-12-02 18:01:42,516 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 06:01:42" (1/1) ... [2023-12-02 18:01:42,522 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 06:01:42" (1/1) ... [2023-12-02 18:01:42,542 INFO L138 Inliner]: procedures = 14, calls = 22, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 69 [2023-12-02 18:01:42,542 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2023-12-02 18:01:42,543 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2023-12-02 18:01:42,543 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2023-12-02 18:01:42,543 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2023-12-02 18:01:42,550 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 06:01:42" (1/1) ... [2023-12-02 18:01:42,550 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 06:01:42" (1/1) ... [2023-12-02 18:01:42,552 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 06:01:42" (1/1) ... [2023-12-02 18:01:42,552 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 06:01:42" (1/1) ... [2023-12-02 18:01:42,555 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 06:01:42" (1/1) ... [2023-12-02 18:01:42,557 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 06:01:42" (1/1) ... [2023-12-02 18:01:42,558 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 06:01:42" (1/1) ... [2023-12-02 18:01:42,559 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 06:01:42" (1/1) ... [2023-12-02 18:01:42,561 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2023-12-02 18:01:42,561 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2023-12-02 18:01:42,561 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2023-12-02 18:01:42,561 INFO L274 PluginConnector]: RCFGBuilder initialized [2023-12-02 18:01:42,562 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 06:01:42" (1/1) ... [2023-12-02 18:01:42,567 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-12-02 18:01:42,578 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 18:01:42,589 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2023-12-02 18:01:42,591 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2023-12-02 18:01:42,619 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2023-12-02 18:01:42,619 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2023-12-02 18:01:42,619 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2023-12-02 18:01:42,620 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2023-12-02 18:01:42,620 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2023-12-02 18:01:42,620 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2023-12-02 18:01:42,678 INFO L241 CfgBuilder]: Building ICFG [2023-12-02 18:01:42,680 INFO L267 CfgBuilder]: Building CFG for each procedure with an implementation [2023-12-02 18:01:42,816 INFO L282 CfgBuilder]: Performing block encoding [2023-12-02 18:01:42,856 INFO L304 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2023-12-02 18:01:42,856 INFO L309 CfgBuilder]: Removed 2 assume(true) statements. [2023-12-02 18:01:42,858 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 02.12 06:01:42 BoogieIcfgContainer [2023-12-02 18:01:42,858 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2023-12-02 18:01:42,860 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2023-12-02 18:01:42,860 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2023-12-02 18:01:42,863 INFO L274 PluginConnector]: TraceAbstraction initialized [2023-12-02 18:01:42,863 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 02.12 06:01:42" (1/3) ... [2023-12-02 18:01:42,864 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4921192e and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 02.12 06:01:42, skipping insertion in model container [2023-12-02 18:01:42,864 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 06:01:42" (2/3) ... [2023-12-02 18:01:42,864 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4921192e and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 02.12 06:01:42, skipping insertion in model container [2023-12-02 18:01:42,864 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 02.12 06:01:42" (3/3) ... [2023-12-02 18:01:42,866 INFO L112 eAbstractionObserver]: Analyzing ICFG hard2_unwindbound5.c [2023-12-02 18:01:42,881 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2023-12-02 18:01:42,881 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2023-12-02 18:01:42,922 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-12-02 18:01:42,928 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;@d90dacf, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2023-12-02 18:01:42,929 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2023-12-02 18:01:42,932 INFO L276 IsEmpty]: Start isEmpty. Operand has 22 states, 12 states have (on average 1.6666666666666667) internal successors, (20), 13 states have internal predecessors, (20), 7 states have call successors, (7), 1 states have call predecessors, (7), 1 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2023-12-02 18:01:42,938 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 8 [2023-12-02 18:01:42,938 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 18:01:42,939 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2023-12-02 18:01:42,940 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 18:01:42,944 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 18:01:42,944 INFO L85 PathProgramCache]: Analyzing trace with hash 1291730102, now seen corresponding path program 1 times [2023-12-02 18:01:42,952 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 18:01:42,952 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2019193790] [2023-12-02 18:01:42,952 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 18:01:42,953 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 18:01:43,031 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 18:01:43,053 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 18:01:43,053 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2019193790] [2023-12-02 18:01:43,054 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unsupported non-linear arithmetic [2023-12-02 18:01:43,054 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1558246815] [2023-12-02 18:01:43,054 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 18:01:43,054 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 18:01:43,054 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 18:01:43,056 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 18:01:43,076 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2023-12-02 18:01:43,137 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 18:01:43,139 INFO L262 TraceCheckSpWp]: Trace formula consists of 62 conjuncts, 1 conjunts are in the unsatisfiable core [2023-12-02 18:01:43,143 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 18:01:43,164 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-02 18:01:43,164 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-12-02 18:01:43,165 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1558246815] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-02 18:01:43,165 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-12-02 18:01:43,165 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2023-12-02 18:01:43,168 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [180051580] [2023-12-02 18:01:43,169 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-02 18:01:43,173 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2023-12-02 18:01:43,173 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 18:01:43,202 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2023-12-02 18:01:43,203 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2023-12-02 18:01:43,205 INFO L87 Difference]: Start difference. First operand has 22 states, 12 states have (on average 1.6666666666666667) internal successors, (20), 13 states have internal predecessors, (20), 7 states have call successors, (7), 1 states have call predecessors, (7), 1 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) Second operand has 2 states, 2 states have (on average 3.0) internal successors, (6), 2 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 18:01:43,263 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 18:01:43,263 INFO L93 Difference]: Finished difference Result 43 states and 74 transitions. [2023-12-02 18:01:43,265 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2023-12-02 18:01:43,266 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 3.0) internal successors, (6), 2 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 7 [2023-12-02 18:01:43,267 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 18:01:43,280 INFO L225 Difference]: With dead ends: 43 [2023-12-02 18:01:43,280 INFO L226 Difference]: Without dead ends: 20 [2023-12-02 18:01:43,283 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 6 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-12-02 18:01:43,287 INFO L413 NwaCegarLoop]: 28 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 3 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 28 SdHoareTripleChecker+Invalid, 3 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 3 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-12-02 18:01:43,288 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 28 Invalid, 3 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 3 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-12-02 18:01:43,301 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 20 states. [2023-12-02 18:01:43,316 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 20 to 20. [2023-12-02 18:01:43,317 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 20 states, 11 states have (on average 1.4545454545454546) internal successors, (16), 12 states have internal predecessors, (16), 7 states have call successors, (7), 1 states have call predecessors, (7), 1 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2023-12-02 18:01:43,318 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 20 states to 20 states and 29 transitions. [2023-12-02 18:01:43,319 INFO L78 Accepts]: Start accepts. Automaton has 20 states and 29 transitions. Word has length 7 [2023-12-02 18:01:43,320 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 18:01:43,320 INFO L495 AbstractCegarLoop]: Abstraction has 20 states and 29 transitions. [2023-12-02 18:01:43,320 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 3.0) internal successors, (6), 2 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 18:01:43,320 INFO L276 IsEmpty]: Start isEmpty. Operand 20 states and 29 transitions. [2023-12-02 18:01:43,321 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 8 [2023-12-02 18:01:43,321 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 18:01:43,321 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2023-12-02 18:01:43,327 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2023-12-02 18:01:43,524 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable0 [2023-12-02 18:01:43,525 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 18:01:43,525 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 18:01:43,526 INFO L85 PathProgramCache]: Analyzing trace with hash 829671692, now seen corresponding path program 1 times [2023-12-02 18:01:43,526 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 18:01:43,526 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1601013775] [2023-12-02 18:01:43,526 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 18:01:43,526 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 18:01:43,542 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 18:01:43,661 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-02 18:01:43,661 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 18:01:43,661 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1601013775] [2023-12-02 18:01:43,662 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1601013775] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-02 18:01:43,662 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-12-02 18:01:43,662 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2023-12-02 18:01:43,662 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2111599957] [2023-12-02 18:01:43,662 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-02 18:01:43,663 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-12-02 18:01:43,663 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 18:01:43,664 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-12-02 18:01:43,664 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2023-12-02 18:01:43,665 INFO L87 Difference]: Start difference. First operand 20 states and 29 transitions. Second operand has 5 states, 5 states have (on average 1.2) internal successors, (6), 3 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 18:01:43,723 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 18:01:43,723 INFO L93 Difference]: Finished difference Result 33 states and 46 transitions. [2023-12-02 18:01:43,723 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-12-02 18:01:43,724 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-12-02 18:01:43,724 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 18:01:43,725 INFO L225 Difference]: With dead ends: 33 [2023-12-02 18:01:43,725 INFO L226 Difference]: Without dead ends: 31 [2023-12-02 18:01:43,726 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-12-02 18:01:43,727 INFO L413 NwaCegarLoop]: 24 mSDtfsCounter, 13 mSDsluCounter, 57 mSDsCounter, 0 mSdLazyCounter, 23 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 19 SdHoareTripleChecker+Valid, 81 SdHoareTripleChecker+Invalid, 24 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 23 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-12-02 18:01:43,728 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [19 Valid, 81 Invalid, 24 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 23 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-12-02 18:01:43,729 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 31 states. [2023-12-02 18:01:43,736 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 31 to 24. [2023-12-02 18:01:43,737 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 24 states, 14 states have (on average 1.3571428571428572) internal successors, (19), 15 states have internal predecessors, (19), 7 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2023-12-02 18:01:43,738 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 32 transitions. [2023-12-02 18:01:43,738 INFO L78 Accepts]: Start accepts. Automaton has 24 states and 32 transitions. Word has length 7 [2023-12-02 18:01:43,738 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 18:01:43,738 INFO L495 AbstractCegarLoop]: Abstraction has 24 states and 32 transitions. [2023-12-02 18:01:43,738 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-12-02 18:01:43,738 INFO L276 IsEmpty]: Start isEmpty. Operand 24 states and 32 transitions. [2023-12-02 18:01:43,739 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 10 [2023-12-02 18:01:43,739 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 18:01:43,739 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 18:01:43,740 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2023-12-02 18:01:43,740 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 18:01:43,740 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 18:01:43,740 INFO L85 PathProgramCache]: Analyzing trace with hash -166824855, now seen corresponding path program 1 times [2023-12-02 18:01:43,741 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 18:01:43,741 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1618109214] [2023-12-02 18:01:43,741 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 18:01:43,741 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 18:01:43,754 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 18:01:43,761 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 18:01:43,761 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1618109214] [2023-12-02 18:01:43,762 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unsupported non-linear arithmetic [2023-12-02 18:01:43,762 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [738243971] [2023-12-02 18:01:43,762 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 18:01:43,762 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 18:01:43,763 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 18:01:43,765 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 18:01:43,773 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2023-12-02 18:01:43,827 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 18:01:43,828 INFO L262 TraceCheckSpWp]: Trace formula consists of 70 conjuncts, 3 conjunts are in the unsatisfiable core [2023-12-02 18:01:43,830 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 18:01:43,860 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-02 18:01:43,861 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-12-02 18:01:43,861 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [738243971] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-02 18:01:43,861 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-12-02 18:01:43,861 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2023-12-02 18:01:43,861 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1212742034] [2023-12-02 18:01:43,862 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-02 18:01:43,862 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2023-12-02 18:01:43,862 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 18:01:43,863 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2023-12-02 18:01:43,863 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2023-12-02 18:01:43,863 INFO L87 Difference]: Start difference. First operand 24 states and 32 transitions. Second operand has 4 states, 4 states have (on average 2.0) internal successors, (8), 3 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 18:01:43,887 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 18:01:43,887 INFO L93 Difference]: Finished difference Result 39 states and 52 transitions. [2023-12-02 18:01:43,887 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2023-12-02 18:01:43,888 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 2.0) internal successors, (8), 3 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 9 [2023-12-02 18:01:43,888 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 18:01:43,888 INFO L225 Difference]: With dead ends: 39 [2023-12-02 18:01:43,889 INFO L226 Difference]: Without dead ends: 26 [2023-12-02 18:01:43,889 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 8 GetRequests, 6 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-12-02 18:01:43,891 INFO L413 NwaCegarLoop]: 25 mSDtfsCounter, 0 mSDsluCounter, 48 mSDsCounter, 0 mSdLazyCounter, 13 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 73 SdHoareTripleChecker+Invalid, 13 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 13 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-12-02 18:01:43,891 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 73 Invalid, 13 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 13 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-12-02 18:01:43,892 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 26 states. [2023-12-02 18:01:43,897 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 26 to 26. [2023-12-02 18:01:43,898 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 26 states, 16 states have (on average 1.3125) internal successors, (21), 17 states have internal predecessors, (21), 7 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2023-12-02 18:01:43,899 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 34 transitions. [2023-12-02 18:01:43,899 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 34 transitions. Word has length 9 [2023-12-02 18:01:43,899 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 18:01:43,900 INFO L495 AbstractCegarLoop]: Abstraction has 26 states and 34 transitions. [2023-12-02 18:01:43,900 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 2.0) internal successors, (8), 3 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 18:01:43,900 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 34 transitions. [2023-12-02 18:01:43,900 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2023-12-02 18:01:43,901 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 18:01:43,901 INFO L195 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 18:01:43,905 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2023-12-02 18:01:44,101 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 18:01:44,102 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 18:01:44,102 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 18:01:44,102 INFO L85 PathProgramCache]: Analyzing trace with hash -439138420, now seen corresponding path program 1 times [2023-12-02 18:01:44,102 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 18:01:44,102 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [118376049] [2023-12-02 18:01:44,103 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 18:01:44,103 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 18:01:44,114 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 18:01:44,199 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-02 18:01:44,200 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 18:01:44,200 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [118376049] [2023-12-02 18:01:44,200 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [118376049] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-02 18:01:44,200 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-12-02 18:01:44,201 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2023-12-02 18:01:44,201 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1764604113] [2023-12-02 18:01:44,201 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-02 18:01:44,201 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-12-02 18:01:44,202 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 18:01:44,203 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-12-02 18:01:44,203 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2023-12-02 18:01:44,203 INFO L87 Difference]: Start difference. First operand 26 states and 34 transitions. Second operand has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 states have internal predecessors, (9), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2023-12-02 18:01:44,252 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 18:01:44,252 INFO L93 Difference]: Finished difference Result 39 states and 51 transitions. [2023-12-02 18:01:44,252 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-12-02 18:01:44,253 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-12-02 18:01:44,253 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 18:01:44,254 INFO L225 Difference]: With dead ends: 39 [2023-12-02 18:01:44,254 INFO L226 Difference]: Without dead ends: 37 [2023-12-02 18:01:44,254 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2023-12-02 18:01:44,256 INFO L413 NwaCegarLoop]: 25 mSDtfsCounter, 11 mSDsluCounter, 56 mSDsCounter, 0 mSdLazyCounter, 29 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 16 SdHoareTripleChecker+Valid, 81 SdHoareTripleChecker+Invalid, 30 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 29 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-12-02 18:01:44,256 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [16 Valid, 81 Invalid, 30 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 29 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-12-02 18:01:44,257 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 37 states. [2023-12-02 18:01:44,263 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 37 to 30. [2023-12-02 18:01:44,263 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 30 states, 19 states have (on average 1.263157894736842) internal successors, (24), 20 states have internal predecessors, (24), 7 states have call successors, (7), 3 states have call predecessors, (7), 3 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2023-12-02 18:01:44,264 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 30 states to 30 states and 37 transitions. [2023-12-02 18:01:44,264 INFO L78 Accepts]: Start accepts. Automaton has 30 states and 37 transitions. Word has length 12 [2023-12-02 18:01:44,264 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 18:01:44,265 INFO L495 AbstractCegarLoop]: Abstraction has 30 states and 37 transitions. [2023-12-02 18:01:44,265 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-12-02 18:01:44,265 INFO L276 IsEmpty]: Start isEmpty. Operand 30 states and 37 transitions. [2023-12-02 18:01:44,265 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2023-12-02 18:01:44,266 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 18:01:44,266 INFO L195 NwaCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 18:01:44,266 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2023-12-02 18:01:44,266 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 18:01:44,267 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 18:01:44,267 INFO L85 PathProgramCache]: Analyzing trace with hash -235147060, now seen corresponding path program 1 times [2023-12-02 18:01:44,267 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 18:01:44,267 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1754355060] [2023-12-02 18:01:44,267 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 18:01:44,268 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 18:01:44,279 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-02 18:01:44,279 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1183238505] [2023-12-02 18:01:44,279 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 18:01:44,279 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 18:01:44,280 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 18:01:44,285 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 18:01:44,296 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2023-12-02 18:01:44,336 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 18:01:44,337 INFO L262 TraceCheckSpWp]: Trace formula consists of 83 conjuncts, 19 conjunts are in the unsatisfiable core [2023-12-02 18:01:44,339 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 18:01:44,459 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 3 proven. 4 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2023-12-02 18:01:44,459 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 18:01:44,579 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 3 proven. 4 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2023-12-02 18:01:44,579 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 18:01:44,580 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1754355060] [2023-12-02 18:01:44,580 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-02 18:01:44,580 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1183238505] [2023-12-02 18:01:44,580 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1183238505] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-02 18:01:44,580 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [774782126] [2023-12-02 18:01:44,599 INFO L159 IcfgInterpreter]: Started Sifa with 12 locations of interest [2023-12-02 18:01:44,599 INFO L166 IcfgInterpreter]: Building call graph [2023-12-02 18:01:44,602 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-12-02 18:01:44,607 INFO L176 IcfgInterpreter]: Starting interpretation [2023-12-02 18:01:44,608 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-12-02 18:01:45,149 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 64 for LOIs [2023-12-02 18:01:45,178 INFO L180 IcfgInterpreter]: Interpretation finished [2023-12-02 18:01:45,823 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSifa [774782126] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-02 18:01:45,823 INFO L185 FreeRefinementEngine]: Found 1 perfect and 2 imperfect interpolant sequences. [2023-12-02 18:01:45,823 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [8, 7] total 17 [2023-12-02 18:01:45,824 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1770508878] [2023-12-02 18:01:45,824 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-02 18:01:45,824 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2023-12-02 18:01:45,825 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 18:01:45,825 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2023-12-02 18:01:45,825 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=65, Invalid=207, Unknown=0, NotChecked=0, Total=272 [2023-12-02 18:01:45,826 INFO L87 Difference]: Start difference. First operand 30 states and 37 transitions. Second operand has 7 states, 6 states have (on average 1.3333333333333333) internal successors, (8), 5 states have internal predecessors, (8), 1 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2023-12-02 18:01:45,949 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 18:01:45,950 INFO L93 Difference]: Finished difference Result 49 states and 57 transitions. [2023-12-02 18:01:45,950 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2023-12-02 18:01:45,950 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 6 states have (on average 1.3333333333333333) internal successors, (8), 5 states have internal predecessors, (8), 1 states have call successors, (3), 1 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-12-02 18:01:45,950 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 18:01:45,951 INFO L225 Difference]: With dead ends: 49 [2023-12-02 18:01:45,951 INFO L226 Difference]: Without dead ends: 47 [2023-12-02 18:01:45,952 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 49 GetRequests, 32 SyntacticMatches, 2 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 85 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=65, Invalid=207, Unknown=0, NotChecked=0, Total=272 [2023-12-02 18:01:45,953 INFO L413 NwaCegarLoop]: 17 mSDtfsCounter, 1 mSDsluCounter, 41 mSDsCounter, 0 mSdLazyCounter, 65 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 58 SdHoareTripleChecker+Invalid, 65 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 65 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-12-02 18:01:45,953 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [2 Valid, 58 Invalid, 65 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 65 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-12-02 18:01:45,954 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2023-12-02 18:01:45,964 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 45. [2023-12-02 18:01:45,965 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 45 states, 28 states have (on average 1.1785714285714286) internal successors, (33), 30 states have internal predecessors, (33), 10 states have call successors, (10), 6 states have call predecessors, (10), 6 states have return successors, (9), 8 states have call predecessors, (9), 9 states have call successors, (9) [2023-12-02 18:01:45,966 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 45 states to 45 states and 52 transitions. [2023-12-02 18:01:45,966 INFO L78 Accepts]: Start accepts. Automaton has 45 states and 52 transitions. Word has length 17 [2023-12-02 18:01:45,966 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 18:01:45,966 INFO L495 AbstractCegarLoop]: Abstraction has 45 states and 52 transitions. [2023-12-02 18:01:45,966 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 6 states have (on average 1.3333333333333333) internal successors, (8), 5 states have internal predecessors, (8), 1 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2023-12-02 18:01:45,967 INFO L276 IsEmpty]: Start isEmpty. Operand 45 states and 52 transitions. [2023-12-02 18:01:45,967 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2023-12-02 18:01:45,967 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 18:01:45,968 INFO L195 NwaCegarLoop]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 18:01:45,972 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2023-12-02 18:01:46,168 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 18:01:46,168 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 18:01:46,169 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 18:01:46,169 INFO L85 PathProgramCache]: Analyzing trace with hash 2012527405, now seen corresponding path program 1 times [2023-12-02 18:01:46,169 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 18:01:46,169 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1779441016] [2023-12-02 18:01:46,169 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 18:01:46,169 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 18:01:46,184 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-02 18:01:46,185 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1132800649] [2023-12-02 18:01:46,185 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 18:01:46,185 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 18:01:46,185 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 18:01:46,186 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 18:01:46,194 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2023-12-02 18:01:46,239 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 18:01:46,240 INFO L262 TraceCheckSpWp]: Trace formula consists of 98 conjuncts, 17 conjunts are in the unsatisfiable core [2023-12-02 18:01:46,242 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 18:01:46,332 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 5 proven. 7 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2023-12-02 18:01:46,332 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 18:01:46,477 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 5 proven. 7 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2023-12-02 18:01:46,478 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 18:01:46,478 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1779441016] [2023-12-02 18:01:46,478 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-02 18:01:46,478 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1132800649] [2023-12-02 18:01:46,478 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1132800649] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-02 18:01:46,478 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [869554292] [2023-12-02 18:01:46,481 INFO L159 IcfgInterpreter]: Started Sifa with 16 locations of interest [2023-12-02 18:01:46,481 INFO L166 IcfgInterpreter]: Building call graph [2023-12-02 18:01:46,481 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-12-02 18:01:46,481 INFO L176 IcfgInterpreter]: Starting interpretation [2023-12-02 18:01:46,482 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-12-02 18:01:47,038 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 10 for LOIs [2023-12-02 18:01:47,042 INFO L180 IcfgInterpreter]: Interpretation finished [2023-12-02 18:01:47,807 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSifa [869554292] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-02 18:01:47,807 INFO L185 FreeRefinementEngine]: Found 1 perfect and 2 imperfect interpolant sequences. [2023-12-02 18:01:47,807 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [7, 7] total 19 [2023-12-02 18:01:47,808 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1895213937] [2023-12-02 18:01:47,808 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-02 18:01:47,808 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2023-12-02 18:01:47,808 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 18:01:47,809 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2023-12-02 18:01:47,809 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=74, Invalid=268, Unknown=0, NotChecked=0, Total=342 [2023-12-02 18:01:47,809 INFO L87 Difference]: Start difference. First operand 45 states and 52 transitions. Second operand has 10 states, 9 states have (on average 1.2222222222222223) internal successors, (11), 8 states have internal predecessors, (11), 2 states have call successors, (4), 1 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2023-12-02 18:01:47,979 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 18:01:47,979 INFO L93 Difference]: Finished difference Result 70 states and 87 transitions. [2023-12-02 18:01:47,979 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2023-12-02 18:01:47,979 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 9 states have (on average 1.2222222222222223) internal successors, (11), 8 states have internal predecessors, (11), 2 states have call successors, (4), 1 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) Word has length 25 [2023-12-02 18:01:47,979 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 18:01:47,980 INFO L225 Difference]: With dead ends: 70 [2023-12-02 18:01:47,980 INFO L226 Difference]: Without dead ends: 46 [2023-12-02 18:01:47,981 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 73 GetRequests, 53 SyntacticMatches, 3 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 110 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=74, Invalid=268, Unknown=0, NotChecked=0, Total=342 [2023-12-02 18:01:47,981 INFO L413 NwaCegarLoop]: 17 mSDtfsCounter, 1 mSDsluCounter, 51 mSDsCounter, 0 mSdLazyCounter, 147 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 68 SdHoareTripleChecker+Invalid, 152 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 147 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-12-02 18:01:47,982 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 68 Invalid, 152 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 147 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-12-02 18:01:47,982 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 46 states. [2023-12-02 18:01:47,988 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 46 to 46. [2023-12-02 18:01:47,988 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 46 states, 29 states have (on average 1.1724137931034482) internal successors, (34), 30 states have internal predecessors, (34), 10 states have call successors, (10), 6 states have call predecessors, (10), 6 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2023-12-02 18:01:47,988 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 46 states to 46 states and 53 transitions. [2023-12-02 18:01:47,989 INFO L78 Accepts]: Start accepts. Automaton has 46 states and 53 transitions. Word has length 25 [2023-12-02 18:01:47,989 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 18:01:47,989 INFO L495 AbstractCegarLoop]: Abstraction has 46 states and 53 transitions. [2023-12-02 18:01:47,989 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 9 states have (on average 1.2222222222222223) internal successors, (11), 8 states have internal predecessors, (11), 2 states have call successors, (4), 1 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2023-12-02 18:01:47,989 INFO L276 IsEmpty]: Start isEmpty. Operand 46 states and 53 transitions. [2023-12-02 18:01:47,990 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2023-12-02 18:01:47,990 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 18:01:47,990 INFO L195 NwaCegarLoop]: trace histogram [4, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 18:01:47,995 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2023-12-02 18:01:48,190 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 18:01:48,191 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 18:01:48,191 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 18:01:48,191 INFO L85 PathProgramCache]: Analyzing trace with hash 2127759890, now seen corresponding path program 1 times [2023-12-02 18:01:48,191 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 18:01:48,191 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1672294803] [2023-12-02 18:01:48,191 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 18:01:48,192 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 18:01:48,199 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-02 18:01:48,199 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [388906996] [2023-12-02 18:01:48,199 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 18:01:48,199 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 18:01:48,199 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 18:01:48,200 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 18:01:48,201 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2023-12-02 18:01:48,242 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 18:01:48,242 INFO L262 TraceCheckSpWp]: Trace formula consists of 107 conjuncts, 5 conjunts are in the unsatisfiable core [2023-12-02 18:01:48,244 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 18:01:48,276 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 6 proven. 2 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2023-12-02 18:01:48,276 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 18:01:48,313 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 6 proven. 2 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2023-12-02 18:01:48,313 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 18:01:48,313 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1672294803] [2023-12-02 18:01:48,313 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-02 18:01:48,314 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [388906996] [2023-12-02 18:01:48,314 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [388906996] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-02 18:01:48,314 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [672883956] [2023-12-02 18:01:48,316 INFO L159 IcfgInterpreter]: Started Sifa with 16 locations of interest [2023-12-02 18:01:48,317 INFO L166 IcfgInterpreter]: Building call graph [2023-12-02 18:01:48,317 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-12-02 18:01:48,317 INFO L176 IcfgInterpreter]: Starting interpretation [2023-12-02 18:01:48,317 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-12-02 18:01:49,765 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 10 for LOIs [2023-12-02 18:01:49,774 INFO L180 IcfgInterpreter]: Interpretation finished [2023-12-02 18:01:50,565 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1198#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-12-02 18:01:50,565 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-12-02 18:01:50,565 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-02 18:01:50,565 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 5] total 8 [2023-12-02 18:01:50,566 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [229397485] [2023-12-02 18:01:50,566 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-02 18:01:50,566 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2023-12-02 18:01:50,566 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 18:01:50,567 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2023-12-02 18:01:50,567 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=68, Invalid=274, Unknown=0, NotChecked=0, Total=342 [2023-12-02 18:01:50,567 INFO L87 Difference]: Start difference. First operand 46 states and 53 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, (7), 3 states have call predecessors, (7), 2 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2023-12-02 18:01:50,665 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 18:01:50,665 INFO L93 Difference]: Finished difference Result 109 states and 130 transitions. [2023-12-02 18:01:50,665 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2023-12-02 18:01:50,665 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, (7), 3 states have call predecessors, (7), 2 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) Word has length 27 [2023-12-02 18:01:50,666 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 18:01:50,667 INFO L225 Difference]: With dead ends: 109 [2023-12-02 18:01:50,667 INFO L226 Difference]: Without dead ends: 96 [2023-12-02 18:01:50,668 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 82 GetRequests, 62 SyntacticMatches, 0 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 107 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=88, Invalid=374, Unknown=0, NotChecked=0, Total=462 [2023-12-02 18:01:50,669 INFO L413 NwaCegarLoop]: 24 mSDtfsCounter, 34 mSDsluCounter, 76 mSDsCounter, 0 mSdLazyCounter, 58 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 34 SdHoareTripleChecker+Valid, 100 SdHoareTripleChecker+Invalid, 60 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 58 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-12-02 18:01:50,669 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [34 Valid, 100 Invalid, 60 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 58 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-12-02 18:01:50,670 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 96 states. [2023-12-02 18:01:50,685 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 96 to 91. [2023-12-02 18:01:50,685 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 91 states, 58 states have (on average 1.1896551724137931) internal successors, (69), 60 states have internal predecessors, (69), 20 states have call successors, (20), 12 states have call predecessors, (20), 12 states have return successors, (18), 18 states have call predecessors, (18), 18 states have call successors, (18) [2023-12-02 18:01:50,687 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 91 states to 91 states and 107 transitions. [2023-12-02 18:01:50,687 INFO L78 Accepts]: Start accepts. Automaton has 91 states and 107 transitions. Word has length 27 [2023-12-02 18:01:50,687 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 18:01:50,687 INFO L495 AbstractCegarLoop]: Abstraction has 91 states and 107 transitions. [2023-12-02 18:01:50,687 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, (7), 3 states have call predecessors, (7), 2 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2023-12-02 18:01:50,688 INFO L276 IsEmpty]: Start isEmpty. Operand 91 states and 107 transitions. [2023-12-02 18:01:50,688 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2023-12-02 18:01:50,689 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 18:01:50,689 INFO L195 NwaCegarLoop]: trace histogram [6, 5, 5, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1] [2023-12-02 18:01:50,694 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2023-12-02 18:01:50,889 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 18:01:50,889 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 18:01:50,890 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 18:01:50,890 INFO L85 PathProgramCache]: Analyzing trace with hash 747162997, now seen corresponding path program 1 times [2023-12-02 18:01:50,890 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 18:01:50,890 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [657634343] [2023-12-02 18:01:50,890 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 18:01:50,890 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 18:01:50,897 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-02 18:01:50,898 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1033705634] [2023-12-02 18:01:50,898 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 18:01:50,898 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 18:01:50,898 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 18:01:50,899 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 18:01:50,900 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2023-12-02 18:01:50,945 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 18:01:50,946 INFO L262 TraceCheckSpWp]: Trace formula consists of 120 conjuncts, 23 conjunts are in the unsatisfiable core [2023-12-02 18:01:50,948 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 18:01:51,042 INFO L134 CoverageAnalysis]: Checked inductivity of 55 backedges. 9 proven. 18 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2023-12-02 18:01:51,042 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 18:01:51,132 INFO L134 CoverageAnalysis]: Checked inductivity of 55 backedges. 12 proven. 13 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2023-12-02 18:01:51,133 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 18:01:51,133 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [657634343] [2023-12-02 18:01:51,133 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-02 18:01:51,133 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1033705634] [2023-12-02 18:01:51,133 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1033705634] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-02 18:01:51,133 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1561647484] [2023-12-02 18:01:51,135 INFO L159 IcfgInterpreter]: Started Sifa with 13 locations of interest [2023-12-02 18:01:51,135 INFO L166 IcfgInterpreter]: Building call graph [2023-12-02 18:01:51,135 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-12-02 18:01:51,135 INFO L176 IcfgInterpreter]: Starting interpretation [2023-12-02 18:01:51,135 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-12-02 18:01:52,152 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 10 for LOIs [2023-12-02 18:01:52,159 INFO L180 IcfgInterpreter]: Interpretation finished [2023-12-02 18:01:52,891 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1717#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-12-02 18:01:52,891 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-12-02 18:01:52,891 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-02 18:01:52,891 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 7] total 13 [2023-12-02 18:01:52,891 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1774656224] [2023-12-02 18:01:52,891 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-02 18:01:52,892 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2023-12-02 18:01:52,892 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 18:01:52,892 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2023-12-02 18:01:52,893 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=83, Invalid=379, Unknown=0, NotChecked=0, Total=462 [2023-12-02 18:01:52,893 INFO L87 Difference]: Start difference. First operand 91 states and 107 transitions. Second operand has 13 states, 13 states have (on average 1.9230769230769231) internal successors, (25), 11 states have internal predecessors, (25), 5 states have call successors, (11), 3 states have call predecessors, (11), 2 states have return successors, (9), 3 states have call predecessors, (9), 5 states have call successors, (9) [2023-12-02 18:01:53,055 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 18:01:53,055 INFO L93 Difference]: Finished difference Result 131 states and 161 transitions. [2023-12-02 18:01:53,055 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2023-12-02 18:01:53,056 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 1.9230769230769231) internal successors, (25), 11 states have internal predecessors, (25), 5 states have call successors, (11), 3 states have call predecessors, (11), 2 states have return successors, (9), 3 states have call predecessors, (9), 5 states have call successors, (9) Word has length 35 [2023-12-02 18:01:53,056 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 18:01:53,058 INFO L225 Difference]: With dead ends: 131 [2023-12-02 18:01:53,058 INFO L226 Difference]: Without dead ends: 111 [2023-12-02 18:01:53,058 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 105 GetRequests, 83 SyntacticMatches, 0 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 119 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=99, Invalid=453, Unknown=0, NotChecked=0, Total=552 [2023-12-02 18:01:53,059 INFO L413 NwaCegarLoop]: 27 mSDtfsCounter, 46 mSDsluCounter, 107 mSDsCounter, 0 mSdLazyCounter, 141 mSolverCounterSat, 32 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 59 SdHoareTripleChecker+Valid, 134 SdHoareTripleChecker+Invalid, 173 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 32 IncrementalHoareTripleChecker+Valid, 141 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-12-02 18:01:53,059 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [59 Valid, 134 Invalid, 173 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [32 Valid, 141 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-12-02 18:01:53,060 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 111 states. [2023-12-02 18:01:53,076 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 111 to 109. [2023-12-02 18:01:53,076 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 109 states, 69 states have (on average 1.1594202898550725) internal successors, (80), 73 states have internal predecessors, (80), 25 states have call successors, (25), 14 states have call predecessors, (25), 14 states have return successors, (22), 21 states have call predecessors, (22), 22 states have call successors, (22) [2023-12-02 18:01:53,078 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 109 states to 109 states and 127 transitions. [2023-12-02 18:01:53,078 INFO L78 Accepts]: Start accepts. Automaton has 109 states and 127 transitions. Word has length 35 [2023-12-02 18:01:53,078 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 18:01:53,078 INFO L495 AbstractCegarLoop]: Abstraction has 109 states and 127 transitions. [2023-12-02 18:01:53,079 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, (11), 3 states have call predecessors, (11), 2 states have return successors, (9), 3 states have call predecessors, (9), 5 states have call successors, (9) [2023-12-02 18:01:53,079 INFO L276 IsEmpty]: Start isEmpty. Operand 109 states and 127 transitions. [2023-12-02 18:01:53,080 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2023-12-02 18:01:53,080 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 18:01:53,080 INFO L195 NwaCegarLoop]: trace histogram [7, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 18:01:53,085 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2023-12-02 18:01:53,281 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,7 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 18:01:53,281 INFO L420 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 18:01:53,281 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 18:01:53,281 INFO L85 PathProgramCache]: Analyzing trace with hash 387112662, now seen corresponding path program 1 times [2023-12-02 18:01:53,282 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 18:01:53,282 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1367192218] [2023-12-02 18:01:53,282 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 18:01:53,282 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 18:01:53,287 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-02 18:01:53,287 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [887485803] [2023-12-02 18:01:53,288 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 18:01:53,288 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 18:01:53,288 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 18:01:53,289 INFO L229 MonitoredProcess]: Starting monitored process 8 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 18:01:53,289 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2023-12-02 18:01:53,333 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 18:01:53,334 INFO L262 TraceCheckSpWp]: Trace formula consists of 135 conjuncts, 17 conjunts are in the unsatisfiable core [2023-12-02 18:01:53,336 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 18:01:53,428 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 11 proven. 16 refuted. 0 times theorem prover too weak. 51 trivial. 0 not checked. [2023-12-02 18:01:53,428 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 18:01:53,536 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 14 proven. 16 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2023-12-02 18:01:53,536 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 18:01:53,536 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1367192218] [2023-12-02 18:01:53,536 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-02 18:01:53,537 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [887485803] [2023-12-02 18:01:53,537 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [887485803] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-02 18:01:53,537 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1500543727] [2023-12-02 18:01:53,539 INFO L159 IcfgInterpreter]: Started Sifa with 16 locations of interest [2023-12-02 18:01:53,539 INFO L166 IcfgInterpreter]: Building call graph [2023-12-02 18:01:53,539 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-12-02 18:01:53,540 INFO L176 IcfgInterpreter]: Starting interpretation [2023-12-02 18:01:53,540 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-12-02 18:01:54,550 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 6 for LOIs [2023-12-02 18:01:54,554 INFO L180 IcfgInterpreter]: Interpretation finished [2023-12-02 18:01:55,364 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '2341#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-12-02 18:01:55,364 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-12-02 18:01:55,364 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-02 18:01:55,365 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 11 [2023-12-02 18:01:55,365 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1974501289] [2023-12-02 18:01:55,365 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-02 18:01:55,365 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2023-12-02 18:01:55,365 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 18:01:55,366 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2023-12-02 18:01:55,366 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=109, Invalid=397, Unknown=0, NotChecked=0, Total=506 [2023-12-02 18:01:55,367 INFO L87 Difference]: Start difference. First operand 109 states and 127 transitions. Second operand has 11 states, 11 states have (on average 2.6363636363636362) internal successors, (29), 10 states have internal predecessors, (29), 3 states have call successors, (9), 3 states have call predecessors, (9), 2 states have return successors, (8), 2 states have call predecessors, (8), 3 states have call successors, (8) [2023-12-02 18:01:55,473 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 18:01:55,473 INFO L93 Difference]: Finished difference Result 125 states and 145 transitions. [2023-12-02 18:01:55,473 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2023-12-02 18:01:55,473 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 11 states have (on average 2.6363636363636362) internal successors, (29), 10 states have internal predecessors, (29), 3 states have call successors, (9), 3 states have call predecessors, (9), 2 states have return successors, (8), 2 states have call predecessors, (8), 3 states have call successors, (8) Word has length 43 [2023-12-02 18:01:55,474 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 18:01:55,475 INFO L225 Difference]: With dead ends: 125 [2023-12-02 18:01:55,475 INFO L226 Difference]: Without dead ends: 121 [2023-12-02 18:01:55,476 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 129 GetRequests, 106 SyntacticMatches, 0 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 162 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=125, Invalid=475, Unknown=0, NotChecked=0, Total=600 [2023-12-02 18:01:55,476 INFO L413 NwaCegarLoop]: 17 mSDtfsCounter, 22 mSDsluCounter, 72 mSDsCounter, 0 mSdLazyCounter, 98 mSolverCounterSat, 17 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 27 SdHoareTripleChecker+Valid, 89 SdHoareTripleChecker+Invalid, 115 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 17 IncrementalHoareTripleChecker+Valid, 98 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-12-02 18:01:55,477 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [27 Valid, 89 Invalid, 115 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [17 Valid, 98 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-12-02 18:01:55,477 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 121 states. [2023-12-02 18:01:55,488 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 121 to 117. [2023-12-02 18:01:55,488 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 117 states, 75 states have (on average 1.1466666666666667) internal successors, (86), 78 states have internal predecessors, (86), 26 states have call successors, (26), 16 states have call predecessors, (26), 15 states have return successors, (23), 22 states have call predecessors, (23), 23 states have call successors, (23) [2023-12-02 18:01:55,489 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 117 states to 117 states and 135 transitions. [2023-12-02 18:01:55,489 INFO L78 Accepts]: Start accepts. Automaton has 117 states and 135 transitions. Word has length 43 [2023-12-02 18:01:55,489 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 18:01:55,489 INFO L495 AbstractCegarLoop]: Abstraction has 117 states and 135 transitions. [2023-12-02 18:01:55,489 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 11 states have (on average 2.6363636363636362) internal successors, (29), 10 states have internal predecessors, (29), 3 states have call successors, (9), 3 states have call predecessors, (9), 2 states have return successors, (8), 2 states have call predecessors, (8), 3 states have call successors, (8) [2023-12-02 18:01:55,490 INFO L276 IsEmpty]: Start isEmpty. Operand 117 states and 135 transitions. [2023-12-02 18:01:55,491 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 49 [2023-12-02 18:01:55,491 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 18:01:55,491 INFO L195 NwaCegarLoop]: trace histogram [8, 7, 7, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 18:01:55,495 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2023-12-02 18:01:55,691 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,8 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 18:01:55,692 INFO L420 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 18:01:55,692 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 18:01:55,692 INFO L85 PathProgramCache]: Analyzing trace with hash 1125945480, now seen corresponding path program 1 times [2023-12-02 18:01:55,692 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 18:01:55,692 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1751953207] [2023-12-02 18:01:55,692 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 18:01:55,692 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 18:01:55,698 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-02 18:01:55,699 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1479733122] [2023-12-02 18:01:55,699 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 18:01:55,699 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 18:01:55,699 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 18:01:55,700 INFO L229 MonitoredProcess]: Starting monitored process 9 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 18:01:55,701 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2023-12-02 18:01:55,745 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 18:01:55,746 INFO L262 TraceCheckSpWp]: Trace formula consists of 144 conjuncts, 7 conjunts are in the unsatisfiable core [2023-12-02 18:01:55,748 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 18:01:55,795 INFO L134 CoverageAnalysis]: Checked inductivity of 104 backedges. 36 proven. 42 refuted. 0 times theorem prover too weak. 26 trivial. 0 not checked. [2023-12-02 18:01:55,796 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 18:01:55,838 INFO L134 CoverageAnalysis]: Checked inductivity of 104 backedges. 14 proven. 6 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2023-12-02 18:01:55,838 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 18:01:55,838 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1751953207] [2023-12-02 18:01:55,839 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-02 18:01:55,839 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1479733122] [2023-12-02 18:01:55,839 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1479733122] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-02 18:01:55,839 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1885615333] [2023-12-02 18:01:55,841 INFO L159 IcfgInterpreter]: Started Sifa with 17 locations of interest [2023-12-02 18:01:55,841 INFO L166 IcfgInterpreter]: Building call graph [2023-12-02 18:01:55,841 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-12-02 18:01:55,842 INFO L176 IcfgInterpreter]: Starting interpretation [2023-12-02 18:01:55,842 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-12-02 18:01:56,849 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 10 for LOIs [2023-12-02 18:01:56,856 INFO L180 IcfgInterpreter]: Interpretation finished [2023-12-02 18:01:57,658 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '2996#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-12-02 18:01:57,658 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-12-02 18:01:57,658 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-02 18:01:57,658 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 6] total 9 [2023-12-02 18:01:57,659 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [27400500] [2023-12-02 18:01:57,659 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-02 18:01:57,659 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2023-12-02 18:01:57,659 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 18:01:57,660 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2023-12-02 18:01:57,660 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=79, Invalid=341, Unknown=0, NotChecked=0, Total=420 [2023-12-02 18:01:57,660 INFO L87 Difference]: Start difference. First operand 117 states and 135 transitions. Second operand has 9 states, 9 states have (on average 3.5555555555555554) internal successors, (32), 9 states have internal predecessors, (32), 5 states have call successors, (15), 4 states have call predecessors, (15), 4 states have return successors, (14), 5 states have call predecessors, (14), 5 states have call successors, (14) [2023-12-02 18:01:57,766 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 18:01:57,766 INFO L93 Difference]: Finished difference Result 173 states and 196 transitions. [2023-12-02 18:01:57,767 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2023-12-02 18:01:57,767 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 3.5555555555555554) internal successors, (32), 9 states have internal predecessors, (32), 5 states have call successors, (15), 4 states have call predecessors, (15), 4 states have return successors, (14), 5 states have call predecessors, (14), 5 states have call successors, (14) Word has length 48 [2023-12-02 18:01:57,767 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 18:01:57,769 INFO L225 Difference]: With dead ends: 173 [2023-12-02 18:01:57,769 INFO L226 Difference]: Without dead ends: 151 [2023-12-02 18:01:57,770 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 144 GetRequests, 121 SyntacticMatches, 2 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 142 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=90, Invalid=416, Unknown=0, NotChecked=0, Total=506 [2023-12-02 18:01:57,770 INFO L413 NwaCegarLoop]: 24 mSDtfsCounter, 33 mSDsluCounter, 86 mSDsCounter, 0 mSdLazyCounter, 74 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 33 SdHoareTripleChecker+Valid, 110 SdHoareTripleChecker+Invalid, 76 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 74 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-12-02 18:01:57,770 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [33 Valid, 110 Invalid, 76 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 74 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-12-02 18:01:57,771 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 151 states. [2023-12-02 18:01:57,783 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 151 to 148. [2023-12-02 18:01:57,783 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 148 states, 96 states have (on average 1.125) internal successors, (108), 100 states have internal predecessors, (108), 31 states have call successors, (31), 20 states have call predecessors, (31), 20 states have return successors, (28), 27 states have call predecessors, (28), 28 states have call successors, (28) [2023-12-02 18:01:57,784 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 148 states to 148 states and 167 transitions. [2023-12-02 18:01:57,784 INFO L78 Accepts]: Start accepts. Automaton has 148 states and 167 transitions. Word has length 48 [2023-12-02 18:01:57,784 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 18:01:57,784 INFO L495 AbstractCegarLoop]: Abstraction has 148 states and 167 transitions. [2023-12-02 18:01:57,785 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 3.5555555555555554) internal successors, (32), 9 states have internal predecessors, (32), 5 states have call successors, (15), 4 states have call predecessors, (15), 4 states have return successors, (14), 5 states have call predecessors, (14), 5 states have call successors, (14) [2023-12-02 18:01:57,785 INFO L276 IsEmpty]: Start isEmpty. Operand 148 states and 167 transitions. [2023-12-02 18:01:57,785 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 57 [2023-12-02 18:01:57,786 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 18:01:57,786 INFO L195 NwaCegarLoop]: trace histogram [9, 8, 8, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 18:01:57,790 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2023-12-02 18:01:57,986 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2023-12-02 18:01:57,986 INFO L420 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 18:01:57,987 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 18:01:57,987 INFO L85 PathProgramCache]: Analyzing trace with hash -1127123487, now seen corresponding path program 1 times [2023-12-02 18:01:57,987 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 18:01:57,987 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1669212222] [2023-12-02 18:01:57,987 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 18:01:57,987 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 18:01:57,994 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-02 18:01:57,994 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [699278832] [2023-12-02 18:01:57,995 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 18:01:57,995 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 18:01:57,995 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 18:01:57,996 INFO L229 MonitoredProcess]: Starting monitored process 10 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 18:01:57,996 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2023-12-02 18:01:58,045 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 18:01:58,047 INFO L262 TraceCheckSpWp]: Trace formula consists of 164 conjuncts, 31 conjunts are in the unsatisfiable core [2023-12-02 18:01:58,049 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 18:01:58,316 INFO L134 CoverageAnalysis]: Checked inductivity of 137 backedges. 15 proven. 31 refuted. 0 times theorem prover too weak. 91 trivial. 0 not checked. [2023-12-02 18:01:58,317 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 18:02:00,469 INFO L134 CoverageAnalysis]: Checked inductivity of 137 backedges. 15 proven. 31 refuted. 0 times theorem prover too weak. 91 trivial. 0 not checked. [2023-12-02 18:02:00,469 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 18:02:00,469 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1669212222] [2023-12-02 18:02:00,469 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-02 18:02:00,469 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [699278832] [2023-12-02 18:02:00,469 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [699278832] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-02 18:02:00,469 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [717461585] [2023-12-02 18:02:00,471 INFO L159 IcfgInterpreter]: Started Sifa with 18 locations of interest [2023-12-02 18:02:00,471 INFO L166 IcfgInterpreter]: Building call graph [2023-12-02 18:02:00,472 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-12-02 18:02:00,472 INFO L176 IcfgInterpreter]: Starting interpretation [2023-12-02 18:02:00,472 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-12-02 18:02:02,021 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2023-12-02 18:02:02,024 INFO L180 IcfgInterpreter]: Interpretation finished [2023-12-02 18:02:03,004 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '3815#(and (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-12-02 18:02:03,004 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-12-02 18:02:03,004 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-02 18:02:03,005 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 15 [2023-12-02 18:02:03,005 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2039640614] [2023-12-02 18:02:03,005 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-02 18:02:03,005 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2023-12-02 18:02:03,005 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 18:02:03,006 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2023-12-02 18:02:03,006 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=98, Invalid=552, Unknown=0, NotChecked=0, Total=650 [2023-12-02 18:02:03,007 INFO L87 Difference]: Start difference. First operand 148 states and 167 transitions. Second operand has 15 states, 15 states have (on average 2.466666666666667) internal successors, (37), 13 states have internal predecessors, (37), 7 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (16), 4 states have call predecessors, (16), 5 states have call successors, (16) [2023-12-02 18:02:06,402 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 18:02:06,402 INFO L93 Difference]: Finished difference Result 177 states and 196 transitions. [2023-12-02 18:02:06,402 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2023-12-02 18:02:06,403 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 15 states have (on average 2.466666666666667) internal successors, (37), 13 states have internal predecessors, (37), 7 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (16), 4 states have call predecessors, (16), 5 states have call successors, (16) Word has length 56 [2023-12-02 18:02:06,403 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 18:02:06,404 INFO L225 Difference]: With dead ends: 177 [2023-12-02 18:02:06,404 INFO L226 Difference]: Without dead ends: 173 [2023-12-02 18:02:06,405 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 171 GetRequests, 141 SyntacticMatches, 2 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 215 ImplicationChecksByTransitivity, 4.1s TimeCoverageRelationStatistics Valid=138, Invalid=732, Unknown=0, NotChecked=0, Total=870 [2023-12-02 18:02:06,405 INFO L413 NwaCegarLoop]: 24 mSDtfsCounter, 44 mSDsluCounter, 170 mSDsCounter, 0 mSdLazyCounter, 203 mSolverCounterSat, 47 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 45 SdHoareTripleChecker+Valid, 194 SdHoareTripleChecker+Invalid, 250 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 47 IncrementalHoareTripleChecker+Valid, 203 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2023-12-02 18:02:06,406 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [45 Valid, 194 Invalid, 250 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [47 Valid, 203 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2023-12-02 18:02:06,406 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 173 states. [2023-12-02 18:02:06,439 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 173 to 169. [2023-12-02 18:02:06,439 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 169 states, 112 states have (on average 1.1071428571428572) internal successors, (124), 116 states have internal predecessors, (124), 32 states have call successors, (32), 25 states have call predecessors, (32), 24 states have return successors, (29), 27 states have call predecessors, (29), 29 states have call successors, (29) [2023-12-02 18:02:06,440 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 169 states to 169 states and 185 transitions. [2023-12-02 18:02:06,440 INFO L78 Accepts]: Start accepts. Automaton has 169 states and 185 transitions. Word has length 56 [2023-12-02 18:02:06,441 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 18:02:06,441 INFO L495 AbstractCegarLoop]: Abstraction has 169 states and 185 transitions. [2023-12-02 18:02:06,441 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 2.466666666666667) internal successors, (37), 13 states have internal predecessors, (37), 7 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (16), 4 states have call predecessors, (16), 5 states have call successors, (16) [2023-12-02 18:02:06,441 INFO L276 IsEmpty]: Start isEmpty. Operand 169 states and 185 transitions. [2023-12-02 18:02:06,442 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 68 [2023-12-02 18:02:06,442 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 18:02:06,443 INFO L195 NwaCegarLoop]: trace histogram [11, 10, 10, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 18:02:06,447 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2023-12-02 18:02:06,643 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2023-12-02 18:02:06,644 INFO L420 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 18:02:06,644 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 18:02:06,644 INFO L85 PathProgramCache]: Analyzing trace with hash -143001442, now seen corresponding path program 1 times [2023-12-02 18:02:06,644 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 18:02:06,644 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [86989438] [2023-12-02 18:02:06,644 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 18:02:06,644 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 18:02:06,651 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-02 18:02:06,651 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [340588975] [2023-12-02 18:02:06,651 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 18:02:06,652 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 18:02:06,652 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 18:02:06,652 INFO L229 MonitoredProcess]: Starting monitored process 11 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 18:02:06,657 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2023-12-02 18:02:06,709 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 18:02:06,711 INFO L262 TraceCheckSpWp]: Trace formula consists of 184 conjuncts, 33 conjunts are in the unsatisfiable core [2023-12-02 18:02:06,714 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 18:02:06,936 INFO L134 CoverageAnalysis]: Checked inductivity of 211 backedges. 19 proven. 39 refuted. 0 times theorem prover too weak. 153 trivial. 0 not checked. [2023-12-02 18:02:06,936 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 18:02:07,574 INFO L134 CoverageAnalysis]: Checked inductivity of 211 backedges. 19 proven. 39 refuted. 0 times theorem prover too weak. 153 trivial. 0 not checked. [2023-12-02 18:02:07,574 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 18:02:07,574 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [86989438] [2023-12-02 18:02:07,574 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-02 18:02:07,574 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [340588975] [2023-12-02 18:02:07,574 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [340588975] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-02 18:02:07,575 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [797440754] [2023-12-02 18:02:07,577 INFO L159 IcfgInterpreter]: Started Sifa with 19 locations of interest [2023-12-02 18:02:07,577 INFO L166 IcfgInterpreter]: Building call graph [2023-12-02 18:02:07,577 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-12-02 18:02:07,577 INFO L176 IcfgInterpreter]: Starting interpretation [2023-12-02 18:02:07,577 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-12-02 18:02:09,041 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2023-12-02 18:02:09,043 INFO L180 IcfgInterpreter]: Interpretation finished [2023-12-02 18:02:10,008 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '4738#(and (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-12-02 18:02:10,008 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-12-02 18:02:10,009 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-02 18:02:10,009 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 17 [2023-12-02 18:02:10,009 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [153789769] [2023-12-02 18:02:10,009 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-02 18:02:10,009 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2023-12-02 18:02:10,010 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 18:02:10,010 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2023-12-02 18:02:10,011 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=130, Invalid=682, Unknown=0, NotChecked=0, Total=812 [2023-12-02 18:02:10,011 INFO L87 Difference]: Start difference. First operand 169 states and 185 transitions. Second operand has 17 states, 15 states have (on average 2.6) internal successors, (39), 15 states have internal predecessors, (39), 9 states have call successors, (22), 3 states have call predecessors, (22), 2 states have return successors, (20), 6 states have call predecessors, (20), 7 states have call successors, (20) [2023-12-02 18:02:10,629 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 18:02:10,629 INFO L93 Difference]: Finished difference Result 188 states and 208 transitions. [2023-12-02 18:02:10,629 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2023-12-02 18:02:10,630 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 15 states have (on average 2.6) internal successors, (39), 15 states have internal predecessors, (39), 9 states have call successors, (22), 3 states have call predecessors, (22), 2 states have return successors, (20), 6 states have call predecessors, (20), 7 states have call successors, (20) Word has length 67 [2023-12-02 18:02:10,630 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 18:02:10,631 INFO L225 Difference]: With dead ends: 188 [2023-12-02 18:02:10,631 INFO L226 Difference]: Without dead ends: 161 [2023-12-02 18:02:10,633 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 204 GetRequests, 170 SyntacticMatches, 3 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 301 ImplicationChecksByTransitivity, 1.5s TimeCoverageRelationStatistics Valid=180, Invalid=876, Unknown=0, NotChecked=0, Total=1056 [2023-12-02 18:02:10,633 INFO L413 NwaCegarLoop]: 24 mSDtfsCounter, 45 mSDsluCounter, 135 mSDsCounter, 0 mSdLazyCounter, 190 mSolverCounterSat, 45 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 46 SdHoareTripleChecker+Valid, 159 SdHoareTripleChecker+Invalid, 235 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 45 IncrementalHoareTripleChecker+Valid, 190 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2023-12-02 18:02:10,634 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [46 Valid, 159 Invalid, 235 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [45 Valid, 190 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2023-12-02 18:02:10,634 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 161 states. [2023-12-02 18:02:10,680 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 161 to 148. [2023-12-02 18:02:10,681 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 148 states, 98 states have (on average 1.1224489795918366) internal successors, (110), 100 states have internal predecessors, (110), 28 states have call successors, (28), 22 states have call predecessors, (28), 21 states have return successors, (26), 25 states have call predecessors, (26), 26 states have call successors, (26) [2023-12-02 18:02:10,682 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 148 states to 148 states and 164 transitions. [2023-12-02 18:02:10,683 INFO L78 Accepts]: Start accepts. Automaton has 148 states and 164 transitions. Word has length 67 [2023-12-02 18:02:10,683 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 18:02:10,683 INFO L495 AbstractCegarLoop]: Abstraction has 148 states and 164 transitions. [2023-12-02 18:02:10,683 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 15 states have (on average 2.6) internal successors, (39), 15 states have internal predecessors, (39), 9 states have call successors, (22), 3 states have call predecessors, (22), 2 states have return successors, (20), 6 states have call predecessors, (20), 7 states have call successors, (20) [2023-12-02 18:02:10,684 INFO L276 IsEmpty]: Start isEmpty. Operand 148 states and 164 transitions. [2023-12-02 18:02:10,685 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 78 [2023-12-02 18:02:10,685 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 18:02:10,685 INFO L195 NwaCegarLoop]: trace histogram [13, 12, 12, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 18:02:10,690 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Ended with exit code 0 [2023-12-02 18:02:10,886 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable11 [2023-12-02 18:02:10,886 INFO L420 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 18:02:10,886 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 18:02:10,886 INFO L85 PathProgramCache]: Analyzing trace with hash -319401384, now seen corresponding path program 1 times [2023-12-02 18:02:10,887 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 18:02:10,887 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1611275024] [2023-12-02 18:02:10,887 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 18:02:10,887 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 18:02:10,894 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-02 18:02:10,895 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [982045701] [2023-12-02 18:02:10,895 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 18:02:10,895 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 18:02:10,895 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 18:02:10,896 INFO L229 MonitoredProcess]: Starting monitored process 12 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 18:02:10,897 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2023-12-02 18:02:10,950 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 18:02:10,951 INFO L262 TraceCheckSpWp]: Trace formula consists of 201 conjuncts, 4 conjunts are in the unsatisfiable core [2023-12-02 18:02:10,953 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 18:02:10,988 INFO L134 CoverageAnalysis]: Checked inductivity of 306 backedges. 84 proven. 0 refuted. 0 times theorem prover too weak. 222 trivial. 0 not checked. [2023-12-02 18:02:10,988 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-12-02 18:02:10,988 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 18:02:10,988 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1611275024] [2023-12-02 18:02:10,988 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-02 18:02:10,988 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [982045701] [2023-12-02 18:02:10,988 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [982045701] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-02 18:02:10,988 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-12-02 18:02:10,988 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2023-12-02 18:02:10,989 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [792999772] [2023-12-02 18:02:10,989 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-02 18:02:10,989 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-12-02 18:02:10,989 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 18:02:10,990 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-12-02 18:02:10,990 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=10, Unknown=0, NotChecked=0, Total=20 [2023-12-02 18:02:10,990 INFO L87 Difference]: Start difference. First operand 148 states and 164 transitions. Second operand has 5 states, 5 states have (on average 4.2) internal successors, (21), 5 states have internal predecessors, (21), 4 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2023-12-02 18:02:11,077 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 18:02:11,078 INFO L93 Difference]: Finished difference Result 163 states and 179 transitions. [2023-12-02 18:02:11,078 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2023-12-02 18:02:11,078 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 4.2) internal successors, (21), 5 states have internal predecessors, (21), 4 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) Word has length 77 [2023-12-02 18:02:11,078 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 18:02:11,079 INFO L225 Difference]: With dead ends: 163 [2023-12-02 18:02:11,080 INFO L226 Difference]: Without dead ends: 143 [2023-12-02 18:02:11,080 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 76 GetRequests, 73 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=10, Invalid=10, Unknown=0, NotChecked=0, Total=20 [2023-12-02 18:02:11,081 INFO L413 NwaCegarLoop]: 43 mSDtfsCounter, 11 mSDsluCounter, 48 mSDsCounter, 0 mSdLazyCounter, 23 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 18 SdHoareTripleChecker+Valid, 91 SdHoareTripleChecker+Invalid, 28 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 23 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-12-02 18:02:11,081 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [18 Valid, 91 Invalid, 28 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 23 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-12-02 18:02:11,082 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 143 states. [2023-12-02 18:02:11,127 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 143 to 140. [2023-12-02 18:02:11,127 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 140 states, 93 states have (on average 1.096774193548387) internal successors, (102), 95 states have internal predecessors, (102), 26 states have call successors, (26), 20 states have call predecessors, (26), 20 states have return successors, (25), 24 states have call predecessors, (25), 25 states have call successors, (25) [2023-12-02 18:02:11,128 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 140 states to 140 states and 153 transitions. [2023-12-02 18:02:11,129 INFO L78 Accepts]: Start accepts. Automaton has 140 states and 153 transitions. Word has length 77 [2023-12-02 18:02:11,129 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 18:02:11,129 INFO L495 AbstractCegarLoop]: Abstraction has 140 states and 153 transitions. [2023-12-02 18:02:11,129 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 4.2) internal successors, (21), 5 states have internal predecessors, (21), 4 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2023-12-02 18:02:11,129 INFO L276 IsEmpty]: Start isEmpty. Operand 140 states and 153 transitions. [2023-12-02 18:02:11,130 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 80 [2023-12-02 18:02:11,130 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 18:02:11,131 INFO L195 NwaCegarLoop]: trace histogram [13, 12, 12, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1] [2023-12-02 18:02:11,135 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2023-12-02 18:02:11,331 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable12,12 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 18:02:11,331 INFO L420 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 18:02:11,331 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 18:02:11,331 INFO L85 PathProgramCache]: Analyzing trace with hash -1379671488, now seen corresponding path program 2 times [2023-12-02 18:02:11,332 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 18:02:11,332 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [427724572] [2023-12-02 18:02:11,332 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 18:02:11,332 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 18:02:11,338 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-02 18:02:11,338 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [628263695] [2023-12-02 18:02:11,338 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-12-02 18:02:11,338 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 18:02:11,338 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 18:02:11,339 INFO L229 MonitoredProcess]: Starting monitored process 13 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 18:02:11,340 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2023-12-02 18:02:11,391 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2023-12-02 18:02:11,391 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-02 18:02:11,392 INFO L262 TraceCheckSpWp]: Trace formula consists of 141 conjuncts, 31 conjunts are in the unsatisfiable core [2023-12-02 18:02:11,395 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 18:02:11,586 INFO L134 CoverageAnalysis]: Checked inductivity of 310 backedges. 41 proven. 38 refuted. 0 times theorem prover too weak. 231 trivial. 0 not checked. [2023-12-02 18:02:11,586 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 18:02:13,333 INFO L134 CoverageAnalysis]: Checked inductivity of 310 backedges. 41 proven. 32 refuted. 0 times theorem prover too weak. 237 trivial. 0 not checked. [2023-12-02 18:02:13,333 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 18:02:13,333 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [427724572] [2023-12-02 18:02:13,333 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-02 18:02:13,333 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [628263695] [2023-12-02 18:02:13,333 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [628263695] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-02 18:02:13,333 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [154008343] [2023-12-02 18:02:13,335 INFO L159 IcfgInterpreter]: Started Sifa with 18 locations of interest [2023-12-02 18:02:13,335 INFO L166 IcfgInterpreter]: Building call graph [2023-12-02 18:02:13,335 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-12-02 18:02:13,335 INFO L176 IcfgInterpreter]: Starting interpretation [2023-12-02 18:02:13,336 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-12-02 18:02:14,591 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2023-12-02 18:02:14,593 INFO L180 IcfgInterpreter]: Interpretation finished [2023-12-02 18:02:15,506 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '6381#(and (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-12-02 18:02:15,506 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-12-02 18:02:15,506 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-02 18:02:15,506 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 9] total 17 [2023-12-02 18:02:15,506 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [794225002] [2023-12-02 18:02:15,506 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-02 18:02:15,507 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2023-12-02 18:02:15,507 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 18:02:15,507 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2023-12-02 18:02:15,508 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=118, Invalid=638, Unknown=0, NotChecked=0, Total=756 [2023-12-02 18:02:15,508 INFO L87 Difference]: Start difference. First operand 140 states and 153 transitions. Second operand has 17 states, 17 states have (on average 2.411764705882353) internal successors, (41), 16 states have internal predecessors, (41), 9 states have call successors, (23), 3 states have call predecessors, (23), 2 states have return successors, (21), 7 states have call predecessors, (21), 9 states have call successors, (21) [2023-12-02 18:02:21,693 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-02 18:02:22,148 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 18:02:22,148 INFO L93 Difference]: Finished difference Result 162 states and 185 transitions. [2023-12-02 18:02:22,148 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2023-12-02 18:02:22,148 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 17 states have (on average 2.411764705882353) internal successors, (41), 16 states have internal predecessors, (41), 9 states have call successors, (23), 3 states have call predecessors, (23), 2 states have return successors, (21), 7 states have call predecessors, (21), 9 states have call successors, (21) Word has length 79 [2023-12-02 18:02:22,149 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 18:02:22,150 INFO L225 Difference]: With dead ends: 162 [2023-12-02 18:02:22,150 INFO L226 Difference]: Without dead ends: 160 [2023-12-02 18:02:22,151 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 238 GetRequests, 207 SyntacticMatches, 3 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 248 ImplicationChecksByTransitivity, 5.2s TimeCoverageRelationStatistics Valid=142, Invalid=728, Unknown=0, NotChecked=0, Total=870 [2023-12-02 18:02:22,151 INFO L413 NwaCegarLoop]: 29 mSDtfsCounter, 40 mSDsluCounter, 159 mSDsCounter, 0 mSdLazyCounter, 230 mSolverCounterSat, 38 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 48 SdHoareTripleChecker+Valid, 188 SdHoareTripleChecker+Invalid, 269 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 38 IncrementalHoareTripleChecker+Valid, 230 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.6s IncrementalHoareTripleChecker+Time [2023-12-02 18:02:22,151 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [48 Valid, 188 Invalid, 269 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [38 Valid, 230 Invalid, 1 Unknown, 0 Unchecked, 2.6s Time] [2023-12-02 18:02:22,152 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 160 states. [2023-12-02 18:02:22,191 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 160 to 156. [2023-12-02 18:02:22,191 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 156 states, 102 states have (on average 1.1176470588235294) internal successors, (114), 105 states have internal predecessors, (114), 32 states have call successors, (32), 21 states have call predecessors, (32), 21 states have return successors, (31), 29 states have call predecessors, (31), 31 states have call successors, (31) [2023-12-02 18:02:22,192 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 156 states to 156 states and 177 transitions. [2023-12-02 18:02:22,192 INFO L78 Accepts]: Start accepts. Automaton has 156 states and 177 transitions. Word has length 79 [2023-12-02 18:02:22,193 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 18:02:22,193 INFO L495 AbstractCegarLoop]: Abstraction has 156 states and 177 transitions. [2023-12-02 18:02:22,193 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 17 states have (on average 2.411764705882353) internal successors, (41), 16 states have internal predecessors, (41), 9 states have call successors, (23), 3 states have call predecessors, (23), 2 states have return successors, (21), 7 states have call predecessors, (21), 9 states have call successors, (21) [2023-12-02 18:02:22,193 INFO L276 IsEmpty]: Start isEmpty. Operand 156 states and 177 transitions. [2023-12-02 18:02:22,194 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 87 [2023-12-02 18:02:22,194 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 18:02:22,194 INFO L195 NwaCegarLoop]: trace histogram [14, 13, 13, 5, 4, 4, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 18:02:22,198 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Ended with exit code 0 [2023-12-02 18:02:22,395 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable13,13 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 18:02:22,395 INFO L420 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 18:02:22,395 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 18:02:22,395 INFO L85 PathProgramCache]: Analyzing trace with hash -501231567, now seen corresponding path program 1 times [2023-12-02 18:02:22,395 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 18:02:22,395 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [738994394] [2023-12-02 18:02:22,395 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 18:02:22,395 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 18:02:22,401 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-02 18:02:22,401 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [402294278] [2023-12-02 18:02:22,401 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 18:02:22,402 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 18:02:22,402 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 18:02:22,403 INFO L229 MonitoredProcess]: Starting monitored process 14 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 18:02:22,404 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2023-12-02 18:02:22,461 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 18:02:22,462 INFO L262 TraceCheckSpWp]: Trace formula consists of 227 conjuncts, 11 conjunts are in the unsatisfiable core [2023-12-02 18:02:22,464 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 18:02:22,558 INFO L134 CoverageAnalysis]: Checked inductivity of 382 backedges. 72 proven. 260 refuted. 0 times theorem prover too weak. 50 trivial. 0 not checked. [2023-12-02 18:02:22,558 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 18:02:22,627 INFO L134 CoverageAnalysis]: Checked inductivity of 382 backedges. 26 proven. 44 refuted. 0 times theorem prover too weak. 312 trivial. 0 not checked. [2023-12-02 18:02:22,627 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 18:02:22,627 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [738994394] [2023-12-02 18:02:22,627 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-02 18:02:22,627 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [402294278] [2023-12-02 18:02:22,628 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [402294278] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-02 18:02:22,628 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [228327872] [2023-12-02 18:02:22,629 INFO L159 IcfgInterpreter]: Started Sifa with 17 locations of interest [2023-12-02 18:02:22,629 INFO L166 IcfgInterpreter]: Building call graph [2023-12-02 18:02:22,630 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-12-02 18:02:22,630 INFO L176 IcfgInterpreter]: Starting interpretation [2023-12-02 18:02:22,630 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-12-02 18:02:23,587 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 10 for LOIs [2023-12-02 18:02:23,595 INFO L180 IcfgInterpreter]: Interpretation finished [2023-12-02 18:02:24,469 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '7369#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-12-02 18:02:24,469 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-12-02 18:02:24,469 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-02 18:02:24,469 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 8] total 8 [2023-12-02 18:02:24,469 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [543990640] [2023-12-02 18:02:24,469 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-02 18:02:24,470 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2023-12-02 18:02:24,470 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 18:02:24,470 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2023-12-02 18:02:24,470 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=80, Invalid=300, Unknown=0, NotChecked=0, Total=380 [2023-12-02 18:02:24,470 INFO L87 Difference]: Start difference. First operand 156 states and 177 transitions. Second operand has 8 states, 8 states have (on average 4.625) internal successors, (37), 8 states have internal predecessors, (37), 5 states have call successors, (27), 6 states have call predecessors, (27), 6 states have return successors, (26), 5 states have call predecessors, (26), 5 states have call successors, (26) [2023-12-02 18:02:24,606 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 18:02:24,606 INFO L93 Difference]: Finished difference Result 202 states and 230 transitions. [2023-12-02 18:02:24,607 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2023-12-02 18:02:24,607 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 4.625) internal successors, (37), 8 states have internal predecessors, (37), 5 states have call successors, (27), 6 states have call predecessors, (27), 6 states have return successors, (26), 5 states have call predecessors, (26), 5 states have call successors, (26) Word has length 86 [2023-12-02 18:02:24,607 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 18:02:24,609 INFO L225 Difference]: With dead ends: 202 [2023-12-02 18:02:24,609 INFO L226 Difference]: Without dead ends: 158 [2023-12-02 18:02:24,609 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 260 GetRequests, 232 SyntacticMatches, 6 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 134 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=108, Invalid=444, Unknown=0, NotChecked=0, Total=552 [2023-12-02 18:02:24,610 INFO L413 NwaCegarLoop]: 24 mSDtfsCounter, 8 mSDsluCounter, 83 mSDsCounter, 0 mSdLazyCounter, 59 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 107 SdHoareTripleChecker+Invalid, 60 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 59 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-12-02 18:02:24,610 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 107 Invalid, 60 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 59 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-12-02 18:02:24,611 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 158 states. [2023-12-02 18:02:24,650 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 158 to 158. [2023-12-02 18:02:24,650 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 158 states, 104 states have (on average 1.1153846153846154) internal successors, (116), 107 states have internal predecessors, (116), 32 states have call successors, (32), 21 states have call predecessors, (32), 21 states have return successors, (31), 29 states have call predecessors, (31), 31 states have call successors, (31) [2023-12-02 18:02:24,651 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 158 states to 158 states and 179 transitions. [2023-12-02 18:02:24,651 INFO L78 Accepts]: Start accepts. Automaton has 158 states and 179 transitions. Word has length 86 [2023-12-02 18:02:24,651 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 18:02:24,652 INFO L495 AbstractCegarLoop]: Abstraction has 158 states and 179 transitions. [2023-12-02 18:02:24,652 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 4.625) internal successors, (37), 8 states have internal predecessors, (37), 5 states have call successors, (27), 6 states have call predecessors, (27), 6 states have return successors, (26), 5 states have call predecessors, (26), 5 states have call successors, (26) [2023-12-02 18:02:24,652 INFO L276 IsEmpty]: Start isEmpty. Operand 158 states and 179 transitions. [2023-12-02 18:02:24,653 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 88 [2023-12-02 18:02:24,653 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 18:02:24,653 INFO L195 NwaCegarLoop]: trace histogram [14, 13, 13, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1] [2023-12-02 18:02:24,657 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Ended with exit code 0 [2023-12-02 18:02:24,853 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable14,14 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 18:02:24,854 INFO L420 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 18:02:24,854 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 18:02:24,854 INFO L85 PathProgramCache]: Analyzing trace with hash 1528689375, now seen corresponding path program 3 times [2023-12-02 18:02:24,854 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 18:02:24,854 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1777606459] [2023-12-02 18:02:24,854 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 18:02:24,854 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 18:02:24,863 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-02 18:02:24,863 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [435480706] [2023-12-02 18:02:24,863 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2023-12-02 18:02:24,863 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 18:02:24,863 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 18:02:24,864 INFO L229 MonitoredProcess]: Starting monitored process 15 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 18:02:24,865 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2023-12-02 18:02:25,025 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2023-12-02 18:02:25,025 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-02 18:02:25,028 INFO L262 TraceCheckSpWp]: Trace formula consists of 181 conjuncts, 51 conjunts are in the unsatisfiable core [2023-12-02 18:02:25,031 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 18:02:46,219 INFO L134 CoverageAnalysis]: Checked inductivity of 367 backedges. 109 proven. 61 refuted. 5 times theorem prover too weak. 192 trivial. 0 not checked. [2023-12-02 18:02:46,219 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 18:03:06,801 WARN L293 SmtUtils]: Spent 8.43s on a formula simplification that was a NOOP. DAG size: 66 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-12-02 18:03:32,208 WARN L293 SmtUtils]: Spent 6.50s on a formula simplification that was a NOOP. DAG size: 52 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-12-02 18:04:44,502 WARN L293 SmtUtils]: Spent 29.46s on a formula simplification that was a NOOP. DAG size: 121 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-12-02 18:06:55,786 WARN L293 SmtUtils]: Spent 5.33s on a formula simplification that was a NOOP. DAG size: 77 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-12-02 18:07:34,884 INFO L134 CoverageAnalysis]: Checked inductivity of 367 backedges. 113 proven. 32 refuted. 0 times theorem prover too weak. 222 trivial. 0 not checked. [2023-12-02 18:07:34,884 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 18:07:34,884 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1777606459] [2023-12-02 18:07:34,884 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-02 18:07:34,884 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [435480706] [2023-12-02 18:07:34,884 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [435480706] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-02 18:07:34,884 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [636802498] [2023-12-02 18:07:34,886 INFO L159 IcfgInterpreter]: Started Sifa with 18 locations of interest [2023-12-02 18:07:34,886 INFO L166 IcfgInterpreter]: Building call graph [2023-12-02 18:07:34,886 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-12-02 18:07:34,886 INFO L176 IcfgInterpreter]: Starting interpretation [2023-12-02 18:07:34,887 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-12-02 18:07:36,164 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2023-12-02 18:07:36,166 INFO L180 IcfgInterpreter]: Interpretation finished [2023-12-02 18:07:38,073 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '8443#(and (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-12-02 18:07:38,073 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-12-02 18:07:38,073 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-02 18:07:38,074 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 15] total 26 [2023-12-02 18:07:38,074 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [596547671] [2023-12-02 18:07:38,074 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-02 18:07:38,074 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 26 states [2023-12-02 18:07:38,074 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 18:07:38,075 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2023-12-02 18:07:38,076 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=240, Invalid=1083, Unknown=9, NotChecked=0, Total=1332 [2023-12-02 18:07:38,076 INFO L87 Difference]: Start difference. First operand 158 states and 179 transitions. Second operand has 26 states, 24 states have (on average 1.9166666666666667) internal successors, (46), 18 states have internal predecessors, (46), 16 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 13 states have call predecessors, (24), 14 states have call successors, (24) [2023-12-02 18:08:47,300 WARN L293 SmtUtils]: Spent 1.09m on a formula simplification. DAG size of input: 190 DAG size of output: 98 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-12-02 18:08:54,723 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-02 18:08:56,725 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-02 18:08:58,236 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.51s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-02 18:09:00,286 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-02 18:09:06,620 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.39s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-02 18:09:21,749 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.64s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-02 18:09:29,753 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.75s for a HTC check with result VALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-02 18:09:31,436 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.55s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-02 18:09:35,033 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-02 18:10:12,633 WARN L293 SmtUtils]: Spent 30.94s on a formula simplification. DAG size of input: 152 DAG size of output: 89 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-12-02 18:10:14,718 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-02 18:10:17,540 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-02 18:10:32,231 WARN L293 SmtUtils]: Spent 6.54s on a formula simplification that was a NOOP. DAG size: 117 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-12-02 18:11:25,506 WARN L293 SmtUtils]: Spent 29.08s on a formula simplification. DAG size of input: 161 DAG size of output: 84 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-12-02 18:11:27,514 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-02 18:11:29,517 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-02 18:11:51,896 WARN L293 SmtUtils]: Spent 14.33s on a formula simplification. DAG size of input: 178 DAG size of output: 62 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-12-02 18:11:53,915 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-02 18:11:56,558 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-02 18:11:58,561 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-02 18:12:07,085 WARN L293 SmtUtils]: Spent 7.25s on a formula simplification. DAG size of input: 64 DAG size of output: 49 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-12-02 18:12:50,935 WARN L293 SmtUtils]: Spent 28.76s on a formula simplification. DAG size of input: 148 DAG size of output: 65 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-12-02 18:12:53,199 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-02 18:12:53,499 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 18:12:53,499 INFO L93 Difference]: Finished difference Result 213 states and 257 transitions. [2023-12-02 18:12:53,500 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 25 states. [2023-12-02 18:12:53,500 INFO L78 Accepts]: Start accepts. Automaton has has 26 states, 24 states have (on average 1.9166666666666667) internal successors, (46), 18 states have internal predecessors, (46), 16 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 13 states have call predecessors, (24), 14 states have call successors, (24) Word has length 87 [2023-12-02 18:12:53,500 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 18:12:53,502 INFO L225 Difference]: With dead ends: 213 [2023-12-02 18:12:53,502 INFO L226 Difference]: Without dead ends: 206 [2023-12-02 18:12:53,504 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 282 GetRequests, 224 SyntacticMatches, 5 SemanticMatches, 53 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 972 ImplicationChecksByTransitivity, 364.1s TimeCoverageRelationStatistics Valid=565, Invalid=2383, Unknown=22, NotChecked=0, Total=2970 [2023-12-02 18:12:53,504 INFO L413 NwaCegarLoop]: 44 mSDtfsCounter, 92 mSDsluCounter, 436 mSDsCounter, 0 mSdLazyCounter, 382 mSolverCounterSat, 115 mSolverCounterUnsat, 12 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 46.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 94 SdHoareTripleChecker+Valid, 480 SdHoareTripleChecker+Invalid, 509 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 115 IncrementalHoareTripleChecker+Valid, 382 IncrementalHoareTripleChecker+Invalid, 12 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 46.3s IncrementalHoareTripleChecker+Time [2023-12-02 18:12:53,504 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [94 Valid, 480 Invalid, 509 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [115 Valid, 382 Invalid, 12 Unknown, 0 Unchecked, 46.3s Time] [2023-12-02 18:12:53,505 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 206 states. [2023-12-02 18:12:53,586 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 206 to 184. [2023-12-02 18:12:53,586 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 184 states, 120 states have (on average 1.1333333333333333) internal successors, (136), 126 states have internal predecessors, (136), 40 states have call successors, (40), 23 states have call predecessors, (40), 23 states have return successors, (38), 34 states have call predecessors, (38), 38 states have call successors, (38) [2023-12-02 18:12:53,587 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 184 states to 184 states and 214 transitions. [2023-12-02 18:12:53,587 INFO L78 Accepts]: Start accepts. Automaton has 184 states and 214 transitions. Word has length 87 [2023-12-02 18:12:53,588 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 18:12:53,588 INFO L495 AbstractCegarLoop]: Abstraction has 184 states and 214 transitions. [2023-12-02 18:12:53,588 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 26 states, 24 states have (on average 1.9166666666666667) internal successors, (46), 18 states have internal predecessors, (46), 16 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 13 states have call predecessors, (24), 14 states have call successors, (24) [2023-12-02 18:12:53,588 INFO L276 IsEmpty]: Start isEmpty. Operand 184 states and 214 transitions. [2023-12-02 18:12:53,589 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 88 [2023-12-02 18:12:53,589 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 18:12:53,589 INFO L195 NwaCegarLoop]: trace histogram [14, 13, 13, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1] [2023-12-02 18:12:53,594 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Ended with exit code 0 [2023-12-02 18:12:53,789 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 15 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable15 [2023-12-02 18:12:53,789 INFO L420 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 18:12:53,790 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 18:12:53,790 INFO L85 PathProgramCache]: Analyzing trace with hash 1526961497, now seen corresponding path program 1 times [2023-12-02 18:12:53,790 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 18:12:53,790 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2004746469] [2023-12-02 18:12:53,790 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 18:12:53,790 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 18:12:53,798 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-02 18:12:53,798 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [350268211] [2023-12-02 18:12:53,798 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 18:12:53,798 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 18:12:53,798 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 18:12:53,799 INFO L229 MonitoredProcess]: Starting monitored process 16 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 18:12:53,801 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2023-12-02 18:12:53,861 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 18:12:53,862 INFO L262 TraceCheckSpWp]: Trace formula consists of 230 conjuncts, 40 conjunts are in the unsatisfiable core [2023-12-02 18:12:53,865 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 18:12:54,188 INFO L134 CoverageAnalysis]: Checked inductivity of 365 backedges. 25 proven. 64 refuted. 0 times theorem prover too weak. 276 trivial. 0 not checked. [2023-12-02 18:12:54,188 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 18:13:12,790 WARN L293 SmtUtils]: Spent 5.01s on a formula simplification that was a NOOP. DAG size: 209 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-12-02 18:14:45,375 INFO L134 CoverageAnalysis]: Checked inductivity of 365 backedges. 25 proven. 64 refuted. 0 times theorem prover too weak. 276 trivial. 0 not checked. [2023-12-02 18:14:45,375 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 18:14:45,375 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2004746469] [2023-12-02 18:14:45,376 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-02 18:14:45,376 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [350268211] [2023-12-02 18:14:45,376 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [350268211] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-02 18:14:45,376 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1456479752] [2023-12-02 18:14:45,377 INFO L159 IcfgInterpreter]: Started Sifa with 19 locations of interest [2023-12-02 18:14:45,377 INFO L166 IcfgInterpreter]: Building call graph [2023-12-02 18:14:45,378 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-12-02 18:14:45,378 INFO L176 IcfgInterpreter]: Starting interpretation [2023-12-02 18:14:45,378 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-12-02 18:14:46,802 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2023-12-02 18:14:46,805 INFO L180 IcfgInterpreter]: Interpretation finished [2023-12-02 18:14:48,386 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '9610#(and (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-12-02 18:14:48,387 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-12-02 18:14:48,387 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-02 18:14:48,387 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11] total 19 [2023-12-02 18:14:48,387 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1105211247] [2023-12-02 18:14:48,387 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-02 18:14:48,387 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2023-12-02 18:14:48,387 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 18:14:48,388 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2023-12-02 18:14:48,389 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=108, Invalid=822, Unknown=0, NotChecked=0, Total=930 [2023-12-02 18:14:48,389 INFO L87 Difference]: Start difference. First operand 184 states and 214 transitions. Second operand has 19 states, 19 states have (on average 2.5789473684210527) internal successors, (49), 17 states have internal predecessors, (49), 11 states have call successors, (28), 3 states have call predecessors, (28), 2 states have return successors, (26), 8 states have call predecessors, (26), 9 states have call successors, (26) [2023-12-02 18:14:51,487 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 18:14:51,487 INFO L93 Difference]: Finished difference Result 197 states and 230 transitions. [2023-12-02 18:14:51,488 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2023-12-02 18:14:51,488 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 19 states have (on average 2.5789473684210527) internal successors, (49), 17 states have internal predecessors, (49), 11 states have call successors, (28), 3 states have call predecessors, (28), 2 states have return successors, (26), 8 states have call predecessors, (26), 9 states have call successors, (26) Word has length 87 [2023-12-02 18:14:51,488 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 18:14:51,489 INFO L225 Difference]: With dead ends: 197 [2023-12-02 18:14:51,489 INFO L226 Difference]: Without dead ends: 195 [2023-12-02 18:14:51,490 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 265 GetRequests, 228 SyntacticMatches, 3 SemanticMatches, 34 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 310 ImplicationChecksByTransitivity, 11.7s TimeCoverageRelationStatistics Valid=144, Invalid=1116, Unknown=0, NotChecked=0, Total=1260 [2023-12-02 18:14:51,491 INFO L413 NwaCegarLoop]: 36 mSDtfsCounter, 41 mSDsluCounter, 286 mSDsCounter, 0 mSdLazyCounter, 340 mSolverCounterSat, 42 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 47 SdHoareTripleChecker+Valid, 322 SdHoareTripleChecker+Invalid, 382 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 42 IncrementalHoareTripleChecker+Valid, 340 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.3s IncrementalHoareTripleChecker+Time [2023-12-02 18:14:51,491 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [47 Valid, 322 Invalid, 382 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [42 Valid, 340 Invalid, 0 Unknown, 0 Unchecked, 1.3s Time] [2023-12-02 18:14:51,491 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 195 states. [2023-12-02 18:14:51,595 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 195 to 184. [2023-12-02 18:14:51,596 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 184 states, 120 states have (on average 1.1333333333333333) internal successors, (136), 126 states have internal predecessors, (136), 40 states have call successors, (40), 23 states have call predecessors, (40), 23 states have return successors, (38), 34 states have call predecessors, (38), 38 states have call successors, (38) [2023-12-02 18:14:51,597 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 184 states to 184 states and 214 transitions. [2023-12-02 18:14:51,597 INFO L78 Accepts]: Start accepts. Automaton has 184 states and 214 transitions. Word has length 87 [2023-12-02 18:14:51,597 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 18:14:51,597 INFO L495 AbstractCegarLoop]: Abstraction has 184 states and 214 transitions. [2023-12-02 18:14:51,598 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 19 states have (on average 2.5789473684210527) internal successors, (49), 17 states have internal predecessors, (49), 11 states have call successors, (28), 3 states have call predecessors, (28), 2 states have return successors, (26), 8 states have call predecessors, (26), 9 states have call successors, (26) [2023-12-02 18:14:51,598 INFO L276 IsEmpty]: Start isEmpty. Operand 184 states and 214 transitions. [2023-12-02 18:14:51,599 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 93 [2023-12-02 18:14:51,599 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 18:14:51,599 INFO L195 NwaCegarLoop]: trace histogram [15, 14, 14, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 18:14:51,605 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Ended with exit code 0 [2023-12-02 18:14:51,799 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 16 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable16 [2023-12-02 18:14:51,800 INFO L420 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 18:14:51,800 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 18:14:51,800 INFO L85 PathProgramCache]: Analyzing trace with hash -29779425, now seen corresponding path program 1 times [2023-12-02 18:14:51,800 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 18:14:51,800 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1045048860] [2023-12-02 18:14:51,800 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 18:14:51,801 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 18:14:51,807 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-02 18:14:51,808 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1720168079] [2023-12-02 18:14:51,808 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 18:14:51,808 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 18:14:51,808 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 18:14:51,809 INFO L229 MonitoredProcess]: Starting monitored process 17 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 18:14:51,810 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2023-12-02 18:14:51,877 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 18:14:51,879 INFO L262 TraceCheckSpWp]: Trace formula consists of 239 conjuncts, 33 conjunts are in the unsatisfiable core [2023-12-02 18:14:51,881 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 18:14:52,074 INFO L134 CoverageAnalysis]: Checked inductivity of 419 backedges. 27 proven. 67 refuted. 0 times theorem prover too weak. 325 trivial. 0 not checked. [2023-12-02 18:14:52,074 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 18:14:53,076 INFO L134 CoverageAnalysis]: Checked inductivity of 419 backedges. 27 proven. 67 refuted. 0 times theorem prover too weak. 325 trivial. 0 not checked. [2023-12-02 18:14:53,076 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 18:14:53,076 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1045048860] [2023-12-02 18:14:53,076 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-02 18:14:53,076 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1720168079] [2023-12-02 18:14:53,076 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1720168079] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-02 18:14:53,077 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1627284238] [2023-12-02 18:14:53,078 INFO L159 IcfgInterpreter]: Started Sifa with 20 locations of interest [2023-12-02 18:14:53,078 INFO L166 IcfgInterpreter]: Building call graph [2023-12-02 18:14:53,078 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-12-02 18:14:53,079 INFO L176 IcfgInterpreter]: Starting interpretation [2023-12-02 18:14:53,079 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-12-02 18:14:54,513 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2023-12-02 18:14:54,517 INFO L180 IcfgInterpreter]: Interpretation finished [2023-12-02 18:14:55,550 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '10747#(and (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-12-02 18:14:55,550 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-12-02 18:14:55,550 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-02 18:14:55,550 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 9] total 18 [2023-12-02 18:14:55,550 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [136095822] [2023-12-02 18:14:55,551 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-02 18:14:55,551 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2023-12-02 18:14:55,551 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 18:14:55,552 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2023-12-02 18:14:55,552 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=104, Invalid=826, Unknown=0, NotChecked=0, Total=930 [2023-12-02 18:14:55,553 INFO L87 Difference]: Start difference. First operand 184 states and 214 transitions. Second operand has 18 states, 18 states have (on average 2.7222222222222223) internal successors, (49), 16 states have internal predecessors, (49), 10 states have call successors, (30), 3 states have call predecessors, (30), 2 states have return successors, (28), 8 states have call predecessors, (28), 10 states have call successors, (28) [2023-12-02 18:14:55,913 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 18:14:55,914 INFO L93 Difference]: Finished difference Result 211 states and 244 transitions. [2023-12-02 18:14:55,914 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2023-12-02 18:14:55,914 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 18 states have (on average 2.7222222222222223) internal successors, (49), 16 states have internal predecessors, (49), 10 states have call successors, (30), 3 states have call predecessors, (30), 2 states have return successors, (28), 8 states have call predecessors, (28), 10 states have call successors, (28) Word has length 92 [2023-12-02 18:14:55,915 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 18:14:55,916 INFO L225 Difference]: With dead ends: 211 [2023-12-02 18:14:55,916 INFO L226 Difference]: Without dead ends: 157 [2023-12-02 18:14:55,916 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 276 GetRequests, 243 SyntacticMatches, 3 SemanticMatches, 30 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 282 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=113, Invalid=879, Unknown=0, NotChecked=0, Total=992 [2023-12-02 18:14:55,917 INFO L413 NwaCegarLoop]: 33 mSDtfsCounter, 23 mSDsluCounter, 212 mSDsCounter, 0 mSdLazyCounter, 240 mSolverCounterSat, 27 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 31 SdHoareTripleChecker+Valid, 245 SdHoareTripleChecker+Invalid, 267 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 27 IncrementalHoareTripleChecker+Valid, 240 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-12-02 18:14:55,917 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [31 Valid, 245 Invalid, 267 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [27 Valid, 240 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-12-02 18:14:55,918 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 157 states. [2023-12-02 18:14:55,997 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 157 to 157. [2023-12-02 18:14:55,997 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 157 states, 103 states have (on average 1.116504854368932) internal successors, (115), 108 states have internal predecessors, (115), 32 states have call successors, (32), 21 states have call predecessors, (32), 21 states have return successors, (30), 27 states have call predecessors, (30), 30 states have call successors, (30) [2023-12-02 18:14:55,998 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 157 states to 157 states and 177 transitions. [2023-12-02 18:14:55,998 INFO L78 Accepts]: Start accepts. Automaton has 157 states and 177 transitions. Word has length 92 [2023-12-02 18:14:55,999 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 18:14:55,999 INFO L495 AbstractCegarLoop]: Abstraction has 157 states and 177 transitions. [2023-12-02 18:14:55,999 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 18 states, 18 states have (on average 2.7222222222222223) internal successors, (49), 16 states have internal predecessors, (49), 10 states have call successors, (30), 3 states have call predecessors, (30), 2 states have return successors, (28), 8 states have call predecessors, (28), 10 states have call successors, (28) [2023-12-02 18:14:55,999 INFO L276 IsEmpty]: Start isEmpty. Operand 157 states and 177 transitions. [2023-12-02 18:14:56,000 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 93 [2023-12-02 18:14:56,000 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 18:14:56,000 INFO L195 NwaCegarLoop]: trace histogram [15, 14, 14, 4, 4, 4, 4, 4, 4, 4, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 18:14:56,004 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Ended with exit code 0 [2023-12-02 18:14:56,200 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 17 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable17 [2023-12-02 18:14:56,200 INFO L420 AbstractCegarLoop]: === Iteration 19 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 18:14:56,201 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 18:14:56,201 INFO L85 PathProgramCache]: Analyzing trace with hash -1379555575, now seen corresponding path program 2 times [2023-12-02 18:14:56,201 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 18:14:56,201 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1561609858] [2023-12-02 18:14:56,201 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 18:14:56,201 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 18:14:56,208 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-02 18:14:56,208 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2126598735] [2023-12-02 18:14:56,208 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-12-02 18:14:56,208 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 18:14:56,208 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 18:14:56,209 INFO L229 MonitoredProcess]: Starting monitored process 18 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 18:14:56,210 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Waiting until timeout for monitored process [2023-12-02 18:14:56,295 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2023-12-02 18:14:56,295 INFO L229 tOrderPrioritization]: Conjunction of SSA is sat [2023-12-02 18:14:56,295 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2023-12-02 18:14:56,319 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2023-12-02 18:14:56,354 INFO L130 FreeRefinementEngine]: Strategy SIFA_TAIPAN found a feasible trace [2023-12-02 18:14:56,354 INFO L360 BasicCegarLoop]: Counterexample is feasible [2023-12-02 18:14:56,355 INFO L805 garLoopResultBuilder]: Registering result UNSAFE for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2023-12-02 18:14:56,362 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Ended with exit code 0 [2023-12-02 18:14:56,557 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable18,18 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 18:14:56,560 INFO L445 BasicCegarLoop]: Path program histogram: [3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 18:14:56,563 INFO L178 ceAbstractionStarter]: Computing trace abstraction results [2023-12-02 18:14:56,583 WARN L1572 BoogieBacktranslator]: Unfinished Backtranslation: IdentifierExpression #t~post5 could not be translated [2023-12-02 18:14:56,585 WARN L1572 BoogieBacktranslator]: Unfinished Backtranslation: IdentifierExpression #t~post5 could not be translated [2023-12-02 18:14:56,587 WARN L1572 BoogieBacktranslator]: Unfinished Backtranslation: IdentifierExpression #t~post5 could not be translated [2023-12-02 18:14:56,588 WARN L1572 BoogieBacktranslator]: Unfinished Backtranslation: IdentifierExpression #t~post5 could not be translated [2023-12-02 18:14:56,589 WARN L1572 BoogieBacktranslator]: Unfinished Backtranslation: IdentifierExpression #t~post6 could not be translated [2023-12-02 18:14:56,590 WARN L1572 BoogieBacktranslator]: Unfinished Backtranslation: IdentifierExpression #t~post6 could not be translated [2023-12-02 18:14:56,602 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 02.12 06:14:56 BoogieIcfgContainer [2023-12-02 18:14:56,602 INFO L131 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2023-12-02 18:14:56,603 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2023-12-02 18:14:56,603 INFO L270 PluginConnector]: Initializing Witness Printer... [2023-12-02 18:14:56,603 INFO L274 PluginConnector]: Witness Printer initialized [2023-12-02 18:14:56,603 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 02.12 06:01:42" (3/4) ... [2023-12-02 18:14:56,604 INFO L131 WitnessPrinter]: Generating witness for reachability counterexample [2023-12-02 18:14:56,611 WARN L1572 BoogieBacktranslator]: Unfinished Backtranslation: IdentifierExpression #t~post5 could not be translated [2023-12-02 18:14:56,612 WARN L1572 BoogieBacktranslator]: Unfinished Backtranslation: IdentifierExpression #t~post5 could not be translated [2023-12-02 18:14:56,613 WARN L1572 BoogieBacktranslator]: Unfinished Backtranslation: IdentifierExpression #t~post5 could not be translated [2023-12-02 18:14:56,614 WARN L1572 BoogieBacktranslator]: Unfinished Backtranslation: IdentifierExpression #t~post5 could not be translated [2023-12-02 18:14:56,615 WARN L1572 BoogieBacktranslator]: Unfinished Backtranslation: IdentifierExpression #t~post6 could not be translated [2023-12-02 18:14:56,616 WARN L1572 BoogieBacktranslator]: Unfinished Backtranslation: IdentifierExpression #t~post6 could not be translated [2023-12-02 18:14:56,661 INFO L149 WitnessManager]: Wrote witness to /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/witness.graphml [2023-12-02 18:14:56,662 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2023-12-02 18:14:56,663 INFO L158 Benchmark]: Toolchain (without parser) took 794400.08ms. Allocated memory was 146.8MB in the beginning and 400.6MB in the end (delta: 253.8MB). Free memory was 105.0MB in the beginning and 261.6MB in the end (delta: -156.7MB). Peak memory consumption was 98.9MB. Max. memory is 16.1GB. [2023-12-02 18:14:56,663 INFO L158 Benchmark]: CDTParser took 0.19ms. Allocated memory is still 146.8MB. Free memory is still 91.3MB. There was no memory consumed. Max. memory is 16.1GB. [2023-12-02 18:14:56,663 INFO L158 Benchmark]: CACSL2BoogieTranslator took 244.72ms. Allocated memory is still 146.8MB. Free memory was 104.6MB in the beginning and 93.8MB in the end (delta: 10.8MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. [2023-12-02 18:14:56,664 INFO L158 Benchmark]: Boogie Procedure Inliner took 33.05ms. Allocated memory is still 146.8MB. Free memory was 93.8MB in the beginning and 92.4MB in the end (delta: 1.4MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2023-12-02 18:14:56,664 INFO L158 Benchmark]: Boogie Preprocessor took 17.77ms. Allocated memory is still 146.8MB. Free memory was 92.4MB in the beginning and 91.3MB in the end (delta: 1.1MB). There was no memory consumed. Max. memory is 16.1GB. [2023-12-02 18:14:56,664 INFO L158 Benchmark]: RCFGBuilder took 296.60ms. Allocated memory is still 146.8MB. Free memory was 91.0MB in the beginning and 78.5MB in the end (delta: 12.6MB). Peak memory consumption was 12.6MB. Max. memory is 16.1GB. [2023-12-02 18:14:56,665 INFO L158 Benchmark]: TraceAbstraction took 793742.04ms. Allocated memory was 146.8MB in the beginning and 400.6MB in the end (delta: 253.8MB). Free memory was 77.7MB in the beginning and 265.8MB in the end (delta: -188.1MB). Peak memory consumption was 67.4MB. Max. memory is 16.1GB. [2023-12-02 18:14:56,665 INFO L158 Benchmark]: Witness Printer took 59.17ms. Allocated memory is still 400.6MB. Free memory was 265.8MB in the beginning and 261.6MB in the end (delta: 4.2MB). Peak memory consumption was 4.2MB. Max. memory is 16.1GB. [2023-12-02 18:14:56,667 INFO L338 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.19ms. Allocated memory is still 146.8MB. Free memory is still 91.3MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 244.72ms. Allocated memory is still 146.8MB. Free memory was 104.6MB in the beginning and 93.8MB in the end (delta: 10.8MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 33.05ms. Allocated memory is still 146.8MB. Free memory was 93.8MB in the beginning and 92.4MB in the end (delta: 1.4MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * Boogie Preprocessor took 17.77ms. Allocated memory is still 146.8MB. Free memory was 92.4MB in the beginning and 91.3MB in the end (delta: 1.1MB). There was no memory consumed. Max. memory is 16.1GB. * RCFGBuilder took 296.60ms. Allocated memory is still 146.8MB. Free memory was 91.0MB in the beginning and 78.5MB in the end (delta: 12.6MB). Peak memory consumption was 12.6MB. Max. memory is 16.1GB. * TraceAbstraction took 793742.04ms. Allocated memory was 146.8MB in the beginning and 400.6MB in the end (delta: 253.8MB). Free memory was 77.7MB in the beginning and 265.8MB in the end (delta: -188.1MB). Peak memory consumption was 67.4MB. Max. memory is 16.1GB. * Witness Printer took 59.17ms. Allocated memory is still 400.6MB. Free memory was 265.8MB in the beginning and 261.6MB in the end (delta: 4.2MB). Peak memory consumption was 4.2MB. Max. memory is 16.1GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: - GenericResult: Unfinished Backtranslation Unfinished Backtranslation: IdentifierExpression #t~post5 could not be translated - GenericResult: Unfinished Backtranslation Unfinished Backtranslation: IdentifierExpression #t~post5 could not be translated - GenericResult: Unfinished Backtranslation Unfinished Backtranslation: IdentifierExpression #t~post5 could not be translated - GenericResult: Unfinished Backtranslation Unfinished Backtranslation: IdentifierExpression #t~post5 could not be translated - GenericResult: Unfinished Backtranslation Unfinished Backtranslation: IdentifierExpression #t~post6 could not be translated - GenericResult: Unfinished Backtranslation Unfinished Backtranslation: IdentifierExpression #t~post6 could not be translated - GenericResult: Unfinished Backtranslation The program execution was not completely translated back. - GenericResult: Unfinished Backtranslation Unfinished Backtranslation: IdentifierExpression #t~post5 could not be translated - GenericResult: Unfinished Backtranslation Unfinished Backtranslation: IdentifierExpression #t~post5 could not be translated - GenericResult: Unfinished Backtranslation Unfinished Backtranslation: IdentifierExpression #t~post5 could not be translated - GenericResult: Unfinished Backtranslation Unfinished Backtranslation: IdentifierExpression #t~post5 could not be translated - GenericResult: Unfinished Backtranslation Unfinished Backtranslation: IdentifierExpression #t~post6 could not be translated - GenericResult: Unfinished Backtranslation Unfinished Backtranslation: IdentifierExpression #t~post6 could not be translated - GenericResult: Unfinished Backtranslation The program execution was not completely translated back. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: ErrorAutomatonStatistics NumberErrorTraces: 0, NumberStatementsAllTraces: 0, NumberRelevantStatements: 0, 0.0s ErrorAutomatonConstructionTimeTotal, 0.0s FaulLocalizationTime, NumberStatementsFirstTrace: -1, TraceLengthAvg: 0, 0.0s ErrorAutomatonConstructionTimeAvg, 0.0s ErrorAutomatonDifferenceTimeAvg, 0.0s ErrorAutomatonDifferenceTimeTotal, NumberOfNoEnhancement: 0, NumberOfFiniteEnhancement: 0, NumberOfInfiniteEnhancement: 0 - CounterExampleResult [Line: 17]: a call to reach_error is reachable a call to reach_error is reachable We found a FailurePath: [L22] int counter = 0; [L24] int A, B; [L25] int r, d, p, q; [L26] A = __VERIFIER_nondet_int() [L27] B = 1 [L29] r = A [L30] d = B [L31] p = 1 [L32] q = 0 VAL [A=7, B=1, counter=0, d=1, p=1, q=0, r=7] [L34] EXPR counter++ VAL [A=7, B=1, counter=1, d=1, p=1, q=0, r=7] [L34] COND TRUE counter++<5 [L35] CALL __VERIFIER_assert(q == 0) VAL [\old(cond)=1, counter=1] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, cond=1, counter=1] [L35] RET __VERIFIER_assert(q == 0) VAL [A=7, B=1, counter=1, d=1, p=1, q=0, r=7] [L36] CALL __VERIFIER_assert(r == A) VAL [\old(cond)=1, counter=1] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, cond=1, counter=1] [L36] RET __VERIFIER_assert(r == A) VAL [A=7, B=1, counter=1, d=1, p=1, q=0, r=7] [L37] CALL __VERIFIER_assert(d == B * p) VAL [\old(cond)=1, counter=1] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, cond=1, counter=1] [L37] RET __VERIFIER_assert(d == B * p) VAL [A=7, B=1, counter=1, d=1, p=1, q=0, r=7] [L38] COND FALSE !(!(r >= d)) [L40] d = 2 * d [L41] p = 2 * p VAL [A=7, B=1, counter=1, d=2, p=2, q=0, r=7] [L34] EXPR counter++ VAL [A=7, B=1, counter=2, d=2, p=2, q=0, r=7] [L34] COND TRUE counter++<5 [L35] CALL __VERIFIER_assert(q == 0) VAL [\old(cond)=1, counter=2] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, cond=1, counter=2] [L35] RET __VERIFIER_assert(q == 0) VAL [A=7, B=1, counter=2, d=2, p=2, q=0, r=7] [L36] CALL __VERIFIER_assert(r == A) VAL [\old(cond)=1, counter=2] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, cond=1, counter=2] [L36] RET __VERIFIER_assert(r == A) VAL [A=7, B=1, counter=2, d=2, p=2, q=0, r=7] [L37] CALL __VERIFIER_assert(d == B * p) VAL [\old(cond)=1, counter=2] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, cond=1, counter=2] [L37] RET __VERIFIER_assert(d == B * p) VAL [A=7, B=1, counter=2, d=2, p=2, q=0, r=7] [L38] COND FALSE !(!(r >= d)) [L40] d = 2 * d [L41] p = 2 * p VAL [A=7, B=1, counter=2, d=4, p=4, q=0, r=7] [L34] EXPR counter++ VAL [A=7, B=1, counter=3, d=4, p=4, q=0, r=7] [L34] COND TRUE counter++<5 [L35] CALL __VERIFIER_assert(q == 0) VAL [\old(cond)=1, counter=3] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, cond=1, counter=3] [L35] RET __VERIFIER_assert(q == 0) VAL [A=7, B=1, counter=3, d=4, p=4, q=0, r=7] [L36] CALL __VERIFIER_assert(r == A) VAL [\old(cond)=1, counter=3] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, cond=1, counter=3] [L36] RET __VERIFIER_assert(r == A) VAL [A=7, B=1, counter=3, d=4, p=4, q=0, r=7] [L37] CALL __VERIFIER_assert(d == B * p) VAL [\old(cond)=1, counter=3] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, cond=1, counter=3] [L37] RET __VERIFIER_assert(d == B * p) VAL [A=7, B=1, counter=3, d=4, p=4, q=0, r=7] [L38] COND FALSE !(!(r >= d)) [L40] d = 2 * d [L41] p = 2 * p VAL [A=7, B=1, counter=3, d=8, p=8, q=0, r=7] [L34] EXPR counter++ VAL [A=7, B=1, counter=4, d=8, p=8, q=0, r=7] [L34] COND TRUE counter++<5 [L35] CALL __VERIFIER_assert(q == 0) VAL [\old(cond)=1, counter=4] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, cond=1, counter=4] [L35] RET __VERIFIER_assert(q == 0) VAL [A=7, B=1, counter=4, d=8, p=8, q=0, r=7] [L36] CALL __VERIFIER_assert(r == A) VAL [\old(cond)=1, counter=4] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, cond=1, counter=4] [L36] RET __VERIFIER_assert(r == A) VAL [A=7, B=1, counter=4, d=8, p=8, q=0, r=7] [L37] CALL __VERIFIER_assert(d == B * p) VAL [\old(cond)=1, counter=4] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, cond=1, counter=4] [L37] RET __VERIFIER_assert(d == B * p) VAL [A=7, B=1, counter=4, d=8, p=8, q=0, r=7] [L38] COND TRUE !(r >= d) VAL [A=7, B=1, counter=4, d=8, p=8, q=0, r=7] [L44] EXPR counter++ VAL [A=7, B=1, counter=5, d=8, p=8, q=0, r=7] [L44] COND TRUE counter++<5 [L45] CALL __VERIFIER_assert(A == q*B + r) VAL [\old(cond)=1, counter=5] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, cond=1, counter=5] [L45] RET __VERIFIER_assert(A == q*B + r) VAL [A=7, B=1, counter=5, d=8, p=8, q=0, r=7] [L46] CALL __VERIFIER_assert(d == B*p) VAL [\old(cond)=1, counter=5] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, cond=1, counter=5] [L46] RET __VERIFIER_assert(d == B*p) VAL [A=7, B=1, counter=5, d=8, p=8, q=0, r=7] [L48] COND FALSE !(!(p != 1)) [L50] d = d / 2 [L51] p = p / 2 [L52] COND TRUE r >= d [L53] r = r - d [L54] q = q + p VAL [A=7, B=1, counter=5, d=4, p=4, q=4, r=3] [L44] EXPR counter++ VAL [A=7, B=1, counter=6, d=4, p=4, q=4, r=3] [L44] COND FALSE !(counter++<5) [L58] CALL __VERIFIER_assert(A == d*q + r) VAL [\old(cond)=0, counter=6] [L15] COND TRUE !(cond) VAL [\old(cond)=0, cond=0, counter=6] [L17] reach_error() VAL [\old(cond)=0, cond=0, counter=6] - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 22 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 793.7s, OverallIterations: 19, TraceHistogramMax: 15, PathProgramHistogramMax: 3, EmptinessCheckTime: 0.0s, AutomataDifference: 330.9s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, HoareTripleCheckerStatistics: 13 mSolverCounterUnknown, 531 SdHoareTripleChecker+Valid, 51.8s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 465 mSDsluCounter, 2608 SdHoareTripleChecker+Invalid, 51.4s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 2123 mSDsCounter, 380 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 2318 IncrementalHoareTripleChecker+Invalid, 2711 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 380 mSolverCounterUnsat, 485 mSDtfsCounter, 2318 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 2379 GetRequests, 1990 SyntacticMatches, 32 SemanticMatches, 357 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3187 ImplicationChecksByTransitivity, 393.8s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=184occurred in iteration=16, InterpolantAutomatonStates: 180, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.6s AutomataMinimizationTime, 18 MinimizatonAttempts, 87 StatesRemovedByMinimization, 13 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.1s SsaConstructionTime, 0.6s SatisfiabilityAnalysisTime, 429.3s InterpolantComputationTime, 969 NumberOfCodeBlocks, 930 NumberOfCodeBlocksAsserted, 28 NumberOfCheckSat, 1579 ConstructedInterpolants, 0 QuantifiedInterpolants, 41171 SizeOfPredicates, 47 NumberOfNonLiveVariables, 2386 ConjunctsInSsa, 326 ConjunctsInUnsatCore, 31 InterpolantComputations, 5 PerfectInterpolantSequences, 4245/5256 InterpolantCoveringCapability, INVARIANT_SYNTHESIS: No data available, INTERPOLANT_CONSOLIDATION: No data available, ABSTRACT_INTERPRETATION: No data available, PDR: No data available, ACCELERATED_INTERPOLATION: No data available, SIFA: OVERALL_TIME: 1.1s, ICFG_INTERPRETER_ENTERED_PROCEDURES: 4, DAG_INTERPRETER_EARLY_EXIT_QUERIES_NONTRIVIAL: 29, DAG_INTERPRETER_EARLY_EXITS: 2, TOOLS_POST_APPLICATIONS: 23, TOOLS_POST_TIME: 0.2s, TOOLS_POST_CALL_APPLICATIONS: 17, TOOLS_POST_CALL_TIME: 0.3s, TOOLS_POST_RETURN_APPLICATIONS: 10, TOOLS_POST_RETURN_TIME: 0.2s, TOOLS_QUANTIFIERELIM_APPLICATIONS: 50, TOOLS_QUANTIFIERELIM_TIME: 0.7s, TOOLS_QUANTIFIERELIM_MAX_TIME: 0.0s, FLUID_QUERY_TIME: 0.0s, FLUID_QUERIES: 72, FLUID_YES_ANSWERS: 0, DOMAIN_JOIN_APPLICATIONS: 21, DOMAIN_JOIN_TIME: 0.3s, DOMAIN_ALPHA_APPLICATIONS: 0, DOMAIN_ALPHA_TIME: 0.0s, DOMAIN_WIDEN_APPLICATIONS: 0, DOMAIN_WIDEN_TIME: 0.0s, DOMAIN_ISSUBSETEQ_APPLICATIONS: 0, DOMAIN_ISSUBSETEQ_TIME: 0.0s, DOMAIN_ISBOTTOM_APPLICATIONS: 29, DOMAIN_ISBOTTOM_TIME: 0.0s, LOOP_SUMMARIZER_APPLICATIONS: 0, LOOP_SUMMARIZER_CACHE_MISSES: 0, LOOP_SUMMARIZER_OVERALL_TIME: 0.0s, LOOP_SUMMARIZER_NEW_COMPUTATION_TIME: 0.0s, LOOP_SUMMARIZER_FIXPOINT_ITERATIONS: 0, CALL_SUMMARIZER_APPLICATIONS: 10, CALL_SUMMARIZER_CACHE_MISSES: 2, CALL_SUMMARIZER_OVERALL_TIME: 0.0s, CALL_SUMMARIZER_NEW_COMPUTATION_TIME: 0.0s, PROCEDURE_GRAPH_BUILDER_TIME: 0.0s, PATH_EXPR_TIME: 0.0s, REGEX_TO_DAG_TIME: 0.0s, DAG_COMPRESSION_TIME: 0.0s, DAG_COMPRESSION_PROCESSED_NODES: 231, DAG_COMPRESSION_RETAINED_NODES: 80, ReuseStatistics: No data available RESULT: Ultimate proved your program to be incorrect! [2023-12-02 18:14:56,833 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bb488dd9-c770-4879-a233-8b6251207c70/bin/utaipan-verify-nQ1chXbOIh/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Ended with exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Writing output log to file Ultimate.log Writing human readable error path to file UltimateCounterExample.errorpath Result: FALSE