./Ultimate.py --spec ../../sv-benchmarks/c/properties/no-overflow.prp --file ../../sv-benchmarks/c/recursive/recHanoi02-2.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for overflows 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_e2e5a0a7-3dc8-432e-8c1f-0b0cd0b6ffc5/bin/utaipan-verify-t7M7D8N6sZ/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e2e5a0a7-3dc8-432e-8c1f-0b0cd0b6ffc5/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_e2e5a0a7-3dc8-432e-8c1f-0b0cd0b6ffc5/bin/utaipan-verify-t7M7D8N6sZ/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e2e5a0a7-3dc8-432e-8c1f-0b0cd0b6ffc5/bin/utaipan-verify-t7M7D8N6sZ/config/TaipanReach.xml -i ../../sv-benchmarks/c/recursive/recHanoi02-2.c -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e2e5a0a7-3dc8-432e-8c1f-0b0cd0b6ffc5/bin/utaipan-verify-t7M7D8N6sZ/config/svcomp-Overflow-32bit-Taipan_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e2e5a0a7-3dc8-432e-8c1f-0b0cd0b6ffc5/bin/utaipan-verify-t7M7D8N6sZ --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(G ! overflow) ) --witnessprinter.graph.data.producer Taipan --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash d379c583eb269678169316efe01a55df7fa26acebe2991472725b0afcb2879ab --- Real Ultimate output --- This is Ultimate 0.2.3-dev-9bd2c7f [2023-11-19 05:04:07,431 INFO L188 SettingsManager]: Resetting all preferences to default values... [2023-11-19 05:04:07,517 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e2e5a0a7-3dc8-432e-8c1f-0b0cd0b6ffc5/bin/utaipan-verify-t7M7D8N6sZ/config/svcomp-Overflow-32bit-Taipan_Default.epf [2023-11-19 05:04:07,524 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2023-11-19 05:04:07,525 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2023-11-19 05:04:07,559 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2023-11-19 05:04:07,560 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2023-11-19 05:04:07,561 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2023-11-19 05:04:07,562 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2023-11-19 05:04:07,562 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2023-11-19 05:04:07,563 INFO L153 SettingsManager]: * User list type=DISABLED [2023-11-19 05:04:07,564 INFO L151 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2023-11-19 05:04:07,564 INFO L153 SettingsManager]: * Explicit value domain=true [2023-11-19 05:04:07,565 INFO L153 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2023-11-19 05:04:07,566 INFO L153 SettingsManager]: * Octagon Domain=false [2023-11-19 05:04:07,566 INFO L153 SettingsManager]: * Abstract domain=CompoundDomain [2023-11-19 05:04:07,567 INFO L153 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2023-11-19 05:04:07,568 INFO L153 SettingsManager]: * Use the RCFG-of-the-future interface=true [2023-11-19 05:04:07,568 INFO L153 SettingsManager]: * Interval Domain=false [2023-11-19 05:04:07,569 INFO L151 SettingsManager]: Preferences of Sifa differ from their defaults: [2023-11-19 05:04:07,570 INFO L153 SettingsManager]: * Call Summarizer=TopInputCallSummarizer [2023-11-19 05:04:07,571 INFO L153 SettingsManager]: * Simplification Technique=POLY_PAC [2023-11-19 05:04:07,572 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2023-11-19 05:04:07,573 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2023-11-19 05:04:07,573 INFO L153 SettingsManager]: * sizeof long=4 [2023-11-19 05:04:07,574 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2023-11-19 05:04:07,575 INFO L153 SettingsManager]: * sizeof POINTER=4 [2023-11-19 05:04:07,575 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2023-11-19 05:04:07,576 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2023-11-19 05:04:07,577 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2023-11-19 05:04:07,577 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2023-11-19 05:04:07,578 INFO L153 SettingsManager]: * Check absence of signed integer overflows=true [2023-11-19 05:04:07,578 INFO L153 SettingsManager]: * Check unreachability of reach_error function=false [2023-11-19 05:04:07,579 INFO L153 SettingsManager]: * sizeof long double=12 [2023-11-19 05:04:07,579 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2023-11-19 05:04:07,580 INFO L153 SettingsManager]: * Use constant arrays=true [2023-11-19 05:04:07,580 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2023-11-19 05:04:07,581 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2023-11-19 05:04:07,599 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-11-19 05:04:07,599 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2023-11-19 05:04:07,599 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2023-11-19 05:04:07,600 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2023-11-19 05:04:07,600 INFO L153 SettingsManager]: * Trace refinement strategy=SIFA_TAIPAN [2023-11-19 05:04:07,600 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2023-11-19 05:04:07,601 INFO L153 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2023-11-19 05:04:07,601 INFO L153 SettingsManager]: * Trace refinement exception blacklist=NONE [2023-11-19 05:04:07,603 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2023-11-19 05:04:07,603 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_e2e5a0a7-3dc8-432e-8c1f-0b0cd0b6ffc5/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_e2e5a0a7-3dc8-432e-8c1f-0b0cd0b6ffc5/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 ! overflow) ) 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 -> d379c583eb269678169316efe01a55df7fa26acebe2991472725b0afcb2879ab [2023-11-19 05:04:08,046 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2023-11-19 05:04:08,082 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2023-11-19 05:04:08,085 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2023-11-19 05:04:08,088 INFO L270 PluginConnector]: Initializing CDTParser... [2023-11-19 05:04:08,089 INFO L274 PluginConnector]: CDTParser initialized [2023-11-19 05:04:08,090 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e2e5a0a7-3dc8-432e-8c1f-0b0cd0b6ffc5/bin/utaipan-verify-t7M7D8N6sZ/../../sv-benchmarks/c/recursive/recHanoi02-2.c [2023-11-19 05:04:11,391 INFO L533 CDTParser]: Created temporary CDT project at NULL [2023-11-19 05:04:11,645 INFO L384 CDTParser]: Found 1 translation units. [2023-11-19 05:04:11,646 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e2e5a0a7-3dc8-432e-8c1f-0b0cd0b6ffc5/sv-benchmarks/c/recursive/recHanoi02-2.c [2023-11-19 05:04:11,656 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e2e5a0a7-3dc8-432e-8c1f-0b0cd0b6ffc5/bin/utaipan-verify-t7M7D8N6sZ/data/ed66f7858/5581faa4d0a7435fbe805f53166d3ddc/FLAG0d15c4afd [2023-11-19 05:04:11,698 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e2e5a0a7-3dc8-432e-8c1f-0b0cd0b6ffc5/bin/utaipan-verify-t7M7D8N6sZ/data/ed66f7858/5581faa4d0a7435fbe805f53166d3ddc [2023-11-19 05:04:11,701 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2023-11-19 05:04:11,702 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2023-11-19 05:04:11,704 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2023-11-19 05:04:11,704 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2023-11-19 05:04:11,710 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2023-11-19 05:04:11,711 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 19.11 05:04:11" (1/1) ... [2023-11-19 05:04:11,712 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@2ceb30d0 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 05:04:11, skipping insertion in model container [2023-11-19 05:04:11,712 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 19.11 05:04:11" (1/1) ... [2023-11-19 05:04:11,735 INFO L177 MainTranslator]: Built tables and reachable declarations [2023-11-19 05:04:11,920 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-19 05:04:11,933 INFO L202 MainTranslator]: Completed pre-run [2023-11-19 05:04:11,952 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-19 05:04:11,967 INFO L206 MainTranslator]: Completed translation [2023-11-19 05:04:11,968 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 05:04:11 WrapperNode [2023-11-19 05:04:11,968 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2023-11-19 05:04:11,970 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2023-11-19 05:04:11,970 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2023-11-19 05:04:11,970 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2023-11-19 05:04:11,980 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 05:04:11" (1/1) ... [2023-11-19 05:04:11,987 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 05:04:11" (1/1) ... [2023-11-19 05:04:12,007 INFO L138 Inliner]: procedures = 13, calls = 10, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 27 [2023-11-19 05:04:12,008 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2023-11-19 05:04:12,009 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2023-11-19 05:04:12,009 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2023-11-19 05:04:12,009 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2023-11-19 05:04:12,020 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 05:04:11" (1/1) ... [2023-11-19 05:04:12,020 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 05:04:11" (1/1) ... [2023-11-19 05:04:12,022 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 05:04:11" (1/1) ... [2023-11-19 05:04:12,022 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 05:04:11" (1/1) ... [2023-11-19 05:04:12,026 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 05:04:11" (1/1) ... [2023-11-19 05:04:12,028 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 05:04:11" (1/1) ... [2023-11-19 05:04:12,029 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 05:04:11" (1/1) ... [2023-11-19 05:04:12,030 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 05:04:11" (1/1) ... [2023-11-19 05:04:12,032 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2023-11-19 05:04:12,033 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2023-11-19 05:04:12,033 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2023-11-19 05:04:12,033 INFO L274 PluginConnector]: RCFGBuilder initialized [2023-11-19 05:04:12,035 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 05:04:11" (1/1) ... [2023-11-19 05:04:12,042 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-11-19 05:04:12,057 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e2e5a0a7-3dc8-432e-8c1f-0b0cd0b6ffc5/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 05:04:12,071 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e2e5a0a7-3dc8-432e-8c1f-0b0cd0b6ffc5/bin/utaipan-verify-t7M7D8N6sZ/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2023-11-19 05:04:12,078 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e2e5a0a7-3dc8-432e-8c1f-0b0cd0b6ffc5/bin/utaipan-verify-t7M7D8N6sZ/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2023-11-19 05:04:12,114 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2023-11-19 05:04:12,114 INFO L130 BoogieDeclarations]: Found specification of procedure hanoi [2023-11-19 05:04:12,115 INFO L138 BoogieDeclarations]: Found implementation of procedure hanoi [2023-11-19 05:04:12,115 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2023-11-19 05:04:12,115 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2023-11-19 05:04:12,115 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2023-11-19 05:04:12,185 INFO L236 CfgBuilder]: Building ICFG [2023-11-19 05:04:12,188 INFO L262 CfgBuilder]: Building CFG for each procedure with an implementation [2023-11-19 05:04:12,403 INFO L277 CfgBuilder]: Performing block encoding [2023-11-19 05:04:12,450 INFO L297 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2023-11-19 05:04:12,456 INFO L302 CfgBuilder]: Removed 0 assume(true) statements. [2023-11-19 05:04:12,461 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 19.11 05:04:12 BoogieIcfgContainer [2023-11-19 05:04:12,461 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2023-11-19 05:04:12,464 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2023-11-19 05:04:12,464 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2023-11-19 05:04:12,468 INFO L274 PluginConnector]: TraceAbstraction initialized [2023-11-19 05:04:12,468 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 19.11 05:04:11" (1/3) ... [2023-11-19 05:04:12,469 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@37ee20ce and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 19.11 05:04:12, skipping insertion in model container [2023-11-19 05:04:12,470 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 05:04:11" (2/3) ... [2023-11-19 05:04:12,470 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@37ee20ce and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 19.11 05:04:12, skipping insertion in model container [2023-11-19 05:04:12,470 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 19.11 05:04:12" (3/3) ... [2023-11-19 05:04:12,472 INFO L112 eAbstractionObserver]: Analyzing ICFG recHanoi02-2.c [2023-11-19 05:04:12,493 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2023-11-19 05:04:12,493 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 6 error locations. [2023-11-19 05:04:12,555 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-11-19 05:04:12,561 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;@282b510, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2023-11-19 05:04:12,561 INFO L358 AbstractCegarLoop]: Starting to check reachability of 6 error locations. [2023-11-19 05:04:12,565 INFO L276 IsEmpty]: Start isEmpty. Operand has 24 states, 14 states have (on average 1.5714285714285714) internal successors, (22), 20 states have internal predecessors, (22), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2023-11-19 05:04:12,575 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 7 [2023-11-19 05:04:12,576 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 05:04:12,577 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1] [2023-11-19 05:04:12,578 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting hanoiErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [hanoiErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, hanoiErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, hanoiErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2023-11-19 05:04:12,586 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 05:04:12,587 INFO L85 PathProgramCache]: Analyzing trace with hash -2064276669, now seen corresponding path program 1 times [2023-11-19 05:04:12,599 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 05:04:12,600 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1941571857] [2023-11-19 05:04:12,600 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 05:04:12,601 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 05:04:12,746 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 05:04:12,963 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-19 05:04:12,964 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 05:04:12,964 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1941571857] [2023-11-19 05:04:12,965 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1941571857] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-19 05:04:12,965 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-19 05:04:12,966 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2023-11-19 05:04:12,968 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1523105812] [2023-11-19 05:04:12,968 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-19 05:04:12,978 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-11-19 05:04:12,978 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 05:04:13,018 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-11-19 05:04:13,020 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2023-11-19 05:04:13,024 INFO L87 Difference]: Start difference. First operand has 24 states, 14 states have (on average 1.5714285714285714) internal successors, (22), 20 states have internal predecessors, (22), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Second operand has 5 states, 3 states have (on average 1.6666666666666667) internal successors, (5), 4 states have internal predecessors, (5), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-19 05:04:13,233 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 05:04:13,233 INFO L93 Difference]: Finished difference Result 45 states and 49 transitions. [2023-11-19 05:04:13,235 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-11-19 05:04:13,237 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 3 states have (on average 1.6666666666666667) internal successors, (5), 4 states have internal predecessors, (5), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 6 [2023-11-19 05:04:13,238 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 05:04:13,248 INFO L225 Difference]: With dead ends: 45 [2023-11-19 05:04:13,249 INFO L226 Difference]: Without dead ends: 38 [2023-11-19 05:04:13,253 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2023-11-19 05:04:13,262 INFO L413 NwaCegarLoop]: 16 mSDtfsCounter, 32 mSDsluCounter, 46 mSDsCounter, 0 mSdLazyCounter, 40 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 33 SdHoareTripleChecker+Valid, 62 SdHoareTripleChecker+Invalid, 46 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 40 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-19 05:04:13,263 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [33 Valid, 62 Invalid, 46 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 40 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-19 05:04:13,285 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 38 states. [2023-11-19 05:04:13,315 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 38 to 31. [2023-11-19 05:04:13,317 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 31 states, 21 states have (on average 1.5238095238095237) internal successors, (32), 26 states have internal predecessors, (32), 3 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2023-11-19 05:04:13,321 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 31 states to 31 states and 37 transitions. [2023-11-19 05:04:13,323 INFO L78 Accepts]: Start accepts. Automaton has 31 states and 37 transitions. Word has length 6 [2023-11-19 05:04:13,323 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 05:04:13,323 INFO L495 AbstractCegarLoop]: Abstraction has 31 states and 37 transitions. [2023-11-19 05:04:13,324 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 3 states have (on average 1.6666666666666667) internal successors, (5), 4 states have internal predecessors, (5), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-19 05:04:13,324 INFO L276 IsEmpty]: Start isEmpty. Operand 31 states and 37 transitions. [2023-11-19 05:04:13,324 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 8 [2023-11-19 05:04:13,325 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 05:04:13,325 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2023-11-19 05:04:13,325 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2023-11-19 05:04:13,326 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting hanoiErr1ASSERT_VIOLATIONINTEGER_OVERFLOW === [hanoiErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, hanoiErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, hanoiErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2023-11-19 05:04:13,327 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 05:04:13,328 INFO L85 PathProgramCache]: Analyzing trace with hash 431932739, now seen corresponding path program 1 times [2023-11-19 05:04:13,328 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 05:04:13,328 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1141286305] [2023-11-19 05:04:13,328 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 05:04:13,329 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 05:04:13,353 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 05:04:13,473 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-19 05:04:13,474 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 05:04:13,475 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1141286305] [2023-11-19 05:04:13,476 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1141286305] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-19 05:04:13,476 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-19 05:04:13,476 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2023-11-19 05:04:13,477 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1861955779] [2023-11-19 05:04:13,477 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-19 05:04:13,479 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-11-19 05:04:13,480 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 05:04:13,481 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-11-19 05:04:13,482 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2023-11-19 05:04:13,483 INFO L87 Difference]: Start difference. First operand 31 states and 37 transitions. Second operand has 5 states, 3 states have (on average 2.0) internal successors, (6), 4 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-19 05:04:13,554 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 05:04:13,554 INFO L93 Difference]: Finished difference Result 31 states and 37 transitions. [2023-11-19 05:04:13,557 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2023-11-19 05:04:13,557 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 3 states have (on average 2.0) internal successors, (6), 4 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 7 [2023-11-19 05:04:13,558 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 05:04:13,561 INFO L225 Difference]: With dead ends: 31 [2023-11-19 05:04:13,562 INFO L226 Difference]: Without dead ends: 30 [2023-11-19 05:04:13,566 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2023-11-19 05:04:13,568 INFO L413 NwaCegarLoop]: 13 mSDtfsCounter, 29 mSDsluCounter, 14 mSDsCounter, 0 mSdLazyCounter, 20 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 29 SdHoareTripleChecker+Valid, 27 SdHoareTripleChecker+Invalid, 23 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 20 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-11-19 05:04:13,569 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [29 Valid, 27 Invalid, 23 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 20 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-11-19 05:04:13,570 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 30 states. [2023-11-19 05:04:13,576 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 30 to 30. [2023-11-19 05:04:13,580 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 30 states, 21 states have (on average 1.4285714285714286) internal successors, (30), 25 states have internal predecessors, (30), 3 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2023-11-19 05:04:13,588 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 30 states to 30 states and 35 transitions. [2023-11-19 05:04:13,589 INFO L78 Accepts]: Start accepts. Automaton has 30 states and 35 transitions. Word has length 7 [2023-11-19 05:04:13,589 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 05:04:13,589 INFO L495 AbstractCegarLoop]: Abstraction has 30 states and 35 transitions. [2023-11-19 05:04:13,590 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 3 states have (on average 2.0) internal successors, (6), 4 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-19 05:04:13,590 INFO L276 IsEmpty]: Start isEmpty. Operand 30 states and 35 transitions. [2023-11-19 05:04:13,590 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2023-11-19 05:04:13,590 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 05:04:13,591 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1] [2023-11-19 05:04:13,591 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2023-11-19 05:04:13,591 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting hanoiErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [hanoiErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, hanoiErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, hanoiErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2023-11-19 05:04:13,592 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 05:04:13,592 INFO L85 PathProgramCache]: Analyzing trace with hash -425354405, now seen corresponding path program 1 times [2023-11-19 05:04:13,592 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 05:04:13,592 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [832396915] [2023-11-19 05:04:13,593 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 05:04:13,593 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 05:04:13,627 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 05:04:13,786 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-19 05:04:13,786 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 05:04:13,786 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [832396915] [2023-11-19 05:04:13,787 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [832396915] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-19 05:04:13,787 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [457816477] [2023-11-19 05:04:13,787 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 05:04:13,788 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 05:04:13,788 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e2e5a0a7-3dc8-432e-8c1f-0b0cd0b6ffc5/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 05:04:13,791 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e2e5a0a7-3dc8-432e-8c1f-0b0cd0b6ffc5/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 05:04:13,823 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e2e5a0a7-3dc8-432e-8c1f-0b0cd0b6ffc5/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2023-11-19 05:04:13,890 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 05:04:13,893 INFO L262 TraceCheckSpWp]: Trace formula consists of 42 conjuncts, 6 conjunts are in the unsatisfiable core [2023-11-19 05:04:13,899 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-19 05:04:13,993 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-19 05:04:13,994 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-19 05:04:14,118 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-19 05:04:14,119 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [457816477] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-19 05:04:14,119 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [571936417] [2023-11-19 05:04:14,155 INFO L159 IcfgInterpreter]: Started Sifa with 9 locations of interest [2023-11-19 05:04:14,156 INFO L166 IcfgInterpreter]: Building call graph [2023-11-19 05:04:14,164 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 05:04:14,171 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-19 05:04:14,171 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6, 6] total 11 [2023-11-19 05:04:14,173 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2020644511] [2023-11-19 05:04:14,173 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-19 05:04:14,176 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2023-11-19 05:04:14,177 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 05:04:14,179 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2023-11-19 05:04:14,180 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=34, Invalid=98, Unknown=0, NotChecked=0, Total=132 [2023-11-19 05:04:14,186 INFO L87 Difference]: Start difference. First operand 30 states and 35 transitions. Second operand has 12 states, 9 states have (on average 1.8888888888888888) internal successors, (17), 8 states have internal predecessors, (17), 4 states have call successors, (4), 4 states have call predecessors, (4), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-19 05:04:14,485 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 05:04:14,485 INFO L93 Difference]: Finished difference Result 91 states and 98 transitions. [2023-11-19 05:04:14,485 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2023-11-19 05:04:14,486 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 9 states have (on average 1.8888888888888888) internal successors, (17), 8 states have internal predecessors, (17), 4 states have call successors, (4), 4 states have call predecessors, (4), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 11 [2023-11-19 05:04:14,486 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 05:04:14,488 INFO L225 Difference]: With dead ends: 91 [2023-11-19 05:04:14,488 INFO L226 Difference]: Without dead ends: 90 [2023-11-19 05:04:14,489 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 33 GetRequests, 16 SyntacticMatches, 0 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 39 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=104, Invalid=238, Unknown=0, NotChecked=0, Total=342 [2023-11-19 05:04:14,491 INFO L413 NwaCegarLoop]: 14 mSDtfsCounter, 157 mSDsluCounter, 108 mSDsCounter, 0 mSdLazyCounter, 73 mSolverCounterSat, 30 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 159 SdHoareTripleChecker+Valid, 122 SdHoareTripleChecker+Invalid, 103 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 30 IncrementalHoareTripleChecker+Valid, 73 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-19 05:04:14,491 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [159 Valid, 122 Invalid, 103 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [30 Valid, 73 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-19 05:04:14,493 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 90 states. [2023-11-19 05:04:14,506 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 90 to 66. [2023-11-19 05:04:14,507 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 66 states, 51 states have (on average 1.4705882352941178) internal successors, (75), 55 states have internal predecessors, (75), 6 states have call successors, (6), 5 states have call predecessors, (6), 4 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2023-11-19 05:04:14,509 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 66 states to 66 states and 86 transitions. [2023-11-19 05:04:14,510 INFO L78 Accepts]: Start accepts. Automaton has 66 states and 86 transitions. Word has length 11 [2023-11-19 05:04:14,510 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 05:04:14,510 INFO L495 AbstractCegarLoop]: Abstraction has 66 states and 86 transitions. [2023-11-19 05:04:14,511 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 9 states have (on average 1.8888888888888888) internal successors, (17), 8 states have internal predecessors, (17), 4 states have call successors, (4), 4 states have call predecessors, (4), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-19 05:04:14,511 INFO L276 IsEmpty]: Start isEmpty. Operand 66 states and 86 transitions. [2023-11-19 05:04:14,511 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2023-11-19 05:04:14,512 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 05:04:14,512 INFO L195 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-19 05:04:14,536 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e2e5a0a7-3dc8-432e-8c1f-0b0cd0b6ffc5/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2023-11-19 05:04:14,728 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e2e5a0a7-3dc8-432e-8c1f-0b0cd0b6ffc5/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 05:04:14,729 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting hanoiErr2ASSERT_VIOLATIONINTEGER_OVERFLOW === [hanoiErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, hanoiErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, hanoiErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2023-11-19 05:04:14,730 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 05:04:14,730 INFO L85 PathProgramCache]: Analyzing trace with hash -1580020958, now seen corresponding path program 1 times [2023-11-19 05:04:14,730 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 05:04:14,730 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [365871240] [2023-11-19 05:04:14,731 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 05:04:14,731 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 05:04:14,754 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 05:04:14,844 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2023-11-19 05:04:14,845 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 05:04:14,845 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [365871240] [2023-11-19 05:04:14,845 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [365871240] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-19 05:04:14,845 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-19 05:04:14,846 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2023-11-19 05:04:14,846 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1259320220] [2023-11-19 05:04:14,846 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-19 05:04:14,847 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2023-11-19 05:04:14,847 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 05:04:14,848 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2023-11-19 05:04:14,848 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2023-11-19 05:04:14,849 INFO L87 Difference]: Start difference. First operand 66 states and 86 transitions. Second operand has 4 states, 3 states have (on average 3.3333333333333335) internal successors, (10), 4 states have internal predecessors, (10), 1 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2023-11-19 05:04:14,884 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 05:04:14,884 INFO L93 Difference]: Finished difference Result 103 states and 139 transitions. [2023-11-19 05:04:14,884 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2023-11-19 05:04:14,885 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 3 states have (on average 3.3333333333333335) internal successors, (10), 4 states have internal predecessors, (10), 1 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 14 [2023-11-19 05:04:14,885 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 05:04:14,887 INFO L225 Difference]: With dead ends: 103 [2023-11-19 05:04:14,887 INFO L226 Difference]: Without dead ends: 92 [2023-11-19 05:04:14,888 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2023-11-19 05:04:14,889 INFO L413 NwaCegarLoop]: 15 mSDtfsCounter, 3 mSDsluCounter, 25 mSDsCounter, 0 mSdLazyCounter, 22 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3 SdHoareTripleChecker+Valid, 40 SdHoareTripleChecker+Invalid, 25 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 22 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-11-19 05:04:14,892 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [3 Valid, 40 Invalid, 25 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 22 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-11-19 05:04:14,894 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 92 states. [2023-11-19 05:04:14,907 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 92 to 92. [2023-11-19 05:04:14,908 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 92 states, 74 states have (on average 1.3108108108108107) internal successors, (97), 77 states have internal predecessors, (97), 6 states have call successors, (6), 5 states have call predecessors, (6), 7 states have return successors, (9), 9 states have call predecessors, (9), 5 states have call successors, (9) [2023-11-19 05:04:14,923 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 92 states to 92 states and 112 transitions. [2023-11-19 05:04:14,923 INFO L78 Accepts]: Start accepts. Automaton has 92 states and 112 transitions. Word has length 14 [2023-11-19 05:04:14,923 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 05:04:14,924 INFO L495 AbstractCegarLoop]: Abstraction has 92 states and 112 transitions. [2023-11-19 05:04:14,924 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 3 states have (on average 3.3333333333333335) internal successors, (10), 4 states have internal predecessors, (10), 1 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2023-11-19 05:04:14,925 INFO L276 IsEmpty]: Start isEmpty. Operand 92 states and 112 transitions. [2023-11-19 05:04:14,927 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2023-11-19 05:04:14,927 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 05:04:14,927 INFO L195 NwaCegarLoop]: trace histogram [5, 5, 4, 4, 4, 1, 1, 1, 1] [2023-11-19 05:04:14,928 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2023-11-19 05:04:14,928 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting hanoiErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [hanoiErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, hanoiErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, hanoiErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2023-11-19 05:04:14,928 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 05:04:14,929 INFO L85 PathProgramCache]: Analyzing trace with hash 163414339, now seen corresponding path program 2 times [2023-11-19 05:04:14,929 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 05:04:14,930 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1093641328] [2023-11-19 05:04:14,931 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 05:04:14,931 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 05:04:14,962 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 05:04:15,254 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 0 proven. 42 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-19 05:04:15,254 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 05:04:15,255 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1093641328] [2023-11-19 05:04:15,255 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1093641328] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-19 05:04:15,255 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1713582162] [2023-11-19 05:04:15,255 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-11-19 05:04:15,255 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 05:04:15,255 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e2e5a0a7-3dc8-432e-8c1f-0b0cd0b6ffc5/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 05:04:15,256 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e2e5a0a7-3dc8-432e-8c1f-0b0cd0b6ffc5/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 05:04:15,262 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e2e5a0a7-3dc8-432e-8c1f-0b0cd0b6ffc5/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2023-11-19 05:04:15,310 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2023-11-19 05:04:15,311 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-19 05:04:15,312 INFO L262 TraceCheckSpWp]: Trace formula consists of 69 conjuncts, 12 conjunts are in the unsatisfiable core [2023-11-19 05:04:15,314 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-19 05:04:15,430 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 0 proven. 42 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-19 05:04:15,430 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-19 05:04:15,689 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 0 proven. 42 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-19 05:04:15,689 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1713582162] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-19 05:04:15,689 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1822865109] [2023-11-19 05:04:15,693 INFO L159 IcfgInterpreter]: Started Sifa with 9 locations of interest [2023-11-19 05:04:15,693 INFO L166 IcfgInterpreter]: Building call graph [2023-11-19 05:04:15,694 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 05:04:15,694 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-19 05:04:15,694 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12, 12] total 23 [2023-11-19 05:04:15,695 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [138393982] [2023-11-19 05:04:15,695 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-19 05:04:15,695 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 24 states [2023-11-19 05:04:15,696 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 05:04:15,698 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2023-11-19 05:04:15,699 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=136, Invalid=416, Unknown=0, NotChecked=0, Total=552 [2023-11-19 05:04:15,701 INFO L87 Difference]: Start difference. First operand 92 states and 112 transitions. Second operand has 24 states, 21 states have (on average 1.9523809523809523) internal successors, (41), 14 states have internal predecessors, (41), 10 states have call successors, (10), 10 states have call predecessors, (10), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-19 05:04:16,299 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 05:04:16,300 INFO L93 Difference]: Finished difference Result 247 states and 262 transitions. [2023-11-19 05:04:16,300 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 33 states. [2023-11-19 05:04:16,301 INFO L78 Accepts]: Start accepts. Automaton has has 24 states, 21 states have (on average 1.9523809523809523) internal successors, (41), 14 states have internal predecessors, (41), 10 states have call successors, (10), 10 states have call predecessors, (10), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 26 [2023-11-19 05:04:16,301 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 05:04:16,308 INFO L225 Difference]: With dead ends: 247 [2023-11-19 05:04:16,309 INFO L226 Difference]: Without dead ends: 246 [2023-11-19 05:04:16,310 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 80 GetRequests, 40 SyntacticMatches, 0 SemanticMatches, 40 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 314 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=515, Invalid=1207, Unknown=0, NotChecked=0, Total=1722 [2023-11-19 05:04:16,312 INFO L413 NwaCegarLoop]: 19 mSDtfsCounter, 467 mSDsluCounter, 247 mSDsCounter, 0 mSdLazyCounter, 158 mSolverCounterSat, 86 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 469 SdHoareTripleChecker+Valid, 266 SdHoareTripleChecker+Invalid, 244 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 86 IncrementalHoareTripleChecker+Valid, 158 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-11-19 05:04:16,315 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [469 Valid, 266 Invalid, 244 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [86 Valid, 158 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-11-19 05:04:16,322 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 246 states. [2023-11-19 05:04:16,366 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 246 to 206. [2023-11-19 05:04:16,367 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 206 states, 170 states have (on average 1.311764705882353) internal successors, (223), 173 states have internal predecessors, (223), 12 states have call successors, (12), 11 states have call predecessors, (12), 19 states have return successors, (21), 21 states have call predecessors, (21), 11 states have call successors, (21) [2023-11-19 05:04:16,369 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 206 states to 206 states and 256 transitions. [2023-11-19 05:04:16,369 INFO L78 Accepts]: Start accepts. Automaton has 206 states and 256 transitions. Word has length 26 [2023-11-19 05:04:16,370 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 05:04:16,370 INFO L495 AbstractCegarLoop]: Abstraction has 206 states and 256 transitions. [2023-11-19 05:04:16,370 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 24 states, 21 states have (on average 1.9523809523809523) internal successors, (41), 14 states have internal predecessors, (41), 10 states have call successors, (10), 10 states have call predecessors, (10), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-19 05:04:16,370 INFO L276 IsEmpty]: Start isEmpty. Operand 206 states and 256 transitions. [2023-11-19 05:04:16,371 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2023-11-19 05:04:16,371 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 05:04:16,371 INFO L195 NwaCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-19 05:04:16,400 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e2e5a0a7-3dc8-432e-8c1f-0b0cd0b6ffc5/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2023-11-19 05:04:16,593 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e2e5a0a7-3dc8-432e-8c1f-0b0cd0b6ffc5/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 05:04:16,593 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting hanoiErr2ASSERT_VIOLATIONINTEGER_OVERFLOW === [hanoiErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, hanoiErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, hanoiErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2023-11-19 05:04:16,594 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 05:04:16,594 INFO L85 PathProgramCache]: Analyzing trace with hash 1883603118, now seen corresponding path program 1 times [2023-11-19 05:04:16,594 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 05:04:16,594 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [37611765] [2023-11-19 05:04:16,594 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 05:04:16,594 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 05:04:16,613 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 05:04:16,691 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2023-11-19 05:04:16,691 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 05:04:16,691 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [37611765] [2023-11-19 05:04:16,691 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [37611765] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-19 05:04:16,691 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [131314456] [2023-11-19 05:04:16,692 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 05:04:16,692 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 05:04:16,692 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e2e5a0a7-3dc8-432e-8c1f-0b0cd0b6ffc5/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 05:04:16,694 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e2e5a0a7-3dc8-432e-8c1f-0b0cd0b6ffc5/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 05:04:16,717 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e2e5a0a7-3dc8-432e-8c1f-0b0cd0b6ffc5/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2023-11-19 05:04:16,740 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 05:04:16,741 INFO L262 TraceCheckSpWp]: Trace formula consists of 70 conjuncts, 5 conjunts are in the unsatisfiable core [2023-11-19 05:04:16,742 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-19 05:04:16,795 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2023-11-19 05:04:16,795 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-11-19 05:04:16,795 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [131314456] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-19 05:04:16,795 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-11-19 05:04:16,796 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [5] total 7 [2023-11-19 05:04:16,796 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1398927482] [2023-11-19 05:04:16,796 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-19 05:04:16,796 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2023-11-19 05:04:16,796 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 05:04:16,797 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2023-11-19 05:04:16,797 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2023-11-19 05:04:16,797 INFO L87 Difference]: Start difference. First operand 206 states and 256 transitions. Second operand has 6 states, 5 states have (on average 3.2) internal successors, (16), 6 states have internal predecessors, (16), 1 states have call successors, (2), 1 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2023-11-19 05:04:16,838 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 05:04:16,839 INFO L93 Difference]: Finished difference Result 206 states and 256 transitions. [2023-11-19 05:04:16,839 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-11-19 05:04:16,839 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 3.2) internal successors, (16), 6 states have internal predecessors, (16), 1 states have call successors, (2), 1 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) Word has length 26 [2023-11-19 05:04:16,840 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 05:04:16,841 INFO L225 Difference]: With dead ends: 206 [2023-11-19 05:04:16,841 INFO L226 Difference]: Without dead ends: 204 [2023-11-19 05:04:16,842 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 30 GetRequests, 24 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2023-11-19 05:04:16,843 INFO L413 NwaCegarLoop]: 13 mSDtfsCounter, 7 mSDsluCounter, 22 mSDsCounter, 0 mSdLazyCounter, 33 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 35 SdHoareTripleChecker+Invalid, 34 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 33 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-11-19 05:04:16,844 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 35 Invalid, 34 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 33 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-11-19 05:04:16,845 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 204 states. [2023-11-19 05:04:16,881 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 204 to 204. [2023-11-19 05:04:16,882 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 204 states, 170 states have (on average 1.1823529411764706) internal successors, (201), 171 states have internal predecessors, (201), 12 states have call successors, (12), 11 states have call predecessors, (12), 19 states have return successors, (21), 21 states have call predecessors, (21), 11 states have call successors, (21) [2023-11-19 05:04:16,883 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 204 states to 204 states and 234 transitions. [2023-11-19 05:04:16,884 INFO L78 Accepts]: Start accepts. Automaton has 204 states and 234 transitions. Word has length 26 [2023-11-19 05:04:16,884 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 05:04:16,884 INFO L495 AbstractCegarLoop]: Abstraction has 204 states and 234 transitions. [2023-11-19 05:04:16,884 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 3.2) internal successors, (16), 6 states have internal predecessors, (16), 1 states have call successors, (2), 1 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2023-11-19 05:04:16,884 INFO L276 IsEmpty]: Start isEmpty. Operand 204 states and 234 transitions. [2023-11-19 05:04:16,885 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2023-11-19 05:04:16,885 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 05:04:16,886 INFO L195 NwaCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-19 05:04:16,913 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e2e5a0a7-3dc8-432e-8c1f-0b0cd0b6ffc5/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2023-11-19 05:04:17,100 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e2e5a0a7-3dc8-432e-8c1f-0b0cd0b6ffc5/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 05:04:17,101 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting hanoiErr3ASSERT_VIOLATIONINTEGER_OVERFLOW === [hanoiErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, hanoiErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, hanoiErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2023-11-19 05:04:17,101 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 05:04:17,102 INFO L85 PathProgramCache]: Analyzing trace with hash -1737845442, now seen corresponding path program 1 times [2023-11-19 05:04:17,102 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 05:04:17,102 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [12205368] [2023-11-19 05:04:17,102 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 05:04:17,102 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 05:04:17,111 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 05:04:17,170 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 0 proven. 5 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2023-11-19 05:04:17,170 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 05:04:17,170 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [12205368] [2023-11-19 05:04:17,171 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [12205368] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-19 05:04:17,171 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1812447763] [2023-11-19 05:04:17,171 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 05:04:17,171 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 05:04:17,171 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e2e5a0a7-3dc8-432e-8c1f-0b0cd0b6ffc5/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 05:04:17,172 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e2e5a0a7-3dc8-432e-8c1f-0b0cd0b6ffc5/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 05:04:17,192 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e2e5a0a7-3dc8-432e-8c1f-0b0cd0b6ffc5/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2023-11-19 05:04:17,227 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 05:04:17,228 INFO L262 TraceCheckSpWp]: Trace formula consists of 71 conjuncts, 5 conjunts are in the unsatisfiable core [2023-11-19 05:04:17,231 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-19 05:04:17,279 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 0 proven. 5 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2023-11-19 05:04:17,280 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-19 05:04:17,449 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 0 proven. 5 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2023-11-19 05:04:17,449 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1812447763] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-19 05:04:17,449 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [241355704] [2023-11-19 05:04:17,453 INFO L159 IcfgInterpreter]: Started Sifa with 16 locations of interest [2023-11-19 05:04:17,453 INFO L166 IcfgInterpreter]: Building call graph [2023-11-19 05:04:17,453 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 05:04:17,454 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-19 05:04:17,454 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5, 5] total 11 [2023-11-19 05:04:17,454 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [312211178] [2023-11-19 05:04:17,454 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-19 05:04:17,455 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2023-11-19 05:04:17,455 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 05:04:17,456 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2023-11-19 05:04:17,457 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=41, Invalid=91, Unknown=0, NotChecked=0, Total=132 [2023-11-19 05:04:17,457 INFO L87 Difference]: Start difference. First operand 204 states and 234 transitions. Second operand has 12 states, 11 states have (on average 3.1818181818181817) internal successors, (35), 12 states have internal predecessors, (35), 1 states have call successors, (2), 1 states have call predecessors, (2), 5 states have return successors, (5), 5 states have call predecessors, (5), 1 states have call successors, (5) [2023-11-19 05:04:17,525 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 05:04:17,525 INFO L93 Difference]: Finished difference Result 408 states and 493 transitions. [2023-11-19 05:04:17,525 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2023-11-19 05:04:17,525 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 11 states have (on average 3.1818181818181817) internal successors, (35), 12 states have internal predecessors, (35), 1 states have call successors, (2), 1 states have call predecessors, (2), 5 states have return successors, (5), 5 states have call predecessors, (5), 1 states have call successors, (5) Word has length 27 [2023-11-19 05:04:17,526 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 05:04:17,532 INFO L225 Difference]: With dead ends: 408 [2023-11-19 05:04:17,532 INFO L226 Difference]: Without dead ends: 343 [2023-11-19 05:04:17,534 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 57 GetRequests, 47 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 30 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=41, Invalid=91, Unknown=0, NotChecked=0, Total=132 [2023-11-19 05:04:17,535 INFO L413 NwaCegarLoop]: 12 mSDtfsCounter, 4 mSDsluCounter, 56 mSDsCounter, 0 mSdLazyCounter, 47 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 68 SdHoareTripleChecker+Invalid, 52 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 47 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-19 05:04:17,536 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 68 Invalid, 52 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 47 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-19 05:04:17,537 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 343 states. [2023-11-19 05:04:17,566 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 343 to 343. [2023-11-19 05:04:17,567 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 343 states, 289 states have (on average 1.0588235294117647) internal successors, (306), 286 states have internal predecessors, (306), 12 states have call successors, (12), 11 states have call predecessors, (12), 40 states have return successors, (45), 45 states have call predecessors, (45), 11 states have call successors, (45) [2023-11-19 05:04:17,570 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 343 states to 343 states and 363 transitions. [2023-11-19 05:04:17,570 INFO L78 Accepts]: Start accepts. Automaton has 343 states and 363 transitions. Word has length 27 [2023-11-19 05:04:17,570 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 05:04:17,571 INFO L495 AbstractCegarLoop]: Abstraction has 343 states and 363 transitions. [2023-11-19 05:04:17,571 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 11 states have (on average 3.1818181818181817) internal successors, (35), 12 states have internal predecessors, (35), 1 states have call successors, (2), 1 states have call predecessors, (2), 5 states have return successors, (5), 5 states have call predecessors, (5), 1 states have call successors, (5) [2023-11-19 05:04:17,571 INFO L276 IsEmpty]: Start isEmpty. Operand 343 states and 363 transitions. [2023-11-19 05:04:17,581 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 57 [2023-11-19 05:04:17,581 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 05:04:17,582 INFO L195 NwaCegarLoop]: trace histogram [11, 11, 10, 10, 10, 1, 1, 1, 1] [2023-11-19 05:04:17,610 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e2e5a0a7-3dc8-432e-8c1f-0b0cd0b6ffc5/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2023-11-19 05:04:17,796 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e2e5a0a7-3dc8-432e-8c1f-0b0cd0b6ffc5/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 05:04:17,797 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting hanoiErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [hanoiErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, hanoiErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, hanoiErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2023-11-19 05:04:17,797 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 05:04:17,797 INFO L85 PathProgramCache]: Analyzing trace with hash 1818144323, now seen corresponding path program 3 times [2023-11-19 05:04:17,797 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 05:04:17,797 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [396431868] [2023-11-19 05:04:17,798 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 05:04:17,798 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 05:04:17,821 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 05:04:18,543 INFO L134 CoverageAnalysis]: Checked inductivity of 255 backedges. 0 proven. 255 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-19 05:04:18,544 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 05:04:18,544 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [396431868] [2023-11-19 05:04:18,544 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [396431868] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-19 05:04:18,544 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1835715875] [2023-11-19 05:04:18,544 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2023-11-19 05:04:18,544 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 05:04:18,544 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e2e5a0a7-3dc8-432e-8c1f-0b0cd0b6ffc5/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 05:04:18,547 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e2e5a0a7-3dc8-432e-8c1f-0b0cd0b6ffc5/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 05:04:18,576 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e2e5a0a7-3dc8-432e-8c1f-0b0cd0b6ffc5/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2023-11-19 05:04:18,619 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2023-11-19 05:04:18,619 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-19 05:04:18,620 INFO L262 TraceCheckSpWp]: Trace formula consists of 123 conjuncts, 24 conjunts are in the unsatisfiable core [2023-11-19 05:04:18,651 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-19 05:04:18,817 INFO L134 CoverageAnalysis]: Checked inductivity of 255 backedges. 0 proven. 255 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-19 05:04:18,817 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-19 05:04:19,635 INFO L134 CoverageAnalysis]: Checked inductivity of 255 backedges. 0 proven. 255 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-19 05:04:19,635 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1835715875] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-19 05:04:19,635 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [888574406] [2023-11-19 05:04:19,638 INFO L159 IcfgInterpreter]: Started Sifa with 9 locations of interest [2023-11-19 05:04:19,638 INFO L166 IcfgInterpreter]: Building call graph [2023-11-19 05:04:19,639 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 05:04:19,640 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-19 05:04:19,640 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [24, 24, 24] total 47 [2023-11-19 05:04:19,641 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1166586832] [2023-11-19 05:04:19,641 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-19 05:04:19,642 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 48 states [2023-11-19 05:04:19,642 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 05:04:19,643 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 48 interpolants. [2023-11-19 05:04:19,645 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=556, Invalid=1700, Unknown=0, NotChecked=0, Total=2256 [2023-11-19 05:04:19,645 INFO L87 Difference]: Start difference. First operand 343 states and 363 transitions. Second operand has 48 states, 45 states have (on average 1.9777777777777779) internal successors, (89), 26 states have internal predecessors, (89), 22 states have call successors, (22), 22 states have call predecessors, (22), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-19 05:04:21,136 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 05:04:21,136 INFO L93 Difference]: Finished difference Result 822 states and 855 transitions. [2023-11-19 05:04:21,137 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 66 states. [2023-11-19 05:04:21,137 INFO L78 Accepts]: Start accepts. Automaton has has 48 states, 45 states have (on average 1.9777777777777779) internal successors, (89), 26 states have internal predecessors, (89), 22 states have call successors, (22), 22 states have call predecessors, (22), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 56 [2023-11-19 05:04:21,140 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 05:04:21,145 INFO L225 Difference]: With dead ends: 822 [2023-11-19 05:04:21,145 INFO L226 Difference]: Without dead ends: 821 [2023-11-19 05:04:21,152 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 173 GetRequests, 88 SyntacticMatches, 0 SemanticMatches, 85 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1598 ImplicationChecksByTransitivity, 1.8s TimeCoverageRelationStatistics Valid=2204, Invalid=5278, Unknown=0, NotChecked=0, Total=7482 [2023-11-19 05:04:21,154 INFO L413 NwaCegarLoop]: 32 mSDtfsCounter, 1012 mSDsluCounter, 415 mSDsCounter, 0 mSdLazyCounter, 308 mSolverCounterSat, 249 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1014 SdHoareTripleChecker+Valid, 447 SdHoareTripleChecker+Invalid, 557 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 249 IncrementalHoareTripleChecker+Valid, 308 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2023-11-19 05:04:21,154 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [1014 Valid, 447 Invalid, 557 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [249 Valid, 308 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2023-11-19 05:04:21,156 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 821 states. [2023-11-19 05:04:21,197 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 821 to 799. [2023-11-19 05:04:21,200 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 799 states, 673 states have (on average 1.0609212481426449) internal successors, (714), 670 states have internal predecessors, (714), 24 states have call successors, (24), 23 states have call predecessors, (24), 100 states have return successors, (105), 105 states have call predecessors, (105), 23 states have call successors, (105) [2023-11-19 05:04:21,206 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 799 states to 799 states and 843 transitions. [2023-11-19 05:04:21,206 INFO L78 Accepts]: Start accepts. Automaton has 799 states and 843 transitions. Word has length 56 [2023-11-19 05:04:21,206 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 05:04:21,206 INFO L495 AbstractCegarLoop]: Abstraction has 799 states and 843 transitions. [2023-11-19 05:04:21,207 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 48 states, 45 states have (on average 1.9777777777777779) internal successors, (89), 26 states have internal predecessors, (89), 22 states have call successors, (22), 22 states have call predecessors, (22), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-19 05:04:21,207 INFO L276 IsEmpty]: Start isEmpty. Operand 799 states and 843 transitions. [2023-11-19 05:04:21,211 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 64 [2023-11-19 05:04:21,211 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 05:04:21,211 INFO L195 NwaCegarLoop]: trace histogram [6, 5, 5, 5, 5, 5, 5, 5, 5, 4, 4, 4, 1, 1, 1, 1, 1] [2023-11-19 05:04:21,236 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e2e5a0a7-3dc8-432e-8c1f-0b0cd0b6ffc5/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2023-11-19 05:04:21,428 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e2e5a0a7-3dc8-432e-8c1f-0b0cd0b6ffc5/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 05:04:21,428 INFO L420 AbstractCegarLoop]: === Iteration 9 === Targeting hanoiErr3ASSERT_VIOLATIONINTEGER_OVERFLOW === [hanoiErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, hanoiErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, hanoiErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2023-11-19 05:04:21,429 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 05:04:21,429 INFO L85 PathProgramCache]: Analyzing trace with hash -1753678774, now seen corresponding path program 2 times [2023-11-19 05:04:21,429 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 05:04:21,429 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1831113199] [2023-11-19 05:04:21,429 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 05:04:21,430 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 05:04:21,459 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 05:04:21,660 INFO L134 CoverageAnalysis]: Checked inductivity of 122 backedges. 0 proven. 62 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2023-11-19 05:04:21,661 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 05:04:21,661 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1831113199] [2023-11-19 05:04:21,661 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1831113199] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-19 05:04:21,661 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2119888945] [2023-11-19 05:04:21,662 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-11-19 05:04:21,662 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 05:04:21,662 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e2e5a0a7-3dc8-432e-8c1f-0b0cd0b6ffc5/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 05:04:21,663 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e2e5a0a7-3dc8-432e-8c1f-0b0cd0b6ffc5/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 05:04:21,684 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e2e5a0a7-3dc8-432e-8c1f-0b0cd0b6ffc5/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2023-11-19 05:04:21,748 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2023-11-19 05:04:21,748 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-19 05:04:21,749 INFO L262 TraceCheckSpWp]: Trace formula consists of 122 conjuncts, 11 conjunts are in the unsatisfiable core [2023-11-19 05:04:21,752 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-19 05:04:21,823 INFO L134 CoverageAnalysis]: Checked inductivity of 122 backedges. 0 proven. 62 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2023-11-19 05:04:21,824 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-19 05:04:22,730 INFO L134 CoverageAnalysis]: Checked inductivity of 122 backedges. 0 proven. 62 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2023-11-19 05:04:22,730 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2119888945] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-19 05:04:22,730 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [399054873] [2023-11-19 05:04:22,733 INFO L159 IcfgInterpreter]: Started Sifa with 16 locations of interest [2023-11-19 05:04:22,734 INFO L166 IcfgInterpreter]: Building call graph [2023-11-19 05:04:22,734 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 05:04:22,736 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-19 05:04:22,736 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11, 11] total 23 [2023-11-19 05:04:22,736 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1282549938] [2023-11-19 05:04:22,737 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-19 05:04:22,737 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 24 states [2023-11-19 05:04:22,738 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 05:04:22,739 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2023-11-19 05:04:22,739 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=155, Invalid=397, Unknown=0, NotChecked=0, Total=552 [2023-11-19 05:04:22,740 INFO L87 Difference]: Start difference. First operand 799 states and 843 transitions. Second operand has 24 states, 23 states have (on average 3.0869565217391304) internal successors, (71), 24 states have internal predecessors, (71), 1 states have call successors, (2), 1 states have call predecessors, (2), 11 states have return successors, (11), 11 states have call predecessors, (11), 1 states have call successors, (11) [2023-11-19 05:04:22,881 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 05:04:22,882 INFO L93 Difference]: Finished difference Result 1742 states and 1923 transitions. [2023-11-19 05:04:22,882 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2023-11-19 05:04:22,882 INFO L78 Accepts]: Start accepts. Automaton has has 24 states, 23 states have (on average 3.0869565217391304) internal successors, (71), 24 states have internal predecessors, (71), 1 states have call successors, (2), 1 states have call predecessors, (2), 11 states have return successors, (11), 11 states have call predecessors, (11), 1 states have call successors, (11) Word has length 63 [2023-11-19 05:04:22,883 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 05:04:22,891 INFO L225 Difference]: With dead ends: 1742 [2023-11-19 05:04:22,891 INFO L226 Difference]: Without dead ends: 1438 [2023-11-19 05:04:22,894 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 135 GetRequests, 113 SyntacticMatches, 0 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 159 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=155, Invalid=397, Unknown=0, NotChecked=0, Total=552 [2023-11-19 05:04:22,895 INFO L413 NwaCegarLoop]: 12 mSDtfsCounter, 4 mSDsluCounter, 71 mSDsCounter, 0 mSdLazyCounter, 91 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 83 SdHoareTripleChecker+Invalid, 93 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 91 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-19 05:04:22,895 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 83 Invalid, 93 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 91 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-19 05:04:22,898 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1438 states. [2023-11-19 05:04:22,946 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1438 to 1438. [2023-11-19 05:04:22,949 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1438 states, 1225 states have (on average 1.0285714285714285) internal successors, (1260), 1216 states have internal predecessors, (1260), 24 states have call successors, (24), 23 states have call predecessors, (24), 187 states have return successors, (198), 198 states have call predecessors, (198), 23 states have call successors, (198) [2023-11-19 05:04:22,959 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1438 states to 1438 states and 1482 transitions. [2023-11-19 05:04:22,959 INFO L78 Accepts]: Start accepts. Automaton has 1438 states and 1482 transitions. Word has length 63 [2023-11-19 05:04:22,960 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 05:04:22,960 INFO L495 AbstractCegarLoop]: Abstraction has 1438 states and 1482 transitions. [2023-11-19 05:04:22,960 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 24 states, 23 states have (on average 3.0869565217391304) internal successors, (71), 24 states have internal predecessors, (71), 1 states have call successors, (2), 1 states have call predecessors, (2), 11 states have return successors, (11), 11 states have call predecessors, (11), 1 states have call successors, (11) [2023-11-19 05:04:22,961 INFO L276 IsEmpty]: Start isEmpty. Operand 1438 states and 1482 transitions. [2023-11-19 05:04:22,963 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 117 [2023-11-19 05:04:22,963 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 05:04:22,964 INFO L195 NwaCegarLoop]: trace histogram [23, 23, 22, 22, 22, 1, 1, 1, 1] [2023-11-19 05:04:22,994 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e2e5a0a7-3dc8-432e-8c1f-0b0cd0b6ffc5/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2023-11-19 05:04:23,184 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,7 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e2e5a0a7-3dc8-432e-8c1f-0b0cd0b6ffc5/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 05:04:23,185 INFO L420 AbstractCegarLoop]: === Iteration 10 === Targeting hanoiErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [hanoiErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, hanoiErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, hanoiErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2023-11-19 05:04:23,185 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 05:04:23,185 INFO L85 PathProgramCache]: Analyzing trace with hash 717932611, now seen corresponding path program 4 times [2023-11-19 05:04:23,185 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 05:04:23,186 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1950208844] [2023-11-19 05:04:23,186 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 05:04:23,186 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 05:04:23,249 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 05:04:25,121 INFO L134 CoverageAnalysis]: Checked inductivity of 1221 backedges. 0 proven. 1221 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-19 05:04:25,121 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 05:04:25,121 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1950208844] [2023-11-19 05:04:25,121 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1950208844] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-19 05:04:25,122 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1522401609] [2023-11-19 05:04:25,122 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2023-11-19 05:04:25,122 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 05:04:25,122 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e2e5a0a7-3dc8-432e-8c1f-0b0cd0b6ffc5/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 05:04:25,124 INFO L229 MonitoredProcess]: Starting monitored process 8 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e2e5a0a7-3dc8-432e-8c1f-0b0cd0b6ffc5/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 05:04:25,160 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e2e5a0a7-3dc8-432e-8c1f-0b0cd0b6ffc5/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2023-11-19 05:04:25,229 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 05:04:25,232 INFO L262 TraceCheckSpWp]: Trace formula consists of 231 conjuncts, 48 conjunts are in the unsatisfiable core [2023-11-19 05:04:25,247 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-19 05:04:25,497 INFO L134 CoverageAnalysis]: Checked inductivity of 1221 backedges. 0 proven. 1221 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-19 05:04:25,497 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-19 05:04:28,258 INFO L134 CoverageAnalysis]: Checked inductivity of 1221 backedges. 0 proven. 1221 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-19 05:04:28,258 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1522401609] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-19 05:04:28,258 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1193381806] [2023-11-19 05:04:28,261 INFO L159 IcfgInterpreter]: Started Sifa with 9 locations of interest [2023-11-19 05:04:28,261 INFO L166 IcfgInterpreter]: Building call graph [2023-11-19 05:04:28,262 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 05:04:28,262 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-19 05:04:28,262 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [48, 48, 48] total 95 [2023-11-19 05:04:28,263 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [697215020] [2023-11-19 05:04:28,263 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-19 05:04:28,264 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 96 states [2023-11-19 05:04:28,264 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 05:04:28,267 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 96 interpolants. [2023-11-19 05:04:28,273 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=2260, Invalid=6860, Unknown=0, NotChecked=0, Total=9120 [2023-11-19 05:04:28,274 INFO L87 Difference]: Start difference. First operand 1438 states and 1482 transitions. Second operand has 96 states, 93 states have (on average 1.989247311827957) internal successors, (185), 50 states have internal predecessors, (185), 46 states have call successors, (46), 46 states have call predecessors, (46), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-19 05:04:33,531 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 05:04:33,531 INFO L93 Difference]: Finished difference Result 3405 states and 3474 transitions. [2023-11-19 05:04:33,532 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 132 states. [2023-11-19 05:04:33,532 INFO L78 Accepts]: Start accepts. Automaton has has 96 states, 93 states have (on average 1.989247311827957) internal successors, (185), 50 states have internal predecessors, (185), 46 states have call successors, (46), 46 states have call predecessors, (46), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 116 [2023-11-19 05:04:33,533 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 05:04:33,551 INFO L225 Difference]: With dead ends: 3405 [2023-11-19 05:04:33,551 INFO L226 Difference]: Without dead ends: 3404 [2023-11-19 05:04:33,570 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 359 GetRequests, 184 SyntacticMatches, 0 SemanticMatches, 175 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7136 ImplicationChecksByTransitivity, 6.5s TimeCoverageRelationStatistics Valid=9119, Invalid=22033, Unknown=0, NotChecked=0, Total=31152 [2023-11-19 05:04:33,571 INFO L413 NwaCegarLoop]: 68 mSDtfsCounter, 2439 mSDsluCounter, 906 mSDsCounter, 0 mSdLazyCounter, 637 mSolverCounterSat, 515 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2441 SdHoareTripleChecker+Valid, 974 SdHoareTripleChecker+Invalid, 1152 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 515 IncrementalHoareTripleChecker+Valid, 637 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.9s IncrementalHoareTripleChecker+Time [2023-11-19 05:04:33,572 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [2441 Valid, 974 Invalid, 1152 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [515 Valid, 637 Invalid, 0 Unknown, 0 Unchecked, 0.9s Time] [2023-11-19 05:04:33,577 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 3404 states. [2023-11-19 05:04:33,668 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 3404 to 3358. [2023-11-19 05:04:33,675 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 3358 states, 2857 states have (on average 1.0290514525726286) internal successors, (2940), 2848 states have internal predecessors, (2940), 48 states have call successors, (48), 47 states have call predecessors, (48), 451 states have return successors, (462), 462 states have call predecessors, (462), 47 states have call successors, (462) [2023-11-19 05:04:33,693 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3358 states to 3358 states and 3450 transitions. [2023-11-19 05:04:33,694 INFO L78 Accepts]: Start accepts. Automaton has 3358 states and 3450 transitions. Word has length 116 [2023-11-19 05:04:33,694 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 05:04:33,695 INFO L495 AbstractCegarLoop]: Abstraction has 3358 states and 3450 transitions. [2023-11-19 05:04:33,695 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 96 states, 93 states have (on average 1.989247311827957) internal successors, (185), 50 states have internal predecessors, (185), 46 states have call successors, (46), 46 states have call predecessors, (46), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-19 05:04:33,695 INFO L276 IsEmpty]: Start isEmpty. Operand 3358 states and 3450 transitions. [2023-11-19 05:04:33,700 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 136 [2023-11-19 05:04:33,700 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 05:04:33,700 INFO L195 NwaCegarLoop]: trace histogram [12, 11, 11, 11, 11, 11, 11, 11, 11, 10, 10, 10, 1, 1, 1, 1, 1] [2023-11-19 05:04:33,735 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e2e5a0a7-3dc8-432e-8c1f-0b0cd0b6ffc5/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2023-11-19 05:04:33,929 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 8 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e2e5a0a7-3dc8-432e-8c1f-0b0cd0b6ffc5/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2023-11-19 05:04:33,929 INFO L420 AbstractCegarLoop]: === Iteration 11 === Targeting hanoiErr3ASSERT_VIOLATIONINTEGER_OVERFLOW === [hanoiErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, hanoiErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, hanoiErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2023-11-19 05:04:33,930 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 05:04:33,930 INFO L85 PathProgramCache]: Analyzing trace with hash 1817796810, now seen corresponding path program 3 times [2023-11-19 05:04:33,930 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 05:04:33,930 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [878180619] [2023-11-19 05:04:33,930 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 05:04:33,931 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 05:04:33,973 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 05:04:34,755 INFO L134 CoverageAnalysis]: Checked inductivity of 662 backedges. 0 proven. 365 refuted. 0 times theorem prover too weak. 297 trivial. 0 not checked. [2023-11-19 05:04:34,756 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 05:04:34,756 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [878180619] [2023-11-19 05:04:34,756 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [878180619] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-19 05:04:34,756 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [769448192] [2023-11-19 05:04:34,756 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2023-11-19 05:04:34,756 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 05:04:34,757 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e2e5a0a7-3dc8-432e-8c1f-0b0cd0b6ffc5/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 05:04:34,765 INFO L229 MonitoredProcess]: Starting monitored process 9 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e2e5a0a7-3dc8-432e-8c1f-0b0cd0b6ffc5/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 05:04:34,797 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e2e5a0a7-3dc8-432e-8c1f-0b0cd0b6ffc5/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2023-11-19 05:04:34,867 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2023-11-19 05:04:34,868 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-19 05:04:34,870 INFO L262 TraceCheckSpWp]: Trace formula consists of 251 conjuncts, 23 conjunts are in the unsatisfiable core [2023-11-19 05:04:34,879 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-19 05:04:35,024 INFO L134 CoverageAnalysis]: Checked inductivity of 662 backedges. 0 proven. 365 refuted. 0 times theorem prover too weak. 297 trivial. 0 not checked. [2023-11-19 05:04:35,024 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-19 05:04:42,038 INFO L134 CoverageAnalysis]: Checked inductivity of 662 backedges. 0 proven. 365 refuted. 0 times theorem prover too weak. 297 trivial. 0 not checked. [2023-11-19 05:04:42,038 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [769448192] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-19 05:04:42,038 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1046087243] [2023-11-19 05:04:42,041 INFO L159 IcfgInterpreter]: Started Sifa with 16 locations of interest [2023-11-19 05:04:42,041 INFO L166 IcfgInterpreter]: Building call graph [2023-11-19 05:04:42,041 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 05:04:42,045 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-19 05:04:42,046 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [23, 23, 23] total 47 [2023-11-19 05:04:42,047 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [454933449] [2023-11-19 05:04:42,047 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-19 05:04:42,050 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 48 states [2023-11-19 05:04:42,050 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 05:04:42,053 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 48 interpolants. [2023-11-19 05:04:42,054 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=599, Invalid=1657, Unknown=0, NotChecked=0, Total=2256 [2023-11-19 05:04:42,055 INFO L87 Difference]: Start difference. First operand 3358 states and 3450 transitions. Second operand has 48 states, 47 states have (on average 3.0425531914893615) internal successors, (143), 48 states have internal predecessors, (143), 1 states have call successors, (2), 1 states have call predecessors, (2), 23 states have return successors, (23), 23 states have call predecessors, (23), 1 states have call successors, (23) [2023-11-19 05:04:42,393 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 05:04:42,393 INFO L93 Difference]: Finished difference Result 7259 states and 7914 transitions. [2023-11-19 05:04:42,394 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 46 states. [2023-11-19 05:04:42,394 INFO L78 Accepts]: Start accepts. Automaton has has 48 states, 47 states have (on average 3.0425531914893615) internal successors, (143), 48 states have internal predecessors, (143), 1 states have call successors, (2), 1 states have call predecessors, (2), 23 states have return successors, (23), 23 states have call predecessors, (23), 1 states have call successors, (23) Word has length 135 [2023-11-19 05:04:42,397 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 05:04:42,428 INFO L225 Difference]: With dead ends: 7259 [2023-11-19 05:04:42,429 INFO L226 Difference]: Without dead ends: 5896 [2023-11-19 05:04:42,438 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 291 GetRequests, 245 SyntacticMatches, 0 SemanticMatches, 46 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 687 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=599, Invalid=1657, Unknown=0, NotChecked=0, Total=2256 [2023-11-19 05:04:42,439 INFO L413 NwaCegarLoop]: 12 mSDtfsCounter, 4 mSDsluCounter, 64 mSDsCounter, 0 mSdLazyCounter, 154 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 76 SdHoareTripleChecker+Invalid, 156 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 154 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-11-19 05:04:42,439 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 76 Invalid, 156 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 154 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-11-19 05:04:42,448 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 5896 states. [2023-11-19 05:04:42,617 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 5896 to 5896. [2023-11-19 05:04:42,629 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5896 states, 5041 states have (on average 1.0140845070422535) internal successors, (5112), 5020 states have internal predecessors, (5112), 48 states have call successors, (48), 47 states have call predecessors, (48), 805 states have return successors, (828), 828 states have call predecessors, (828), 47 states have call successors, (828) [2023-11-19 05:04:42,658 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5896 states to 5896 states and 5988 transitions. [2023-11-19 05:04:42,658 INFO L78 Accepts]: Start accepts. Automaton has 5896 states and 5988 transitions. Word has length 135 [2023-11-19 05:04:42,660 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 05:04:42,660 INFO L495 AbstractCegarLoop]: Abstraction has 5896 states and 5988 transitions. [2023-11-19 05:04:42,661 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 48 states, 47 states have (on average 3.0425531914893615) internal successors, (143), 48 states have internal predecessors, (143), 1 states have call successors, (2), 1 states have call predecessors, (2), 23 states have return successors, (23), 23 states have call predecessors, (23), 1 states have call successors, (23) [2023-11-19 05:04:42,661 INFO L276 IsEmpty]: Start isEmpty. Operand 5896 states and 5988 transitions. [2023-11-19 05:04:42,674 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 237 [2023-11-19 05:04:42,674 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 05:04:42,674 INFO L195 NwaCegarLoop]: trace histogram [47, 47, 46, 46, 46, 1, 1, 1, 1] [2023-11-19 05:04:42,691 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e2e5a0a7-3dc8-432e-8c1f-0b0cd0b6ffc5/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2023-11-19 05:04:42,874 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e2e5a0a7-3dc8-432e-8c1f-0b0cd0b6ffc5/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2023-11-19 05:04:42,875 INFO L420 AbstractCegarLoop]: === Iteration 12 === Targeting hanoiErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [hanoiErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, hanoiErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, hanoiErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2023-11-19 05:04:42,875 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 05:04:42,875 INFO L85 PathProgramCache]: Analyzing trace with hash -418775997, now seen corresponding path program 5 times [2023-11-19 05:04:42,875 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 05:04:42,876 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1491106343] [2023-11-19 05:04:42,876 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 05:04:42,876 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 05:04:42,938 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 05:04:49,310 INFO L134 CoverageAnalysis]: Checked inductivity of 5313 backedges. 0 proven. 5313 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-19 05:04:49,311 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 05:04:49,311 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1491106343] [2023-11-19 05:04:49,311 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1491106343] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-19 05:04:49,311 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [807934870] [2023-11-19 05:04:49,311 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-11-19 05:04:49,312 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 05:04:49,312 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e2e5a0a7-3dc8-432e-8c1f-0b0cd0b6ffc5/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 05:04:49,313 INFO L229 MonitoredProcess]: Starting monitored process 10 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e2e5a0a7-3dc8-432e-8c1f-0b0cd0b6ffc5/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 05:04:49,324 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e2e5a0a7-3dc8-432e-8c1f-0b0cd0b6ffc5/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2023-11-19 05:04:49,613 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 47 check-sat command(s) [2023-11-19 05:04:49,613 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-19 05:04:49,617 INFO L262 TraceCheckSpWp]: Trace formula consists of 447 conjuncts, 96 conjunts are in the unsatisfiable core [2023-11-19 05:04:49,624 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-19 05:04:50,068 INFO L134 CoverageAnalysis]: Checked inductivity of 5313 backedges. 0 proven. 5313 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-19 05:04:50,069 INFO L327 TraceCheckSpWp]: Computing backward predicates...