./Ultimate.py --spec ../../sv-benchmarks/c/properties/unreach-call.prp --file ../../sv-benchmarks/c/verifythis/tree_max.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 9bd2c7ff 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_f2f6415e-ee1b-4f50-8e0f-824c676a7e97/bin/utaipan-verify-t7M7D8N6sZ/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2f6415e-ee1b-4f50-8e0f-824c676a7e97/bin/utaipan-verify-t7M7D8N6sZ/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2f6415e-ee1b-4f50-8e0f-824c676a7e97/bin/utaipan-verify-t7M7D8N6sZ/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2f6415e-ee1b-4f50-8e0f-824c676a7e97/bin/utaipan-verify-t7M7D8N6sZ/config/TaipanReach.xml -i ../../sv-benchmarks/c/verifythis/tree_max.c -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2f6415e-ee1b-4f50-8e0f-824c676a7e97/bin/utaipan-verify-t7M7D8N6sZ/config/svcomp-Reach-32bit-Taipan_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2f6415e-ee1b-4f50-8e0f-824c676a7e97/bin/utaipan-verify-t7M7D8N6sZ --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(G ! call(reach_error())) ) --witnessprinter.graph.data.producer Taipan --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash e98a60ea9ee0c00575c08606ce8b95d0660c5b235c5932147dfee4b13512f57c --- Real Ultimate output --- This is Ultimate 0.2.3-dev-9bd2c7f [2023-11-19 04:11:00,284 INFO L188 SettingsManager]: Resetting all preferences to default values... [2023-11-19 04:11:00,443 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2f6415e-ee1b-4f50-8e0f-824c676a7e97/bin/utaipan-verify-t7M7D8N6sZ/config/svcomp-Reach-32bit-Taipan_Default.epf [2023-11-19 04:11:00,448 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2023-11-19 04:11:00,449 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2023-11-19 04:11:00,490 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2023-11-19 04:11:00,491 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2023-11-19 04:11:00,493 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2023-11-19 04:11:00,494 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2023-11-19 04:11:00,501 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2023-11-19 04:11:00,501 INFO L153 SettingsManager]: * User list type=DISABLED [2023-11-19 04:11:00,503 INFO L151 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2023-11-19 04:11:00,504 INFO L153 SettingsManager]: * Explicit value domain=true [2023-11-19 04:11:00,506 INFO L153 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2023-11-19 04:11:00,507 INFO L153 SettingsManager]: * Octagon Domain=false [2023-11-19 04:11:00,507 INFO L153 SettingsManager]: * Abstract domain=CompoundDomain [2023-11-19 04:11:00,508 INFO L153 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2023-11-19 04:11:00,508 INFO L153 SettingsManager]: * Use the RCFG-of-the-future interface=true [2023-11-19 04:11:00,509 INFO L153 SettingsManager]: * Interval Domain=false [2023-11-19 04:11:00,510 INFO L151 SettingsManager]: Preferences of Sifa differ from their defaults: [2023-11-19 04:11:00,511 INFO L153 SettingsManager]: * Call Summarizer=TopInputCallSummarizer [2023-11-19 04:11:00,512 INFO L153 SettingsManager]: * Simplification Technique=POLY_PAC [2023-11-19 04:11:00,513 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2023-11-19 04:11:00,514 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2023-11-19 04:11:00,515 INFO L153 SettingsManager]: * sizeof long=4 [2023-11-19 04:11:00,515 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2023-11-19 04:11:00,516 INFO L153 SettingsManager]: * sizeof POINTER=4 [2023-11-19 04:11:00,516 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2023-11-19 04:11:00,517 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2023-11-19 04:11:00,518 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2023-11-19 04:11:00,520 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2023-11-19 04:11:00,520 INFO L153 SettingsManager]: * sizeof long double=12 [2023-11-19 04:11:00,521 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2023-11-19 04:11:00,521 INFO L153 SettingsManager]: * Use constant arrays=true [2023-11-19 04:11:00,521 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2023-11-19 04:11:00,522 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2023-11-19 04:11:00,522 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-11-19 04:11:00,523 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2023-11-19 04:11:00,523 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2023-11-19 04:11:00,524 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2023-11-19 04:11:00,524 INFO L153 SettingsManager]: * Trace refinement strategy=SIFA_TAIPAN [2023-11-19 04:11:00,525 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2023-11-19 04:11:00,526 INFO L153 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2023-11-19 04:11:00,526 INFO L153 SettingsManager]: * Trace refinement exception blacklist=NONE [2023-11-19 04:11:00,527 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2023-11-19 04:11:00,528 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_f2f6415e-ee1b-4f50-8e0f-824c676a7e97/bin/utaipan-verify-t7M7D8N6sZ/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Entry function -> main Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness directory -> /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2f6415e-ee1b-4f50-8e0f-824c676a7e97/bin/utaipan-verify-t7M7D8N6sZ Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Write witness besides input file -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data specification -> CHECK( init(main()), LTL(G ! call(reach_error())) ) Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data producer -> Taipan Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data architecture -> 32bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> e98a60ea9ee0c00575c08606ce8b95d0660c5b235c5932147dfee4b13512f57c [2023-11-19 04:11:00,903 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2023-11-19 04:11:00,936 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2023-11-19 04:11:00,939 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2023-11-19 04:11:00,941 INFO L270 PluginConnector]: Initializing CDTParser... [2023-11-19 04:11:00,941 INFO L274 PluginConnector]: CDTParser initialized [2023-11-19 04:11:00,945 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2f6415e-ee1b-4f50-8e0f-824c676a7e97/bin/utaipan-verify-t7M7D8N6sZ/../../sv-benchmarks/c/verifythis/tree_max.c [2023-11-19 04:11:04,389 INFO L533 CDTParser]: Created temporary CDT project at NULL [2023-11-19 04:11:04,609 INFO L384 CDTParser]: Found 1 translation units. [2023-11-19 04:11:04,610 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2f6415e-ee1b-4f50-8e0f-824c676a7e97/sv-benchmarks/c/verifythis/tree_max.c [2023-11-19 04:11:04,619 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2f6415e-ee1b-4f50-8e0f-824c676a7e97/bin/utaipan-verify-t7M7D8N6sZ/data/9d3ce9925/7903d142b93e411cabddc88ad4bd015c/FLAG908dda752 [2023-11-19 04:11:04,635 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2f6415e-ee1b-4f50-8e0f-824c676a7e97/bin/utaipan-verify-t7M7D8N6sZ/data/9d3ce9925/7903d142b93e411cabddc88ad4bd015c [2023-11-19 04:11:04,638 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2023-11-19 04:11:04,640 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2023-11-19 04:11:04,642 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2023-11-19 04:11:04,642 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2023-11-19 04:11:04,648 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2023-11-19 04:11:04,649 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 19.11 04:11:04" (1/1) ... [2023-11-19 04:11:04,650 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@206369fb and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 04:11:04, skipping insertion in model container [2023-11-19 04:11:04,650 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 19.11 04:11:04" (1/1) ... [2023-11-19 04:11:04,675 INFO L177 MainTranslator]: Built tables and reachable declarations [2023-11-19 04:11:04,864 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_f2f6415e-ee1b-4f50-8e0f-824c676a7e97/sv-benchmarks/c/verifythis/tree_max.c[544,557] [2023-11-19 04:11:04,889 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-19 04:11:04,900 INFO L202 MainTranslator]: Completed pre-run [2023-11-19 04:11:04,913 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_f2f6415e-ee1b-4f50-8e0f-824c676a7e97/sv-benchmarks/c/verifythis/tree_max.c[544,557] [2023-11-19 04:11:04,922 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-19 04:11:04,939 INFO L206 MainTranslator]: Completed translation [2023-11-19 04:11:04,940 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 04:11:04 WrapperNode [2023-11-19 04:11:04,940 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2023-11-19 04:11:04,941 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2023-11-19 04:11:04,941 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2023-11-19 04:11:04,941 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2023-11-19 04:11:04,949 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 04:11:04" (1/1) ... [2023-11-19 04:11:04,975 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 04:11:04" (1/1) ... [2023-11-19 04:11:05,004 INFO L138 Inliner]: procedures = 24, calls = 28, calls flagged for inlining = 4, calls inlined = 4, statements flattened = 38 [2023-11-19 04:11:05,005 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2023-11-19 04:11:05,005 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2023-11-19 04:11:05,006 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2023-11-19 04:11:05,006 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2023-11-19 04:11:05,015 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 04:11:04" (1/1) ... [2023-11-19 04:11:05,015 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 04:11:04" (1/1) ... [2023-11-19 04:11:05,018 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 04:11:04" (1/1) ... [2023-11-19 04:11:05,018 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 04:11:04" (1/1) ... [2023-11-19 04:11:05,037 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 04:11:04" (1/1) ... [2023-11-19 04:11:05,039 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 04:11:04" (1/1) ... [2023-11-19 04:11:05,041 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 04:11:04" (1/1) ... [2023-11-19 04:11:05,042 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 04:11:04" (1/1) ... [2023-11-19 04:11:05,045 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2023-11-19 04:11:05,047 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2023-11-19 04:11:05,047 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2023-11-19 04:11:05,048 INFO L274 PluginConnector]: RCFGBuilder initialized [2023-11-19 04:11:05,048 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 04:11:04" (1/1) ... [2023-11-19 04:11:05,055 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-11-19 04:11:05,067 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2f6415e-ee1b-4f50-8e0f-824c676a7e97/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 04:11:05,079 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2f6415e-ee1b-4f50-8e0f-824c676a7e97/bin/utaipan-verify-t7M7D8N6sZ/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2023-11-19 04:11:05,083 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2f6415e-ee1b-4f50-8e0f-824c676a7e97/bin/utaipan-verify-t7M7D8N6sZ/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2023-11-19 04:11:05,110 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$ [2023-11-19 04:11:05,110 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2023-11-19 04:11:05,110 INFO L130 BoogieDeclarations]: Found specification of procedure max [2023-11-19 04:11:05,110 INFO L138 BoogieDeclarations]: Found implementation of procedure max [2023-11-19 04:11:05,110 INFO L130 BoogieDeclarations]: Found specification of procedure nondet_tree [2023-11-19 04:11:05,111 INFO L138 BoogieDeclarations]: Found implementation of procedure nondet_tree [2023-11-19 04:11:05,113 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2023-11-19 04:11:05,113 INFO L130 BoogieDeclarations]: Found specification of procedure check [2023-11-19 04:11:05,113 INFO L138 BoogieDeclarations]: Found implementation of procedure check [2023-11-19 04:11:05,113 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$ [2023-11-19 04:11:05,113 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2023-11-19 04:11:05,114 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnHeap [2023-11-19 04:11:05,114 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2023-11-19 04:11:05,114 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2023-11-19 04:11:05,114 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2023-11-19 04:11:05,191 INFO L236 CfgBuilder]: Building ICFG [2023-11-19 04:11:05,193 INFO L262 CfgBuilder]: Building CFG for each procedure with an implementation [2023-11-19 04:11:05,424 INFO L277 CfgBuilder]: Performing block encoding [2023-11-19 04:11:05,466 INFO L297 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2023-11-19 04:11:05,466 INFO L302 CfgBuilder]: Removed 0 assume(true) statements. [2023-11-19 04:11:05,472 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 19.11 04:11:05 BoogieIcfgContainer [2023-11-19 04:11:05,472 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2023-11-19 04:11:05,475 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2023-11-19 04:11:05,475 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2023-11-19 04:11:05,479 INFO L274 PluginConnector]: TraceAbstraction initialized [2023-11-19 04:11:05,479 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 19.11 04:11:04" (1/3) ... [2023-11-19 04:11:05,480 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3eab016f and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 19.11 04:11:05, skipping insertion in model container [2023-11-19 04:11:05,480 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 04:11:04" (2/3) ... [2023-11-19 04:11:05,480 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3eab016f and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 19.11 04:11:05, skipping insertion in model container [2023-11-19 04:11:05,481 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 19.11 04:11:05" (3/3) ... [2023-11-19 04:11:05,482 INFO L112 eAbstractionObserver]: Analyzing ICFG tree_max.c [2023-11-19 04:11:05,522 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2023-11-19 04:11:05,522 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2023-11-19 04:11:05,593 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-11-19 04:11:05,602 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;@3139ed4c, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2023-11-19 04:11:05,602 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2023-11-19 04:11:05,608 INFO L276 IsEmpty]: Start isEmpty. Operand has 37 states, 23 states have (on average 1.2608695652173914) internal successors, (29), 24 states have internal predecessors, (29), 9 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2023-11-19 04:11:05,619 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2023-11-19 04:11:05,619 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 04:11:05,620 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-19 04:11:05,620 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting checkErr0ASSERT_VIOLATIONERROR_FUNCTION === [checkErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 04:11:05,626 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 04:11:05,627 INFO L85 PathProgramCache]: Analyzing trace with hash 475588941, now seen corresponding path program 1 times [2023-11-19 04:11:05,650 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 04:11:05,651 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [383373270] [2023-11-19 04:11:05,651 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 04:11:05,652 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 04:11:05,788 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 04:11:06,228 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-19 04:11:06,229 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 04:11:06,230 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [383373270] [2023-11-19 04:11:06,230 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [383373270] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-19 04:11:06,231 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-19 04:11:06,231 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2023-11-19 04:11:06,233 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1348073138] [2023-11-19 04:11:06,234 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-19 04:11:06,240 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2023-11-19 04:11:06,240 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 04:11:06,273 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2023-11-19 04:11:06,274 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2023-11-19 04:11:06,276 INFO L87 Difference]: Start difference. First operand has 37 states, 23 states have (on average 1.2608695652173914) internal successors, (29), 24 states have internal predecessors, (29), 9 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) Second operand has 7 states, 7 states have (on average 1.8571428571428572) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2023-11-19 04:11:06,412 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 04:11:06,412 INFO L93 Difference]: Finished difference Result 65 states and 88 transitions. [2023-11-19 04:11:06,417 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2023-11-19 04:11:06,419 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 1.8571428571428572) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 18 [2023-11-19 04:11:06,420 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 04:11:06,431 INFO L225 Difference]: With dead ends: 65 [2023-11-19 04:11:06,432 INFO L226 Difference]: Without dead ends: 33 [2023-11-19 04:11:06,438 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 9 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=19, Invalid=53, Unknown=0, NotChecked=0, Total=72 [2023-11-19 04:11:06,446 INFO L413 NwaCegarLoop]: 39 mSDtfsCounter, 8 mSDsluCounter, 190 mSDsCounter, 0 mSdLazyCounter, 45 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 229 SdHoareTripleChecker+Invalid, 49 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 45 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-19 04:11:06,447 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 229 Invalid, 49 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 45 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-19 04:11:06,467 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 33 states. [2023-11-19 04:11:06,492 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 33 to 33. [2023-11-19 04:11:06,494 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 33 states, 20 states have (on average 1.2) internal successors, (24), 23 states have internal predecessors, (24), 9 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (8), 6 states have call predecessors, (8), 6 states have call successors, (8) [2023-11-19 04:11:06,498 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 33 states to 33 states and 41 transitions. [2023-11-19 04:11:06,499 INFO L78 Accepts]: Start accepts. Automaton has 33 states and 41 transitions. Word has length 18 [2023-11-19 04:11:06,500 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 04:11:06,500 INFO L495 AbstractCegarLoop]: Abstraction has 33 states and 41 transitions. [2023-11-19 04:11:06,500 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 1.8571428571428572) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2023-11-19 04:11:06,500 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 41 transitions. [2023-11-19 04:11:06,502 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2023-11-19 04:11:06,502 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 04:11:06,503 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-19 04:11:06,503 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2023-11-19 04:11:06,503 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting checkErr0ASSERT_VIOLATIONERROR_FUNCTION === [checkErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 04:11:06,504 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 04:11:06,504 INFO L85 PathProgramCache]: Analyzing trace with hash -1555229686, now seen corresponding path program 1 times [2023-11-19 04:11:06,504 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 04:11:06,505 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1383563733] [2023-11-19 04:11:06,505 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 04:11:06,505 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 04:11:06,624 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 04:11:06,946 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2023-11-19 04:11:06,947 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 04:11:06,948 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1383563733] [2023-11-19 04:11:06,948 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1383563733] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-19 04:11:06,948 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-19 04:11:06,948 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2023-11-19 04:11:06,949 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [778924648] [2023-11-19 04:11:06,949 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-19 04:11:06,951 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2023-11-19 04:11:06,951 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 04:11:06,955 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2023-11-19 04:11:06,956 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=43, Unknown=0, NotChecked=0, Total=56 [2023-11-19 04:11:06,956 INFO L87 Difference]: Start difference. First operand 33 states and 41 transitions. Second operand has 8 states, 7 states have (on average 2.4285714285714284) internal successors, (17), 7 states have internal predecessors, (17), 4 states have call successors, (5), 2 states have call predecessors, (5), 3 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2023-11-19 04:11:07,122 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 04:11:07,123 INFO L93 Difference]: Finished difference Result 46 states and 57 transitions. [2023-11-19 04:11:07,124 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2023-11-19 04:11:07,124 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 7 states have (on average 2.4285714285714284) internal successors, (17), 7 states have internal predecessors, (17), 4 states have call successors, (5), 2 states have call predecessors, (5), 3 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) Word has length 30 [2023-11-19 04:11:07,126 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 04:11:07,131 INFO L225 Difference]: With dead ends: 46 [2023-11-19 04:11:07,131 INFO L226 Difference]: Without dead ends: 35 [2023-11-19 04:11:07,136 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 12 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=25, Invalid=85, Unknown=0, NotChecked=0, Total=110 [2023-11-19 04:11:07,139 INFO L413 NwaCegarLoop]: 30 mSDtfsCounter, 11 mSDsluCounter, 152 mSDsCounter, 0 mSdLazyCounter, 79 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 15 SdHoareTripleChecker+Valid, 182 SdHoareTripleChecker+Invalid, 81 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 79 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-19 04:11:07,141 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [15 Valid, 182 Invalid, 81 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 79 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-19 04:11:07,143 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 35 states. [2023-11-19 04:11:07,152 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 35 to 35. [2023-11-19 04:11:07,153 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 35 states, 21 states have (on average 1.1904761904761905) internal successors, (25), 25 states have internal predecessors, (25), 9 states have call successors, (9), 3 states have call predecessors, (9), 4 states have return successors, (10), 6 states have call predecessors, (10), 6 states have call successors, (10) [2023-11-19 04:11:07,158 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 35 states to 35 states and 44 transitions. [2023-11-19 04:11:07,158 INFO L78 Accepts]: Start accepts. Automaton has 35 states and 44 transitions. Word has length 30 [2023-11-19 04:11:07,159 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 04:11:07,159 INFO L495 AbstractCegarLoop]: Abstraction has 35 states and 44 transitions. [2023-11-19 04:11:07,160 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 7 states have (on average 2.4285714285714284) internal successors, (17), 7 states have internal predecessors, (17), 4 states have call successors, (5), 2 states have call predecessors, (5), 3 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2023-11-19 04:11:07,161 INFO L276 IsEmpty]: Start isEmpty. Operand 35 states and 44 transitions. [2023-11-19 04:11:07,164 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 43 [2023-11-19 04:11:07,165 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 04:11:07,165 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-19 04:11:07,165 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2023-11-19 04:11:07,166 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting checkErr0ASSERT_VIOLATIONERROR_FUNCTION === [checkErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 04:11:07,167 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 04:11:07,168 INFO L85 PathProgramCache]: Analyzing trace with hash 447805235, now seen corresponding path program 1 times [2023-11-19 04:11:07,168 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 04:11:07,168 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [961086518] [2023-11-19 04:11:07,169 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 04:11:07,170 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 04:11:07,249 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 04:11:08,457 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 4 proven. 10 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2023-11-19 04:11:08,457 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 04:11:08,457 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [961086518] [2023-11-19 04:11:08,458 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [961086518] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-19 04:11:08,458 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [821178303] [2023-11-19 04:11:08,458 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 04:11:08,458 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 04:11:08,459 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2f6415e-ee1b-4f50-8e0f-824c676a7e97/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 04:11:08,461 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2f6415e-ee1b-4f50-8e0f-824c676a7e97/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 04:11:08,480 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2f6415e-ee1b-4f50-8e0f-824c676a7e97/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2023-11-19 04:11:08,604 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 04:11:08,619 INFO L262 TraceCheckSpWp]: Trace formula consists of 245 conjuncts, 56 conjunts are in the unsatisfiable core [2023-11-19 04:11:08,628 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-19 04:11:09,573 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 37 treesize of output 25 [2023-11-19 04:11:09,625 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 4 proven. 6 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2023-11-19 04:11:09,626 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-19 04:11:09,946 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 17 treesize of output 9 [2023-11-19 04:11:10,723 INFO L349 Elim1Store]: treesize reduction 4, result has 63.6 percent of original size [2023-11-19 04:11:10,723 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 39 treesize of output 34 [2023-11-19 04:11:10,774 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 4 proven. 4 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2023-11-19 04:11:10,775 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [821178303] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-19 04:11:10,775 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [322626805] [2023-11-19 04:11:10,796 INFO L159 IcfgInterpreter]: Started Sifa with 27 locations of interest [2023-11-19 04:11:10,796 INFO L166 IcfgInterpreter]: Building call graph [2023-11-19 04:11:10,801 FATAL L? ?]: Ignoring exception! java.lang.IllegalArgumentException: Recursive programs are not supported. at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.topsortRelevant(CallGraph.java:132) at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.(CallGraph.java:97) at de.uni_freiburg.informatik.ultimate.lib.sifa.IcfgInterpreter.(IcfgInterpreter.java:92) at de.uni_freiburg.informatik.ultimate.plugins.sifa.SifaBuilder.construct(SifaBuilder.java:96) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.SifaRunner.(SifaRunner.java:98) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleSifa.construct(IpTcStrategyModuleSifa.java:68) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getOrConstruct(IpTcStrategyModuleBase.java:101) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getInterpolantComputationStatus(IpTcStrategyModuleBase.java:77) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.tryExecuteInterpolantGenerator(AutomatonFreeRefinementEngine.java:267) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.generateProof(AutomatonFreeRefinementEngine.java:148) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.executeStrategy(AutomatonFreeRefinementEngine.java:137) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.(AutomatonFreeRefinementEngine.java:85) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.TraceAbstractionRefinementEngine.(TraceAbstractionRefinementEngine.java:82) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.BasicCegarLoop.isCounterexampleFeasible(BasicCegarLoop.java:337) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterate(AbstractCegarLoop.java:431) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.startCegar(AbstractCegarLoop.java:366) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.runCegar(AbstractCegarLoop.java:348) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.executeCegarLoop(TraceAbstractionStarter.java:415) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseProgram(TraceAbstractionStarter.java:302) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseSequentialProgram(TraceAbstractionStarter.java:262) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.runCegarLoops(TraceAbstractionStarter.java:175) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.(TraceAbstractionStarter.java:154) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver.finish(TraceAbstractionObserver.java:124) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runObserver(PluginConnector.java:167) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runTool(PluginConnector.java:150) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.run(PluginConnector.java:127) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.executePluginConnector(ToolchainWalker.java:233) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.processPlugin(ToolchainWalker.java:227) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walkUnprotected(ToolchainWalker.java:144) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walk(ToolchainWalker.java:106) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainManager$Toolchain.processToolchain(ToolchainManager.java:319) at de.uni_freiburg.informatik.ultimate.core.coreplugin.toolchain.DefaultToolchainJob.run(DefaultToolchainJob.java:145) at org.eclipse.core.internal.jobs.Worker.run(Worker.java:63) [2023-11-19 04:11:10,802 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-19 04:11:10,802 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 18, 14] total 37 [2023-11-19 04:11:10,803 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [391388498] [2023-11-19 04:11:10,803 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-19 04:11:10,804 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 37 states [2023-11-19 04:11:10,804 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 04:11:10,805 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 37 interpolants. [2023-11-19 04:11:10,806 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=132, Invalid=1200, Unknown=0, NotChecked=0, Total=1332 [2023-11-19 04:11:10,806 INFO L87 Difference]: Start difference. First operand 35 states and 44 transitions. Second operand has 37 states, 28 states have (on average 1.75) internal successors, (49), 25 states have internal predecessors, (49), 11 states have call successors, (17), 4 states have call predecessors, (17), 9 states have return successors, (17), 12 states have call predecessors, (17), 9 states have call successors, (17) [2023-11-19 04:11:11,973 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 04:11:11,973 INFO L93 Difference]: Finished difference Result 50 states and 65 transitions. [2023-11-19 04:11:11,973 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2023-11-19 04:11:11,974 INFO L78 Accepts]: Start accepts. Automaton has has 37 states, 28 states have (on average 1.75) internal successors, (49), 25 states have internal predecessors, (49), 11 states have call successors, (17), 4 states have call predecessors, (17), 9 states have return successors, (17), 12 states have call predecessors, (17), 9 states have call successors, (17) Word has length 42 [2023-11-19 04:11:11,975 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 04:11:11,980 INFO L225 Difference]: With dead ends: 50 [2023-11-19 04:11:11,980 INFO L226 Difference]: Without dead ends: 48 [2023-11-19 04:11:11,982 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 125 GetRequests, 69 SyntacticMatches, 4 SemanticMatches, 52 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 636 ImplicationChecksByTransitivity, 1.6s TimeCoverageRelationStatistics Valid=292, Invalid=2570, Unknown=0, NotChecked=0, Total=2862 [2023-11-19 04:11:11,985 INFO L413 NwaCegarLoop]: 14 mSDtfsCounter, 75 mSDsluCounter, 255 mSDsCounter, 0 mSdLazyCounter, 747 mSolverCounterSat, 52 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 75 SdHoareTripleChecker+Valid, 269 SdHoareTripleChecker+Invalid, 799 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 52 IncrementalHoareTripleChecker+Valid, 747 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2023-11-19 04:11:11,987 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [75 Valid, 269 Invalid, 799 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [52 Valid, 747 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2023-11-19 04:11:11,989 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 48 states. [2023-11-19 04:11:12,009 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 48 to 38. [2023-11-19 04:11:12,009 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 38 states, 24 states have (on average 1.1666666666666667) internal successors, (28), 27 states have internal predecessors, (28), 9 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (10), 6 states have call predecessors, (10), 6 states have call successors, (10) [2023-11-19 04:11:12,016 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 38 states to 38 states and 47 transitions. [2023-11-19 04:11:12,017 INFO L78 Accepts]: Start accepts. Automaton has 38 states and 47 transitions. Word has length 42 [2023-11-19 04:11:12,018 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 04:11:12,018 INFO L495 AbstractCegarLoop]: Abstraction has 38 states and 47 transitions. [2023-11-19 04:11:12,018 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 37 states, 28 states have (on average 1.75) internal successors, (49), 25 states have internal predecessors, (49), 11 states have call successors, (17), 4 states have call predecessors, (17), 9 states have return successors, (17), 12 states have call predecessors, (17), 9 states have call successors, (17) [2023-11-19 04:11:12,019 INFO L276 IsEmpty]: Start isEmpty. Operand 38 states and 47 transitions. [2023-11-19 04:11:12,027 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 49 [2023-11-19 04:11:12,028 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 04:11:12,029 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-19 04:11:12,054 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2f6415e-ee1b-4f50-8e0f-824c676a7e97/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2023-11-19 04:11:12,251 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2f6415e-ee1b-4f50-8e0f-824c676a7e97/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 04:11:12,252 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting checkErr0ASSERT_VIOLATIONERROR_FUNCTION === [checkErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 04:11:12,252 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 04:11:12,252 INFO L85 PathProgramCache]: Analyzing trace with hash 266574098, now seen corresponding path program 1 times [2023-11-19 04:11:12,253 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 04:11:12,253 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1032529286] [2023-11-19 04:11:12,253 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 04:11:12,253 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 04:11:12,298 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 04:11:13,228 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 8 proven. 8 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2023-11-19 04:11:13,229 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 04:11:13,229 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1032529286] [2023-11-19 04:11:13,229 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1032529286] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-19 04:11:13,230 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [688630514] [2023-11-19 04:11:13,230 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 04:11:13,230 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 04:11:13,230 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2f6415e-ee1b-4f50-8e0f-824c676a7e97/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 04:11:13,231 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2f6415e-ee1b-4f50-8e0f-824c676a7e97/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 04:11:13,241 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2f6415e-ee1b-4f50-8e0f-824c676a7e97/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2023-11-19 04:11:13,341 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 04:11:13,344 INFO L262 TraceCheckSpWp]: Trace formula consists of 273 conjuncts, 61 conjunts are in the unsatisfiable core [2023-11-19 04:11:13,348 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-19 04:11:13,710 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 5 proven. 8 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2023-11-19 04:11:13,710 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-19 04:11:16,159 INFO L349 Elim1Store]: treesize reduction 4, result has 63.6 percent of original size [2023-11-19 04:11:16,160 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 30 treesize of output 25 [2023-11-19 04:11:16,173 INFO L349 Elim1Store]: treesize reduction 10, result has 9.1 percent of original size [2023-11-19 04:11:16,174 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 24 treesize of output 12 [2023-11-19 04:11:16,207 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 3 proven. 9 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2023-11-19 04:11:16,208 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [688630514] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-19 04:11:16,208 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1313023520] [2023-11-19 04:11:16,213 INFO L159 IcfgInterpreter]: Started Sifa with 30 locations of interest [2023-11-19 04:11:16,213 INFO L166 IcfgInterpreter]: Building call graph [2023-11-19 04:11:16,213 FATAL L? ?]: Ignoring exception! java.lang.IllegalArgumentException: Recursive programs are not supported. at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.topsortRelevant(CallGraph.java:132) at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.(CallGraph.java:97) at de.uni_freiburg.informatik.ultimate.lib.sifa.IcfgInterpreter.(IcfgInterpreter.java:92) at de.uni_freiburg.informatik.ultimate.plugins.sifa.SifaBuilder.construct(SifaBuilder.java:96) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.SifaRunner.(SifaRunner.java:98) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleSifa.construct(IpTcStrategyModuleSifa.java:68) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getOrConstruct(IpTcStrategyModuleBase.java:101) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getInterpolantComputationStatus(IpTcStrategyModuleBase.java:77) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.tryExecuteInterpolantGenerator(AutomatonFreeRefinementEngine.java:267) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.generateProof(AutomatonFreeRefinementEngine.java:148) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.executeStrategy(AutomatonFreeRefinementEngine.java:137) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.(AutomatonFreeRefinementEngine.java:85) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.TraceAbstractionRefinementEngine.(TraceAbstractionRefinementEngine.java:82) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.BasicCegarLoop.isCounterexampleFeasible(BasicCegarLoop.java:337) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterate(AbstractCegarLoop.java:431) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.startCegar(AbstractCegarLoop.java:366) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.runCegar(AbstractCegarLoop.java:348) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.executeCegarLoop(TraceAbstractionStarter.java:415) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseProgram(TraceAbstractionStarter.java:302) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseSequentialProgram(TraceAbstractionStarter.java:262) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.runCegarLoops(TraceAbstractionStarter.java:175) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.(TraceAbstractionStarter.java:154) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver.finish(TraceAbstractionObserver.java:124) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runObserver(PluginConnector.java:167) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runTool(PluginConnector.java:150) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.run(PluginConnector.java:127) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.executePluginConnector(ToolchainWalker.java:233) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.processPlugin(ToolchainWalker.java:227) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walkUnprotected(ToolchainWalker.java:144) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walk(ToolchainWalker.java:106) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainManager$Toolchain.processToolchain(ToolchainManager.java:319) at de.uni_freiburg.informatik.ultimate.core.coreplugin.toolchain.DefaultToolchainJob.run(DefaultToolchainJob.java:145) at org.eclipse.core.internal.jobs.Worker.run(Worker.java:63) [2023-11-19 04:11:16,214 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-19 04:11:16,214 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 13, 13] total 27 [2023-11-19 04:11:16,215 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1503377912] [2023-11-19 04:11:16,215 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-19 04:11:16,218 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 27 states [2023-11-19 04:11:16,218 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 04:11:16,220 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 27 interpolants. [2023-11-19 04:11:16,247 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=73, Invalid=628, Unknown=1, NotChecked=0, Total=702 [2023-11-19 04:11:16,249 INFO L87 Difference]: Start difference. First operand 38 states and 47 transitions. Second operand has 27 states, 22 states have (on average 2.3181818181818183) internal successors, (51), 22 states have internal predecessors, (51), 11 states have call successors, (16), 5 states have call predecessors, (16), 7 states have return successors, (14), 8 states have call predecessors, (14), 8 states have call successors, (14) [2023-11-19 04:11:17,312 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 04:11:17,312 INFO L93 Difference]: Finished difference Result 68 states and 87 transitions. [2023-11-19 04:11:17,313 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2023-11-19 04:11:17,313 INFO L78 Accepts]: Start accepts. Automaton has has 27 states, 22 states have (on average 2.3181818181818183) internal successors, (51), 22 states have internal predecessors, (51), 11 states have call successors, (16), 5 states have call predecessors, (16), 7 states have return successors, (14), 8 states have call predecessors, (14), 8 states have call successors, (14) Word has length 48 [2023-11-19 04:11:17,314 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 04:11:17,315 INFO L225 Difference]: With dead ends: 68 [2023-11-19 04:11:17,315 INFO L226 Difference]: Without dead ends: 56 [2023-11-19 04:11:17,317 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 129 GetRequests, 88 SyntacticMatches, 1 SemanticMatches, 40 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 279 ImplicationChecksByTransitivity, 3.1s TimeCoverageRelationStatistics Valid=191, Invalid=1530, Unknown=1, NotChecked=0, Total=1722 [2023-11-19 04:11:17,318 INFO L413 NwaCegarLoop]: 30 mSDtfsCounter, 51 mSDsluCounter, 376 mSDsCounter, 0 mSdLazyCounter, 513 mSolverCounterSat, 40 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 51 SdHoareTripleChecker+Valid, 406 SdHoareTripleChecker+Invalid, 553 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 40 IncrementalHoareTripleChecker+Valid, 513 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2023-11-19 04:11:17,318 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [51 Valid, 406 Invalid, 553 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [40 Valid, 513 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2023-11-19 04:11:17,319 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 56 states. [2023-11-19 04:11:17,336 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 56 to 55. [2023-11-19 04:11:17,337 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 55 states, 36 states have (on average 1.1388888888888888) internal successors, (41), 39 states have internal predecessors, (41), 12 states have call successors, (12), 6 states have call predecessors, (12), 6 states have return successors, (19), 9 states have call predecessors, (19), 8 states have call successors, (19) [2023-11-19 04:11:17,340 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 55 states to 55 states and 72 transitions. [2023-11-19 04:11:17,340 INFO L78 Accepts]: Start accepts. Automaton has 55 states and 72 transitions. Word has length 48 [2023-11-19 04:11:17,342 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 04:11:17,342 INFO L495 AbstractCegarLoop]: Abstraction has 55 states and 72 transitions. [2023-11-19 04:11:17,342 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 27 states, 22 states have (on average 2.3181818181818183) internal successors, (51), 22 states have internal predecessors, (51), 11 states have call successors, (16), 5 states have call predecessors, (16), 7 states have return successors, (14), 8 states have call predecessors, (14), 8 states have call successors, (14) [2023-11-19 04:11:17,342 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 72 transitions. [2023-11-19 04:11:17,345 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 49 [2023-11-19 04:11:17,345 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 04:11:17,346 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-19 04:11:17,373 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2f6415e-ee1b-4f50-8e0f-824c676a7e97/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2023-11-19 04:11:17,565 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2f6415e-ee1b-4f50-8e0f-824c676a7e97/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 04:11:17,565 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting checkErr0ASSERT_VIOLATIONERROR_FUNCTION === [checkErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 04:11:17,566 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 04:11:17,566 INFO L85 PathProgramCache]: Analyzing trace with hash 382937744, now seen corresponding path program 1 times [2023-11-19 04:11:17,566 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 04:11:17,566 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [627156322] [2023-11-19 04:11:17,566 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 04:11:17,566 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 04:11:17,599 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 04:11:18,188 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 5 proven. 4 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2023-11-19 04:11:18,188 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 04:11:18,188 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [627156322] [2023-11-19 04:11:18,188 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [627156322] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-19 04:11:18,188 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [234887935] [2023-11-19 04:11:18,188 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 04:11:18,189 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 04:11:18,189 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2f6415e-ee1b-4f50-8e0f-824c676a7e97/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 04:11:18,197 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2f6415e-ee1b-4f50-8e0f-824c676a7e97/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 04:11:18,231 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2f6415e-ee1b-4f50-8e0f-824c676a7e97/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2023-11-19 04:11:18,317 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 04:11:18,320 INFO L262 TraceCheckSpWp]: Trace formula consists of 274 conjuncts, 57 conjunts are in the unsatisfiable core [2023-11-19 04:11:18,324 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-19 04:11:18,364 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 13 treesize of output 9 [2023-11-19 04:11:18,370 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 13 treesize of output 9 [2023-11-19 04:11:18,740 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 5 proven. 4 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2023-11-19 04:11:18,741 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-19 04:11:18,953 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 5 proven. 4 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2023-11-19 04:11:18,954 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [234887935] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-19 04:11:18,954 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1830101468] [2023-11-19 04:11:18,957 INFO L159 IcfgInterpreter]: Started Sifa with 30 locations of interest [2023-11-19 04:11:18,958 INFO L166 IcfgInterpreter]: Building call graph [2023-11-19 04:11:18,958 FATAL L? ?]: Ignoring exception! java.lang.IllegalArgumentException: Recursive programs are not supported. at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.topsortRelevant(CallGraph.java:132) at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.(CallGraph.java:97) at de.uni_freiburg.informatik.ultimate.lib.sifa.IcfgInterpreter.(IcfgInterpreter.java:92) at de.uni_freiburg.informatik.ultimate.plugins.sifa.SifaBuilder.construct(SifaBuilder.java:96) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.SifaRunner.(SifaRunner.java:98) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleSifa.construct(IpTcStrategyModuleSifa.java:68) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getOrConstruct(IpTcStrategyModuleBase.java:101) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getInterpolantComputationStatus(IpTcStrategyModuleBase.java:77) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.tryExecuteInterpolantGenerator(AutomatonFreeRefinementEngine.java:267) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.generateProof(AutomatonFreeRefinementEngine.java:148) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.executeStrategy(AutomatonFreeRefinementEngine.java:137) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.(AutomatonFreeRefinementEngine.java:85) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.TraceAbstractionRefinementEngine.(TraceAbstractionRefinementEngine.java:82) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.BasicCegarLoop.isCounterexampleFeasible(BasicCegarLoop.java:337) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterate(AbstractCegarLoop.java:431) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.startCegar(AbstractCegarLoop.java:366) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.runCegar(AbstractCegarLoop.java:348) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.executeCegarLoop(TraceAbstractionStarter.java:415) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseProgram(TraceAbstractionStarter.java:302) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseSequentialProgram(TraceAbstractionStarter.java:262) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.runCegarLoops(TraceAbstractionStarter.java:175) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.(TraceAbstractionStarter.java:154) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver.finish(TraceAbstractionObserver.java:124) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runObserver(PluginConnector.java:167) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runTool(PluginConnector.java:150) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.run(PluginConnector.java:127) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.executePluginConnector(ToolchainWalker.java:233) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.processPlugin(ToolchainWalker.java:227) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walkUnprotected(ToolchainWalker.java:144) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walk(ToolchainWalker.java:106) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainManager$Toolchain.processToolchain(ToolchainManager.java:319) at de.uni_freiburg.informatik.ultimate.core.coreplugin.toolchain.DefaultToolchainJob.run(DefaultToolchainJob.java:145) at org.eclipse.core.internal.jobs.Worker.run(Worker.java:63) [2023-11-19 04:11:18,959 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-19 04:11:18,959 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13, 12] total 20 [2023-11-19 04:11:18,960 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [422405659] [2023-11-19 04:11:18,960 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-19 04:11:18,961 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2023-11-19 04:11:18,961 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 04:11:18,962 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2023-11-19 04:11:18,962 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=54, Invalid=326, Unknown=0, NotChecked=0, Total=380 [2023-11-19 04:11:18,962 INFO L87 Difference]: Start difference. First operand 55 states and 72 transitions. Second operand has 20 states, 19 states have (on average 2.3157894736842106) internal successors, (44), 13 states have internal predecessors, (44), 6 states have call successors, (15), 5 states have call predecessors, (15), 5 states have return successors, (13), 9 states have call predecessors, (13), 5 states have call successors, (13) [2023-11-19 04:11:19,516 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 04:11:19,517 INFO L93 Difference]: Finished difference Result 118 states and 152 transitions. [2023-11-19 04:11:19,517 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2023-11-19 04:11:19,517 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 19 states have (on average 2.3157894736842106) internal successors, (44), 13 states have internal predecessors, (44), 6 states have call successors, (15), 5 states have call predecessors, (15), 5 states have return successors, (13), 9 states have call predecessors, (13), 5 states have call successors, (13) Word has length 48 [2023-11-19 04:11:19,520 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 04:11:19,522 INFO L225 Difference]: With dead ends: 118 [2023-11-19 04:11:19,522 INFO L226 Difference]: Without dead ends: 99 [2023-11-19 04:11:19,523 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 116 GetRequests, 90 SyntacticMatches, 1 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 63 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=98, Invalid=604, Unknown=0, NotChecked=0, Total=702 [2023-11-19 04:11:19,524 INFO L413 NwaCegarLoop]: 33 mSDtfsCounter, 31 mSDsluCounter, 311 mSDsCounter, 0 mSdLazyCounter, 310 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 33 SdHoareTripleChecker+Valid, 344 SdHoareTripleChecker+Invalid, 316 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 310 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2023-11-19 04:11:19,524 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [33 Valid, 344 Invalid, 316 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 310 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2023-11-19 04:11:19,529 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 99 states. [2023-11-19 04:11:19,559 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 99 to 87. [2023-11-19 04:11:19,560 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 87 states, 57 states have (on average 1.1228070175438596) internal successors, (64), 61 states have internal predecessors, (64), 18 states have call successors, (18), 9 states have call predecessors, (18), 11 states have return successors, (35), 16 states have call predecessors, (35), 13 states have call successors, (35) [2023-11-19 04:11:19,561 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 87 states to 87 states and 117 transitions. [2023-11-19 04:11:19,562 INFO L78 Accepts]: Start accepts. Automaton has 87 states and 117 transitions. Word has length 48 [2023-11-19 04:11:19,562 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 04:11:19,562 INFO L495 AbstractCegarLoop]: Abstraction has 87 states and 117 transitions. [2023-11-19 04:11:19,562 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 19 states have (on average 2.3157894736842106) internal successors, (44), 13 states have internal predecessors, (44), 6 states have call successors, (15), 5 states have call predecessors, (15), 5 states have return successors, (13), 9 states have call predecessors, (13), 5 states have call successors, (13) [2023-11-19 04:11:19,563 INFO L276 IsEmpty]: Start isEmpty. Operand 87 states and 117 transitions. [2023-11-19 04:11:19,564 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 61 [2023-11-19 04:11:19,564 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 04:11:19,565 INFO L195 NwaCegarLoop]: trace histogram [5, 5, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-19 04:11:19,592 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2f6415e-ee1b-4f50-8e0f-824c676a7e97/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2023-11-19 04:11:19,781 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2f6415e-ee1b-4f50-8e0f-824c676a7e97/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 04:11:19,781 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting checkErr0ASSERT_VIOLATIONERROR_FUNCTION === [checkErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 04:11:19,782 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 04:11:19,782 INFO L85 PathProgramCache]: Analyzing trace with hash 712213875, now seen corresponding path program 2 times [2023-11-19 04:11:19,782 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 04:11:19,782 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1958854274] [2023-11-19 04:11:19,782 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 04:11:19,782 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 04:11:19,838 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 04:11:20,722 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 15 proven. 5 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2023-11-19 04:11:20,722 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 04:11:20,722 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1958854274] [2023-11-19 04:11:20,722 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1958854274] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-19 04:11:20,722 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [855927846] [2023-11-19 04:11:20,722 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-11-19 04:11:20,723 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 04:11:20,723 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2f6415e-ee1b-4f50-8e0f-824c676a7e97/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 04:11:20,724 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2f6415e-ee1b-4f50-8e0f-824c676a7e97/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 04:11:20,746 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2f6415e-ee1b-4f50-8e0f-824c676a7e97/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2023-11-19 04:11:20,832 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 2 check-sat command(s) [2023-11-19 04:11:20,832 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-19 04:11:20,835 INFO L262 TraceCheckSpWp]: Trace formula consists of 217 conjuncts, 65 conjunts are in the unsatisfiable core [2023-11-19 04:11:20,839 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-19 04:11:20,847 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 1 [2023-11-19 04:11:20,849 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 1 [2023-11-19 04:11:21,072 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 6 proven. 5 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2023-11-19 04:11:21,072 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-19 04:11:23,675 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 6 proven. 6 refuted. 0 times theorem prover too weak. 47 trivial. 0 not checked. [2023-11-19 04:11:23,675 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [855927846] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-19 04:11:23,676 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [945635177] [2023-11-19 04:11:23,683 INFO L159 IcfgInterpreter]: Started Sifa with 30 locations of interest [2023-11-19 04:11:23,683 INFO L166 IcfgInterpreter]: Building call graph [2023-11-19 04:11:23,684 FATAL L? ?]: Ignoring exception! java.lang.IllegalArgumentException: Recursive programs are not supported. at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.topsortRelevant(CallGraph.java:132) at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.(CallGraph.java:97) at de.uni_freiburg.informatik.ultimate.lib.sifa.IcfgInterpreter.(IcfgInterpreter.java:92) at de.uni_freiburg.informatik.ultimate.plugins.sifa.SifaBuilder.construct(SifaBuilder.java:96) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.SifaRunner.(SifaRunner.java:98) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleSifa.construct(IpTcStrategyModuleSifa.java:68) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getOrConstruct(IpTcStrategyModuleBase.java:101) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getInterpolantComputationStatus(IpTcStrategyModuleBase.java:77) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.tryExecuteInterpolantGenerator(AutomatonFreeRefinementEngine.java:267) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.generateProof(AutomatonFreeRefinementEngine.java:148) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.executeStrategy(AutomatonFreeRefinementEngine.java:137) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.(AutomatonFreeRefinementEngine.java:85) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.TraceAbstractionRefinementEngine.(TraceAbstractionRefinementEngine.java:82) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.BasicCegarLoop.isCounterexampleFeasible(BasicCegarLoop.java:337) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterate(AbstractCegarLoop.java:431) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.startCegar(AbstractCegarLoop.java:366) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.runCegar(AbstractCegarLoop.java:348) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.executeCegarLoop(TraceAbstractionStarter.java:415) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseProgram(TraceAbstractionStarter.java:302) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseSequentialProgram(TraceAbstractionStarter.java:262) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.runCegarLoops(TraceAbstractionStarter.java:175) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.(TraceAbstractionStarter.java:154) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver.finish(TraceAbstractionObserver.java:124) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runObserver(PluginConnector.java:167) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runTool(PluginConnector.java:150) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.run(PluginConnector.java:127) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.executePluginConnector(ToolchainWalker.java:233) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.processPlugin(ToolchainWalker.java:227) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walkUnprotected(ToolchainWalker.java:144) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walk(ToolchainWalker.java:106) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainManager$Toolchain.processToolchain(ToolchainManager.java:319) at de.uni_freiburg.informatik.ultimate.core.coreplugin.toolchain.DefaultToolchainJob.run(DefaultToolchainJob.java:145) at org.eclipse.core.internal.jobs.Worker.run(Worker.java:63) [2023-11-19 04:11:23,685 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-19 04:11:23,685 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 12, 13] total 26 [2023-11-19 04:11:23,686 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1337316658] [2023-11-19 04:11:23,686 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-19 04:11:23,687 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 26 states [2023-11-19 04:11:23,687 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 04:11:23,688 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2023-11-19 04:11:23,689 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=64, Invalid=585, Unknown=1, NotChecked=0, Total=650 [2023-11-19 04:11:23,689 INFO L87 Difference]: Start difference. First operand 87 states and 117 transitions. Second operand has 26 states, 21 states have (on average 2.4285714285714284) internal successors, (51), 22 states have internal predecessors, (51), 12 states have call successors, (16), 4 states have call predecessors, (16), 6 states have return successors, (14), 10 states have call predecessors, (14), 9 states have call successors, (14) [2023-11-19 04:11:24,337 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 04:11:24,337 INFO L93 Difference]: Finished difference Result 133 states and 180 transitions. [2023-11-19 04:11:24,338 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2023-11-19 04:11:24,338 INFO L78 Accepts]: Start accepts. Automaton has has 26 states, 21 states have (on average 2.4285714285714284) internal successors, (51), 22 states have internal predecessors, (51), 12 states have call successors, (16), 4 states have call predecessors, (16), 6 states have return successors, (14), 10 states have call predecessors, (14), 9 states have call successors, (14) Word has length 60 [2023-11-19 04:11:24,340 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 04:11:24,345 INFO L225 Difference]: With dead ends: 133 [2023-11-19 04:11:24,346 INFO L226 Difference]: Without dead ends: 114 [2023-11-19 04:11:24,350 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 150 GetRequests, 116 SyntacticMatches, 0 SemanticMatches, 34 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 138 ImplicationChecksByTransitivity, 2.8s TimeCoverageRelationStatistics Valid=136, Invalid=1123, Unknown=1, NotChecked=0, Total=1260 [2023-11-19 04:11:24,352 INFO L413 NwaCegarLoop]: 29 mSDtfsCounter, 47 mSDsluCounter, 361 mSDsCounter, 0 mSdLazyCounter, 395 mSolverCounterSat, 18 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 47 SdHoareTripleChecker+Valid, 390 SdHoareTripleChecker+Invalid, 413 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 18 IncrementalHoareTripleChecker+Valid, 395 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2023-11-19 04:11:24,353 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [47 Valid, 390 Invalid, 413 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [18 Valid, 395 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2023-11-19 04:11:24,355 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 114 states. [2023-11-19 04:11:24,392 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 114 to 93. [2023-11-19 04:11:24,393 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 93 states, 61 states have (on average 1.1147540983606556) internal successors, (68), 65 states have internal predecessors, (68), 18 states have call successors, (18), 9 states have call predecessors, (18), 13 states have return successors, (44), 18 states have call predecessors, (44), 13 states have call successors, (44) [2023-11-19 04:11:24,395 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 93 states to 93 states and 130 transitions. [2023-11-19 04:11:24,396 INFO L78 Accepts]: Start accepts. Automaton has 93 states and 130 transitions. Word has length 60 [2023-11-19 04:11:24,398 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 04:11:24,399 INFO L495 AbstractCegarLoop]: Abstraction has 93 states and 130 transitions. [2023-11-19 04:11:24,399 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 26 states, 21 states have (on average 2.4285714285714284) internal successors, (51), 22 states have internal predecessors, (51), 12 states have call successors, (16), 4 states have call predecessors, (16), 6 states have return successors, (14), 10 states have call predecessors, (14), 9 states have call successors, (14) [2023-11-19 04:11:24,399 INFO L276 IsEmpty]: Start isEmpty. Operand 93 states and 130 transitions. [2023-11-19 04:11:24,403 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 61 [2023-11-19 04:11:24,403 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 04:11:24,404 INFO L195 NwaCegarLoop]: trace histogram [5, 5, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-19 04:11:24,431 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2f6415e-ee1b-4f50-8e0f-824c676a7e97/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2023-11-19 04:11:24,626 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2f6415e-ee1b-4f50-8e0f-824c676a7e97/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 04:11:24,626 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting checkErr0ASSERT_VIOLATIONERROR_FUNCTION === [checkErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 04:11:24,626 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 04:11:24,627 INFO L85 PathProgramCache]: Analyzing trace with hash -1890494007, now seen corresponding path program 2 times [2023-11-19 04:11:24,627 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 04:11:24,627 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1760484778] [2023-11-19 04:11:24,627 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 04:11:24,627 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 04:11:24,652 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 04:11:25,479 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 15 proven. 20 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2023-11-19 04:11:25,479 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 04:11:25,479 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1760484778] [2023-11-19 04:11:25,479 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1760484778] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-19 04:11:25,480 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1861577003] [2023-11-19 04:11:25,480 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-11-19 04:11:25,480 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 04:11:25,480 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2f6415e-ee1b-4f50-8e0f-824c676a7e97/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 04:11:25,485 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2f6415e-ee1b-4f50-8e0f-824c676a7e97/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 04:11:25,508 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2f6415e-ee1b-4f50-8e0f-824c676a7e97/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2023-11-19 04:11:25,601 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 2 check-sat command(s) [2023-11-19 04:11:25,601 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-19 04:11:25,604 INFO L262 TraceCheckSpWp]: Trace formula consists of 216 conjuncts, 61 conjunts are in the unsatisfiable core [2023-11-19 04:11:25,613 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-19 04:11:25,647 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 13 treesize of output 9 [2023-11-19 04:11:25,654 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 13 treesize of output 9 [2023-11-19 04:11:25,709 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 13 [2023-11-19 04:11:25,715 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 13 [2023-11-19 04:11:26,222 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 5 proven. 8 refuted. 0 times theorem prover too weak. 46 trivial. 0 not checked. [2023-11-19 04:11:26,222 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-19 04:11:26,725 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 5 proven. 8 refuted. 0 times theorem prover too weak. 46 trivial. 0 not checked. [2023-11-19 04:11:26,726 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1861577003] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-19 04:11:26,726 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1219546455] [2023-11-19 04:11:26,734 INFO L159 IcfgInterpreter]: Started Sifa with 30 locations of interest [2023-11-19 04:11:26,734 INFO L166 IcfgInterpreter]: Building call graph [2023-11-19 04:11:26,735 FATAL L? ?]: Ignoring exception! java.lang.IllegalArgumentException: Recursive programs are not supported. at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.topsortRelevant(CallGraph.java:132) at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.(CallGraph.java:97) at de.uni_freiburg.informatik.ultimate.lib.sifa.IcfgInterpreter.(IcfgInterpreter.java:92) at de.uni_freiburg.informatik.ultimate.plugins.sifa.SifaBuilder.construct(SifaBuilder.java:96) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.SifaRunner.(SifaRunner.java:98) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleSifa.construct(IpTcStrategyModuleSifa.java:68) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getOrConstruct(IpTcStrategyModuleBase.java:101) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getInterpolantComputationStatus(IpTcStrategyModuleBase.java:77) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.tryExecuteInterpolantGenerator(AutomatonFreeRefinementEngine.java:267) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.generateProof(AutomatonFreeRefinementEngine.java:148) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.executeStrategy(AutomatonFreeRefinementEngine.java:137) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.(AutomatonFreeRefinementEngine.java:85) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.TraceAbstractionRefinementEngine.(TraceAbstractionRefinementEngine.java:82) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.BasicCegarLoop.isCounterexampleFeasible(BasicCegarLoop.java:337) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterate(AbstractCegarLoop.java:431) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.startCegar(AbstractCegarLoop.java:366) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.runCegar(AbstractCegarLoop.java:348) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.executeCegarLoop(TraceAbstractionStarter.java:415) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseProgram(TraceAbstractionStarter.java:302) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseSequentialProgram(TraceAbstractionStarter.java:262) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.runCegarLoops(TraceAbstractionStarter.java:175) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.(TraceAbstractionStarter.java:154) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver.finish(TraceAbstractionObserver.java:124) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runObserver(PluginConnector.java:167) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runTool(PluginConnector.java:150) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.run(PluginConnector.java:127) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.executePluginConnector(ToolchainWalker.java:233) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.processPlugin(ToolchainWalker.java:227) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walkUnprotected(ToolchainWalker.java:144) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walk(ToolchainWalker.java:106) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainManager$Toolchain.processToolchain(ToolchainManager.java:319) at de.uni_freiburg.informatik.ultimate.core.coreplugin.toolchain.DefaultToolchainJob.run(DefaultToolchainJob.java:145) at org.eclipse.core.internal.jobs.Worker.run(Worker.java:63) [2023-11-19 04:11:26,735 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-19 04:11:26,735 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 15, 14] total 29 [2023-11-19 04:11:26,735 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [334895297] [2023-11-19 04:11:26,736 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-19 04:11:26,738 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 29 states [2023-11-19 04:11:26,738 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 04:11:26,739 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 29 interpolants. [2023-11-19 04:11:26,739 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=78, Invalid=734, Unknown=0, NotChecked=0, Total=812 [2023-11-19 04:11:26,740 INFO L87 Difference]: Start difference. First operand 93 states and 130 transitions. Second operand has 29 states, 25 states have (on average 2.32) internal successors, (58), 22 states have internal predecessors, (58), 13 states have call successors, (21), 7 states have call predecessors, (21), 9 states have return successors, (18), 14 states have call predecessors, (18), 11 states have call successors, (18) [2023-11-19 04:11:28,388 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 04:11:28,388 INFO L93 Difference]: Finished difference Result 142 states and 197 transitions. [2023-11-19 04:11:28,388 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2023-11-19 04:11:28,389 INFO L78 Accepts]: Start accepts. Automaton has has 29 states, 25 states have (on average 2.32) internal successors, (58), 22 states have internal predecessors, (58), 13 states have call successors, (21), 7 states have call predecessors, (21), 9 states have return successors, (18), 14 states have call predecessors, (18), 11 states have call successors, (18) Word has length 60 [2023-11-19 04:11:28,389 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 04:11:28,391 INFO L225 Difference]: With dead ends: 142 [2023-11-19 04:11:28,391 INFO L226 Difference]: Without dead ends: 104 [2023-11-19 04:11:28,392 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 153 GetRequests, 109 SyntacticMatches, 1 SemanticMatches, 43 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 346 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=247, Invalid=1733, Unknown=0, NotChecked=0, Total=1980 [2023-11-19 04:11:28,393 INFO L413 NwaCegarLoop]: 18 mSDtfsCounter, 74 mSDsluCounter, 298 mSDsCounter, 0 mSdLazyCounter, 899 mSolverCounterSat, 46 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 78 SdHoareTripleChecker+Valid, 316 SdHoareTripleChecker+Invalid, 945 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 46 IncrementalHoareTripleChecker+Valid, 899 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.8s IncrementalHoareTripleChecker+Time [2023-11-19 04:11:28,394 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [78 Valid, 316 Invalid, 945 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [46 Valid, 899 Invalid, 0 Unknown, 0 Unchecked, 0.8s Time] [2023-11-19 04:11:28,394 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 104 states. [2023-11-19 04:11:28,428 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 104 to 102. [2023-11-19 04:11:28,429 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 102 states, 67 states have (on average 1.1194029850746268) internal successors, (75), 71 states have internal predecessors, (75), 19 states have call successors, (19), 10 states have call predecessors, (19), 15 states have return successors, (50), 20 states have call predecessors, (50), 14 states have call successors, (50) [2023-11-19 04:11:28,432 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 102 states to 102 states and 144 transitions. [2023-11-19 04:11:28,432 INFO L78 Accepts]: Start accepts. Automaton has 102 states and 144 transitions. Word has length 60 [2023-11-19 04:11:28,432 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 04:11:28,433 INFO L495 AbstractCegarLoop]: Abstraction has 102 states and 144 transitions. [2023-11-19 04:11:28,433 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 29 states, 25 states have (on average 2.32) internal successors, (58), 22 states have internal predecessors, (58), 13 states have call successors, (21), 7 states have call predecessors, (21), 9 states have return successors, (18), 14 states have call predecessors, (18), 11 states have call successors, (18) [2023-11-19 04:11:28,433 INFO L276 IsEmpty]: Start isEmpty. Operand 102 states and 144 transitions. [2023-11-19 04:11:28,435 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 73 [2023-11-19 04:11:28,435 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 04:11:28,435 INFO L195 NwaCegarLoop]: trace histogram [5, 5, 5, 5, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-19 04:11:28,465 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2f6415e-ee1b-4f50-8e0f-824c676a7e97/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2023-11-19 04:11:28,657 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2f6415e-ee1b-4f50-8e0f-824c676a7e97/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 04:11:28,657 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting checkErr0ASSERT_VIOLATIONERROR_FUNCTION === [checkErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 04:11:28,657 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 04:11:28,657 INFO L85 PathProgramCache]: Analyzing trace with hash -1253566102, now seen corresponding path program 3 times [2023-11-19 04:11:28,658 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 04:11:28,658 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [800398848] [2023-11-19 04:11:28,658 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 04:11:28,658 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 04:11:28,733 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 04:11:30,679 INFO L134 CoverageAnalysis]: Checked inductivity of 91 backedges. 19 proven. 24 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2023-11-19 04:11:30,679 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 04:11:30,679 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [800398848] [2023-11-19 04:11:30,679 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [800398848] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-19 04:11:30,679 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1013267907] [2023-11-19 04:11:30,679 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2023-11-19 04:11:30,679 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 04:11:30,680 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2f6415e-ee1b-4f50-8e0f-824c676a7e97/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 04:11:30,681 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2f6415e-ee1b-4f50-8e0f-824c676a7e97/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 04:11:30,696 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2f6415e-ee1b-4f50-8e0f-824c676a7e97/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2023-11-19 04:11:30,836 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2023-11-19 04:11:30,836 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-19 04:11:30,841 INFO L262 TraceCheckSpWp]: Trace formula consists of 421 conjuncts, 126 conjunts are in the unsatisfiable core [2023-11-19 04:11:30,848 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-19 04:11:30,880 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2023-11-19 04:11:30,882 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-11-19 04:11:33,056 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 45 treesize of output 33 [2023-11-19 04:11:33,064 INFO L349 Elim1Store]: treesize reduction 7, result has 12.5 percent of original size [2023-11-19 04:11:33,064 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 15 treesize of output 7 [2023-11-19 04:11:33,500 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-11-19 04:11:33,501 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 53 treesize of output 57 [2023-11-19 04:11:33,595 INFO L134 CoverageAnalysis]: Checked inductivity of 91 backedges. 16 proven. 26 refuted. 0 times theorem prover too weak. 49 trivial. 0 not checked. [2023-11-19 04:11:33,595 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-19 04:11:34,544 INFO L349 Elim1Store]: treesize reduction 22, result has 4.3 percent of original size [2023-11-19 04:11:34,544 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 55 treesize of output 1 [2023-11-19 04:11:47,523 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1013267907] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-19 04:11:47,523 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1974275415] [2023-11-19 04:11:47,527 INFO L159 IcfgInterpreter]: Started Sifa with 30 locations of interest [2023-11-19 04:11:47,527 INFO L166 IcfgInterpreter]: Building call graph [2023-11-19 04:11:47,528 FATAL L? ?]: Ignoring exception! java.lang.IllegalArgumentException: Recursive programs are not supported. at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.topsortRelevant(CallGraph.java:132) at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.(CallGraph.java:97) at de.uni_freiburg.informatik.ultimate.lib.sifa.IcfgInterpreter.(IcfgInterpreter.java:92) at de.uni_freiburg.informatik.ultimate.plugins.sifa.SifaBuilder.construct(SifaBuilder.java:96) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.SifaRunner.(SifaRunner.java:98) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleSifa.construct(IpTcStrategyModuleSifa.java:68) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getOrConstruct(IpTcStrategyModuleBase.java:101) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getInterpolantComputationStatus(IpTcStrategyModuleBase.java:77) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.tryExecuteInterpolantGenerator(AutomatonFreeRefinementEngine.java:267) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.generateProof(AutomatonFreeRefinementEngine.java:148) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.executeStrategy(AutomatonFreeRefinementEngine.java:137) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.(AutomatonFreeRefinementEngine.java:85) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.TraceAbstractionRefinementEngine.(TraceAbstractionRefinementEngine.java:82) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.BasicCegarLoop.isCounterexampleFeasible(BasicCegarLoop.java:337) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterate(AbstractCegarLoop.java:431) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.startCegar(AbstractCegarLoop.java:366) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.runCegar(AbstractCegarLoop.java:348) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.executeCegarLoop(TraceAbstractionStarter.java:415) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseProgram(TraceAbstractionStarter.java:302) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseSequentialProgram(TraceAbstractionStarter.java:262) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.runCegarLoops(TraceAbstractionStarter.java:175) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.(TraceAbstractionStarter.java:154) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver.finish(TraceAbstractionObserver.java:124) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runObserver(PluginConnector.java:167) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runTool(PluginConnector.java:150) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.run(PluginConnector.java:127) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.executePluginConnector(ToolchainWalker.java:233) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.processPlugin(ToolchainWalker.java:227) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walkUnprotected(ToolchainWalker.java:144) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walk(ToolchainWalker.java:106) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainManager$Toolchain.processToolchain(ToolchainManager.java:319) at de.uni_freiburg.informatik.ultimate.core.coreplugin.toolchain.DefaultToolchainJob.run(DefaultToolchainJob.java:145) at org.eclipse.core.internal.jobs.Worker.run(Worker.java:63) [2023-11-19 04:11:47,529 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-19 04:11:47,529 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [28, 31] total 51 [2023-11-19 04:11:47,530 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [579091204] [2023-11-19 04:11:47,530 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-19 04:11:47,530 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 51 states [2023-11-19 04:11:47,531 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 04:11:47,532 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 51 interpolants. [2023-11-19 04:11:47,535 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=250, Invalid=4040, Unknown=0, NotChecked=0, Total=4290 [2023-11-19 04:11:47,535 INFO L87 Difference]: Start difference. First operand 102 states and 144 transitions. Second operand has 51 states, 39 states have (on average 1.4102564102564104) internal successors, (55), 35 states have internal predecessors, (55), 15 states have call successors, (17), 6 states have call predecessors, (17), 9 states have return successors, (14), 13 states have call predecessors, (14), 11 states have call successors, (14) [2023-11-19 04:11:50,863 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 04:11:50,863 INFO L93 Difference]: Finished difference Result 127 states and 181 transitions. [2023-11-19 04:11:50,864 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 34 states. [2023-11-19 04:11:50,864 INFO L78 Accepts]: Start accepts. Automaton has has 51 states, 39 states have (on average 1.4102564102564104) internal successors, (55), 35 states have internal predecessors, (55), 15 states have call successors, (17), 6 states have call predecessors, (17), 9 states have return successors, (14), 13 states have call predecessors, (14), 11 states have call successors, (14) Word has length 72 [2023-11-19 04:11:50,865 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 04:11:50,867 INFO L225 Difference]: With dead ends: 127 [2023-11-19 04:11:50,867 INFO L226 Difference]: Without dead ends: 125