./Ultimate.py --spec ../../sv-benchmarks/c/properties/unreach-call.prp --file ../../sv-benchmarks/c/recursive/Ackermann03.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version d790fecc Calling Ultimate with: /usr/bin/java -Dosgi.configuration.area=/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/plugins/org.eclipse.equinox.launcher_1.6.800.v20240513-1750.jar -data @noDefault -ultimatedata /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/config/AutomizerReach.xml -i ../../sv-benchmarks/c/recursive/Ackermann03.c -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/config/svcomp-Reach-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(G ! call(reach_error())) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash c244f72db2906c596b7f122d769fc1464836d7d05d9227ee4269773d59ed10bd --- Real Ultimate output --- This is Ultimate 0.3.0-dev-d790fec [2024-11-27 23:23:23,382 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-27 23:23:23,467 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-11-27 23:23:23,472 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-27 23:23:23,472 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-27 23:23:23,497 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-27 23:23:23,497 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-27 23:23:23,497 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-27 23:23:23,498 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-27 23:23:23,498 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-27 23:23:23,498 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-27 23:23:23,498 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-27 23:23:23,498 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-27 23:23:23,498 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-27 23:23:23,498 INFO L153 SettingsManager]: * Use SBE=true [2024-11-27 23:23:23,499 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-27 23:23:23,499 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-27 23:23:23,499 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-27 23:23:23,499 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-27 23:23:23,499 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-27 23:23:23,499 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-27 23:23:23,499 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-27 23:23:23,499 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-27 23:23:23,499 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-27 23:23:23,500 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-27 23:23:23,500 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-27 23:23:23,500 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2024-11-27 23:23:23,500 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-27 23:23:23,500 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2024-11-27 23:23:23,500 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-27 23:23:23,500 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-27 23:23:23,500 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-27 23:23:23,500 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-27 23:23:23,501 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-27 23:23:23,501 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-27 23:23:23,501 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-27 23:23:23,501 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-27 23:23:23,501 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-27 23:23:23,501 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-27 23:23:23,501 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-27 23:23:23,501 INFO L153 SettingsManager]: * Compute procedure contracts=false [2024-11-27 23:23:23,501 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-27 23:23:23,501 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-27 23:23:23,502 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-27 23:23:23,502 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-27 23:23:23,502 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-27 23:23:23,502 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-27 23:23:23,502 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-27 23:23:23,502 INFO L153 SettingsManager]: * Looper check in Petri net analysis=SEMANTIC 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_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Write witness besides input file -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data specification -> CHECK( init(main()), LTL(G ! call(reach_error())) ) Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data producer -> Automizer 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 -> c244f72db2906c596b7f122d769fc1464836d7d05d9227ee4269773d59ed10bd [2024-11-27 23:23:23,752 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-27 23:23:23,768 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-27 23:23:23,770 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-27 23:23:23,774 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-27 23:23:23,774 INFO L274 PluginConnector]: CDTParser initialized [2024-11-27 23:23:23,775 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/../../sv-benchmarks/c/recursive/Ackermann03.c [2024-11-27 23:23:26,776 INFO L533 CDTParser]: Created temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/data/d644da15c/71c2cfc0ae3f42818534bf1a201b0b17/FLAG321ba08d3 [2024-11-27 23:23:27,061 INFO L384 CDTParser]: Found 1 translation units. [2024-11-27 23:23:27,062 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/sv-benchmarks/c/recursive/Ackermann03.c [2024-11-27 23:23:27,070 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/data/d644da15c/71c2cfc0ae3f42818534bf1a201b0b17/FLAG321ba08d3 [2024-11-27 23:23:27,095 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/data/d644da15c/71c2cfc0ae3f42818534bf1a201b0b17 [2024-11-27 23:23:27,098 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-27 23:23:27,101 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-27 23:23:27,102 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-27 23:23:27,103 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-27 23:23:27,108 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-27 23:23:27,109 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 27.11 11:23:27" (1/1) ... [2024-11-27 23:23:27,112 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@5c80a2c3 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.11 11:23:27, skipping insertion in model container [2024-11-27 23:23:27,112 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 27.11 11:23:27" (1/1) ... [2024-11-27 23:23:27,127 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-27 23:23:27,302 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/sv-benchmarks/c/recursive/Ackermann03.c[1168,1181] [2024-11-27 23:23:27,305 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-27 23:23:27,318 INFO L200 MainTranslator]: Completed pre-run [2024-11-27 23:23:27,338 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/sv-benchmarks/c/recursive/Ackermann03.c[1168,1181] [2024-11-27 23:23:27,339 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-27 23:23:27,359 INFO L204 MainTranslator]: Completed translation [2024-11-27 23:23:27,360 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.11 11:23:27 WrapperNode [2024-11-27 23:23:27,361 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-27 23:23:27,362 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-27 23:23:27,362 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-27 23:23:27,362 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-27 23:23:27,373 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.11 11:23:27" (1/1) ... [2024-11-27 23:23:27,381 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.11 11:23:27" (1/1) ... [2024-11-27 23:23:27,399 INFO L138 Inliner]: procedures = 13, calls = 11, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 33 [2024-11-27 23:23:27,400 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-27 23:23:27,400 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-27 23:23:27,401 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-27 23:23:27,401 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-27 23:23:27,411 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.11 11:23:27" (1/1) ... [2024-11-27 23:23:27,411 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.11 11:23:27" (1/1) ... [2024-11-27 23:23:27,412 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.11 11:23:27" (1/1) ... [2024-11-27 23:23:27,427 INFO L175 MemorySlicer]: Split 2 memory accesses to 1 slices as follows [2]. 100 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2]. The 0 writes are split as follows [0]. [2024-11-27 23:23:27,427 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.11 11:23:27" (1/1) ... [2024-11-27 23:23:27,428 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.11 11:23:27" (1/1) ... [2024-11-27 23:23:27,431 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.11 11:23:27" (1/1) ... [2024-11-27 23:23:27,433 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.11 11:23:27" (1/1) ... [2024-11-27 23:23:27,435 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.11 11:23:27" (1/1) ... [2024-11-27 23:23:27,439 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.11 11:23:27" (1/1) ... [2024-11-27 23:23:27,440 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.11 11:23:27" (1/1) ... [2024-11-27 23:23:27,441 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-27 23:23:27,442 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-27 23:23:27,442 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-27 23:23:27,442 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-27 23:23:27,445 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.11 11:23:27" (1/1) ... [2024-11-27 23:23:27,450 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-27 23:23:27,466 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/z3 [2024-11-27 23:23:27,481 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2024-11-27 23:23:27,484 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2024-11-27 23:23:27,511 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-27 23:23:27,511 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-27 23:23:27,511 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-27 23:23:27,511 INFO L130 BoogieDeclarations]: Found specification of procedure ackermann [2024-11-27 23:23:27,512 INFO L138 BoogieDeclarations]: Found implementation of procedure ackermann [2024-11-27 23:23:27,512 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-27 23:23:27,575 INFO L234 CfgBuilder]: Building ICFG [2024-11-27 23:23:27,577 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-27 23:23:27,716 INFO L? ?]: Removed 13 outVars from TransFormulas that were not future-live. [2024-11-27 23:23:27,716 INFO L283 CfgBuilder]: Performing block encoding [2024-11-27 23:23:27,724 INFO L307 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-27 23:23:27,725 INFO L312 CfgBuilder]: Removed 0 assume(true) statements. [2024-11-27 23:23:27,725 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 27.11 11:23:27 BoogieIcfgContainer [2024-11-27 23:23:27,725 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-27 23:23:27,728 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-27 23:23:27,728 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-27 23:23:27,733 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-27 23:23:27,734 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 27.11 11:23:27" (1/3) ... [2024-11-27 23:23:27,734 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@146d4be9 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 27.11 11:23:27, skipping insertion in model container [2024-11-27 23:23:27,734 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.11 11:23:27" (2/3) ... [2024-11-27 23:23:27,735 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@146d4be9 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 27.11 11:23:27, skipping insertion in model container [2024-11-27 23:23:27,735 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 27.11 11:23:27" (3/3) ... [2024-11-27 23:23:27,736 INFO L128 eAbstractionObserver]: Analyzing ICFG Ackermann03.c [2024-11-27 23:23:27,756 INFO L216 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-27 23:23:27,759 INFO L151 ceAbstractionStarter]: Applying trace abstraction to ICFG Ackermann03.c that has 2 procedures, 23 locations, 1 initial locations, 0 loop locations, and 1 error locations. [2024-11-27 23:23:27,834 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-27 23:23:27,852 INFO L333 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=FPandBP, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mAutomataTypeConcurrency=PETRI_NET, 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;@248eae8d, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-27 23:23:27,852 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-27 23:23:27,858 INFO L276 IsEmpty]: Start isEmpty. Operand has 23 states, 16 states have (on average 1.375) internal successors, (22), 17 states have internal predecessors, (22), 4 states have call successors, (4), 1 states have call predecessors, (4), 1 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2024-11-27 23:23:27,865 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2024-11-27 23:23:27,865 INFO L210 NwaCegarLoop]: Found error trace [2024-11-27 23:23:27,865 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-27 23:23:27,866 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-27 23:23:27,872 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-27 23:23:27,873 INFO L85 PathProgramCache]: Analyzing trace with hash 1470704041, now seen corresponding path program 1 times [2024-11-27 23:23:27,881 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-27 23:23:27,881 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [355384627] [2024-11-27 23:23:27,881 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-27 23:23:27,882 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-27 23:23:27,973 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-27 23:23:28,129 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-27 23:23:28,131 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-27 23:23:28,131 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [355384627] [2024-11-27 23:23:28,132 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [355384627] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-27 23:23:28,134 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-27 23:23:28,134 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-27 23:23:28,136 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1788671456] [2024-11-27 23:23:28,136 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-27 23:23:28,141 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-27 23:23:28,141 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-27 23:23:28,162 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-27 23:23:28,163 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-27 23:23:28,165 INFO L87 Difference]: Start difference. First operand has 23 states, 16 states have (on average 1.375) internal successors, (22), 17 states have internal predecessors, (22), 4 states have call successors, (4), 1 states have call predecessors, (4), 1 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) Second operand has 5 states, 5 states have (on average 2.0) internal successors, (10), 5 states have internal predecessors, (10), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-27 23:23:28,346 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-27 23:23:28,346 INFO L93 Difference]: Finished difference Result 37 states and 53 transitions. [2024-11-27 23:23:28,348 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-27 23:23:28,349 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.0) internal successors, (10), 5 states have internal predecessors, (10), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 12 [2024-11-27 23:23:28,349 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-27 23:23:28,356 INFO L225 Difference]: With dead ends: 37 [2024-11-27 23:23:28,356 INFO L226 Difference]: Without dead ends: 27 [2024-11-27 23:23:28,359 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-27 23:23:28,362 INFO L435 NwaCegarLoop]: 25 mSDtfsCounter, 10 mSDsluCounter, 46 mSDsCounter, 0 mSdLazyCounter, 68 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 16 SdHoareTripleChecker+Valid, 71 SdHoareTripleChecker+Invalid, 71 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 68 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-27 23:23:28,362 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [16 Valid, 71 Invalid, 71 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 68 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-27 23:23:28,377 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 27 states. [2024-11-27 23:23:28,403 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 27 to 25. [2024-11-27 23:23:28,405 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 25 states, 17 states have (on average 1.1176470588235294) internal successors, (19), 17 states have internal predecessors, (19), 5 states have call successors, (5), 1 states have call predecessors, (5), 2 states have return successors, (9), 6 states have call predecessors, (9), 5 states have call successors, (9) [2024-11-27 23:23:28,411 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 25 states to 25 states and 33 transitions. [2024-11-27 23:23:28,415 INFO L78 Accepts]: Start accepts. Automaton has 25 states and 33 transitions. Word has length 12 [2024-11-27 23:23:28,416 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-27 23:23:28,416 INFO L471 AbstractCegarLoop]: Abstraction has 25 states and 33 transitions. [2024-11-27 23:23:28,416 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.0) internal successors, (10), 5 states have internal predecessors, (10), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-27 23:23:28,416 INFO L276 IsEmpty]: Start isEmpty. Operand 25 states and 33 transitions. [2024-11-27 23:23:28,418 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2024-11-27 23:23:28,419 INFO L210 NwaCegarLoop]: Found error trace [2024-11-27 23:23:28,420 INFO L218 NwaCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-27 23:23:28,420 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-27 23:23:28,420 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-27 23:23:28,421 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-27 23:23:28,422 INFO L85 PathProgramCache]: Analyzing trace with hash 941922339, now seen corresponding path program 1 times [2024-11-27 23:23:28,422 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-27 23:23:28,422 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [828274324] [2024-11-27 23:23:28,423 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-27 23:23:28,423 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-27 23:23:28,469 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-27 23:23:28,638 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 1 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-27 23:23:28,652 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-27 23:23:28,652 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [828274324] [2024-11-27 23:23:28,652 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [828274324] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-27 23:23:28,652 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1120724226] [2024-11-27 23:23:28,652 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-27 23:23:28,652 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-27 23:23:28,652 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/z3 [2024-11-27 23:23:28,656 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-27 23:23:28,657 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-11-27 23:23:28,717 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-27 23:23:28,719 INFO L256 TraceCheckSpWp]: Trace formula consists of 76 conjuncts, 4 conjuncts are in the unsatisfiable core [2024-11-27 23:23:28,724 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-27 23:23:28,787 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 1 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-27 23:23:28,787 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-11-27 23:23:28,947 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 1 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-27 23:23:28,947 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1120724226] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-27 23:23:28,947 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-27 23:23:28,948 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5, 5] total 8 [2024-11-27 23:23:28,948 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1073423816] [2024-11-27 23:23:28,948 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-27 23:23:28,949 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-11-27 23:23:28,949 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-27 23:23:28,951 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-11-27 23:23:28,951 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=38, Unknown=0, NotChecked=0, Total=56 [2024-11-27 23:23:28,952 INFO L87 Difference]: Start difference. First operand 25 states and 33 transitions. Second operand has 8 states, 8 states have (on average 2.75) internal successors, (22), 8 states have internal predecessors, (22), 3 states have call successors, (3), 1 states have call predecessors, (3), 3 states have return successors, (4), 4 states have call predecessors, (4), 3 states have call successors, (4) [2024-11-27 23:23:29,153 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-27 23:23:29,153 INFO L93 Difference]: Finished difference Result 69 states and 124 transitions. [2024-11-27 23:23:29,154 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2024-11-27 23:23:29,154 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 2.75) internal successors, (22), 8 states have internal predecessors, (22), 3 states have call successors, (3), 1 states have call predecessors, (3), 3 states have return successors, (4), 4 states have call predecessors, (4), 3 states have call successors, (4) Word has length 19 [2024-11-27 23:23:29,154 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-27 23:23:29,156 INFO L225 Difference]: With dead ends: 69 [2024-11-27 23:23:29,156 INFO L226 Difference]: Without dead ends: 45 [2024-11-27 23:23:29,157 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 43 GetRequests, 36 SyntacticMatches, 0 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=23, Invalid=49, Unknown=0, NotChecked=0, Total=72 [2024-11-27 23:23:29,157 INFO L435 NwaCegarLoop]: 27 mSDtfsCounter, 17 mSDsluCounter, 39 mSDsCounter, 0 mSdLazyCounter, 81 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 19 SdHoareTripleChecker+Valid, 66 SdHoareTripleChecker+Invalid, 92 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 81 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-27 23:23:29,158 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [19 Valid, 66 Invalid, 92 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 81 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-27 23:23:29,158 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 45 states. [2024-11-27 23:23:29,169 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 45 to 41. [2024-11-27 23:23:29,170 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 41 states, 27 states have (on average 1.1481481481481481) internal successors, (31), 28 states have internal predecessors, (31), 8 states have call successors, (8), 2 states have call predecessors, (8), 5 states have return successors, (27), 10 states have call predecessors, (27), 8 states have call successors, (27) [2024-11-27 23:23:29,171 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 41 states to 41 states and 66 transitions. [2024-11-27 23:23:29,172 INFO L78 Accepts]: Start accepts. Automaton has 41 states and 66 transitions. Word has length 19 [2024-11-27 23:23:29,172 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-27 23:23:29,172 INFO L471 AbstractCegarLoop]: Abstraction has 41 states and 66 transitions. [2024-11-27 23:23:29,172 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 2.75) internal successors, (22), 8 states have internal predecessors, (22), 3 states have call successors, (3), 1 states have call predecessors, (3), 3 states have return successors, (4), 4 states have call predecessors, (4), 3 states have call successors, (4) [2024-11-27 23:23:29,172 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 66 transitions. [2024-11-27 23:23:29,175 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 46 [2024-11-27 23:23:29,175 INFO L210 NwaCegarLoop]: Found error trace [2024-11-27 23:23:29,175 INFO L218 NwaCegarLoop]: trace histogram [6, 6, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-27 23:23:29,186 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2024-11-27 23:23:29,379 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable1 [2024-11-27 23:23:29,379 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-27 23:23:29,380 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-27 23:23:29,380 INFO L85 PathProgramCache]: Analyzing trace with hash -574784801, now seen corresponding path program 1 times [2024-11-27 23:23:29,380 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-27 23:23:29,380 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [344886277] [2024-11-27 23:23:29,380 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-27 23:23:29,380 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-27 23:23:29,439 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-27 23:23:29,712 INFO L134 CoverageAnalysis]: Checked inductivity of 67 backedges. 6 proven. 24 refuted. 0 times theorem prover too weak. 37 trivial. 0 not checked. [2024-11-27 23:23:29,712 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-27 23:23:29,712 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [344886277] [2024-11-27 23:23:29,713 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [344886277] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-27 23:23:29,713 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [9792073] [2024-11-27 23:23:29,713 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-27 23:23:29,713 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-27 23:23:29,713 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/z3 [2024-11-27 23:23:29,718 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-27 23:23:29,719 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-11-27 23:23:29,790 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-27 23:23:29,791 INFO L256 TraceCheckSpWp]: Trace formula consists of 152 conjuncts, 10 conjuncts are in the unsatisfiable core [2024-11-27 23:23:29,794 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-27 23:23:29,903 INFO L134 CoverageAnalysis]: Checked inductivity of 67 backedges. 6 proven. 24 refuted. 0 times theorem prover too weak. 37 trivial. 0 not checked. [2024-11-27 23:23:29,904 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-11-27 23:23:30,696 INFO L134 CoverageAnalysis]: Checked inductivity of 67 backedges. 6 proven. 27 refuted. 0 times theorem prover too weak. 34 trivial. 0 not checked. [2024-11-27 23:23:30,697 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [9792073] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-27 23:23:30,697 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-27 23:23:30,697 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6, 7] total 8 [2024-11-27 23:23:30,697 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [25558348] [2024-11-27 23:23:30,697 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-27 23:23:30,698 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-11-27 23:23:30,698 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-27 23:23:30,699 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-11-27 23:23:30,700 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=19, Invalid=37, Unknown=0, NotChecked=0, Total=56 [2024-11-27 23:23:30,700 INFO L87 Difference]: Start difference. First operand 41 states and 66 transitions. Second operand has 8 states, 8 states have (on average 3.25) internal successors, (26), 8 states have internal predecessors, (26), 4 states have call successors, (6), 1 states have call predecessors, (6), 3 states have return successors, (6), 2 states have call predecessors, (6), 4 states have call successors, (6) [2024-11-27 23:23:30,853 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-27 23:23:30,853 INFO L93 Difference]: Finished difference Result 62 states and 124 transitions. [2024-11-27 23:23:30,853 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-11-27 23:23:30,854 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 3.25) internal successors, (26), 8 states have internal predecessors, (26), 4 states have call successors, (6), 1 states have call predecessors, (6), 3 states have return successors, (6), 2 states have call predecessors, (6), 4 states have call successors, (6) Word has length 45 [2024-11-27 23:23:30,854 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-27 23:23:30,857 INFO L225 Difference]: With dead ends: 62 [2024-11-27 23:23:30,857 INFO L226 Difference]: Without dead ends: 58 [2024-11-27 23:23:30,857 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 103 GetRequests, 90 SyntacticMatches, 5 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=33, Invalid=57, Unknown=0, NotChecked=0, Total=90 [2024-11-27 23:23:30,858 INFO L435 NwaCegarLoop]: 20 mSDtfsCounter, 22 mSDsluCounter, 48 mSDsCounter, 0 mSdLazyCounter, 59 mSolverCounterSat, 23 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 30 SdHoareTripleChecker+Valid, 68 SdHoareTripleChecker+Invalid, 82 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 23 IncrementalHoareTripleChecker+Valid, 59 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-27 23:23:30,859 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [30 Valid, 68 Invalid, 82 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [23 Valid, 59 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-27 23:23:30,859 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 58 states. [2024-11-27 23:23:30,874 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 58 to 54. [2024-11-27 23:23:30,875 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 54 states, 35 states have (on average 1.1142857142857143) internal successors, (39), 36 states have internal predecessors, (39), 10 states have call successors, (10), 2 states have call predecessors, (10), 8 states have return successors, (60), 15 states have call predecessors, (60), 10 states have call successors, (60) [2024-11-27 23:23:30,877 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 109 transitions. [2024-11-27 23:23:30,877 INFO L78 Accepts]: Start accepts. Automaton has 54 states and 109 transitions. Word has length 45 [2024-11-27 23:23:30,877 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-27 23:23:30,878 INFO L471 AbstractCegarLoop]: Abstraction has 54 states and 109 transitions. [2024-11-27 23:23:30,878 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 3.25) internal successors, (26), 8 states have internal predecessors, (26), 4 states have call successors, (6), 1 states have call predecessors, (6), 3 states have return successors, (6), 2 states have call predecessors, (6), 4 states have call successors, (6) [2024-11-27 23:23:30,878 INFO L276 IsEmpty]: Start isEmpty. Operand 54 states and 109 transitions. [2024-11-27 23:23:30,881 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 80 [2024-11-27 23:23:30,882 INFO L210 NwaCegarLoop]: Found error trace [2024-11-27 23:23:30,882 INFO L218 NwaCegarLoop]: trace histogram [11, 11, 7, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-27 23:23:30,891 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2024-11-27 23:23:31,086 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-27 23:23:31,086 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-27 23:23:31,086 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-27 23:23:31,087 INFO L85 PathProgramCache]: Analyzing trace with hash -749766204, now seen corresponding path program 2 times [2024-11-27 23:23:31,087 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-27 23:23:31,087 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1285673512] [2024-11-27 23:23:31,087 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-27 23:23:31,087 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-27 23:23:31,150 INFO L229 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-27 23:23:31,154 INFO L230 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-27 23:23:31,525 INFO L134 CoverageAnalysis]: Checked inductivity of 265 backedges. 104 proven. 14 refuted. 0 times theorem prover too weak. 147 trivial. 0 not checked. [2024-11-27 23:23:31,525 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-27 23:23:31,525 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1285673512] [2024-11-27 23:23:31,525 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1285673512] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-27 23:23:31,525 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1648174381] [2024-11-27 23:23:31,525 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-27 23:23:31,526 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-27 23:23:31,526 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/z3 [2024-11-27 23:23:31,531 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-27 23:23:31,533 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-11-27 23:23:31,639 INFO L229 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-27 23:23:31,639 INFO L230 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-27 23:23:31,641 INFO L256 TraceCheckSpWp]: Trace formula consists of 250 conjuncts, 17 conjuncts are in the unsatisfiable core [2024-11-27 23:23:31,644 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-27 23:23:31,795 INFO L134 CoverageAnalysis]: Checked inductivity of 265 backedges. 141 proven. 37 refuted. 0 times theorem prover too weak. 87 trivial. 0 not checked. [2024-11-27 23:23:31,797 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-11-27 23:23:33,862 INFO L134 CoverageAnalysis]: Checked inductivity of 265 backedges. 85 proven. 65 refuted. 0 times theorem prover too weak. 115 trivial. 0 not checked. [2024-11-27 23:23:33,862 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1648174381] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-27 23:23:33,862 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-27 23:23:33,862 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 12, 15] total 27 [2024-11-27 23:23:33,863 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1667831908] [2024-11-27 23:23:33,863 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-27 23:23:33,863 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 27 states [2024-11-27 23:23:33,863 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-27 23:23:33,864 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 27 interpolants. [2024-11-27 23:23:33,865 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=97, Invalid=605, Unknown=0, NotChecked=0, Total=702 [2024-11-27 23:23:33,865 INFO L87 Difference]: Start difference. First operand 54 states and 109 transitions. Second operand has 27 states, 27 states have (on average 2.1481481481481484) internal successors, (58), 20 states have internal predecessors, (58), 7 states have call successors, (12), 2 states have call predecessors, (12), 11 states have return successors, (24), 14 states have call predecessors, (24), 7 states have call successors, (24) [2024-11-27 23:23:35,311 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-27 23:23:35,311 INFO L93 Difference]: Finished difference Result 294 states and 1388 transitions. [2024-11-27 23:23:35,312 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 38 states. [2024-11-27 23:23:35,312 INFO L78 Accepts]: Start accepts. Automaton has has 27 states, 27 states have (on average 2.1481481481481484) internal successors, (58), 20 states have internal predecessors, (58), 7 states have call successors, (12), 2 states have call predecessors, (12), 11 states have return successors, (24), 14 states have call predecessors, (24), 7 states have call successors, (24) Word has length 79 [2024-11-27 23:23:35,313 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-27 23:23:35,329 INFO L225 Difference]: With dead ends: 294 [2024-11-27 23:23:35,330 INFO L226 Difference]: Without dead ends: 245 [2024-11-27 23:23:35,335 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 200 GetRequests, 141 SyntacticMatches, 1 SemanticMatches, 58 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 703 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=692, Invalid=2848, Unknown=0, NotChecked=0, Total=3540 [2024-11-27 23:23:35,336 INFO L435 NwaCegarLoop]: 33 mSDtfsCounter, 14 mSDsluCounter, 143 mSDsCounter, 0 mSdLazyCounter, 567 mSolverCounterSat, 41 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 176 SdHoareTripleChecker+Invalid, 608 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 41 IncrementalHoareTripleChecker+Valid, 567 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2024-11-27 23:23:35,337 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [14 Valid, 176 Invalid, 608 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [41 Valid, 567 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2024-11-27 23:23:35,338 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 245 states. [2024-11-27 23:23:35,437 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 245 to 92. [2024-11-27 23:23:35,438 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 92 states, 58 states have (on average 1.0689655172413792) internal successors, (62), 60 states have internal predecessors, (62), 16 states have call successors, (16), 2 states have call predecessors, (16), 17 states have return successors, (194), 29 states have call predecessors, (194), 16 states have call successors, (194) [2024-11-27 23:23:35,441 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 92 states to 92 states and 272 transitions. [2024-11-27 23:23:35,442 INFO L78 Accepts]: Start accepts. Automaton has 92 states and 272 transitions. Word has length 79 [2024-11-27 23:23:35,442 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-27 23:23:35,442 INFO L471 AbstractCegarLoop]: Abstraction has 92 states and 272 transitions. [2024-11-27 23:23:35,443 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 27 states, 27 states have (on average 2.1481481481481484) internal successors, (58), 20 states have internal predecessors, (58), 7 states have call successors, (12), 2 states have call predecessors, (12), 11 states have return successors, (24), 14 states have call predecessors, (24), 7 states have call successors, (24) [2024-11-27 23:23:35,443 INFO L276 IsEmpty]: Start isEmpty. Operand 92 states and 272 transitions. [2024-11-27 23:23:35,450 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 132 [2024-11-27 23:23:35,450 INFO L210 NwaCegarLoop]: Found error trace [2024-11-27 23:23:35,450 INFO L218 NwaCegarLoop]: trace histogram [19, 19, 11, 8, 7, 7, 7, 7, 7, 7, 7, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-27 23:23:35,460 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2024-11-27 23:23:35,655 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-27 23:23:35,655 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-27 23:23:35,655 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-27 23:23:35,656 INFO L85 PathProgramCache]: Analyzing trace with hash -1991913426, now seen corresponding path program 3 times [2024-11-27 23:23:35,656 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-27 23:23:35,656 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [338170713] [2024-11-27 23:23:35,656 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-27 23:23:35,656 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-27 23:23:35,683 INFO L229 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2024-11-27 23:23:35,684 INFO L230 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-27 23:23:35,735 INFO L134 CoverageAnalysis]: Checked inductivity of 835 backedges. 192 proven. 22 refuted. 0 times theorem prover too weak. 621 trivial. 0 not checked. [2024-11-27 23:23:35,735 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-27 23:23:35,735 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [338170713] [2024-11-27 23:23:35,735 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [338170713] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-27 23:23:35,736 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [167416495] [2024-11-27 23:23:35,736 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-27 23:23:35,736 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-27 23:23:35,737 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/z3 [2024-11-27 23:23:35,743 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-27 23:23:35,747 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-11-27 23:23:35,846 INFO L229 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2024-11-27 23:23:35,847 INFO L230 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-27 23:23:35,853 INFO L256 TraceCheckSpWp]: Trace formula consists of 183 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-11-27 23:23:35,857 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-27 23:23:35,917 INFO L134 CoverageAnalysis]: Checked inductivity of 835 backedges. 348 proven. 3 refuted. 0 times theorem prover too weak. 484 trivial. 0 not checked. [2024-11-27 23:23:35,919 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-11-27 23:23:36,425 INFO L134 CoverageAnalysis]: Checked inductivity of 835 backedges. 216 proven. 27 refuted. 0 times theorem prover too weak. 592 trivial. 0 not checked. [2024-11-27 23:23:36,426 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [167416495] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-27 23:23:36,426 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-27 23:23:36,426 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 7, 7] total 12 [2024-11-27 23:23:36,426 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1688729592] [2024-11-27 23:23:36,426 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-27 23:23:36,427 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2024-11-27 23:23:36,427 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-27 23:23:36,428 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2024-11-27 23:23:36,428 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=99, Unknown=0, NotChecked=0, Total=132 [2024-11-27 23:23:36,428 INFO L87 Difference]: Start difference. First operand 92 states and 272 transitions. Second operand has 12 states, 12 states have (on average 3.3333333333333335) internal successors, (40), 12 states have internal predecessors, (40), 4 states have call successors, (9), 2 states have call predecessors, (9), 5 states have return successors, (12), 3 states have call predecessors, (12), 4 states have call successors, (12) [2024-11-27 23:23:36,545 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-27 23:23:36,545 INFO L93 Difference]: Finished difference Result 144 states and 486 transitions. [2024-11-27 23:23:36,546 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2024-11-27 23:23:36,546 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 3.3333333333333335) internal successors, (40), 12 states have internal predecessors, (40), 4 states have call successors, (9), 2 states have call predecessors, (9), 5 states have return successors, (12), 3 states have call predecessors, (12), 4 states have call successors, (12) Word has length 131 [2024-11-27 23:23:36,547 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-27 23:23:36,548 INFO L225 Difference]: With dead ends: 144 [2024-11-27 23:23:36,548 INFO L226 Difference]: Without dead ends: 57 [2024-11-27 23:23:36,550 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 268 GetRequests, 252 SyntacticMatches, 3 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 18 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=60, Invalid=150, Unknown=0, NotChecked=0, Total=210 [2024-11-27 23:23:36,551 INFO L435 NwaCegarLoop]: 23 mSDtfsCounter, 40 mSDsluCounter, 66 mSDsCounter, 0 mSdLazyCounter, 84 mSolverCounterSat, 33 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 40 SdHoareTripleChecker+Valid, 89 SdHoareTripleChecker+Invalid, 117 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 33 IncrementalHoareTripleChecker+Valid, 84 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-27 23:23:36,552 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [40 Valid, 89 Invalid, 117 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [33 Valid, 84 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-27 23:23:36,552 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 57 states. [2024-11-27 23:23:36,561 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 57 to 48. [2024-11-27 23:23:36,561 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 48 states, 31 states have (on average 1.1290322580645162) internal successors, (35), 34 states have internal predecessors, (35), 8 states have call successors, (8), 2 states have call predecessors, (8), 8 states have return successors, (36), 11 states have call predecessors, (36), 8 states have call successors, (36) [2024-11-27 23:23:36,562 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 48 states to 48 states and 79 transitions. [2024-11-27 23:23:36,563 INFO L78 Accepts]: Start accepts. Automaton has 48 states and 79 transitions. Word has length 131 [2024-11-27 23:23:36,563 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-27 23:23:36,563 INFO L471 AbstractCegarLoop]: Abstraction has 48 states and 79 transitions. [2024-11-27 23:23:36,563 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 3.3333333333333335) internal successors, (40), 12 states have internal predecessors, (40), 4 states have call successors, (9), 2 states have call predecessors, (9), 5 states have return successors, (12), 3 states have call predecessors, (12), 4 states have call successors, (12) [2024-11-27 23:23:36,564 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 79 transitions. [2024-11-27 23:23:36,566 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 211 [2024-11-27 23:23:36,566 INFO L210 NwaCegarLoop]: Found error trace [2024-11-27 23:23:36,566 INFO L218 NwaCegarLoop]: trace histogram [31, 31, 18, 13, 12, 12, 12, 12, 12, 12, 12, 6, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-27 23:23:36,575 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2024-11-27 23:23:36,770 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-27 23:23:36,770 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-27 23:23:36,770 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-27 23:23:36,770 INFO L85 PathProgramCache]: Analyzing trace with hash 373404425, now seen corresponding path program 4 times [2024-11-27 23:23:36,770 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-27 23:23:36,771 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1928906960] [2024-11-27 23:23:36,771 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-27 23:23:36,771 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-27 23:23:36,835 INFO L229 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-27 23:23:36,838 INFO L230 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-27 23:23:37,553 INFO L134 CoverageAnalysis]: Checked inductivity of 2307 backedges. 432 proven. 724 refuted. 0 times theorem prover too weak. 1151 trivial. 0 not checked. [2024-11-27 23:23:37,553 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-27 23:23:37,553 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1928906960] [2024-11-27 23:23:37,554 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1928906960] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-27 23:23:37,554 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [456609575] [2024-11-27 23:23:37,554 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-27 23:23:37,554 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-27 23:23:37,554 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/z3 [2024-11-27 23:23:37,556 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-27 23:23:37,561 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2024-11-27 23:23:37,697 INFO L229 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-27 23:23:37,697 INFO L230 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-27 23:23:37,699 INFO L256 TraceCheckSpWp]: Trace formula consists of 505 conjuncts, 16 conjuncts are in the unsatisfiable core [2024-11-27 23:23:37,705 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-27 23:23:37,820 INFO L134 CoverageAnalysis]: Checked inductivity of 2307 backedges. 528 proven. 242 refuted. 0 times theorem prover too weak. 1537 trivial. 0 not checked. [2024-11-27 23:23:37,821 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-11-27 23:23:40,136 INFO L134 CoverageAnalysis]: Checked inductivity of 2307 backedges. 528 proven. 276 refuted. 0 times theorem prover too weak. 1503 trivial. 0 not checked. [2024-11-27 23:23:40,136 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [456609575] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-27 23:23:40,136 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-27 23:23:40,136 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 8, 11] total 18 [2024-11-27 23:23:40,136 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1204371820] [2024-11-27 23:23:40,137 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-27 23:23:40,137 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2024-11-27 23:23:40,137 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-27 23:23:40,138 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2024-11-27 23:23:40,138 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=63, Invalid=243, Unknown=0, NotChecked=0, Total=306 [2024-11-27 23:23:40,138 INFO L87 Difference]: Start difference. First operand 48 states and 79 transitions. Second operand has 18 states, 18 states have (on average 3.888888888888889) internal successors, (70), 18 states have internal predecessors, (70), 12 states have call successors, (22), 1 states have call predecessors, (22), 9 states have return successors, (27), 11 states have call predecessors, (27), 12 states have call successors, (27) [2024-11-27 23:23:40,446 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-27 23:23:40,447 INFO L93 Difference]: Finished difference Result 131 states and 306 transitions. [2024-11-27 23:23:40,447 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2024-11-27 23:23:40,447 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 18 states have (on average 3.888888888888889) internal successors, (70), 18 states have internal predecessors, (70), 12 states have call successors, (22), 1 states have call predecessors, (22), 9 states have return successors, (27), 11 states have call predecessors, (27), 12 states have call successors, (27) Word has length 210 [2024-11-27 23:23:40,448 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-27 23:23:40,449 INFO L225 Difference]: With dead ends: 131 [2024-11-27 23:23:40,449 INFO L226 Difference]: Without dead ends: 57 [2024-11-27 23:23:40,451 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 452 GetRequests, 419 SyntacticMatches, 8 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 165 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=180, Invalid=522, Unknown=0, NotChecked=0, Total=702 [2024-11-27 23:23:40,451 INFO L435 NwaCegarLoop]: 38 mSDtfsCounter, 87 mSDsluCounter, 155 mSDsCounter, 0 mSdLazyCounter, 261 mSolverCounterSat, 64 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 94 SdHoareTripleChecker+Valid, 193 SdHoareTripleChecker+Invalid, 325 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 64 IncrementalHoareTripleChecker+Valid, 261 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-27 23:23:40,452 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [94 Valid, 193 Invalid, 325 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [64 Valid, 261 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-27 23:23:40,452 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 57 states. [2024-11-27 23:23:40,461 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 57 to 57. [2024-11-27 23:23:40,462 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 57 states, 38 states have (on average 1.131578947368421) internal successors, (43), 40 states have internal predecessors, (43), 10 states have call successors, (10), 5 states have call predecessors, (10), 8 states have return successors, (22), 11 states have call predecessors, (22), 10 states have call successors, (22) [2024-11-27 23:23:40,462 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 57 states to 57 states and 75 transitions. [2024-11-27 23:23:40,463 INFO L78 Accepts]: Start accepts. Automaton has 57 states and 75 transitions. Word has length 210 [2024-11-27 23:23:40,463 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-27 23:23:40,463 INFO L471 AbstractCegarLoop]: Abstraction has 57 states and 75 transitions. [2024-11-27 23:23:40,463 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 18 states, 18 states have (on average 3.888888888888889) internal successors, (70), 18 states have internal predecessors, (70), 12 states have call successors, (22), 1 states have call predecessors, (22), 9 states have return successors, (27), 11 states have call predecessors, (27), 12 states have call successors, (27) [2024-11-27 23:23:40,464 INFO L276 IsEmpty]: Start isEmpty. Operand 57 states and 75 transitions. [2024-11-27 23:23:40,465 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 106 [2024-11-27 23:23:40,465 INFO L210 NwaCegarLoop]: Found error trace [2024-11-27 23:23:40,465 INFO L218 NwaCegarLoop]: trace histogram [15, 15, 9, 6, 5, 5, 5, 5, 5, 5, 5, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-27 23:23:40,474 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2024-11-27 23:23:40,669 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-27 23:23:40,669 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-27 23:23:40,670 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-27 23:23:40,670 INFO L85 PathProgramCache]: Analyzing trace with hash -1271355446, now seen corresponding path program 5 times [2024-11-27 23:23:40,670 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-27 23:23:40,670 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [107444491] [2024-11-27 23:23:40,670 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2024-11-27 23:23:40,670 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-27 23:23:40,690 INFO L229 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 7 check-sat command(s) [2024-11-27 23:23:40,690 INFO L230 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-27 23:23:41,089 INFO L134 CoverageAnalysis]: Checked inductivity of 508 backedges. 107 proven. 189 refuted. 0 times theorem prover too weak. 212 trivial. 0 not checked. [2024-11-27 23:23:41,089 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-27 23:23:41,089 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [107444491] [2024-11-27 23:23:41,089 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [107444491] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-27 23:23:41,089 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1299349285] [2024-11-27 23:23:41,089 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2024-11-27 23:23:41,090 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-27 23:23:41,090 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/z3 [2024-11-27 23:23:41,092 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-27 23:23:41,095 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2024-11-27 23:23:41,204 INFO L229 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 7 check-sat command(s) [2024-11-27 23:23:41,204 INFO L230 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-27 23:23:41,205 INFO L256 TraceCheckSpWp]: Trace formula consists of 176 conjuncts, 19 conjuncts are in the unsatisfiable core [2024-11-27 23:23:41,208 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-27 23:23:41,345 INFO L134 CoverageAnalysis]: Checked inductivity of 508 backedges. 286 proven. 71 refuted. 0 times theorem prover too weak. 151 trivial. 0 not checked. [2024-11-27 23:23:41,345 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-11-27 23:23:43,265 INFO L134 CoverageAnalysis]: Checked inductivity of 508 backedges. 121 proven. 161 refuted. 0 times theorem prover too weak. 226 trivial. 0 not checked. [2024-11-27 23:23:43,265 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1299349285] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-27 23:23:43,265 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-27 23:23:43,265 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 13, 16] total 28 [2024-11-27 23:23:43,266 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1835681104] [2024-11-27 23:23:43,266 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-27 23:23:43,266 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 28 states [2024-11-27 23:23:43,266 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-27 23:23:43,267 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 28 interpolants. [2024-11-27 23:23:43,268 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=97, Invalid=659, Unknown=0, NotChecked=0, Total=756 [2024-11-27 23:23:43,268 INFO L87 Difference]: Start difference. First operand 57 states and 75 transitions. Second operand has 28 states, 28 states have (on average 2.392857142857143) internal successors, (67), 21 states have internal predecessors, (67), 11 states have call successors, (17), 2 states have call predecessors, (17), 12 states have return successors, (29), 15 states have call predecessors, (29), 11 states have call successors, (29) [2024-11-27 23:23:44,568 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-27 23:23:44,568 INFO L93 Difference]: Finished difference Result 145 states and 188 transitions. [2024-11-27 23:23:44,569 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 40 states. [2024-11-27 23:23:44,569 INFO L78 Accepts]: Start accepts. Automaton has has 28 states, 28 states have (on average 2.392857142857143) internal successors, (67), 21 states have internal predecessors, (67), 11 states have call successors, (17), 2 states have call predecessors, (17), 12 states have return successors, (29), 15 states have call predecessors, (29), 11 states have call successors, (29) Word has length 105 [2024-11-27 23:23:44,569 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-27 23:23:44,570 INFO L225 Difference]: With dead ends: 145 [2024-11-27 23:23:44,572 INFO L226 Difference]: Without dead ends: 86 [2024-11-27 23:23:44,573 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 263 GetRequests, 196 SyntacticMatches, 6 SemanticMatches, 61 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 811 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=785, Invalid=3121, Unknown=0, NotChecked=0, Total=3906 [2024-11-27 23:23:44,574 INFO L435 NwaCegarLoop]: 28 mSDtfsCounter, 86 mSDsluCounter, 259 mSDsCounter, 0 mSdLazyCounter, 561 mSolverCounterSat, 119 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 86 SdHoareTripleChecker+Valid, 287 SdHoareTripleChecker+Invalid, 680 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 119 IncrementalHoareTripleChecker+Valid, 561 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2024-11-27 23:23:44,574 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [86 Valid, 287 Invalid, 680 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [119 Valid, 561 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2024-11-27 23:23:44,575 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 86 states. [2024-11-27 23:23:44,596 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 86 to 74. [2024-11-27 23:23:44,598 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 74 states, 50 states have (on average 1.12) internal successors, (56), 52 states have internal predecessors, (56), 14 states have call successors, (14), 8 states have call predecessors, (14), 9 states have return successors, (22), 13 states have call predecessors, (22), 14 states have call successors, (22) [2024-11-27 23:23:44,599 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 74 states to 74 states and 92 transitions. [2024-11-27 23:23:44,599 INFO L78 Accepts]: Start accepts. Automaton has 74 states and 92 transitions. Word has length 105 [2024-11-27 23:23:44,600 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-27 23:23:44,600 INFO L471 AbstractCegarLoop]: Abstraction has 74 states and 92 transitions. [2024-11-27 23:23:44,600 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 28 states, 28 states have (on average 2.392857142857143) internal successors, (67), 21 states have internal predecessors, (67), 11 states have call successors, (17), 2 states have call predecessors, (17), 12 states have return successors, (29), 15 states have call predecessors, (29), 11 states have call successors, (29) [2024-11-27 23:23:44,600 INFO L276 IsEmpty]: Start isEmpty. Operand 74 states and 92 transitions. [2024-11-27 23:23:44,601 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 132 [2024-11-27 23:23:44,601 INFO L210 NwaCegarLoop]: Found error trace [2024-11-27 23:23:44,601 INFO L218 NwaCegarLoop]: trace histogram [19, 19, 11, 8, 7, 7, 7, 7, 7, 7, 7, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-27 23:23:44,612 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2024-11-27 23:23:44,801 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 7 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable6 [2024-11-27 23:23:44,803 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-27 23:23:44,803 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-27 23:23:44,803 INFO L85 PathProgramCache]: Analyzing trace with hash -1811622132, now seen corresponding path program 6 times [2024-11-27 23:23:44,803 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-27 23:23:44,803 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1487756581] [2024-11-27 23:23:44,803 INFO L95 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2024-11-27 23:23:44,803 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-27 23:23:44,887 INFO L229 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 14 check-sat command(s) [2024-11-27 23:23:44,887 INFO L230 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-27 23:23:45,397 INFO L134 CoverageAnalysis]: Checked inductivity of 835 backedges. 141 proven. 306 refuted. 0 times theorem prover too weak. 388 trivial. 0 not checked. [2024-11-27 23:23:45,397 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-27 23:23:45,397 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1487756581] [2024-11-27 23:23:45,397 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1487756581] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-27 23:23:45,397 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [699460486] [2024-11-27 23:23:45,398 INFO L95 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2024-11-27 23:23:45,398 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-27 23:23:45,398 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/z3 [2024-11-27 23:23:45,400 INFO L229 MonitoredProcess]: Starting monitored process 8 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-27 23:23:45,403 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2024-11-27 23:23:45,564 INFO L229 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 14 check-sat command(s) [2024-11-27 23:23:45,564 INFO L230 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-27 23:23:45,566 INFO L256 TraceCheckSpWp]: Trace formula consists of 402 conjuncts, 21 conjuncts are in the unsatisfiable core [2024-11-27 23:23:45,570 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-27 23:23:45,656 INFO L134 CoverageAnalysis]: Checked inductivity of 835 backedges. 475 proven. 114 refuted. 0 times theorem prover too weak. 246 trivial. 0 not checked. [2024-11-27 23:23:45,656 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-11-27 23:23:47,656 INFO L134 CoverageAnalysis]: Checked inductivity of 835 backedges. 155 proven. 295 refuted. 0 times theorem prover too weak. 385 trivial. 0 not checked. [2024-11-27 23:23:47,656 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [699460486] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-27 23:23:47,657 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-27 23:23:47,657 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 14, 17] total 22 [2024-11-27 23:23:47,657 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2124465768] [2024-11-27 23:23:47,657 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-27 23:23:47,657 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2024-11-27 23:23:47,658 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-27 23:23:47,658 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2024-11-27 23:23:47,659 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=81, Invalid=381, Unknown=0, NotChecked=0, Total=462 [2024-11-27 23:23:47,659 INFO L87 Difference]: Start difference. First operand 74 states and 92 transitions. Second operand has 22 states, 22 states have (on average 3.0454545454545454) internal successors, (67), 19 states have internal predecessors, (67), 12 states have call successors, (18), 2 states have call predecessors, (18), 11 states have return successors, (27), 11 states have call predecessors, (27), 12 states have call successors, (27) [2024-11-27 23:23:48,079 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-27 23:23:48,080 INFO L93 Difference]: Finished difference Result 131 states and 163 transitions. [2024-11-27 23:23:48,080 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 25 states. [2024-11-27 23:23:48,080 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 22 states have (on average 3.0454545454545454) internal successors, (67), 19 states have internal predecessors, (67), 12 states have call successors, (18), 2 states have call predecessors, (18), 11 states have return successors, (27), 11 states have call predecessors, (27), 12 states have call successors, (27) Word has length 131 [2024-11-27 23:23:48,081 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-27 23:23:48,082 INFO L225 Difference]: With dead ends: 131 [2024-11-27 23:23:48,082 INFO L226 Difference]: Without dead ends: 74 [2024-11-27 23:23:48,083 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 298 GetRequests, 249 SyntacticMatches, 11 SemanticMatches, 38 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 353 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=337, Invalid=1223, Unknown=0, NotChecked=0, Total=1560 [2024-11-27 23:23:48,084 INFO L435 NwaCegarLoop]: 22 mSDtfsCounter, 32 mSDsluCounter, 142 mSDsCounter, 0 mSdLazyCounter, 291 mSolverCounterSat, 43 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 37 SdHoareTripleChecker+Valid, 164 SdHoareTripleChecker+Invalid, 334 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 43 IncrementalHoareTripleChecker+Valid, 291 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-27 23:23:48,084 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [37 Valid, 164 Invalid, 334 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [43 Valid, 291 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-27 23:23:48,085 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 74 states. [2024-11-27 23:23:48,099 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 74 to 69. [2024-11-27 23:23:48,099 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 69 states, 47 states have (on average 1.0638297872340425) internal successors, (50), 48 states have internal predecessors, (50), 12 states have call successors, (12), 7 states have call predecessors, (12), 9 states have return successors, (19), 13 states have call predecessors, (19), 12 states have call successors, (19) [2024-11-27 23:23:48,100 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 69 states to 69 states and 81 transitions. [2024-11-27 23:23:48,100 INFO L78 Accepts]: Start accepts. Automaton has 69 states and 81 transitions. Word has length 131 [2024-11-27 23:23:48,101 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-27 23:23:48,101 INFO L471 AbstractCegarLoop]: Abstraction has 69 states and 81 transitions. [2024-11-27 23:23:48,101 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 22 states have (on average 3.0454545454545454) internal successors, (67), 19 states have internal predecessors, (67), 12 states have call successors, (18), 2 states have call predecessors, (18), 11 states have return successors, (27), 11 states have call predecessors, (27), 12 states have call successors, (27) [2024-11-27 23:23:48,101 INFO L276 IsEmpty]: Start isEmpty. Operand 69 states and 81 transitions. [2024-11-27 23:23:48,103 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 158 [2024-11-27 23:23:48,103 INFO L210 NwaCegarLoop]: Found error trace [2024-11-27 23:23:48,103 INFO L218 NwaCegarLoop]: trace histogram [23, 23, 13, 10, 9, 9, 9, 9, 9, 9, 9, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-27 23:23:48,113 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2024-11-27 23:23:48,308 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 8 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable7 [2024-11-27 23:23:48,308 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-27 23:23:48,308 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-27 23:23:48,309 INFO L85 PathProgramCache]: Analyzing trace with hash -1701842998, now seen corresponding path program 7 times [2024-11-27 23:23:48,309 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-27 23:23:48,309 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [285277973] [2024-11-27 23:23:48,309 INFO L95 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2024-11-27 23:23:48,309 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-27 23:23:48,354 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-27 23:23:49,102 INFO L134 CoverageAnalysis]: Checked inductivity of 1246 backedges. 439 proven. 281 refuted. 0 times theorem prover too weak. 526 trivial. 0 not checked. [2024-11-27 23:23:49,102 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-27 23:23:49,102 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [285277973] [2024-11-27 23:23:49,102 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [285277973] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-27 23:23:49,102 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1506822655] [2024-11-27 23:23:49,102 INFO L95 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2024-11-27 23:23:49,102 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-27 23:23:49,103 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/z3 [2024-11-27 23:23:49,107 INFO L229 MonitoredProcess]: Starting monitored process 9 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-27 23:23:49,109 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2024-11-27 23:23:49,298 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-27 23:23:49,301 INFO L256 TraceCheckSpWp]: Trace formula consists of 478 conjuncts, 35 conjuncts are in the unsatisfiable core [2024-11-27 23:23:49,306 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-27 23:23:49,412 INFO L134 CoverageAnalysis]: Checked inductivity of 1246 backedges. 421 proven. 286 refuted. 0 times theorem prover too weak. 539 trivial. 0 not checked. [2024-11-27 23:23:49,413 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-11-27 23:23:54,421 INFO L134 CoverageAnalysis]: Checked inductivity of 1246 backedges. 467 proven. 286 refuted. 0 times theorem prover too weak. 493 trivial. 0 not checked. [2024-11-27 23:23:54,421 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1506822655] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-27 23:23:54,421 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-27 23:23:54,421 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 20, 27] total 35 [2024-11-27 23:23:54,421 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1244277199] [2024-11-27 23:23:54,421 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-27 23:23:54,422 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 35 states [2024-11-27 23:23:54,422 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-27 23:23:54,423 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 35 interpolants. [2024-11-27 23:23:54,423 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=152, Invalid=1038, Unknown=0, NotChecked=0, Total=1190 [2024-11-27 23:23:54,423 INFO L87 Difference]: Start difference. First operand 69 states and 81 transitions. Second operand has 35 states, 35 states have (on average 2.142857142857143) internal successors, (75), 29 states have internal predecessors, (75), 14 states have call successors, (17), 1 states have call predecessors, (17), 17 states have return successors, (32), 17 states have call predecessors, (32), 14 states have call successors, (32) [2024-11-27 23:23:55,325 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-27 23:23:55,326 INFO L93 Difference]: Finished difference Result 134 states and 164 transitions. [2024-11-27 23:23:55,326 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 36 states. [2024-11-27 23:23:55,326 INFO L78 Accepts]: Start accepts. Automaton has has 35 states, 35 states have (on average 2.142857142857143) internal successors, (75), 29 states have internal predecessors, (75), 14 states have call successors, (17), 1 states have call predecessors, (17), 17 states have return successors, (32), 17 states have call predecessors, (32), 14 states have call successors, (32) Word has length 157 [2024-11-27 23:23:55,327 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-27 23:23:55,328 INFO L225 Difference]: With dead ends: 134 [2024-11-27 23:23:55,328 INFO L226 Difference]: Without dead ends: 90 [2024-11-27 23:23:55,330 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 374 GetRequests, 297 SyntacticMatches, 14 SemanticMatches, 63 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1090 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=761, Invalid=3399, Unknown=0, NotChecked=0, Total=4160 [2024-11-27 23:23:55,330 INFO L435 NwaCegarLoop]: 27 mSDtfsCounter, 55 mSDsluCounter, 235 mSDsCounter, 0 mSdLazyCounter, 538 mSolverCounterSat, 87 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 55 SdHoareTripleChecker+Valid, 262 SdHoareTripleChecker+Invalid, 625 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 87 IncrementalHoareTripleChecker+Valid, 538 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2024-11-27 23:23:55,331 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [55 Valid, 262 Invalid, 625 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [87 Valid, 538 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2024-11-27 23:23:55,331 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 90 states. [2024-11-27 23:23:55,342 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 90 to 74. [2024-11-27 23:23:55,342 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 74 states, 50 states have (on average 1.06) internal successors, (53), 51 states have internal predecessors, (53), 13 states have call successors, (13), 7 states have call predecessors, (13), 10 states have return successors, (23), 15 states have call predecessors, (23), 13 states have call successors, (23) [2024-11-27 23:23:55,343 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 74 states to 74 states and 89 transitions. [2024-11-27 23:23:55,343 INFO L78 Accepts]: Start accepts. Automaton has 74 states and 89 transitions. Word has length 157 [2024-11-27 23:23:55,344 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-27 23:23:55,344 INFO L471 AbstractCegarLoop]: Abstraction has 74 states and 89 transitions. [2024-11-27 23:23:55,344 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 35 states, 35 states have (on average 2.142857142857143) internal successors, (75), 29 states have internal predecessors, (75), 14 states have call successors, (17), 1 states have call predecessors, (17), 17 states have return successors, (32), 17 states have call predecessors, (32), 14 states have call successors, (32) [2024-11-27 23:23:55,344 INFO L276 IsEmpty]: Start isEmpty. Operand 74 states and 89 transitions. [2024-11-27 23:23:55,346 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 184 [2024-11-27 23:23:55,346 INFO L210 NwaCegarLoop]: Found error trace [2024-11-27 23:23:55,346 INFO L218 NwaCegarLoop]: trace histogram [27, 27, 15, 12, 11, 11, 11, 11, 11, 11, 11, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-27 23:23:55,356 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2024-11-27 23:23:55,551 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable8 [2024-11-27 23:23:55,551 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-27 23:23:55,551 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-27 23:23:55,551 INFO L85 PathProgramCache]: Analyzing trace with hash 332854534, now seen corresponding path program 8 times [2024-11-27 23:23:55,551 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-27 23:23:55,551 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [89944743] [2024-11-27 23:23:55,552 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-27 23:23:55,552 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-27 23:23:55,602 INFO L229 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-27 23:23:55,603 INFO L230 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-27 23:23:56,651 INFO L134 CoverageAnalysis]: Checked inductivity of 1741 backedges. 600 proven. 156 refuted. 0 times theorem prover too weak. 985 trivial. 0 not checked. [2024-11-27 23:23:56,651 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-27 23:23:56,652 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [89944743] [2024-11-27 23:23:56,652 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [89944743] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-27 23:23:56,652 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [457095362] [2024-11-27 23:23:56,652 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-27 23:23:56,652 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-27 23:23:56,652 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/z3 [2024-11-27 23:23:56,654 INFO L229 MonitoredProcess]: Starting monitored process 10 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-27 23:23:56,657 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2024-11-27 23:23:56,913 INFO L229 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-27 23:23:56,914 INFO L230 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-27 23:23:56,917 INFO L256 TraceCheckSpWp]: Trace formula consists of 554 conjuncts, 79 conjuncts are in the unsatisfiable core [2024-11-27 23:23:56,921 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-27 23:23:57,021 INFO L134 CoverageAnalysis]: Checked inductivity of 1741 backedges. 583 proven. 158 refuted. 0 times theorem prover too weak. 1000 trivial. 0 not checked. [2024-11-27 23:23:57,022 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-11-27 23:23:58,286 INFO L134 CoverageAnalysis]: Checked inductivity of 1741 backedges. 597 proven. 189 refuted. 0 times theorem prover too weak. 955 trivial. 0 not checked. [2024-11-27 23:23:58,286 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [457095362] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-27 23:23:58,286 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-27 23:23:58,286 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [25, 23, 33] total 36 [2024-11-27 23:23:58,287 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1231200752] [2024-11-27 23:23:58,287 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-27 23:23:58,287 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 36 states [2024-11-27 23:23:58,287 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-27 23:23:58,288 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 36 interpolants. [2024-11-27 23:23:58,288 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=89, Invalid=1171, Unknown=0, NotChecked=0, Total=1260 [2024-11-27 23:23:58,289 INFO L87 Difference]: Start difference. First operand 74 states and 89 transitions. Second operand has 36 states, 36 states have (on average 1.5555555555555556) internal successors, (56), 29 states have internal predecessors, (56), 6 states have call successors, (9), 1 states have call predecessors, (9), 14 states have return successors, (22), 13 states have call predecessors, (22), 6 states have call successors, (22) [2024-11-27 23:24:01,201 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-27 23:24:01,201 INFO L93 Difference]: Finished difference Result 158 states and 207 transitions. [2024-11-27 23:24:01,201 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 56 states. [2024-11-27 23:24:01,201 INFO L78 Accepts]: Start accepts. Automaton has has 36 states, 36 states have (on average 1.5555555555555556) internal successors, (56), 29 states have internal predecessors, (56), 6 states have call successors, (9), 1 states have call predecessors, (9), 14 states have return successors, (22), 13 states have call predecessors, (22), 6 states have call successors, (22) Word has length 183 [2024-11-27 23:24:01,202 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-27 23:24:01,204 INFO L225 Difference]: With dead ends: 158 [2024-11-27 23:24:01,204 INFO L226 Difference]: Without dead ends: 148 [2024-11-27 23:24:01,206 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 449 GetRequests, 365 SyntacticMatches, 0 SemanticMatches, 84 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1318 ImplicationChecksByTransitivity, 2.1s TimeCoverageRelationStatistics Valid=898, Invalid=6412, Unknown=0, NotChecked=0, Total=7310 [2024-11-27 23:24:01,210 INFO L435 NwaCegarLoop]: 42 mSDtfsCounter, 169 mSDsluCounter, 539 mSDsCounter, 0 mSdLazyCounter, 2560 mSolverCounterSat, 192 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 175 SdHoareTripleChecker+Valid, 581 SdHoareTripleChecker+Invalid, 2752 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 192 IncrementalHoareTripleChecker+Valid, 2560 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.2s IncrementalHoareTripleChecker+Time [2024-11-27 23:24:01,210 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [175 Valid, 581 Invalid, 2752 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [192 Valid, 2560 Invalid, 0 Unknown, 0 Unchecked, 1.2s Time] [2024-11-27 23:24:01,211 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 148 states. [2024-11-27 23:24:01,231 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 148 to 96. [2024-11-27 23:24:01,231 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 96 states, 64 states have (on average 1.046875) internal successors, (67), 65 states have internal predecessors, (67), 17 states have call successors, (17), 8 states have call predecessors, (17), 14 states have return successors, (43), 22 states have call predecessors, (43), 17 states have call successors, (43) [2024-11-27 23:24:01,234 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 96 states to 96 states and 127 transitions. [2024-11-27 23:24:01,234 INFO L78 Accepts]: Start accepts. Automaton has 96 states and 127 transitions. Word has length 183 [2024-11-27 23:24:01,236 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-27 23:24:01,237 INFO L471 AbstractCegarLoop]: Abstraction has 96 states and 127 transitions. [2024-11-27 23:24:01,238 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 36 states, 36 states have (on average 1.5555555555555556) internal successors, (56), 29 states have internal predecessors, (56), 6 states have call successors, (9), 1 states have call predecessors, (9), 14 states have return successors, (22), 13 states have call predecessors, (22), 6 states have call successors, (22) [2024-11-27 23:24:01,238 INFO L276 IsEmpty]: Start isEmpty. Operand 96 states and 127 transitions. [2024-11-27 23:24:01,241 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 171 [2024-11-27 23:24:01,241 INFO L210 NwaCegarLoop]: Found error trace [2024-11-27 23:24:01,241 INFO L218 NwaCegarLoop]: trace histogram [25, 25, 14, 11, 10, 10, 10, 10, 10, 10, 10, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-27 23:24:01,251 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2024-11-27 23:24:01,442 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2024-11-27 23:24:01,442 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-27 23:24:01,442 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-27 23:24:01,442 INFO L85 PathProgramCache]: Analyzing trace with hash -860565711, now seen corresponding path program 9 times [2024-11-27 23:24:01,443 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-27 23:24:01,443 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1797519649] [2024-11-27 23:24:01,443 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-27 23:24:01,443 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-27 23:24:01,495 INFO L229 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 16 check-sat command(s) [2024-11-27 23:24:01,495 INFO L230 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-27 23:24:03,067 INFO L134 CoverageAnalysis]: Checked inductivity of 1483 backedges. 607 proven. 353 refuted. 0 times theorem prover too weak. 523 trivial. 0 not checked. [2024-11-27 23:24:03,067 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-27 23:24:03,067 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1797519649] [2024-11-27 23:24:03,068 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1797519649] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-27 23:24:03,068 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1939609365] [2024-11-27 23:24:03,068 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-27 23:24:03,068 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-27 23:24:03,068 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/z3 [2024-11-27 23:24:03,070 INFO L229 MonitoredProcess]: Starting monitored process 11 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-27 23:24:03,073 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2024-11-27 23:24:03,338 INFO L229 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 16 check-sat command(s) [2024-11-27 23:24:03,338 INFO L230 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-27 23:24:03,341 INFO L256 TraceCheckSpWp]: Trace formula consists of 490 conjuncts, 37 conjuncts are in the unsatisfiable core [2024-11-27 23:24:03,345 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-27 23:24:03,560 INFO L134 CoverageAnalysis]: Checked inductivity of 1483 backedges. 477 proven. 372 refuted. 0 times theorem prover too weak. 634 trivial. 0 not checked. [2024-11-27 23:24:03,561 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-11-27 23:24:08,775 INFO L134 CoverageAnalysis]: Checked inductivity of 1483 backedges. 525 proven. 384 refuted. 0 times theorem prover too weak. 574 trivial. 0 not checked. [2024-11-27 23:24:08,776 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1939609365] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-27 23:24:08,776 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-27 23:24:08,776 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [34, 21, 28] total 46 [2024-11-27 23:24:08,776 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [583604622] [2024-11-27 23:24:08,776 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-27 23:24:08,777 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 46 states [2024-11-27 23:24:08,777 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-27 23:24:08,778 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 46 interpolants. [2024-11-27 23:24:08,778 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=320, Invalid=1750, Unknown=0, NotChecked=0, Total=2070 [2024-11-27 23:24:08,779 INFO L87 Difference]: Start difference. First operand 96 states and 127 transitions. Second operand has 46 states, 45 states have (on average 2.1333333333333333) internal successors, (96), 39 states have internal predecessors, (96), 20 states have call successors, (23), 1 states have call predecessors, (23), 22 states have return successors, (40), 21 states have call predecessors, (40), 20 states have call successors, (40) [2024-11-27 23:24:09,894 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-27 23:24:09,894 INFO L93 Difference]: Finished difference Result 212 states and 276 transitions. [2024-11-27 23:24:09,895 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 53 states. [2024-11-27 23:24:09,895 INFO L78 Accepts]: Start accepts. Automaton has has 46 states, 45 states have (on average 2.1333333333333333) internal successors, (96), 39 states have internal predecessors, (96), 20 states have call successors, (23), 1 states have call predecessors, (23), 22 states have return successors, (40), 21 states have call predecessors, (40), 20 states have call successors, (40) Word has length 170 [2024-11-27 23:24:09,896 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-27 23:24:09,897 INFO L225 Difference]: With dead ends: 212 [2024-11-27 23:24:09,897 INFO L226 Difference]: Without dead ends: 141 [2024-11-27 23:24:09,900 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 428 GetRequests, 322 SyntacticMatches, 19 SemanticMatches, 87 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2551 ImplicationChecksByTransitivity, 1.6s TimeCoverageRelationStatistics Valid=1306, Invalid=6526, Unknown=0, NotChecked=0, Total=7832 [2024-11-27 23:24:09,900 INFO L435 NwaCegarLoop]: 27 mSDtfsCounter, 111 mSDsluCounter, 222 mSDsCounter, 0 mSdLazyCounter, 604 mSolverCounterSat, 185 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 119 SdHoareTripleChecker+Valid, 249 SdHoareTripleChecker+Invalid, 789 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 185 IncrementalHoareTripleChecker+Valid, 604 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2024-11-27 23:24:09,915 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [119 Valid, 249 Invalid, 789 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [185 Valid, 604 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2024-11-27 23:24:09,916 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 141 states. [2024-11-27 23:24:09,946 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 141 to 105. [2024-11-27 23:24:09,946 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 105 states, 71 states have (on average 1.0422535211267605) internal successors, (74), 72 states have internal predecessors, (74), 17 states have call successors, (17), 11 states have call predecessors, (17), 16 states have return successors, (38), 21 states have call predecessors, (38), 17 states have call successors, (38) [2024-11-27 23:24:09,947 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 105 states to 105 states and 129 transitions. [2024-11-27 23:24:09,948 INFO L78 Accepts]: Start accepts. Automaton has 105 states and 129 transitions. Word has length 170 [2024-11-27 23:24:09,949 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-27 23:24:09,950 INFO L471 AbstractCegarLoop]: Abstraction has 105 states and 129 transitions. [2024-11-27 23:24:09,950 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 46 states, 45 states have (on average 2.1333333333333333) internal successors, (96), 39 states have internal predecessors, (96), 20 states have call successors, (23), 1 states have call predecessors, (23), 22 states have return successors, (40), 21 states have call predecessors, (40), 20 states have call successors, (40) [2024-11-27 23:24:09,950 INFO L276 IsEmpty]: Start isEmpty. Operand 105 states and 129 transitions. [2024-11-27 23:24:09,952 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 197 [2024-11-27 23:24:09,952 INFO L210 NwaCegarLoop]: Found error trace [2024-11-27 23:24:09,953 INFO L218 NwaCegarLoop]: trace histogram [29, 29, 16, 13, 12, 12, 12, 12, 12, 12, 12, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-27 23:24:09,962 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Ended with exit code 0 [2024-11-27 23:24:10,157 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2024-11-27 23:24:10,157 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-27 23:24:10,158 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-27 23:24:10,158 INFO L85 PathProgramCache]: Analyzing trace with hash 530318069, now seen corresponding path program 10 times [2024-11-27 23:24:10,158 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-27 23:24:10,158 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [597131344] [2024-11-27 23:24:10,158 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-27 23:24:10,158 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-27 23:24:10,214 INFO L229 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-27 23:24:10,214 INFO L230 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-27 23:24:11,237 INFO L134 CoverageAnalysis]: Checked inductivity of 2020 backedges. 651 proven. 554 refuted. 0 times theorem prover too weak. 815 trivial. 0 not checked. [2024-11-27 23:24:11,238 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-27 23:24:11,238 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [597131344] [2024-11-27 23:24:11,238 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [597131344] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-27 23:24:11,238 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [36116470] [2024-11-27 23:24:11,238 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-27 23:24:11,238 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-27 23:24:11,238 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/z3 [2024-11-27 23:24:11,240 INFO L229 MonitoredProcess]: Starting monitored process 12 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-27 23:24:11,245 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2024-11-27 23:24:11,568 INFO L229 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-27 23:24:11,568 INFO L230 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-27 23:24:11,571 INFO L256 TraceCheckSpWp]: Trace formula consists of 592 conjuncts, 41 conjuncts are in the unsatisfiable core [2024-11-27 23:24:11,577 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-27 23:24:11,737 INFO L134 CoverageAnalysis]: Checked inductivity of 2020 backedges. 647 proven. 519 refuted. 0 times theorem prover too weak. 854 trivial. 0 not checked. [2024-11-27 23:24:11,738 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-11-27 23:24:18,100 INFO L134 CoverageAnalysis]: Checked inductivity of 2020 backedges. 685 proven. 580 refuted. 0 times theorem prover too weak. 755 trivial. 0 not checked. [2024-11-27 23:24:18,101 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [36116470] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-27 23:24:18,101 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-27 23:24:18,101 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [24, 23, 32] total 35 [2024-11-27 23:24:18,101 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1315133843] [2024-11-27 23:24:18,101 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-27 23:24:18,102 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 35 states [2024-11-27 23:24:18,102 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-27 23:24:18,103 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 35 interpolants. [2024-11-27 23:24:18,103 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=174, Invalid=1016, Unknown=0, NotChecked=0, Total=1190 [2024-11-27 23:24:18,103 INFO L87 Difference]: Start difference. First operand 105 states and 129 transitions. Second operand has 35 states, 35 states have (on average 2.5428571428571427) internal successors, (89), 31 states have internal predecessors, (89), 20 states have call successors, (23), 1 states have call predecessors, (23), 18 states have return successors, (38), 17 states have call predecessors, (38), 20 states have call successors, (38) [2024-11-27 23:24:18,952 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-27 23:24:18,952 INFO L93 Difference]: Finished difference Result 220 states and 268 transitions. [2024-11-27 23:24:18,953 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 29 states. [2024-11-27 23:24:18,953 INFO L78 Accepts]: Start accepts. Automaton has has 35 states, 35 states have (on average 2.5428571428571427) internal successors, (89), 31 states have internal predecessors, (89), 20 states have call successors, (23), 1 states have call predecessors, (23), 18 states have return successors, (38), 17 states have call predecessors, (38), 20 states have call successors, (38) Word has length 196 [2024-11-27 23:24:18,953 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-27 23:24:18,955 INFO L225 Difference]: With dead ends: 220 [2024-11-27 23:24:18,955 INFO L226 Difference]: Without dead ends: 146 [2024-11-27 23:24:18,959 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 451 GetRequests, 374 SyntacticMatches, 21 SemanticMatches, 56 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 936 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=631, Invalid=2675, Unknown=0, NotChecked=0, Total=3306 [2024-11-27 23:24:18,959 INFO L435 NwaCegarLoop]: 33 mSDtfsCounter, 48 mSDsluCounter, 298 mSDsCounter, 0 mSdLazyCounter, 878 mSolverCounterSat, 39 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 49 SdHoareTripleChecker+Valid, 331 SdHoareTripleChecker+Invalid, 917 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 39 IncrementalHoareTripleChecker+Valid, 878 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2024-11-27 23:24:18,960 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [49 Valid, 331 Invalid, 917 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [39 Valid, 878 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2024-11-27 23:24:18,960 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 146 states. [2024-11-27 23:24:18,987 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 146 to 110. [2024-11-27 23:24:18,987 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 110 states, 74 states have (on average 1.0405405405405406) internal successors, (77), 75 states have internal predecessors, (77), 18 states have call successors, (18), 11 states have call predecessors, (18), 17 states have return successors, (40), 23 states have call predecessors, (40), 18 states have call successors, (40) [2024-11-27 23:24:18,989 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 110 states to 110 states and 135 transitions. [2024-11-27 23:24:18,989 INFO L78 Accepts]: Start accepts. Automaton has 110 states and 135 transitions. Word has length 196 [2024-11-27 23:24:18,989 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-27 23:24:18,990 INFO L471 AbstractCegarLoop]: Abstraction has 110 states and 135 transitions. [2024-11-27 23:24:18,990 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 35 states, 35 states have (on average 2.5428571428571427) internal successors, (89), 31 states have internal predecessors, (89), 20 states have call successors, (23), 1 states have call predecessors, (23), 18 states have return successors, (38), 17 states have call predecessors, (38), 20 states have call successors, (38) [2024-11-27 23:24:18,990 INFO L276 IsEmpty]: Start isEmpty. Operand 110 states and 135 transitions. [2024-11-27 23:24:18,993 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 210 [2024-11-27 23:24:18,993 INFO L210 NwaCegarLoop]: Found error trace [2024-11-27 23:24:18,993 INFO L218 NwaCegarLoop]: trace histogram [31, 31, 17, 14, 13, 13, 13, 13, 13, 13, 13, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-27 23:24:19,004 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2024-11-27 23:24:19,198 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11,12 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-27 23:24:19,198 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-27 23:24:19,198 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-27 23:24:19,198 INFO L85 PathProgramCache]: Analyzing trace with hash 660925528, now seen corresponding path program 11 times [2024-11-27 23:24:19,198 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-27 23:24:19,199 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [902551702] [2024-11-27 23:24:19,199 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2024-11-27 23:24:19,199 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-27 23:24:19,230 INFO L229 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 9 check-sat command(s) [2024-11-27 23:24:19,230 INFO L230 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-27 23:24:19,636 INFO L134 CoverageAnalysis]: Checked inductivity of 2320 backedges. 214 proven. 772 refuted. 0 times theorem prover too weak. 1334 trivial. 0 not checked. [2024-11-27 23:24:19,637 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-27 23:24:19,637 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [902551702] [2024-11-27 23:24:19,637 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [902551702] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-27 23:24:19,637 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1405281623] [2024-11-27 23:24:19,637 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2024-11-27 23:24:19,637 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-27 23:24:19,637 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/z3 [2024-11-27 23:24:19,640 INFO L229 MonitoredProcess]: Starting monitored process 13 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-27 23:24:19,643 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2024-11-27 23:24:19,995 INFO L229 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 9 check-sat command(s) [2024-11-27 23:24:19,995 INFO L230 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-27 23:24:19,997 INFO L256 TraceCheckSpWp]: Trace formula consists of 252 conjuncts, 45 conjuncts are in the unsatisfiable core [2024-11-27 23:24:20,004 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-27 23:24:20,087 INFO L134 CoverageAnalysis]: Checked inductivity of 2320 backedges. 1296 proven. 226 refuted. 0 times theorem prover too weak. 798 trivial. 0 not checked. [2024-11-27 23:24:20,087 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-11-27 23:24:21,219 INFO L134 CoverageAnalysis]: Checked inductivity of 2320 backedges. 224 proven. 778 refuted. 0 times theorem prover too weak. 1318 trivial. 0 not checked. [2024-11-27 23:24:21,219 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1405281623] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-27 23:24:21,219 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-27 23:24:21,219 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 15, 19] total 23 [2024-11-27 23:24:21,219 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1387556039] [2024-11-27 23:24:21,219 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-27 23:24:21,220 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2024-11-27 23:24:21,220 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-27 23:24:21,221 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2024-11-27 23:24:21,221 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=63, Invalid=443, Unknown=0, NotChecked=0, Total=506 [2024-11-27 23:24:21,221 INFO L87 Difference]: Start difference. First operand 110 states and 135 transitions. Second operand has 23 states, 22 states have (on average 3.1363636363636362) internal successors, (69), 20 states have internal predecessors, (69), 13 states have call successors, (20), 2 states have call predecessors, (20), 11 states have return successors, (29), 11 states have call predecessors, (29), 13 states have call successors, (29) [2024-11-27 23:24:21,976 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-27 23:24:21,977 INFO L93 Difference]: Finished difference Result 210 states and 265 transitions. [2024-11-27 23:24:21,977 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 30 states. [2024-11-27 23:24:21,978 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 22 states have (on average 3.1363636363636362) internal successors, (69), 20 states have internal predecessors, (69), 13 states have call successors, (20), 2 states have call predecessors, (20), 11 states have return successors, (29), 11 states have call predecessors, (29), 13 states have call successors, (29) Word has length 209 [2024-11-27 23:24:21,978 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-27 23:24:21,980 INFO L225 Difference]: With dead ends: 210 [2024-11-27 23:24:21,980 INFO L226 Difference]: Without dead ends: 127 [2024-11-27 23:24:21,982 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 464 GetRequests, 418 SyntacticMatches, 0 SemanticMatches, 46 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 312 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=416, Invalid=1840, Unknown=0, NotChecked=0, Total=2256 [2024-11-27 23:24:21,983 INFO L435 NwaCegarLoop]: 37 mSDtfsCounter, 72 mSDsluCounter, 289 mSDsCounter, 0 mSdLazyCounter, 601 mSolverCounterSat, 92 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 72 SdHoareTripleChecker+Valid, 326 SdHoareTripleChecker+Invalid, 693 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 92 IncrementalHoareTripleChecker+Valid, 601 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2024-11-27 23:24:21,983 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [72 Valid, 326 Invalid, 693 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [92 Valid, 601 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2024-11-27 23:24:21,984 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 127 states. [2024-11-27 23:24:22,009 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 127 to 116. [2024-11-27 23:24:22,010 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 116 states, 80 states have (on average 1.0375) internal successors, (83), 80 states have internal predecessors, (83), 19 states have call successors, (19), 14 states have call predecessors, (19), 16 states have return successors, (32), 21 states have call predecessors, (32), 19 states have call successors, (32) [2024-11-27 23:24:22,011 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 116 states to 116 states and 134 transitions. [2024-11-27 23:24:22,012 INFO L78 Accepts]: Start accepts. Automaton has 116 states and 134 transitions. Word has length 209 [2024-11-27 23:24:22,012 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-27 23:24:22,012 INFO L471 AbstractCegarLoop]: Abstraction has 116 states and 134 transitions. [2024-11-27 23:24:22,012 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 22 states have (on average 3.1363636363636362) internal successors, (69), 20 states have internal predecessors, (69), 13 states have call successors, (20), 2 states have call predecessors, (20), 11 states have return successors, (29), 11 states have call predecessors, (29), 13 states have call successors, (29) [2024-11-27 23:24:22,012 INFO L276 IsEmpty]: Start isEmpty. Operand 116 states and 134 transitions. [2024-11-27 23:24:22,017 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 282 [2024-11-27 23:24:22,017 INFO L210 NwaCegarLoop]: Found error trace [2024-11-27 23:24:22,017 INFO L218 NwaCegarLoop]: trace histogram [42, 42, 23, 19, 18, 18, 18, 18, 18, 18, 18, 5, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-27 23:24:22,027 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Ended with exit code 0 [2024-11-27 23:24:22,222 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2024-11-27 23:24:22,222 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-27 23:24:22,222 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-27 23:24:22,223 INFO L85 PathProgramCache]: Analyzing trace with hash 471385981, now seen corresponding path program 12 times [2024-11-27 23:24:22,223 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-27 23:24:22,223 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [367455206] [2024-11-27 23:24:22,223 INFO L95 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2024-11-27 23:24:22,223 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-27 23:24:22,313 INFO L229 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 23 check-sat command(s) [2024-11-27 23:24:22,313 INFO L230 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-27 23:24:22,561 INFO L134 CoverageAnalysis]: Checked inductivity of 4329 backedges. 210 proven. 402 refuted. 0 times theorem prover too weak. 3717 trivial. 0 not checked. [2024-11-27 23:24:22,561 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-27 23:24:22,561 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [367455206] [2024-11-27 23:24:22,561 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [367455206] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-27 23:24:22,561 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1012923470] [2024-11-27 23:24:22,561 INFO L95 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2024-11-27 23:24:22,561 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-27 23:24:22,562 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/z3 [2024-11-27 23:24:22,563 INFO L229 MonitoredProcess]: Starting monitored process 14 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-27 23:24:22,567 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2024-11-27 23:24:23,062 INFO L229 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 23 check-sat command(s) [2024-11-27 23:24:23,062 INFO L230 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-27 23:24:23,069 INFO L256 TraceCheckSpWp]: Trace formula consists of 777 conjuncts, 15 conjuncts are in the unsatisfiable core [2024-11-27 23:24:23,077 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-27 23:24:23,125 INFO L134 CoverageAnalysis]: Checked inductivity of 4329 backedges. 210 proven. 398 refuted. 0 times theorem prover too weak. 3721 trivial. 0 not checked. [2024-11-27 23:24:23,125 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-11-27 23:24:23,985 INFO L134 CoverageAnalysis]: Checked inductivity of 4329 backedges. 210 proven. 405 refuted. 0 times theorem prover too weak. 3714 trivial. 0 not checked. [2024-11-27 23:24:23,985 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1012923470] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-27 23:24:23,985 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-27 23:24:23,985 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 7, 9] total 11 [2024-11-27 23:24:23,986 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1965246316] [2024-11-27 23:24:23,986 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-27 23:24:23,986 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2024-11-27 23:24:23,986 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-27 23:24:23,987 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2024-11-27 23:24:23,987 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=83, Unknown=0, NotChecked=0, Total=110 [2024-11-27 23:24:23,987 INFO L87 Difference]: Start difference. First operand 116 states and 134 transitions. Second operand has 11 states, 11 states have (on average 3.727272727272727) internal successors, (41), 11 states have internal predecessors, (41), 7 states have call successors, (11), 1 states have call predecessors, (11), 4 states have return successors, (12), 5 states have call predecessors, (12), 7 states have call successors, (12) [2024-11-27 23:24:24,166 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-27 23:24:24,166 INFO L93 Difference]: Finished difference Result 119 states and 137 transitions. [2024-11-27 23:24:24,167 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2024-11-27 23:24:24,167 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 11 states have (on average 3.727272727272727) internal successors, (41), 11 states have internal predecessors, (41), 7 states have call successors, (11), 1 states have call predecessors, (11), 4 states have return successors, (12), 5 states have call predecessors, (12), 7 states have call successors, (12) Word has length 281 [2024-11-27 23:24:24,168 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-27 23:24:24,168 INFO L225 Difference]: With dead ends: 119 [2024-11-27 23:24:24,168 INFO L226 Difference]: Without dead ends: 0 [2024-11-27 23:24:24,169 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 576 GetRequests, 560 SyntacticMatches, 0 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 18 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=93, Invalid=213, Unknown=0, NotChecked=0, Total=306 [2024-11-27 23:24:24,169 INFO L435 NwaCegarLoop]: 31 mSDtfsCounter, 31 mSDsluCounter, 67 mSDsCounter, 0 mSdLazyCounter, 110 mSolverCounterSat, 31 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 31 SdHoareTripleChecker+Valid, 98 SdHoareTripleChecker+Invalid, 141 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 31 IncrementalHoareTripleChecker+Valid, 110 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-27 23:24:24,170 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [31 Valid, 98 Invalid, 141 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [31 Valid, 110 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-27 23:24:24,170 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 0 states. [2024-11-27 23:24:24,172 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 0 to 0. [2024-11-27 23:24:24,172 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 0 states, 0 states have (on average 0.0) internal successors, (0), 0 states have internal predecessors, (0), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-27 23:24:24,172 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 0 states to 0 states and 0 transitions. [2024-11-27 23:24:24,172 INFO L78 Accepts]: Start accepts. Automaton has 0 states and 0 transitions. Word has length 281 [2024-11-27 23:24:24,172 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-27 23:24:24,173 INFO L471 AbstractCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-27 23:24:24,173 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 11 states have (on average 3.727272727272727) internal successors, (41), 11 states have internal predecessors, (41), 7 states have call successors, (11), 1 states have call predecessors, (11), 4 states have return successors, (12), 5 states have call predecessors, (12), 7 states have call successors, (12) [2024-11-27 23:24:24,173 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2024-11-27 23:24:24,173 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2024-11-27 23:24:24,175 INFO L782 garLoopResultBuilder]: Registering result SAFE for location ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2024-11-27 23:24:24,188 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Ended with exit code 0 [2024-11-27 23:24:24,376 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2024-11-27 23:24:24,379 INFO L422 BasicCegarLoop]: Path program histogram: [12, 1, 1] [2024-11-27 23:24:24,381 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends 0 states and 0 transitions. [2024-11-27 23:24:40,427 INFO L170 ceAbstractionStarter]: Computing trace abstraction results [2024-11-27 23:24:40,432 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 27.11 11:24:40 BoogieIcfgContainer [2024-11-27 23:24:40,432 INFO L131 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2024-11-27 23:24:40,433 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2024-11-27 23:24:40,433 INFO L270 PluginConnector]: Initializing Witness Printer... [2024-11-27 23:24:40,433 INFO L274 PluginConnector]: Witness Printer initialized [2024-11-27 23:24:40,434 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 27.11 11:23:27" (3/4) ... [2024-11-27 23:24:40,436 INFO L146 WitnessPrinter]: Generating witness for correct program [2024-11-27 23:24:40,442 INFO L361 RCFGBacktranslator]: Ignoring RootEdge to procedure ackermann [2024-11-27 23:24:40,446 INFO L919 BoogieBacktranslator]: Reduced CFG by removing 11 nodes and edges [2024-11-27 23:24:40,446 INFO L919 BoogieBacktranslator]: Reduced CFG by removing 5 nodes and edges [2024-11-27 23:24:40,446 INFO L919 BoogieBacktranslator]: Reduced CFG by removing 3 nodes and edges [2024-11-27 23:24:40,446 INFO L919 BoogieBacktranslator]: Reduced CFG by removing 1 nodes and edges [2024-11-27 23:24:40,527 INFO L149 WitnessManager]: Wrote witness to /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/witness.graphml [2024-11-27 23:24:40,527 INFO L149 WitnessManager]: Wrote witness to /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/witness.yml [2024-11-27 23:24:40,527 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2024-11-27 23:24:40,528 INFO L158 Benchmark]: Toolchain (without parser) took 73427.80ms. Allocated memory was 117.4MB in the beginning and 906.0MB in the end (delta: 788.5MB). Free memory was 93.3MB in the beginning and 696.5MB in the end (delta: -603.2MB). Peak memory consumption was 184.5MB. Max. memory is 16.1GB. [2024-11-27 23:24:40,528 INFO L158 Benchmark]: CDTParser took 0.38ms. Allocated memory is still 117.4MB. Free memory is still 74.5MB. There was no memory consumed. Max. memory is 16.1GB. [2024-11-27 23:24:40,529 INFO L158 Benchmark]: CACSL2BoogieTranslator took 259.71ms. Allocated memory is still 117.4MB. Free memory was 93.0MB in the beginning and 82.2MB in the end (delta: 10.8MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2024-11-27 23:24:40,530 INFO L158 Benchmark]: Boogie Procedure Inliner took 37.82ms. Allocated memory is still 117.4MB. Free memory was 82.2MB in the beginning and 81.1MB in the end (delta: 1.1MB). There was no memory consumed. Max. memory is 16.1GB. [2024-11-27 23:24:40,530 INFO L158 Benchmark]: Boogie Preprocessor took 40.67ms. Allocated memory is still 117.4MB. Free memory was 81.1MB in the beginning and 80.1MB in the end (delta: 1.0MB). There was no memory consumed. Max. memory is 16.1GB. [2024-11-27 23:24:40,530 INFO L158 Benchmark]: RCFGBuilder took 283.54ms. Allocated memory is still 117.4MB. Free memory was 80.1MB in the beginning and 70.0MB in the end (delta: 10.1MB). Peak memory consumption was 16.8MB. Max. memory is 16.1GB. [2024-11-27 23:24:40,531 INFO L158 Benchmark]: TraceAbstraction took 72704.58ms. Allocated memory was 117.4MB in the beginning and 906.0MB in the end (delta: 788.5MB). Free memory was 69.4MB in the beginning and 700.9MB in the end (delta: -631.5MB). Peak memory consumption was 529.5MB. Max. memory is 16.1GB. [2024-11-27 23:24:40,531 INFO L158 Benchmark]: Witness Printer took 94.53ms. Allocated memory is still 906.0MB. Free memory was 700.9MB in the beginning and 696.5MB in the end (delta: 4.4MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2024-11-27 23:24:40,533 INFO L338 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.38ms. Allocated memory is still 117.4MB. Free memory is still 74.5MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 259.71ms. Allocated memory is still 117.4MB. Free memory was 93.0MB in the beginning and 82.2MB in the end (delta: 10.8MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 37.82ms. Allocated memory is still 117.4MB. Free memory was 82.2MB in the beginning and 81.1MB in the end (delta: 1.1MB). There was no memory consumed. Max. memory is 16.1GB. * Boogie Preprocessor took 40.67ms. Allocated memory is still 117.4MB. Free memory was 81.1MB in the beginning and 80.1MB in the end (delta: 1.0MB). There was no memory consumed. Max. memory is 16.1GB. * RCFGBuilder took 283.54ms. Allocated memory is still 117.4MB. Free memory was 80.1MB in the beginning and 70.0MB in the end (delta: 10.1MB). Peak memory consumption was 16.8MB. Max. memory is 16.1GB. * TraceAbstraction took 72704.58ms. Allocated memory was 117.4MB in the beginning and 906.0MB in the end (delta: 788.5MB). Free memory was 69.4MB in the beginning and 700.9MB in the end (delta: -631.5MB). Peak memory consumption was 529.5MB. Max. memory is 16.1GB. * Witness Printer took 94.53ms. Allocated memory is still 906.0MB. Free memory was 700.9MB in the beginning and 696.5MB in the end (delta: 4.4MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: ErrorAutomatonStatistics NumberErrorTraces: 0, NumberStatementsAllTraces: 0, NumberRelevantStatements: 0, 0.0s ErrorAutomatonConstructionTimeTotal, 0.0s FaulLocalizationTime, NumberStatementsFirstTrace: -1, TraceLengthAvg: 0, 0.0s ErrorAutomatonConstructionTimeAvg, 0.0s ErrorAutomatonDifferenceTimeAvg, 0.0s ErrorAutomatonDifferenceTimeTotal, NumberOfNoEnhancement: 0, NumberOfFiniteEnhancement: 0, NumberOfInfiniteEnhancement: 0 - PositiveResult [Line: 45]: a call to reach_error is unreachable For all program executions holds that a call to reach_error is unreachable at this location - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 23 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 56.6s, OverallIterations: 14, TraceHistogramMax: 42, PathProgramHistogramMax: 12, EmptinessCheckTime: 0.1s, AutomataDifference: 11.0s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 837 SdHoareTripleChecker+Valid, 4.8s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 794 mSDsluCounter, 2961 SdHoareTripleChecker+Invalid, 4.1s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 2548 mSDsCounter, 963 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 7263 IncrementalHoareTripleChecker+Invalid, 8226 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 963 mSolverCounterUnsat, 413 mSDtfsCounter, 7263 mSolverCounterSat, 0.1s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 4375 GetRequests, 3721 SyntacticMatches, 88 SemanticMatches, 566 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8287 ImplicationChecksByTransitivity, 9.9s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=116occurred in iteration=13, InterpolantAutomatonStates: 364, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.4s AutomataMinimizationTime, 14 MinimizatonAttempts, 340 StatesRemovedByMinimization, 12 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.3s SsaConstructionTime, 1.3s SatisfiabilityAnalysisTime, 38.8s InterpolantComputationTime, 3844 NumberOfCodeBlocks, 3228 NumberOfCodeBlocksAsserted, 169 NumberOfCheckSat, 5720 ConstructedInterpolants, 0 QuantifiedInterpolants, 10511 SizeOfPredicates, 50 NumberOfNonLiveVariables, 4887 ConjunctsInSsa, 345 ConjunctsInUnsatCore, 40 InterpolantComputations, 1 PerfectInterpolantSequences, 44157/53880 InterpolantCoveringCapability, INVARIANT_SYNTHESIS: No data available, INTERPOLANT_CONSOLIDATION: No data available, ABSTRACT_INTERPRETATION: No data available, PDR: No data available, ACCELERATED_INTERPOLATION: No data available, SIFA: No data available, ReuseStatistics: No data available, ConComCheckerStatistics: No data available - AllSpecificationsHoldResult: All specifications hold 1 specifications checked. All of them hold RESULT: Ultimate proved your program to be correct! [2024-11-27 23:24:40,556 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_570dfa06-3c68-42d4-bdcd-e60856dfe8a9/bin/uautomizer-verify-aQ6SnzHsRB/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Ended with exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Writing output log to file Ultimate.log Result: TRUE