./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/aws-c-common/aws_linked_list_push_back_harness.i --full-output --architecture 64bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 798a7b37 Calling Ultimate with: /root/.sdkman/candidates/java/21.0.5-tem/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.6.800.v20240513-1750.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/aws-c-common/aws_linked_list_push_back_harness.i -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-64bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux --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 64bit --witnessprinter.graph.data.programhash 4526081b0c55ba26ca543a72264ba075e2706c93c97faea07fd81ad62d180974 --- Real Ultimate output --- This is Ultimate 0.3.0-?-798a7b3-m [2025-03-04 02:59:07,387 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-03-04 02:59:07,430 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-64bit-Automizer_Default.epf [2025-03-04 02:59:07,434 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-03-04 02:59:07,435 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-03-04 02:59:07,449 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-03-04 02:59:07,449 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-03-04 02:59:07,450 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-03-04 02:59:07,450 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-03-04 02:59:07,450 INFO L153 SettingsManager]: * Use memory slicer=true [2025-03-04 02:59:07,450 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2025-03-04 02:59:07,450 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2025-03-04 02:59:07,450 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-03-04 02:59:07,451 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-03-04 02:59:07,451 INFO L153 SettingsManager]: * Use SBE=true [2025-03-04 02:59:07,451 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-03-04 02:59:07,451 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2025-03-04 02:59:07,451 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2025-03-04 02:59:07,451 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-03-04 02:59:07,451 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2025-03-04 02:59:07,451 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2025-03-04 02:59:07,451 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2025-03-04 02:59:07,452 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-03-04 02:59:07,452 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-03-04 02:59:07,452 INFO L153 SettingsManager]: * Use constant arrays=true [2025-03-04 02:59:07,452 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-03-04 02:59:07,452 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-03-04 02:59:07,452 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-03-04 02:59:07,452 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-03-04 02:59:07,452 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-04 02:59:07,452 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-03-04 02:59:07,453 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2025-03-04 02:59:07,453 INFO L153 SettingsManager]: * Compute procedure contracts=false [2025-03-04 02:59:07,453 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2025-03-04 02:59:07,453 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2025-03-04 02:59:07,453 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2025-03-04 02:59:07,453 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2025-03-04 02:59:07,453 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2025-03-04 02:59:07,453 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2025-03-04 02:59:07,453 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2025-03-04 02:59:07,453 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 -> /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux 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 -> 64bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> 4526081b0c55ba26ca543a72264ba075e2706c93c97faea07fd81ad62d180974 [2025-03-04 02:59:07,686 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-03-04 02:59:07,693 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-03-04 02:59:07,695 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-03-04 02:59:07,695 INFO L270 PluginConnector]: Initializing CDTParser... [2025-03-04 02:59:07,696 INFO L274 PluginConnector]: CDTParser initialized [2025-03-04 02:59:07,696 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/aws-c-common/aws_linked_list_push_back_harness.i [2025-03-04 02:59:08,794 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/3ae9b15ce/03aa607f386b40cf8768b8c24f6d1356/FLAG2fb965bbc [2025-03-04 02:59:09,229 INFO L384 CDTParser]: Found 1 translation units. [2025-03-04 02:59:09,230 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/aws-c-common/aws_linked_list_push_back_harness.i [2025-03-04 02:59:09,254 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/3ae9b15ce/03aa607f386b40cf8768b8c24f6d1356/FLAG2fb965bbc [2025-03-04 02:59:09,361 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/3ae9b15ce/03aa607f386b40cf8768b8c24f6d1356 [2025-03-04 02:59:09,362 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-03-04 02:59:09,363 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-03-04 02:59:09,364 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-03-04 02:59:09,364 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-03-04 02:59:09,367 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-03-04 02:59:09,367 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 04.03 02:59:09" (1/1) ... [2025-03-04 02:59:09,368 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@7692193e and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.03 02:59:09, skipping insertion in model container [2025-03-04 02:59:09,368 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 04.03 02:59:09" (1/1) ... [2025-03-04 02:59:09,428 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-03-04 02:59:09,594 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/aws-c-common/aws_linked_list_push_back_harness.i[4499,4512] [2025-03-04 02:59:09,599 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/aws-c-common/aws_linked_list_push_back_harness.i[4559,4572] [2025-03-04 02:59:09,967 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-04 02:59:09,972 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-04 02:59:09,972 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-04 02:59:09,973 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-04 02:59:09,973 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-04 02:59:09,983 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-04 02:59:09,983 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-04 02:59:09,984 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-04 02:59:09,985 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-04 02:59:09,986 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-04 02:59:09,986 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-04 02:59:09,987 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-04 02:59:09,987 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-04 02:59:10,283 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/aws-c-common/aws_linked_list_push_back_harness.i[150688,150701] [2025-03-04 02:59:10,284 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-04 02:59:10,295 INFO L200 MainTranslator]: Completed pre-run [2025-03-04 02:59:10,304 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/aws-c-common/aws_linked_list_push_back_harness.i[4499,4512] [2025-03-04 02:59:10,306 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/aws-c-common/aws_linked_list_push_back_harness.i[4559,4572] [2025-03-04 02:59:10,347 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-04 02:59:10,349 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-04 02:59:10,350 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-04 02:59:10,350 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-04 02:59:10,351 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-04 02:59:10,359 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-04 02:59:10,359 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-04 02:59:10,362 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-04 02:59:10,362 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-04 02:59:10,363 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-04 02:59:10,364 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-04 02:59:10,364 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-04 02:59:10,364 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-04 02:59:10,453 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/aws-c-common/aws_linked_list_push_back_harness.i[150688,150701] [2025-03-04 02:59:10,454 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-04 02:59:10,539 INFO L204 MainTranslator]: Completed translation [2025-03-04 02:59:10,540 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.03 02:59:10 WrapperNode [2025-03-04 02:59:10,540 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-03-04 02:59:10,540 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-03-04 02:59:10,541 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-03-04 02:59:10,541 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-03-04 02:59:10,544 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.03 02:59:10" (1/1) ... [2025-03-04 02:59:10,602 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.03 02:59:10" (1/1) ... [2025-03-04 02:59:10,637 INFO L138 Inliner]: procedures = 668, calls = 1046, calls flagged for inlining = 53, calls inlined = 6, statements flattened = 145 [2025-03-04 02:59:10,637 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-03-04 02:59:10,639 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-03-04 02:59:10,639 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-03-04 02:59:10,639 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-03-04 02:59:10,645 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.03 02:59:10" (1/1) ... [2025-03-04 02:59:10,645 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.03 02:59:10" (1/1) ... [2025-03-04 02:59:10,647 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.03 02:59:10" (1/1) ... [2025-03-04 02:59:10,664 INFO L175 MemorySlicer]: Split 35 memory accesses to 3 slices as follows [2, 5, 28]. 80 percent of accesses are in the largest equivalence class. The 7 initializations are split as follows [2, 5, 0]. The 10 writes are split as follows [0, 0, 10]. [2025-03-04 02:59:10,664 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.03 02:59:10" (1/1) ... [2025-03-04 02:59:10,664 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.03 02:59:10" (1/1) ... [2025-03-04 02:59:10,672 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.03 02:59:10" (1/1) ... [2025-03-04 02:59:10,672 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.03 02:59:10" (1/1) ... [2025-03-04 02:59:10,674 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.03 02:59:10" (1/1) ... [2025-03-04 02:59:10,679 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.03 02:59:10" (1/1) ... [2025-03-04 02:59:10,687 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-03-04 02:59:10,689 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2025-03-04 02:59:10,689 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2025-03-04 02:59:10,690 INFO L274 PluginConnector]: IcfgBuilder initialized [2025-03-04 02:59:10,690 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.03 02:59:10" (1/1) ... [2025-03-04 02:59:10,693 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-04 02:59:10,703 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 02:59:10,718 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2025-03-04 02:59:10,719 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2025-03-04 02:59:10,734 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2025-03-04 02:59:10,734 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2025-03-04 02:59:10,734 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2025-03-04 02:59:10,734 INFO L130 BoogieDeclarations]: Found specification of procedure aws_linked_list_node_next_is_valid [2025-03-04 02:59:10,734 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_linked_list_node_next_is_valid [2025-03-04 02:59:10,734 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnHeap [2025-03-04 02:59:10,734 INFO L130 BoogieDeclarations]: Found specification of procedure aws_linked_list_is_valid [2025-03-04 02:59:10,734 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_linked_list_is_valid [2025-03-04 02:59:10,734 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2025-03-04 02:59:10,734 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$#0 [2025-03-04 02:59:10,734 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$#1 [2025-03-04 02:59:10,734 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$#2 [2025-03-04 02:59:10,734 INFO L130 BoogieDeclarations]: Found specification of procedure aws_linked_list_insert_before [2025-03-04 02:59:10,734 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_linked_list_insert_before [2025-03-04 02:59:10,734 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-03-04 02:59:10,734 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-03-04 02:59:10,734 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2025-03-04 02:59:10,734 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2025-03-04 02:59:10,734 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2025-03-04 02:59:10,734 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$#0 [2025-03-04 02:59:10,734 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$#1 [2025-03-04 02:59:10,734 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$#2 [2025-03-04 02:59:10,734 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$#0 [2025-03-04 02:59:10,734 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$#1 [2025-03-04 02:59:10,734 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$#2 [2025-03-04 02:59:10,734 INFO L130 BoogieDeclarations]: Found specification of procedure nondet_uint64_t [2025-03-04 02:59:10,734 INFO L138 BoogieDeclarations]: Found implementation of procedure nondet_uint64_t [2025-03-04 02:59:10,735 INFO L130 BoogieDeclarations]: Found specification of procedure aws_linked_list_node_prev_is_valid [2025-03-04 02:59:10,735 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_linked_list_node_prev_is_valid [2025-03-04 02:59:10,735 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2025-03-04 02:59:10,735 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#1 [2025-03-04 02:59:10,735 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#2 [2025-03-04 02:59:10,908 INFO L256 CfgBuilder]: Building ICFG [2025-03-04 02:59:10,909 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2025-03-04 02:59:10,954 INFO L1325 $ProcedureCfgBuilder]: dead code at ProgramPoint L4718: havoc #t~mem312.base, #t~mem312.offset;havoc #t~short313;havoc #t~mem314.base, #t~mem314.offset;havoc #t~mem315.base, #t~mem315.offset;havoc #t~short316; [2025-03-04 02:59:10,975 INFO L1325 $ProcedureCfgBuilder]: dead code at ProgramPoint L4729: havoc #t~mem317.base, #t~mem317.offset;havoc #t~short318;havoc #t~mem319.base, #t~mem319.offset;havoc #t~mem320.base, #t~mem320.offset;havoc #t~short321; [2025-03-04 02:59:10,986 INFO L1325 $ProcedureCfgBuilder]: dead code at ProgramPoint L266: havoc #t~nondet9; [2025-03-04 02:59:11,142 INFO L1325 $ProcedureCfgBuilder]: dead code at ProgramPoint L4700: havoc #t~ret311#1; [2025-03-04 02:59:11,170 INFO L? ?]: Removed 66 outVars from TransFormulas that were not future-live. [2025-03-04 02:59:11,170 INFO L307 CfgBuilder]: Performing block encoding [2025-03-04 02:59:11,176 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-03-04 02:59:11,176 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2025-03-04 02:59:11,177 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 04.03 02:59:11 BoogieIcfgContainer [2025-03-04 02:59:11,177 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2025-03-04 02:59:11,178 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2025-03-04 02:59:11,178 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2025-03-04 02:59:11,182 INFO L274 PluginConnector]: TraceAbstraction initialized [2025-03-04 02:59:11,182 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 04.03 02:59:09" (1/3) ... [2025-03-04 02:59:11,183 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6580686 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 04.03 02:59:11, skipping insertion in model container [2025-03-04 02:59:11,183 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.03 02:59:10" (2/3) ... [2025-03-04 02:59:11,183 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6580686 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 04.03 02:59:11, skipping insertion in model container [2025-03-04 02:59:11,183 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 04.03 02:59:11" (3/3) ... [2025-03-04 02:59:11,184 INFO L128 eAbstractionObserver]: Analyzing ICFG aws_linked_list_push_back_harness.i [2025-03-04 02:59:11,193 INFO L216 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2025-03-04 02:59:11,194 INFO L151 ceAbstractionStarter]: Applying trace abstraction to ICFG aws_linked_list_push_back_harness.i that has 8 procedures, 101 locations, 1 initial locations, 2 loop locations, and 1 error locations. [2025-03-04 02:59:11,233 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2025-03-04 02:59:11,242 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;@2832d2d8, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2025-03-04 02:59:11,244 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2025-03-04 02:59:11,247 INFO L276 IsEmpty]: Start isEmpty. Operand has 101 states, 64 states have (on average 1.265625) internal successors, (81), 65 states have internal predecessors, (81), 28 states have call successors, (28), 7 states have call predecessors, (28), 7 states have return successors, (28), 28 states have call predecessors, (28), 28 states have call successors, (28) [2025-03-04 02:59:11,252 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 74 [2025-03-04 02:59:11,252 INFO L210 NwaCegarLoop]: Found error trace [2025-03-04 02:59:11,252 INFO L218 NwaCegarLoop]: trace histogram [5, 5, 5, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-04 02:59:11,253 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-04 02:59:11,256 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 02:59:11,256 INFO L85 PathProgramCache]: Analyzing trace with hash 1171475621, now seen corresponding path program 1 times [2025-03-04 02:59:11,260 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-04 02:59:11,260 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2098008352] [2025-03-04 02:59:11,261 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-04 02:59:11,261 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-04 02:59:11,377 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 73 statements into 1 equivalence classes. [2025-03-04 02:59:11,398 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 73 of 73 statements. [2025-03-04 02:59:11,399 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 02:59:11,399 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 02:59:11,543 INFO L134 CoverageAnalysis]: Checked inductivity of 47 backedges. 0 proven. 8 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2025-03-04 02:59:11,543 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-04 02:59:11,543 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2098008352] [2025-03-04 02:59:11,544 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2098008352] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-04 02:59:11,544 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1538145947] [2025-03-04 02:59:11,544 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-04 02:59:11,544 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-04 02:59:11,544 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 02:59:11,546 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-04 02:59:11,548 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2025-03-04 02:59:11,646 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 73 statements into 1 equivalence classes. [2025-03-04 02:59:11,699 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 73 of 73 statements. [2025-03-04 02:59:11,700 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 02:59:11,700 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 02:59:11,702 INFO L256 TraceCheckSpWp]: Trace formula consists of 422 conjuncts, 1 conjuncts are in the unsatisfiable core [2025-03-04 02:59:11,706 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-04 02:59:11,719 INFO L134 CoverageAnalysis]: Checked inductivity of 47 backedges. 8 proven. 0 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2025-03-04 02:59:11,720 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-04 02:59:11,720 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1538145947] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-04 02:59:11,721 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-03-04 02:59:11,721 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [2] total 2 [2025-03-04 02:59:11,722 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [944192605] [2025-03-04 02:59:11,722 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-04 02:59:11,724 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2025-03-04 02:59:11,725 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-04 02:59:11,736 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2025-03-04 02:59:11,736 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2025-03-04 02:59:11,738 INFO L87 Difference]: Start difference. First operand has 101 states, 64 states have (on average 1.265625) internal successors, (81), 65 states have internal predecessors, (81), 28 states have call successors, (28), 7 states have call predecessors, (28), 7 states have return successors, (28), 28 states have call predecessors, (28), 28 states have call successors, (28) Second operand has 2 states, 2 states have (on average 18.5) internal successors, (37), 2 states have internal predecessors, (37), 2 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) [2025-03-04 02:59:11,763 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-04 02:59:11,763 INFO L93 Difference]: Finished difference Result 194 states and 282 transitions. [2025-03-04 02:59:11,764 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2025-03-04 02:59:11,765 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 18.5) internal successors, (37), 2 states have internal predecessors, (37), 2 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) Word has length 73 [2025-03-04 02:59:11,765 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-04 02:59:11,769 INFO L225 Difference]: With dead ends: 194 [2025-03-04 02:59:11,769 INFO L226 Difference]: Without dead ends: 96 [2025-03-04 02:59:11,773 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 74 GetRequests, 74 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2025-03-04 02:59:11,776 INFO L435 NwaCegarLoop]: 135 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 0 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 135 SdHoareTripleChecker+Invalid, 0 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 0 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-04 02:59:11,777 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 135 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-04 02:59:11,785 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 96 states. [2025-03-04 02:59:11,800 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 96 to 96. [2025-03-04 02:59:11,801 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 96 states, 60 states have (on average 1.25) internal successors, (75), 61 states have internal predecessors, (75), 28 states have call successors, (28), 7 states have call predecessors, (28), 7 states have return successors, (27), 27 states have call predecessors, (27), 27 states have call successors, (27) [2025-03-04 02:59:11,804 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 96 states to 96 states and 130 transitions. [2025-03-04 02:59:11,807 INFO L78 Accepts]: Start accepts. Automaton has 96 states and 130 transitions. Word has length 73 [2025-03-04 02:59:11,808 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-04 02:59:11,808 INFO L471 AbstractCegarLoop]: Abstraction has 96 states and 130 transitions. [2025-03-04 02:59:11,808 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 18.5) internal successors, (37), 2 states have internal predecessors, (37), 2 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) [2025-03-04 02:59:11,808 INFO L276 IsEmpty]: Start isEmpty. Operand 96 states and 130 transitions. [2025-03-04 02:59:11,810 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 74 [2025-03-04 02:59:11,811 INFO L210 NwaCegarLoop]: Found error trace [2025-03-04 02:59:11,811 INFO L218 NwaCegarLoop]: trace histogram [5, 5, 5, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-04 02:59:11,818 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2025-03-04 02:59:12,011 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable0 [2025-03-04 02:59:12,012 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-04 02:59:12,013 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 02:59:12,013 INFO L85 PathProgramCache]: Analyzing trace with hash 624241476, now seen corresponding path program 1 times [2025-03-04 02:59:12,013 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-04 02:59:12,013 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2095963537] [2025-03-04 02:59:12,014 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-04 02:59:12,014 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-04 02:59:12,063 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 73 statements into 1 equivalence classes. [2025-03-04 02:59:12,081 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 73 of 73 statements. [2025-03-04 02:59:12,081 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 02:59:12,082 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 02:59:12,248 INFO L134 CoverageAnalysis]: Checked inductivity of 47 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 47 trivial. 0 not checked. [2025-03-04 02:59:12,248 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-04 02:59:12,248 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2095963537] [2025-03-04 02:59:12,248 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2095963537] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-04 02:59:12,248 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-04 02:59:12,248 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2025-03-04 02:59:12,248 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [399991838] [2025-03-04 02:59:12,249 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-04 02:59:12,249 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2025-03-04 02:59:12,249 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-04 02:59:12,250 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2025-03-04 02:59:12,250 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2025-03-04 02:59:12,250 INFO L87 Difference]: Start difference. First operand 96 states and 130 transitions. Second operand has 4 states, 4 states have (on average 8.75) internal successors, (35), 4 states have internal predecessors, (35), 2 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) [2025-03-04 02:59:12,287 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-04 02:59:12,287 INFO L93 Difference]: Finished difference Result 183 states and 253 transitions. [2025-03-04 02:59:12,289 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2025-03-04 02:59:12,289 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 8.75) internal successors, (35), 4 states have internal predecessors, (35), 2 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) Word has length 73 [2025-03-04 02:59:12,290 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-04 02:59:12,291 INFO L225 Difference]: With dead ends: 183 [2025-03-04 02:59:12,291 INFO L226 Difference]: Without dead ends: 99 [2025-03-04 02:59:12,291 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2025-03-04 02:59:12,292 INFO L435 NwaCegarLoop]: 127 mSDtfsCounter, 1 mSDsluCounter, 248 mSDsCounter, 0 mSdLazyCounter, 13 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1 SdHoareTripleChecker+Valid, 375 SdHoareTripleChecker+Invalid, 15 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 13 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-04 02:59:12,292 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [1 Valid, 375 Invalid, 15 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 13 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-04 02:59:12,292 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 99 states. [2025-03-04 02:59:12,302 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 99 to 99. [2025-03-04 02:59:12,303 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 99 states, 63 states have (on average 1.2380952380952381) internal successors, (78), 64 states have internal predecessors, (78), 28 states have call successors, (28), 7 states have call predecessors, (28), 7 states have return successors, (27), 27 states have call predecessors, (27), 27 states have call successors, (27) [2025-03-04 02:59:12,307 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 99 states to 99 states and 133 transitions. [2025-03-04 02:59:12,307 INFO L78 Accepts]: Start accepts. Automaton has 99 states and 133 transitions. Word has length 73 [2025-03-04 02:59:12,308 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-04 02:59:12,308 INFO L471 AbstractCegarLoop]: Abstraction has 99 states and 133 transitions. [2025-03-04 02:59:12,308 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 8.75) internal successors, (35), 4 states have internal predecessors, (35), 2 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) [2025-03-04 02:59:12,308 INFO L276 IsEmpty]: Start isEmpty. Operand 99 states and 133 transitions. [2025-03-04 02:59:12,309 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 74 [2025-03-04 02:59:12,309 INFO L210 NwaCegarLoop]: Found error trace [2025-03-04 02:59:12,309 INFO L218 NwaCegarLoop]: trace histogram [5, 5, 5, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-04 02:59:12,309 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2025-03-04 02:59:12,310 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-04 02:59:12,310 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 02:59:12,310 INFO L85 PathProgramCache]: Analyzing trace with hash 383701347, now seen corresponding path program 1 times [2025-03-04 02:59:12,310 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-04 02:59:12,310 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [851326841] [2025-03-04 02:59:12,310 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-04 02:59:12,310 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-04 02:59:12,340 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 73 statements into 1 equivalence classes. [2025-03-04 02:59:12,410 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 73 of 73 statements. [2025-03-04 02:59:12,411 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 02:59:12,411 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 02:59:12,790 INFO L134 CoverageAnalysis]: Checked inductivity of 47 backedges. 3 proven. 9 refuted. 0 times theorem prover too weak. 35 trivial. 0 not checked. [2025-03-04 02:59:12,791 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-04 02:59:12,791 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [851326841] [2025-03-04 02:59:12,791 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [851326841] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-04 02:59:12,791 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [29311548] [2025-03-04 02:59:12,791 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-04 02:59:12,791 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-04 02:59:12,791 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 02:59:12,794 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-04 02:59:12,796 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2025-03-04 02:59:12,913 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 73 statements into 1 equivalence classes. [2025-03-04 02:59:12,968 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 73 of 73 statements. [2025-03-04 02:59:12,969 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 02:59:12,969 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 02:59:12,972 INFO L256 TraceCheckSpWp]: Trace formula consists of 417 conjuncts, 110 conjuncts are in the unsatisfiable core [2025-03-04 02:59:12,978 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-04 02:59:13,026 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 10 treesize of output 8 [2025-03-04 02:59:13,157 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 3 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 15 [2025-03-04 02:59:13,164 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 9 treesize of output 12 [2025-03-04 02:59:13,169 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 1 [2025-03-04 02:59:14,083 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-04 02:59:14,089 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 3 new quantified variables, introduced 0 case distinctions, treesize of input 216 treesize of output 188 [2025-03-04 02:59:14,095 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-04 02:59:14,099 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 132 treesize of output 85 [2025-03-04 02:59:14,104 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 60 treesize of output 52 [2025-03-04 02:59:14,107 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 1 [2025-03-04 02:59:14,115 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 53 treesize of output 47 [2025-03-04 02:59:14,119 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2025-03-04 02:59:14,122 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 1 [2025-03-04 02:59:14,651 INFO L134 CoverageAnalysis]: Checked inductivity of 47 backedges. 19 proven. 13 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2025-03-04 02:59:14,652 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-04 02:59:19,099 WARN L851 $PredicateComparison]: unable to prove that (let ((.cse4 (select |c_#memory_$Pointer$#2.base| c_aws_linked_list_insert_before_~to_add.base)) (.cse1 (+ 8 c_aws_linked_list_insert_before_~before.offset))) (and (forall ((aws_linked_list_insert_before_~to_add.offset Int) (v_ArrVal_342 (Array Int Int))) (= (select (select (let ((.cse0 (let ((.cse2 (store |c_#memory_$Pointer$#2.base| c_aws_linked_list_insert_before_~to_add.base (let ((.cse3 (store .cse4 aws_linked_list_insert_before_~to_add.offset c_aws_linked_list_insert_before_~before.base))) (store .cse3 (+ aws_linked_list_insert_before_~to_add.offset 8) (select (select (store |c_#memory_$Pointer$#2.base| c_aws_linked_list_insert_before_~to_add.base .cse3) c_aws_linked_list_insert_before_~before.base) .cse1)))))) (store .cse2 (select (select .cse2 c_aws_linked_list_insert_before_~before.base) .cse1) v_ArrVal_342)))) (store .cse0 c_aws_linked_list_insert_before_~before.base (store (select .cse0 c_aws_linked_list_insert_before_~before.base) .cse1 c_aws_linked_list_insert_before_~to_add.base))) c_aws_linked_list_insert_before_~to_add.base) aws_linked_list_insert_before_~to_add.offset) c_aws_linked_list_insert_before_~before.base)) (forall ((aws_linked_list_insert_before_~to_add.offset Int) (v_ArrVal_340 (Array Int Int))) (= c_aws_linked_list_insert_before_~before.offset (select (select (let ((.cse5 (let ((.cse7 (+ aws_linked_list_insert_before_~to_add.offset 8))) (store (store |c_#memory_$Pointer$#2.offset| c_aws_linked_list_insert_before_~to_add.base (let ((.cse6 (store (select |c_#memory_$Pointer$#2.offset| c_aws_linked_list_insert_before_~to_add.base) aws_linked_list_insert_before_~to_add.offset c_aws_linked_list_insert_before_~before.offset))) (store .cse6 .cse7 (select (select (store |c_#memory_$Pointer$#2.offset| c_aws_linked_list_insert_before_~to_add.base .cse6) c_aws_linked_list_insert_before_~before.base) .cse1)))) (select (select (store |c_#memory_$Pointer$#2.base| c_aws_linked_list_insert_before_~to_add.base (let ((.cse8 (store .cse4 aws_linked_list_insert_before_~to_add.offset c_aws_linked_list_insert_before_~before.base))) (store .cse8 .cse7 (select (select (store |c_#memory_$Pointer$#2.base| c_aws_linked_list_insert_before_~to_add.base .cse8) c_aws_linked_list_insert_before_~before.base) .cse1)))) c_aws_linked_list_insert_before_~before.base) .cse1) v_ArrVal_340)))) (store .cse5 c_aws_linked_list_insert_before_~before.base (store (select .cse5 c_aws_linked_list_insert_before_~before.base) .cse1 aws_linked_list_insert_before_~to_add.offset))) c_aws_linked_list_insert_before_~to_add.base) aws_linked_list_insert_before_~to_add.offset))))) is different from false [2025-03-04 02:59:19,126 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [29311548] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-04 02:59:19,127 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-04 02:59:19,127 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 21] total 25 [2025-03-04 02:59:19,127 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1524304322] [2025-03-04 02:59:19,127 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-04 02:59:19,127 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 25 states [2025-03-04 02:59:19,127 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-04 02:59:19,128 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2025-03-04 02:59:19,128 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=85, Invalid=910, Unknown=1, NotChecked=60, Total=1056 [2025-03-04 02:59:19,128 INFO L87 Difference]: Start difference. First operand 99 states and 133 transitions. Second operand has 25 states, 22 states have (on average 3.590909090909091) internal successors, (79), 20 states have internal predecessors, (79), 8 states have call successors, (22), 6 states have call predecessors, (22), 6 states have return successors, (18), 7 states have call predecessors, (18), 7 states have call successors, (18) [2025-03-04 02:59:21,823 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-04 02:59:21,823 INFO L93 Difference]: Finished difference Result 333 states and 449 transitions. [2025-03-04 02:59:21,823 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 29 states. [2025-03-04 02:59:21,823 INFO L78 Accepts]: Start accepts. Automaton has has 25 states, 22 states have (on average 3.590909090909091) internal successors, (79), 20 states have internal predecessors, (79), 8 states have call successors, (22), 6 states have call predecessors, (22), 6 states have return successors, (18), 7 states have call predecessors, (18), 7 states have call successors, (18) Word has length 73 [2025-03-04 02:59:21,823 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-04 02:59:21,826 INFO L225 Difference]: With dead ends: 333 [2025-03-04 02:59:21,826 INFO L226 Difference]: Without dead ends: 239 [2025-03-04 02:59:21,828 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 125 GetRequests, 57 SyntacticMatches, 11 SemanticMatches, 57 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 703 ImplicationChecksByTransitivity, 5.9s TimeCoverageRelationStatistics Valid=263, Invalid=3046, Unknown=1, NotChecked=112, Total=3422 [2025-03-04 02:59:21,830 INFO L435 NwaCegarLoop]: 131 mSDtfsCounter, 299 mSDsluCounter, 1896 mSDsCounter, 0 mSdLazyCounter, 1302 mSolverCounterSat, 131 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 306 SdHoareTripleChecker+Valid, 2027 SdHoareTripleChecker+Invalid, 1433 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 131 IncrementalHoareTripleChecker+Valid, 1302 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.8s IncrementalHoareTripleChecker+Time [2025-03-04 02:59:21,830 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [306 Valid, 2027 Invalid, 1433 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [131 Valid, 1302 Invalid, 0 Unknown, 0 Unchecked, 1.8s Time] [2025-03-04 02:59:21,831 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 239 states. [2025-03-04 02:59:21,856 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 239 to 229. [2025-03-04 02:59:21,857 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 229 states, 153 states have (on average 1.261437908496732) internal successors, (193), 157 states have internal predecessors, (193), 56 states have call successors, (56), 17 states have call predecessors, (56), 19 states have return successors, (59), 54 states have call predecessors, (59), 54 states have call successors, (59) [2025-03-04 02:59:21,858 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 229 states to 229 states and 308 transitions. [2025-03-04 02:59:21,859 INFO L78 Accepts]: Start accepts. Automaton has 229 states and 308 transitions. Word has length 73 [2025-03-04 02:59:21,859 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-04 02:59:21,859 INFO L471 AbstractCegarLoop]: Abstraction has 229 states and 308 transitions. [2025-03-04 02:59:21,859 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 25 states, 22 states have (on average 3.590909090909091) internal successors, (79), 20 states have internal predecessors, (79), 8 states have call successors, (22), 6 states have call predecessors, (22), 6 states have return successors, (18), 7 states have call predecessors, (18), 7 states have call successors, (18) [2025-03-04 02:59:21,859 INFO L276 IsEmpty]: Start isEmpty. Operand 229 states and 308 transitions. [2025-03-04 02:59:21,864 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 75 [2025-03-04 02:59:21,865 INFO L210 NwaCegarLoop]: Found error trace [2025-03-04 02:59:21,865 INFO L218 NwaCegarLoop]: trace histogram [5, 5, 5, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-04 02:59:21,873 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2025-03-04 02:59:22,065 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable2 [2025-03-04 02:59:22,066 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-04 02:59:22,066 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 02:59:22,066 INFO L85 PathProgramCache]: Analyzing trace with hash -367753902, now seen corresponding path program 1 times [2025-03-04 02:59:22,066 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-04 02:59:22,066 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1092308569] [2025-03-04 02:59:22,066 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-04 02:59:22,066 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-04 02:59:22,085 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 74 statements into 1 equivalence classes. [2025-03-04 02:59:22,092 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 74 of 74 statements. [2025-03-04 02:59:22,092 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 02:59:22,092 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 02:59:22,317 INFO L134 CoverageAnalysis]: Checked inductivity of 47 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 47 trivial. 0 not checked. [2025-03-04 02:59:22,317 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-04 02:59:22,317 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1092308569] [2025-03-04 02:59:22,317 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1092308569] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-04 02:59:22,317 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-04 02:59:22,317 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2025-03-04 02:59:22,317 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [680193811] [2025-03-04 02:59:22,317 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-04 02:59:22,317 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2025-03-04 02:59:22,318 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-04 02:59:22,318 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2025-03-04 02:59:22,318 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2025-03-04 02:59:22,318 INFO L87 Difference]: Start difference. First operand 229 states and 308 transitions. Second operand has 8 states, 7 states have (on average 5.285714285714286) internal successors, (37), 8 states have internal predecessors, (37), 3 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (9), 2 states have call predecessors, (9), 3 states have call successors, (9) [2025-03-04 02:59:22,412 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-04 02:59:22,412 INFO L93 Difference]: Finished difference Result 481 states and 656 transitions. [2025-03-04 02:59:22,412 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2025-03-04 02:59:22,412 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 7 states have (on average 5.285714285714286) internal successors, (37), 8 states have internal predecessors, (37), 3 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (9), 2 states have call predecessors, (9), 3 states have call successors, (9) Word has length 74 [2025-03-04 02:59:22,413 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-04 02:59:22,414 INFO L225 Difference]: With dead ends: 481 [2025-03-04 02:59:22,415 INFO L226 Difference]: Without dead ends: 283 [2025-03-04 02:59:22,415 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 9 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=21, Invalid=51, Unknown=0, NotChecked=0, Total=72 [2025-03-04 02:59:22,416 INFO L435 NwaCegarLoop]: 118 mSDtfsCounter, 29 mSDsluCounter, 435 mSDsCounter, 0 mSdLazyCounter, 85 mSolverCounterSat, 16 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 38 SdHoareTripleChecker+Valid, 553 SdHoareTripleChecker+Invalid, 101 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 16 IncrementalHoareTripleChecker+Valid, 85 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-04 02:59:22,416 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [38 Valid, 553 Invalid, 101 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [16 Valid, 85 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-04 02:59:22,417 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 283 states. [2025-03-04 02:59:22,442 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 283 to 253. [2025-03-04 02:59:22,442 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 253 states, 177 states have (on average 1.2768361581920904) internal successors, (226), 181 states have internal predecessors, (226), 56 states have call successors, (56), 17 states have call predecessors, (56), 19 states have return successors, (59), 54 states have call predecessors, (59), 54 states have call successors, (59) [2025-03-04 02:59:22,444 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 253 states to 253 states and 341 transitions. [2025-03-04 02:59:22,444 INFO L78 Accepts]: Start accepts. Automaton has 253 states and 341 transitions. Word has length 74 [2025-03-04 02:59:22,445 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-04 02:59:22,445 INFO L471 AbstractCegarLoop]: Abstraction has 253 states and 341 transitions. [2025-03-04 02:59:22,445 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 7 states have (on average 5.285714285714286) internal successors, (37), 8 states have internal predecessors, (37), 3 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (9), 2 states have call predecessors, (9), 3 states have call successors, (9) [2025-03-04 02:59:22,445 INFO L276 IsEmpty]: Start isEmpty. Operand 253 states and 341 transitions. [2025-03-04 02:59:22,446 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 75 [2025-03-04 02:59:22,446 INFO L210 NwaCegarLoop]: Found error trace [2025-03-04 02:59:22,446 INFO L218 NwaCegarLoop]: trace histogram [5, 5, 5, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-04 02:59:22,446 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2025-03-04 02:59:22,446 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-04 02:59:22,447 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 02:59:22,447 INFO L85 PathProgramCache]: Analyzing trace with hash 262704723, now seen corresponding path program 1 times [2025-03-04 02:59:22,447 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-04 02:59:22,447 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [370459339] [2025-03-04 02:59:22,447 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-04 02:59:22,447 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-04 02:59:22,466 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 74 statements into 1 equivalence classes. [2025-03-04 02:59:22,471 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 74 of 74 statements. [2025-03-04 02:59:22,471 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 02:59:22,471 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 02:59:22,539 INFO L134 CoverageAnalysis]: Checked inductivity of 47 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 47 trivial. 0 not checked. [2025-03-04 02:59:22,539 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-04 02:59:22,539 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [370459339] [2025-03-04 02:59:22,539 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [370459339] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-04 02:59:22,539 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-04 02:59:22,539 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2025-03-04 02:59:22,539 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2142611963] [2025-03-04 02:59:22,539 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-04 02:59:22,540 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2025-03-04 02:59:22,540 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-04 02:59:22,540 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2025-03-04 02:59:22,540 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2025-03-04 02:59:22,540 INFO L87 Difference]: Start difference. First operand 253 states and 341 transitions. Second operand has 4 states, 4 states have (on average 9.25) internal successors, (37), 4 states have internal predecessors, (37), 2 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) [2025-03-04 02:59:22,569 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-04 02:59:22,570 INFO L93 Difference]: Finished difference Result 482 states and 658 transitions. [2025-03-04 02:59:22,570 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2025-03-04 02:59:22,570 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 9.25) internal successors, (37), 4 states have internal predecessors, (37), 2 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) Word has length 74 [2025-03-04 02:59:22,571 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-04 02:59:22,572 INFO L225 Difference]: With dead ends: 482 [2025-03-04 02:59:22,572 INFO L226 Difference]: Without dead ends: 256 [2025-03-04 02:59:22,573 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2025-03-04 02:59:22,574 INFO L435 NwaCegarLoop]: 130 mSDtfsCounter, 0 mSDsluCounter, 248 mSDsCounter, 0 mSdLazyCounter, 17 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 378 SdHoareTripleChecker+Invalid, 18 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 17 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-04 02:59:22,574 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 378 Invalid, 18 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 17 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-04 02:59:22,574 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 256 states. [2025-03-04 02:59:22,590 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 256 to 253. [2025-03-04 02:59:22,590 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 253 states, 177 states have (on average 1.2598870056497176) internal successors, (223), 181 states have internal predecessors, (223), 56 states have call successors, (56), 17 states have call predecessors, (56), 19 states have return successors, (59), 54 states have call predecessors, (59), 54 states have call successors, (59) [2025-03-04 02:59:22,592 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 253 states to 253 states and 338 transitions. [2025-03-04 02:59:22,593 INFO L78 Accepts]: Start accepts. Automaton has 253 states and 338 transitions. Word has length 74 [2025-03-04 02:59:22,593 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-04 02:59:22,593 INFO L471 AbstractCegarLoop]: Abstraction has 253 states and 338 transitions. [2025-03-04 02:59:22,593 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 9.25) internal successors, (37), 4 states have internal predecessors, (37), 2 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) [2025-03-04 02:59:22,593 INFO L276 IsEmpty]: Start isEmpty. Operand 253 states and 338 transitions. [2025-03-04 02:59:22,594 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 75 [2025-03-04 02:59:22,594 INFO L210 NwaCegarLoop]: Found error trace [2025-03-04 02:59:22,594 INFO L218 NwaCegarLoop]: trace histogram [5, 5, 5, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-04 02:59:22,594 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4 [2025-03-04 02:59:22,594 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-04 02:59:22,594 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 02:59:22,594 INFO L85 PathProgramCache]: Analyzing trace with hash 956097428, now seen corresponding path program 1 times [2025-03-04 02:59:22,595 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-04 02:59:22,595 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1835833171] [2025-03-04 02:59:22,595 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-04 02:59:22,595 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-04 02:59:22,615 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 74 statements into 1 equivalence classes. [2025-03-04 02:59:22,620 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 74 of 74 statements. [2025-03-04 02:59:22,620 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 02:59:22,620 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 02:59:22,684 INFO L134 CoverageAnalysis]: Checked inductivity of 47 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 47 trivial. 0 not checked. [2025-03-04 02:59:22,684 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-04 02:59:22,684 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1835833171] [2025-03-04 02:59:22,684 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1835833171] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-04 02:59:22,684 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-04 02:59:22,684 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2025-03-04 02:59:22,684 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1113374586] [2025-03-04 02:59:22,684 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-04 02:59:22,684 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2025-03-04 02:59:22,684 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-04 02:59:22,685 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2025-03-04 02:59:22,685 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2025-03-04 02:59:22,685 INFO L87 Difference]: Start difference. First operand 253 states and 338 transitions. Second operand has 4 states, 4 states have (on average 9.25) internal successors, (37), 4 states have internal predecessors, (37), 2 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) [2025-03-04 02:59:22,715 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-04 02:59:22,715 INFO L93 Difference]: Finished difference Result 475 states and 641 transitions. [2025-03-04 02:59:22,716 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2025-03-04 02:59:22,716 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 9.25) internal successors, (37), 4 states have internal predecessors, (37), 2 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) Word has length 74 [2025-03-04 02:59:22,716 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-04 02:59:22,717 INFO L225 Difference]: With dead ends: 475 [2025-03-04 02:59:22,717 INFO L226 Difference]: Without dead ends: 241 [2025-03-04 02:59:22,718 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2025-03-04 02:59:22,718 INFO L435 NwaCegarLoop]: 129 mSDtfsCounter, 0 mSDsluCounter, 246 mSDsCounter, 0 mSdLazyCounter, 17 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 375 SdHoareTripleChecker+Invalid, 18 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 17 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-04 02:59:22,718 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 375 Invalid, 18 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 17 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-04 02:59:22,719 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 241 states. [2025-03-04 02:59:22,736 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 241 to 237. [2025-03-04 02:59:22,736 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 237 states, 161 states have (on average 1.2173913043478262) internal successors, (196), 165 states have internal predecessors, (196), 56 states have call successors, (56), 17 states have call predecessors, (56), 19 states have return successors, (59), 54 states have call predecessors, (59), 54 states have call successors, (59) [2025-03-04 02:59:22,738 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 237 states to 237 states and 311 transitions. [2025-03-04 02:59:22,738 INFO L78 Accepts]: Start accepts. Automaton has 237 states and 311 transitions. Word has length 74 [2025-03-04 02:59:22,739 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-04 02:59:22,739 INFO L471 AbstractCegarLoop]: Abstraction has 237 states and 311 transitions. [2025-03-04 02:59:22,740 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 9.25) internal successors, (37), 4 states have internal predecessors, (37), 2 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) [2025-03-04 02:59:22,740 INFO L276 IsEmpty]: Start isEmpty. Operand 237 states and 311 transitions. [2025-03-04 02:59:22,740 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 77 [2025-03-04 02:59:22,740 INFO L210 NwaCegarLoop]: Found error trace [2025-03-04 02:59:22,740 INFO L218 NwaCegarLoop]: trace histogram [5, 5, 5, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-04 02:59:22,740 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5 [2025-03-04 02:59:22,741 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-04 02:59:22,741 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 02:59:22,741 INFO L85 PathProgramCache]: Analyzing trace with hash -180058550, now seen corresponding path program 1 times [2025-03-04 02:59:22,741 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-04 02:59:22,741 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1864918653] [2025-03-04 02:59:22,741 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-04 02:59:22,741 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-04 02:59:22,758 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 76 statements into 1 equivalence classes. [2025-03-04 02:59:22,763 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 76 of 76 statements. [2025-03-04 02:59:22,763 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 02:59:22,764 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 02:59:22,967 INFO L134 CoverageAnalysis]: Checked inductivity of 47 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 47 trivial. 0 not checked. [2025-03-04 02:59:22,967 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-04 02:59:22,968 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1864918653] [2025-03-04 02:59:22,968 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1864918653] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-04 02:59:22,968 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-04 02:59:22,968 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [] total 9 [2025-03-04 02:59:22,968 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [98775897] [2025-03-04 02:59:22,968 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-04 02:59:22,968 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2025-03-04 02:59:22,968 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-04 02:59:22,969 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2025-03-04 02:59:22,969 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=52, Unknown=0, NotChecked=0, Total=72 [2025-03-04 02:59:22,969 INFO L87 Difference]: Start difference. First operand 237 states and 311 transitions. Second operand has 9 states, 8 states have (on average 4.875) internal successors, (39), 9 states have internal predecessors, (39), 3 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (9), 2 states have call predecessors, (9), 3 states have call successors, (9) [2025-03-04 02:59:23,094 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-04 02:59:23,094 INFO L93 Difference]: Finished difference Result 483 states and 639 transitions. [2025-03-04 02:59:23,094 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2025-03-04 02:59:23,095 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 8 states have (on average 4.875) internal successors, (39), 9 states have internal predecessors, (39), 3 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (9), 2 states have call predecessors, (9), 3 states have call successors, (9) Word has length 76 [2025-03-04 02:59:23,095 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-04 02:59:23,097 INFO L225 Difference]: With dead ends: 483 [2025-03-04 02:59:23,097 INFO L226 Difference]: Without dead ends: 274 [2025-03-04 02:59:23,098 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 11 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=29, Invalid=81, Unknown=0, NotChecked=0, Total=110 [2025-03-04 02:59:23,098 INFO L435 NwaCegarLoop]: 113 mSDtfsCounter, 30 mSDsluCounter, 625 mSDsCounter, 0 mSdLazyCounter, 121 mSolverCounterSat, 18 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 39 SdHoareTripleChecker+Valid, 738 SdHoareTripleChecker+Invalid, 139 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 18 IncrementalHoareTripleChecker+Valid, 121 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-04 02:59:23,098 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [39 Valid, 738 Invalid, 139 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [18 Valid, 121 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-04 02:59:23,099 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 274 states. [2025-03-04 02:59:23,112 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 274 to 240. [2025-03-04 02:59:23,113 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 240 states, 164 states have (on average 1.2134146341463414) internal successors, (199), 168 states have internal predecessors, (199), 56 states have call successors, (56), 17 states have call predecessors, (56), 19 states have return successors, (59), 54 states have call predecessors, (59), 54 states have call successors, (59) [2025-03-04 02:59:23,114 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 240 states to 240 states and 314 transitions. [2025-03-04 02:59:23,115 INFO L78 Accepts]: Start accepts. Automaton has 240 states and 314 transitions. Word has length 76 [2025-03-04 02:59:23,116 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-04 02:59:23,116 INFO L471 AbstractCegarLoop]: Abstraction has 240 states and 314 transitions. [2025-03-04 02:59:23,116 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 8 states have (on average 4.875) internal successors, (39), 9 states have internal predecessors, (39), 3 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (9), 2 states have call predecessors, (9), 3 states have call successors, (9) [2025-03-04 02:59:23,116 INFO L276 IsEmpty]: Start isEmpty. Operand 240 states and 314 transitions. [2025-03-04 02:59:23,119 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 78 [2025-03-04 02:59:23,119 INFO L210 NwaCegarLoop]: Found error trace [2025-03-04 02:59:23,119 INFO L218 NwaCegarLoop]: trace histogram [5, 5, 5, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-04 02:59:23,119 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6 [2025-03-04 02:59:23,119 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-04 02:59:23,119 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 02:59:23,119 INFO L85 PathProgramCache]: Analyzing trace with hash -1387750375, now seen corresponding path program 1 times [2025-03-04 02:59:23,119 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-04 02:59:23,120 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [421494995] [2025-03-04 02:59:23,120 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-04 02:59:23,120 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-04 02:59:23,139 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 77 statements into 1 equivalence classes. [2025-03-04 02:59:23,145 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 77 of 77 statements. [2025-03-04 02:59:23,145 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 02:59:23,145 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 02:59:23,355 INFO L134 CoverageAnalysis]: Checked inductivity of 47 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 47 trivial. 0 not checked. [2025-03-04 02:59:23,356 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-04 02:59:23,356 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [421494995] [2025-03-04 02:59:23,356 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [421494995] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-04 02:59:23,356 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-04 02:59:23,356 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2025-03-04 02:59:23,356 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [84437343] [2025-03-04 02:59:23,356 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-04 02:59:23,356 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2025-03-04 02:59:23,356 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-04 02:59:23,357 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2025-03-04 02:59:23,357 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=43, Unknown=0, NotChecked=0, Total=56 [2025-03-04 02:59:23,357 INFO L87 Difference]: Start difference. First operand 240 states and 314 transitions. Second operand has 8 states, 7 states have (on average 5.714285714285714) internal successors, (40), 8 states have internal predecessors, (40), 3 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (9), 2 states have call predecessors, (9), 3 states have call successors, (9) [2025-03-04 02:59:23,478 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-04 02:59:23,479 INFO L93 Difference]: Finished difference Result 471 states and 623 transitions. [2025-03-04 02:59:23,479 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2025-03-04 02:59:23,479 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 7 states have (on average 5.714285714285714) internal successors, (40), 8 states have internal predecessors, (40), 3 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (9), 2 states have call predecessors, (9), 3 states have call successors, (9) Word has length 77 [2025-03-04 02:59:23,479 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-04 02:59:23,481 INFO L225 Difference]: With dead ends: 471 [2025-03-04 02:59:23,481 INFO L226 Difference]: Without dead ends: 260 [2025-03-04 02:59:23,482 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 10 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=21, Invalid=69, Unknown=0, NotChecked=0, Total=90 [2025-03-04 02:59:23,482 INFO L435 NwaCegarLoop]: 117 mSDtfsCounter, 29 mSDsluCounter, 631 mSDsCounter, 0 mSdLazyCounter, 113 mSolverCounterSat, 18 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 38 SdHoareTripleChecker+Valid, 748 SdHoareTripleChecker+Invalid, 131 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 18 IncrementalHoareTripleChecker+Valid, 113 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-04 02:59:23,482 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [38 Valid, 748 Invalid, 131 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [18 Valid, 113 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-04 02:59:23,484 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 260 states. [2025-03-04 02:59:23,497 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 260 to 243. [2025-03-04 02:59:23,499 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 243 states, 167 states have (on average 1.2095808383233533) internal successors, (202), 171 states have internal predecessors, (202), 56 states have call successors, (56), 17 states have call predecessors, (56), 19 states have return successors, (59), 54 states have call predecessors, (59), 54 states have call successors, (59) [2025-03-04 02:59:23,500 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 243 states to 243 states and 317 transitions. [2025-03-04 02:59:23,500 INFO L78 Accepts]: Start accepts. Automaton has 243 states and 317 transitions. Word has length 77 [2025-03-04 02:59:23,501 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-04 02:59:23,501 INFO L471 AbstractCegarLoop]: Abstraction has 243 states and 317 transitions. [2025-03-04 02:59:23,501 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 7 states have (on average 5.714285714285714) internal successors, (40), 8 states have internal predecessors, (40), 3 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (9), 2 states have call predecessors, (9), 3 states have call successors, (9) [2025-03-04 02:59:23,501 INFO L276 IsEmpty]: Start isEmpty. Operand 243 states and 317 transitions. [2025-03-04 02:59:23,502 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 86 [2025-03-04 02:59:23,502 INFO L210 NwaCegarLoop]: Found error trace [2025-03-04 02:59:23,503 INFO L218 NwaCegarLoop]: trace histogram [5, 5, 5, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-04 02:59:23,503 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7 [2025-03-04 02:59:23,503 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-04 02:59:23,503 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 02:59:23,503 INFO L85 PathProgramCache]: Analyzing trace with hash 1742495738, now seen corresponding path program 1 times [2025-03-04 02:59:23,503 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-04 02:59:23,503 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [207369135] [2025-03-04 02:59:23,503 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-04 02:59:23,503 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-04 02:59:23,521 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 85 statements into 1 equivalence classes. [2025-03-04 02:59:23,566 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 85 of 85 statements. [2025-03-04 02:59:23,567 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 02:59:23,567 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 02:59:23,976 INFO L134 CoverageAnalysis]: Checked inductivity of 47 backedges. 3 proven. 9 refuted. 0 times theorem prover too weak. 35 trivial. 0 not checked. [2025-03-04 02:59:23,977 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-04 02:59:23,977 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [207369135] [2025-03-04 02:59:23,977 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [207369135] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-04 02:59:23,977 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1027492880] [2025-03-04 02:59:23,977 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-04 02:59:23,977 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-04 02:59:23,977 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 02:59:23,980 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-04 02:59:23,981 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2025-03-04 02:59:24,099 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 85 statements into 1 equivalence classes. [2025-03-04 02:59:24,143 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 85 of 85 statements. [2025-03-04 02:59:24,144 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 02:59:24,144 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 02:59:24,146 INFO L256 TraceCheckSpWp]: Trace formula consists of 472 conjuncts, 31 conjuncts are in the unsatisfiable core [2025-03-04 02:59:24,149 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-04 02:59:24,829 INFO L349 Elim1Store]: treesize reduction 300, result has 32.6 percent of original size [2025-03-04 02:59:24,829 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 6 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 8 new quantified variables, introduced 12 case distinctions, treesize of input 326 treesize of output 795 [2025-03-04 02:59:24,859 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 501 treesize of output 425 [2025-03-04 02:59:25,058 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 25 treesize of output 19 [2025-03-04 02:59:27,128 INFO L173 IndexEqualityManager]: detected equality via solver [2025-03-04 02:59:27,130 INFO L173 IndexEqualityManager]: detected equality via solver [2025-03-04 02:59:27,144 INFO L173 IndexEqualityManager]: detected equality via solver [2025-03-04 02:59:27,146 INFO L173 IndexEqualityManager]: detected equality via solver [2025-03-04 02:59:27,151 INFO L173 IndexEqualityManager]: detected equality via solver [2025-03-04 02:59:27,151 INFO L173 IndexEqualityManager]: detected equality via solver [2025-03-04 02:59:27,170 INFO L349 Elim1Store]: treesize reduction 28, result has 3.4 percent of original size [2025-03-04 02:59:27,170 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 3 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 1 new quantified variables, introduced 2 case distinctions, treesize of input 3324 treesize of output 3299 [2025-03-04 02:59:28,275 INFO L349 Elim1Store]: treesize reduction 206, result has 9.3 percent of original size [2025-03-04 02:59:28,276 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 3 stores, 3 select indices, 3 select index equivalence classes, 1 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 16 case distinctions, treesize of input 2179 treesize of output 2172 [2025-03-04 02:59:29,099 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-04 02:59:29,184 INFO L349 Elim1Store]: treesize reduction 174, result has 10.8 percent of original size [2025-03-04 02:59:29,185 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 2 stores, 3 select indices, 3 select index equivalence classes, 1 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 12 case distinctions, treesize of input 1542 treesize of output 1465 [2025-03-04 02:59:29,613 INFO L173 IndexEqualityManager]: detected equality via solver [2025-03-04 02:59:29,614 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 1 [2025-03-04 02:59:29,625 INFO L173 IndexEqualityManager]: detected equality via solver [2025-03-04 02:59:29,625 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 1 [2025-03-04 02:59:29,643 INFO L173 IndexEqualityManager]: detected equality via solver [2025-03-04 02:59:29,644 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 22 treesize of output 7 [2025-03-04 02:59:33,552 WARN L320 FreeRefinementEngine]: Global settings require throwing the following exception [2025-03-04 02:59:33,559 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2025-03-04 02:59:33,752 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-04 02:59:33,753 FATAL L? ?]: The Plugin de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction has thrown an exception: java.lang.AssertionError: no need to replace index at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.arrays.DerPreprocessor.constructReplacementForSelectCase(DerPreprocessor.java:331) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.arrays.DerPreprocessor.constructDerEnabler(DerPreprocessor.java:186) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.arrays.DerPreprocessor.(DerPreprocessor.java:144) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.arrays.ElimStorePlain.applyComplexEliminationRules(ElimStorePlain.java:153) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.DualJunctionSaa.tryToEliminate(DualJunctionSaa.java:190) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.DualJunctionSaa.tryToEliminateOne3(DualJunctionSaa.java:172) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.DualJunctionSaa.tryToEliminateOne2(DualJunctionSaa.java:151) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.DualJunctionSaa.tryToEliminateOne1(DualJunctionSaa.java:140) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.DualJunctionSaa.tryToEliminateOne0(DualJunctionSaa.java:122) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.DualJunctionSaa.tryToEliminateOne(DualJunctionSaa.java:108) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.DualJunctionSaa.tryExhaustivelyToEliminate(DualJunctionSaa.java:93) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.DualJunctionSaa.tryToEliminate(DualJunctionSaa.java:88) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.tryToEliminateOne(QuantifierPusher.java:542) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.applyNewEliminationTechniquesExhaustively(QuantifierPusher.java:521) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.applyDualJunctionEliminationTechniques(QuantifierPusher.java:514) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.tryToPushOverDualFiniteConnective(QuantifierPusher.java:325) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPushTermWalker.convert(QuantifierPushTermWalker.java:189) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPushTermWalker.convert(QuantifierPushTermWalker.java:1) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.TermContextTransformationEngine$ApplicationTermTask.doStep(TermContextTransformationEngine.java:209) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.TermContextTransformationEngine.transform(TermContextTransformationEngine.java:100) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.TermContextTransformationEngine.transform(TermContextTransformationEngine.java:84) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPushTermWalker.eliminate(QuantifierPushTermWalker.java:297) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPushUtilsForSubsetPush.pushMinionEliminatees(QuantifierPushUtilsForSubsetPush.java:255) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPushUtilsForSubsetPush.sequentialSubsetPush(QuantifierPushUtilsForSubsetPush.java:151) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.tryToPushOverDualFiniteConnective(QuantifierPusher.java:337) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPushTermWalker.convert(QuantifierPushTermWalker.java:189) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPushTermWalker.convert(QuantifierPushTermWalker.java:1) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.TermContextTransformationEngine$ApplicationTermTask.doStep(TermContextTransformationEngine.java:209) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.TermContextTransformationEngine.transform(TermContextTransformationEngine.java:100) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.TermContextTransformationEngine.transform(TermContextTransformationEngine.java:84) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPushTermWalker.eliminate(QuantifierPushTermWalker.java:297) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPushTermWalker.eliminate(QuantifierPushTermWalker.java:283) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.PartialQuantifierElimination.eliminate(PartialQuantifierElimination.java:51) at de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.predicates.IterativePredicateTransformer$QuantifierEliminationPostprocessor.postprocess(IterativePredicateTransformer.java:234) at de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.predicates.IterativePredicateTransformer.applyPostprocessors(IterativePredicateTransformer.java:416) at de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.predicates.IterativePredicateTransformer.computeStrongestPostconditionSequence(IterativePredicateTransformer.java:195) at de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.singletracecheck.TraceCheckSpWp.computeInterpolantsUsingUnsatCore(TraceCheckSpWp.java:291) at de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.singletracecheck.TraceCheckSpWp.computeInterpolants(TraceCheckSpWp.java:181) at de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.singletracecheck.TraceCheckSpWp.(TraceCheckSpWp.java:160) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleSpWp.construct(IpTcStrategyModuleSpWp.java:106) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleSpWp.construct(IpTcStrategyModuleSpWp.java:1) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getOrConstruct(IpTcStrategyModuleBase.java:101) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getInterpolantComputationStatus(IpTcStrategyModuleBase.java:77) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.tryExecuteInterpolantGenerator(AutomatonFreeRefinementEngine.java:267) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.generateProof(AutomatonFreeRefinementEngine.java:148) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.executeStrategy(AutomatonFreeRefinementEngine.java:137) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.(AutomatonFreeRefinementEngine.java:85) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.TraceAbstractionRefinementEngine.(TraceAbstractionRefinementEngine.java:82) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.BasicCegarLoop.isCounterexampleFeasible(BasicCegarLoop.java:317) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterate(AbstractCegarLoop.java:407) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.startCegar(AbstractCegarLoop.java:342) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.runCegar(AbstractCegarLoop.java:324) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.executeCegarLoop(TraceAbstractionStarter.java:428) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseProgram(TraceAbstractionStarter.java:314) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseSequentialProgram(TraceAbstractionStarter.java:275) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.runCegarLoops(TraceAbstractionStarter.java:167) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.(TraceAbstractionStarter.java:140) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver.finish(TraceAbstractionObserver.java:132) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runObserver(PluginConnector.java:167) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runTool(PluginConnector.java:150) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.run(PluginConnector.java:127) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.executePluginConnector(ToolchainWalker.java:233) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.processPlugin(ToolchainWalker.java:227) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walkUnprotected(ToolchainWalker.java:144) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walk(ToolchainWalker.java:106) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainManager$Toolchain.processToolchain(ToolchainManager.java:319) at de.uni_freiburg.informatik.ultimate.core.coreplugin.toolchain.DefaultToolchainJob.run(DefaultToolchainJob.java:145) at org.eclipse.core.internal.jobs.Worker.run(Worker.java:63) [2025-03-04 02:59:33,758 INFO L158 Benchmark]: Toolchain (without parser) took 24395.32ms. Allocated memory was 142.6MB in the beginning and 704.6MB in the end (delta: 562.0MB). Free memory was 99.3MB in the beginning and 339.8MB in the end (delta: -240.5MB). Peak memory consumption was 358.4MB. Max. memory is 16.1GB. [2025-03-04 02:59:33,759 INFO L158 Benchmark]: CDTParser took 0.40ms. Allocated memory is still 201.3MB. Free memory is still 126.0MB. There was no memory consumed. Max. memory is 16.1GB. [2025-03-04 02:59:33,759 INFO L158 Benchmark]: CACSL2BoogieTranslator took 1176.10ms. Allocated memory is still 142.6MB. Free memory was 99.3MB in the beginning and 43.2MB in the end (delta: 56.1MB). Peak memory consumption was 85.4MB. Max. memory is 16.1GB. [2025-03-04 02:59:33,759 INFO L158 Benchmark]: Boogie Procedure Inliner took 96.54ms. Allocated memory is still 142.6MB. Free memory was 43.2MB in the beginning and 96.7MB in the end (delta: -53.4MB). Peak memory consumption was 14.7MB. Max. memory is 16.1GB. [2025-03-04 02:59:33,759 INFO L158 Benchmark]: Boogie Preprocessor took 49.95ms. Allocated memory is still 142.6MB. Free memory was 96.7MB in the beginning and 92.1MB in the end (delta: 4.5MB). There was no memory consumed. Max. memory is 16.1GB. [2025-03-04 02:59:33,759 INFO L158 Benchmark]: IcfgBuilder took 487.29ms. Allocated memory is still 142.6MB. Free memory was 92.1MB in the beginning and 62.2MB in the end (delta: 29.9MB). Peak memory consumption was 33.6MB. Max. memory is 16.1GB. [2025-03-04 02:59:33,759 INFO L158 Benchmark]: TraceAbstraction took 22579.83ms. Allocated memory was 142.6MB in the beginning and 704.6MB in the end (delta: 562.0MB). Free memory was 61.4MB in the beginning and 339.8MB in the end (delta: -278.4MB). Peak memory consumption was 322.9MB. Max. memory is 16.1GB. [2025-03-04 02:59:33,760 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.40ms. Allocated memory is still 201.3MB. Free memory is still 126.0MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 1176.10ms. Allocated memory is still 142.6MB. Free memory was 99.3MB in the beginning and 43.2MB in the end (delta: 56.1MB). Peak memory consumption was 85.4MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 96.54ms. Allocated memory is still 142.6MB. Free memory was 43.2MB in the beginning and 96.7MB in the end (delta: -53.4MB). Peak memory consumption was 14.7MB. Max. memory is 16.1GB. * Boogie Preprocessor took 49.95ms. Allocated memory is still 142.6MB. Free memory was 96.7MB in the beginning and 92.1MB in the end (delta: 4.5MB). There was no memory consumed. Max. memory is 16.1GB. * IcfgBuilder took 487.29ms. Allocated memory is still 142.6MB. Free memory was 92.1MB in the beginning and 62.2MB in the end (delta: 29.9MB). Peak memory consumption was 33.6MB. Max. memory is 16.1GB. * TraceAbstraction took 22579.83ms. Allocated memory was 142.6MB in the beginning and 704.6MB in the end (delta: 562.0MB). Free memory was 61.4MB in the beginning and 339.8MB in the end (delta: -278.4MB). Peak memory consumption was 322.9MB. Max. memory is 16.1GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - ExceptionOrErrorResult: AssertionError: no need to replace index de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: AssertionError: no need to replace index: de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.arrays.DerPreprocessor.constructReplacementForSelectCase(DerPreprocessor.java:331) RESULT: Ultimate could not prove your program: Toolchain returned no result. [2025-03-04 02:59:33,791 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/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 Using bit-precise analysis Retrying with bit-precise analysis ### Bit-precise run ### Calling Ultimate with: /root/.sdkman/candidates/java/21.0.5-tem/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.6.800.v20240513-1750.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/aws-c-common/aws_linked_list_push_back_harness.i -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-64bit-Automizer_Bitvector.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux --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 64bit --witnessprinter.graph.data.programhash 4526081b0c55ba26ca543a72264ba075e2706c93c97faea07fd81ad62d180974 --- Real Ultimate output --- This is Ultimate 0.3.0-?-798a7b3-m [2025-03-04 02:59:35,590 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-03-04 02:59:35,660 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-64bit-Automizer_Bitvector.epf [2025-03-04 02:59:35,665 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-03-04 02:59:35,665 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-03-04 02:59:35,685 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-03-04 02:59:35,687 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-03-04 02:59:35,687 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-03-04 02:59:35,687 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-03-04 02:59:35,687 INFO L153 SettingsManager]: * Use memory slicer=true [2025-03-04 02:59:35,687 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2025-03-04 02:59:35,687 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2025-03-04 02:59:35,687 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-03-04 02:59:35,687 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-03-04 02:59:35,688 INFO L153 SettingsManager]: * Use SBE=true [2025-03-04 02:59:35,688 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-03-04 02:59:35,688 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2025-03-04 02:59:35,688 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-03-04 02:59:35,688 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2025-03-04 02:59:35,688 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2025-03-04 02:59:35,688 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2025-03-04 02:59:35,688 INFO L153 SettingsManager]: * Adapt memory model on pointer casts if necessary=true [2025-03-04 02:59:35,688 INFO L153 SettingsManager]: * Use bitvectors instead of ints=true [2025-03-04 02:59:35,688 INFO L153 SettingsManager]: * Memory model=HoenickeLindenmann_4ByteResolution [2025-03-04 02:59:35,688 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-03-04 02:59:35,688 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-03-04 02:59:35,688 INFO L153 SettingsManager]: * Use constant arrays=true [2025-03-04 02:59:35,688 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-03-04 02:59:35,688 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-03-04 02:59:35,688 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-03-04 02:59:35,688 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-03-04 02:59:35,688 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-04 02:59:35,689 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-03-04 02:59:35,689 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2025-03-04 02:59:35,689 INFO L153 SettingsManager]: * Compute procedure contracts=false [2025-03-04 02:59:35,689 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2025-03-04 02:59:35,689 INFO L153 SettingsManager]: * Trace refinement strategy=FOX [2025-03-04 02:59:35,689 INFO L153 SettingsManager]: * Command for external solver=cvc4 --incremental --print-success --lang smt [2025-03-04 02:59:35,689 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2025-03-04 02:59:35,689 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2025-03-04 02:59:35,689 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2025-03-04 02:59:35,689 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2025-03-04 02:59:35,689 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 -> /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux 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 -> 64bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> 4526081b0c55ba26ca543a72264ba075e2706c93c97faea07fd81ad62d180974 [2025-03-04 02:59:35,913 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-03-04 02:59:35,921 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-03-04 02:59:35,922 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-03-04 02:59:35,924 INFO L270 PluginConnector]: Initializing CDTParser... [2025-03-04 02:59:35,924 INFO L274 PluginConnector]: CDTParser initialized [2025-03-04 02:59:35,925 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/aws-c-common/aws_linked_list_push_back_harness.i [2025-03-04 02:59:37,078 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/ea1804c50/d336c0e4c87f450291809783953f7eaa/FLAG9610aacd4 [2025-03-04 02:59:37,462 INFO L384 CDTParser]: Found 1 translation units. [2025-03-04 02:59:37,463 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/aws-c-common/aws_linked_list_push_back_harness.i [2025-03-04 02:59:37,497 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/ea1804c50/d336c0e4c87f450291809783953f7eaa/FLAG9610aacd4 [2025-03-04 02:59:37,661 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/ea1804c50/d336c0e4c87f450291809783953f7eaa [2025-03-04 02:59:37,663 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-03-04 02:59:37,664 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-03-04 02:59:37,664 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-03-04 02:59:37,664 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-03-04 02:59:37,667 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-03-04 02:59:37,668 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 04.03 02:59:37" (1/1) ... [2025-03-04 02:59:37,668 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@78f67bc6 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.03 02:59:37, skipping insertion in model container [2025-03-04 02:59:37,668 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 04.03 02:59:37" (1/1) ... [2025-03-04 02:59:37,724 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-03-04 02:59:37,882 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/aws-c-common/aws_linked_list_push_back_harness.i[4499,4512] [2025-03-04 02:59:37,887 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/aws-c-common/aws_linked_list_push_back_harness.i[4559,4572] [2025-03-04 02:59:38,242 WARN L1100 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2025-03-04 02:59:38,307 WARN L1100 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2025-03-04 02:59:38,308 WARN L1100 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2025-03-04 02:59:38,308 WARN L1100 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2025-03-04 02:59:38,319 WARN L1100 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2025-03-04 02:59:38,320 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-04 02:59:38,321 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-04 02:59:38,321 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-04 02:59:38,322 WARN L1100 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2025-03-04 02:59:38,322 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-04 02:59:38,322 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-04 02:59:38,324 WARN L1100 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2025-03-04 02:59:38,324 WARN L1100 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2025-03-04 02:59:38,325 WARN L1100 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2025-03-04 02:59:38,325 WARN L1100 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2025-03-04 02:59:38,332 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-04 02:59:38,332 WARN L1100 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2025-03-04 02:59:38,332 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-04 02:59:38,332 WARN L1100 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2025-03-04 02:59:38,338 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-04 02:59:38,338 WARN L1100 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2025-03-04 02:59:38,338 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-04 02:59:38,338 WARN L1100 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2025-03-04 02:59:38,339 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-04 02:59:38,340 WARN L1100 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2025-03-04 02:59:38,341 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-04 02:59:38,341 WARN L1100 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2025-03-04 02:59:38,341 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-04 02:59:38,341 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-04 02:59:38,547 WARN L1100 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2025-03-04 02:59:38,547 WARN L1100 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2025-03-04 02:59:38,548 WARN L1100 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2025-03-04 02:59:38,548 WARN L1100 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2025-03-04 02:59:38,635 WARN L1100 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2025-03-04 02:59:38,647 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/aws-c-common/aws_linked_list_push_back_harness.i[150688,150701] [2025-03-04 02:59:38,648 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-04 02:59:38,662 INFO L197 MainTranslator]: Restarting translation with changed settings: SettingsChange [mNewPreferredMemoryModel=HoenickeLindenmann_1ByteResolution] [2025-03-04 02:59:38,692 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-03-04 02:59:38,695 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/aws-c-common/aws_linked_list_push_back_harness.i[4499,4512] [2025-03-04 02:59:38,697 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/aws-c-common/aws_linked_list_push_back_harness.i[4559,4572] [2025-03-04 02:59:38,713 WARN L1100 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2025-03-04 02:59:38,729 WARN L1100 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2025-03-04 02:59:38,732 WARN L1100 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2025-03-04 02:59:38,732 WARN L1100 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2025-03-04 02:59:38,738 WARN L1100 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2025-03-04 02:59:38,740 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-04 02:59:38,740 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-04 02:59:38,741 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-04 02:59:38,741 WARN L1100 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2025-03-04 02:59:38,741 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-04 02:59:38,741 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-04 02:59:38,742 WARN L1100 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2025-03-04 02:59:38,745 WARN L1100 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2025-03-04 02:59:38,746 WARN L1100 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2025-03-04 02:59:38,746 WARN L1100 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2025-03-04 02:59:38,748 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-04 02:59:38,751 WARN L1100 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2025-03-04 02:59:38,751 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-04 02:59:38,751 WARN L1100 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2025-03-04 02:59:38,752 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-04 02:59:38,754 WARN L1100 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2025-03-04 02:59:38,754 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-04 02:59:38,754 WARN L1100 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2025-03-04 02:59:38,754 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-04 02:59:38,755 WARN L1100 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2025-03-04 02:59:38,755 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-04 02:59:38,755 WARN L1100 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2025-03-04 02:59:38,755 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-04 02:59:38,755 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-04 02:59:38,792 WARN L1100 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2025-03-04 02:59:38,793 WARN L1100 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2025-03-04 02:59:38,793 WARN L1100 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2025-03-04 02:59:38,793 WARN L1100 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2025-03-04 02:59:38,821 WARN L1100 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2025-03-04 02:59:38,827 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/aws-c-common/aws_linked_list_push_back_harness.i[150688,150701] [2025-03-04 02:59:38,828 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-04 02:59:38,834 INFO L200 MainTranslator]: Completed pre-run [2025-03-04 02:59:38,844 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/aws-c-common/aws_linked_list_push_back_harness.i[4499,4512] [2025-03-04 02:59:38,848 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/aws-c-common/aws_linked_list_push_back_harness.i[4559,4572] [2025-03-04 02:59:38,883 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-04 02:59:38,883 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-04 02:59:38,883 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-04 02:59:38,884 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-04 02:59:38,885 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-04 02:59:38,888 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-04 02:59:38,888 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-04 02:59:38,889 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-04 02:59:38,889 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-04 02:59:38,890 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-04 02:59:38,891 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-04 02:59:38,891 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-04 02:59:38,891 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-04 02:59:38,940 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/aws-c-common/aws_linked_list_push_back_harness.i[150688,150701] [2025-03-04 02:59:38,940 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-04 02:59:39,076 INFO L204 MainTranslator]: Completed translation [2025-03-04 02:59:39,076 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.03 02:59:39 WrapperNode [2025-03-04 02:59:39,077 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-03-04 02:59:39,077 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-03-04 02:59:39,077 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-03-04 02:59:39,077 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-03-04 02:59:39,083 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.03 02:59:39" (1/1) ... [2025-03-04 02:59:39,146 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.03 02:59:39" (1/1) ... [2025-03-04 02:59:39,180 INFO L138 Inliner]: procedures = 687, calls = 1046, calls flagged for inlining = 53, calls inlined = 6, statements flattened = 146 [2025-03-04 02:59:39,181 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-03-04 02:59:39,182 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-03-04 02:59:39,182 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-03-04 02:59:39,182 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-03-04 02:59:39,189 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.03 02:59:39" (1/1) ... [2025-03-04 02:59:39,189 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.03 02:59:39" (1/1) ... [2025-03-04 02:59:39,193 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.03 02:59:39" (1/1) ... [2025-03-04 02:59:39,210 INFO L175 MemorySlicer]: Split 35 memory accesses to 3 slices as follows [2, 5, 28]. 80 percent of accesses are in the largest equivalence class. The 7 initializations are split as follows [2, 5, 0]. The 10 writes are split as follows [0, 0, 10]. [2025-03-04 02:59:39,213 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.03 02:59:39" (1/1) ... [2025-03-04 02:59:39,213 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.03 02:59:39" (1/1) ... [2025-03-04 02:59:39,223 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.03 02:59:39" (1/1) ... [2025-03-04 02:59:39,224 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.03 02:59:39" (1/1) ... [2025-03-04 02:59:39,230 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.03 02:59:39" (1/1) ... [2025-03-04 02:59:39,232 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.03 02:59:39" (1/1) ... [2025-03-04 02:59:39,236 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-03-04 02:59:39,241 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2025-03-04 02:59:39,241 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2025-03-04 02:59:39,241 INFO L274 PluginConnector]: IcfgBuilder initialized [2025-03-04 02:59:39,242 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.03 02:59:39" (1/1) ... [2025-03-04 02:59:39,246 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-04 02:59:39,254 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 02:59:39,266 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2025-03-04 02:59:39,270 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2025-03-04 02:59:39,284 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2025-03-04 02:59:39,285 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~intINTTYPE1#0 [2025-03-04 02:59:39,285 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~intINTTYPE1#1 [2025-03-04 02:59:39,285 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~intINTTYPE1#2 [2025-03-04 02:59:39,285 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2025-03-04 02:59:39,287 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2025-03-04 02:59:39,287 INFO L130 BoogieDeclarations]: Found specification of procedure aws_linked_list_node_next_is_valid [2025-03-04 02:59:39,287 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_linked_list_node_next_is_valid [2025-03-04 02:59:39,287 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnHeap [2025-03-04 02:59:39,287 INFO L130 BoogieDeclarations]: Found specification of procedure aws_linked_list_is_valid [2025-03-04 02:59:39,287 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_linked_list_is_valid [2025-03-04 02:59:39,287 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2025-03-04 02:59:39,287 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$#0 [2025-03-04 02:59:39,287 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$#1 [2025-03-04 02:59:39,287 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$#2 [2025-03-04 02:59:39,287 INFO L130 BoogieDeclarations]: Found specification of procedure aws_linked_list_insert_before [2025-03-04 02:59:39,288 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_linked_list_insert_before [2025-03-04 02:59:39,288 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-03-04 02:59:39,288 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-03-04 02:59:39,288 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2025-03-04 02:59:39,288 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2025-03-04 02:59:39,288 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2025-03-04 02:59:39,288 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$#0 [2025-03-04 02:59:39,288 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$#1 [2025-03-04 02:59:39,288 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$#2 [2025-03-04 02:59:39,288 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$#0 [2025-03-04 02:59:39,288 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$#1 [2025-03-04 02:59:39,288 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$#2 [2025-03-04 02:59:39,288 INFO L130 BoogieDeclarations]: Found specification of procedure nondet_uint64_t [2025-03-04 02:59:39,288 INFO L138 BoogieDeclarations]: Found implementation of procedure nondet_uint64_t [2025-03-04 02:59:39,288 INFO L130 BoogieDeclarations]: Found specification of procedure aws_linked_list_node_prev_is_valid [2025-03-04 02:59:39,288 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_linked_list_node_prev_is_valid [2025-03-04 02:59:39,474 INFO L256 CfgBuilder]: Building ICFG [2025-03-04 02:59:39,475 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2025-03-04 02:59:39,527 INFO L1325 $ProcedureCfgBuilder]: dead code at ProgramPoint L4718: havoc #t~mem303.base, #t~mem303.offset;havoc #t~short304;havoc #t~mem305.base, #t~mem305.offset;havoc #t~mem306.base, #t~mem306.offset;havoc #t~short307; [2025-03-04 02:59:39,549 INFO L1325 $ProcedureCfgBuilder]: dead code at ProgramPoint L4729: havoc #t~mem308.base, #t~mem308.offset;havoc #t~short309;havoc #t~mem310.base, #t~mem310.offset;havoc #t~mem311.base, #t~mem311.offset;havoc #t~short312; [2025-03-04 02:59:39,555 INFO L1325 $ProcedureCfgBuilder]: dead code at ProgramPoint L266: havoc #t~nondet9; [2025-03-04 02:59:39,808 INFO L1325 $ProcedureCfgBuilder]: dead code at ProgramPoint L4700: havoc #t~ret302#1; [2025-03-04 02:59:39,848 INFO L? ?]: Removed 66 outVars from TransFormulas that were not future-live. [2025-03-04 02:59:39,848 INFO L307 CfgBuilder]: Performing block encoding [2025-03-04 02:59:39,857 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-03-04 02:59:39,857 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2025-03-04 02:59:39,858 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 04.03 02:59:39 BoogieIcfgContainer [2025-03-04 02:59:39,858 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2025-03-04 02:59:39,859 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2025-03-04 02:59:39,859 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2025-03-04 02:59:39,865 INFO L274 PluginConnector]: TraceAbstraction initialized [2025-03-04 02:59:39,865 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 04.03 02:59:37" (1/3) ... [2025-03-04 02:59:39,866 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5db3e2c0 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 04.03 02:59:39, skipping insertion in model container [2025-03-04 02:59:39,866 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.03 02:59:39" (2/3) ... [2025-03-04 02:59:39,866 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5db3e2c0 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 04.03 02:59:39, skipping insertion in model container [2025-03-04 02:59:39,866 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 04.03 02:59:39" (3/3) ... [2025-03-04 02:59:39,867 INFO L128 eAbstractionObserver]: Analyzing ICFG aws_linked_list_push_back_harness.i [2025-03-04 02:59:39,877 INFO L216 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2025-03-04 02:59:39,878 INFO L151 ceAbstractionStarter]: Applying trace abstraction to ICFG aws_linked_list_push_back_harness.i that has 8 procedures, 101 locations, 1 initial locations, 2 loop locations, and 1 error locations. [2025-03-04 02:59:39,917 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2025-03-04 02:59:39,923 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;@457eefdc, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2025-03-04 02:59:39,923 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2025-03-04 02:59:39,927 INFO L276 IsEmpty]: Start isEmpty. Operand has 101 states, 64 states have (on average 1.265625) internal successors, (81), 65 states have internal predecessors, (81), 28 states have call successors, (28), 7 states have call predecessors, (28), 7 states have return successors, (28), 28 states have call predecessors, (28), 28 states have call successors, (28) [2025-03-04 02:59:39,933 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 74 [2025-03-04 02:59:39,933 INFO L210 NwaCegarLoop]: Found error trace [2025-03-04 02:59:39,934 INFO L218 NwaCegarLoop]: trace histogram [5, 5, 5, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-04 02:59:39,934 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-04 02:59:39,938 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 02:59:39,938 INFO L85 PathProgramCache]: Analyzing trace with hash 1171475621, now seen corresponding path program 1 times [2025-03-04 02:59:39,945 INFO L118 FreeRefinementEngine]: Executing refinement strategy FOX [2025-03-04 02:59:39,945 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [407347983] [2025-03-04 02:59:39,946 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-04 02:59:39,946 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-04 02:59:39,946 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 02:59:39,949 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-04 02:59:39,949 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2025-03-04 02:59:40,093 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 73 statements into 1 equivalence classes. [2025-03-04 02:59:40,143 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 73 of 73 statements. [2025-03-04 02:59:40,143 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 02:59:40,143 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 02:59:40,148 INFO L256 TraceCheckSpWp]: Trace formula consists of 255 conjuncts, 1 conjuncts are in the unsatisfiable core [2025-03-04 02:59:40,155 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-04 02:59:40,179 INFO L134 CoverageAnalysis]: Checked inductivity of 47 backedges. 8 proven. 0 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2025-03-04 02:59:40,179 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-04 02:59:40,180 INFO L136 FreeRefinementEngine]: Strategy FOX found an infeasible trace [2025-03-04 02:59:40,180 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [407347983] [2025-03-04 02:59:40,180 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [407347983] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-04 02:59:40,180 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-04 02:59:40,181 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2025-03-04 02:59:40,182 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [887499872] [2025-03-04 02:59:40,183 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-04 02:59:40,186 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2025-03-04 02:59:40,186 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FOX [2025-03-04 02:59:40,199 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2025-03-04 02:59:40,200 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2025-03-04 02:59:40,202 INFO L87 Difference]: Start difference. First operand has 101 states, 64 states have (on average 1.265625) internal successors, (81), 65 states have internal predecessors, (81), 28 states have call successors, (28), 7 states have call predecessors, (28), 7 states have return successors, (28), 28 states have call predecessors, (28), 28 states have call successors, (28) Second operand has 2 states, 2 states have (on average 18.5) internal successors, (37), 2 states have internal predecessors, (37), 2 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) [2025-03-04 02:59:40,224 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-04 02:59:40,224 INFO L93 Difference]: Finished difference Result 194 states and 282 transitions. [2025-03-04 02:59:40,225 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2025-03-04 02:59:40,225 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 18.5) internal successors, (37), 2 states have internal predecessors, (37), 2 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) Word has length 73 [2025-03-04 02:59:40,226 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-04 02:59:40,229 INFO L225 Difference]: With dead ends: 194 [2025-03-04 02:59:40,230 INFO L226 Difference]: Without dead ends: 96 [2025-03-04 02:59:40,232 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 72 GetRequests, 72 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2025-03-04 02:59:40,234 INFO L435 NwaCegarLoop]: 135 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 0 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 135 SdHoareTripleChecker+Invalid, 0 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 0 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-04 02:59:40,235 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 135 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-04 02:59:40,245 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 96 states. [2025-03-04 02:59:40,260 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 96 to 96. [2025-03-04 02:59:40,262 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 96 states, 60 states have (on average 1.25) internal successors, (75), 61 states have internal predecessors, (75), 28 states have call successors, (28), 7 states have call predecessors, (28), 7 states have return successors, (27), 27 states have call predecessors, (27), 27 states have call successors, (27) [2025-03-04 02:59:40,265 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 96 states to 96 states and 130 transitions. [2025-03-04 02:59:40,268 INFO L78 Accepts]: Start accepts. Automaton has 96 states and 130 transitions. Word has length 73 [2025-03-04 02:59:40,268 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-04 02:59:40,269 INFO L471 AbstractCegarLoop]: Abstraction has 96 states and 130 transitions. [2025-03-04 02:59:40,269 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 18.5) internal successors, (37), 2 states have internal predecessors, (37), 2 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) [2025-03-04 02:59:40,269 INFO L276 IsEmpty]: Start isEmpty. Operand 96 states and 130 transitions. [2025-03-04 02:59:40,270 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 74 [2025-03-04 02:59:40,271 INFO L210 NwaCegarLoop]: Found error trace [2025-03-04 02:59:40,272 INFO L218 NwaCegarLoop]: trace histogram [5, 5, 5, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-04 02:59:40,281 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2025-03-04 02:59:40,472 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-04 02:59:40,472 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-04 02:59:40,473 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 02:59:40,473 INFO L85 PathProgramCache]: Analyzing trace with hash 624241476, now seen corresponding path program 1 times [2025-03-04 02:59:40,474 INFO L118 FreeRefinementEngine]: Executing refinement strategy FOX [2025-03-04 02:59:40,474 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [288026386] [2025-03-04 02:59:40,474 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-04 02:59:40,474 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-04 02:59:40,474 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 02:59:40,476 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-04 02:59:40,477 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2025-03-04 02:59:40,614 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 73 statements into 1 equivalence classes. [2025-03-04 02:59:40,654 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 73 of 73 statements. [2025-03-04 02:59:40,654 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 02:59:40,654 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 02:59:40,658 INFO L256 TraceCheckSpWp]: Trace formula consists of 255 conjuncts, 3 conjuncts are in the unsatisfiable core [2025-03-04 02:59:40,661 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-04 02:59:40,692 INFO L134 CoverageAnalysis]: Checked inductivity of 47 backedges. 16 proven. 0 refuted. 0 times theorem prover too weak. 31 trivial. 0 not checked. [2025-03-04 02:59:40,692 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-04 02:59:40,692 INFO L136 FreeRefinementEngine]: Strategy FOX found an infeasible trace [2025-03-04 02:59:40,692 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [288026386] [2025-03-04 02:59:40,692 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [288026386] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-04 02:59:40,692 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-04 02:59:40,692 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2025-03-04 02:59:40,692 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [866222541] [2025-03-04 02:59:40,692 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-04 02:59:40,695 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2025-03-04 02:59:40,695 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FOX [2025-03-04 02:59:40,697 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2025-03-04 02:59:40,697 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2025-03-04 02:59:40,697 INFO L87 Difference]: Start difference. First operand 96 states and 130 transitions. Second operand has 4 states, 4 states have (on average 9.5) internal successors, (38), 4 states have internal predecessors, (38), 2 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) [2025-03-04 02:59:40,736 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-04 02:59:40,736 INFO L93 Difference]: Finished difference Result 183 states and 253 transitions. [2025-03-04 02:59:40,736 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2025-03-04 02:59:40,736 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 9.5) internal successors, (38), 4 states have internal predecessors, (38), 2 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) Word has length 73 [2025-03-04 02:59:40,737 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-04 02:59:40,738 INFO L225 Difference]: With dead ends: 183 [2025-03-04 02:59:40,738 INFO L226 Difference]: Without dead ends: 99 [2025-03-04 02:59:40,738 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 72 GetRequests, 70 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2025-03-04 02:59:40,739 INFO L435 NwaCegarLoop]: 127 mSDtfsCounter, 1 mSDsluCounter, 248 mSDsCounter, 0 mSdLazyCounter, 13 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1 SdHoareTripleChecker+Valid, 375 SdHoareTripleChecker+Invalid, 15 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 13 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-04 02:59:40,739 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [1 Valid, 375 Invalid, 15 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 13 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-04 02:59:40,739 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 99 states. [2025-03-04 02:59:40,747 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 99 to 99. [2025-03-04 02:59:40,747 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 99 states, 63 states have (on average 1.2380952380952381) internal successors, (78), 64 states have internal predecessors, (78), 28 states have call successors, (28), 7 states have call predecessors, (28), 7 states have return successors, (27), 27 states have call predecessors, (27), 27 states have call successors, (27) [2025-03-04 02:59:40,748 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 99 states to 99 states and 133 transitions. [2025-03-04 02:59:40,748 INFO L78 Accepts]: Start accepts. Automaton has 99 states and 133 transitions. Word has length 73 [2025-03-04 02:59:40,749 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-04 02:59:40,749 INFO L471 AbstractCegarLoop]: Abstraction has 99 states and 133 transitions. [2025-03-04 02:59:40,749 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 9.5) internal successors, (38), 4 states have internal predecessors, (38), 2 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) [2025-03-04 02:59:40,751 INFO L276 IsEmpty]: Start isEmpty. Operand 99 states and 133 transitions. [2025-03-04 02:59:40,754 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 74 [2025-03-04 02:59:40,754 INFO L210 NwaCegarLoop]: Found error trace [2025-03-04 02:59:40,754 INFO L218 NwaCegarLoop]: trace histogram [5, 5, 5, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-04 02:59:40,764 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2025-03-04 02:59:40,954 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-04 02:59:40,954 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-04 02:59:40,955 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 02:59:40,955 INFO L85 PathProgramCache]: Analyzing trace with hash 383701347, now seen corresponding path program 1 times [2025-03-04 02:59:40,955 INFO L118 FreeRefinementEngine]: Executing refinement strategy FOX [2025-03-04 02:59:40,955 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [178105079] [2025-03-04 02:59:40,955 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-04 02:59:40,955 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-04 02:59:40,955 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 02:59:40,957 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-04 02:59:40,958 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2025-03-04 02:59:41,056 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 73 statements into 1 equivalence classes. [2025-03-04 02:59:41,093 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 73 of 73 statements. [2025-03-04 02:59:41,093 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 02:59:41,093 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 02:59:41,097 INFO L256 TraceCheckSpWp]: Trace formula consists of 252 conjuncts, 5 conjuncts are in the unsatisfiable core [2025-03-04 02:59:41,099 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-04 02:59:41,135 INFO L134 CoverageAnalysis]: Checked inductivity of 47 backedges. 27 proven. 0 refuted. 0 times theorem prover too weak. 20 trivial. 0 not checked. [2025-03-04 02:59:41,138 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-04 02:59:41,139 INFO L136 FreeRefinementEngine]: Strategy FOX found an infeasible trace [2025-03-04 02:59:41,139 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [178105079] [2025-03-04 02:59:41,139 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [178105079] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-04 02:59:41,139 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-04 02:59:41,139 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2025-03-04 02:59:41,139 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [781026489] [2025-03-04 02:59:41,139 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-04 02:59:41,139 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2025-03-04 02:59:41,139 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FOX [2025-03-04 02:59:41,140 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2025-03-04 02:59:41,140 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2025-03-04 02:59:41,140 INFO L87 Difference]: Start difference. First operand 99 states and 133 transitions. Second operand has 6 states, 5 states have (on average 8.2) internal successors, (41), 5 states have internal predecessors, (41), 3 states have call successors, (11), 2 states have call predecessors, (11), 4 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) [2025-03-04 02:59:41,210 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-04 02:59:41,210 INFO L93 Difference]: Finished difference Result 188 states and 255 transitions. [2025-03-04 02:59:41,212 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2025-03-04 02:59:41,212 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 8.2) internal successors, (41), 5 states have internal predecessors, (41), 3 states have call successors, (11), 2 states have call predecessors, (11), 4 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) Word has length 73 [2025-03-04 02:59:41,212 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-04 02:59:41,214 INFO L225 Difference]: With dead ends: 188 [2025-03-04 02:59:41,214 INFO L226 Difference]: Without dead ends: 101 [2025-03-04 02:59:41,214 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 72 GetRequests, 68 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2025-03-04 02:59:41,215 INFO L435 NwaCegarLoop]: 124 mSDtfsCounter, 0 mSDsluCounter, 478 mSDsCounter, 0 mSdLazyCounter, 44 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 602 SdHoareTripleChecker+Invalid, 44 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 44 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-04 02:59:41,215 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 602 Invalid, 44 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 44 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-04 02:59:41,218 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 101 states. [2025-03-04 02:59:41,227 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 101 to 101. [2025-03-04 02:59:41,228 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 101 states, 64 states have (on average 1.234375) internal successors, (79), 66 states have internal predecessors, (79), 28 states have call successors, (28), 7 states have call predecessors, (28), 8 states have return successors, (29), 27 states have call predecessors, (29), 27 states have call successors, (29) [2025-03-04 02:59:41,229 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 101 states to 101 states and 136 transitions. [2025-03-04 02:59:41,229 INFO L78 Accepts]: Start accepts. Automaton has 101 states and 136 transitions. Word has length 73 [2025-03-04 02:59:41,230 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-04 02:59:41,230 INFO L471 AbstractCegarLoop]: Abstraction has 101 states and 136 transitions. [2025-03-04 02:59:41,230 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 8.2) internal successors, (41), 5 states have internal predecessors, (41), 3 states have call successors, (11), 2 states have call predecessors, (11), 4 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) [2025-03-04 02:59:41,230 INFO L276 IsEmpty]: Start isEmpty. Operand 101 states and 136 transitions. [2025-03-04 02:59:41,231 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 75 [2025-03-04 02:59:41,232 INFO L210 NwaCegarLoop]: Found error trace [2025-03-04 02:59:41,232 INFO L218 NwaCegarLoop]: trace histogram [5, 5, 5, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-04 02:59:41,240 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2025-03-04 02:59:41,436 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-04 02:59:41,436 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-04 02:59:41,436 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 02:59:41,436 INFO L85 PathProgramCache]: Analyzing trace with hash -2110564237, now seen corresponding path program 1 times [2025-03-04 02:59:41,437 INFO L118 FreeRefinementEngine]: Executing refinement strategy FOX [2025-03-04 02:59:41,437 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [479837851] [2025-03-04 02:59:41,437 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-04 02:59:41,437 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-04 02:59:41,437 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 02:59:41,440 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-04 02:59:41,449 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2025-03-04 02:59:41,569 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 74 statements into 1 equivalence classes. [2025-03-04 02:59:41,613 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 74 of 74 statements. [2025-03-04 02:59:41,613 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 02:59:41,613 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 02:59:41,618 INFO L256 TraceCheckSpWp]: Trace formula consists of 265 conjuncts, 8 conjuncts are in the unsatisfiable core [2025-03-04 02:59:41,621 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-04 02:59:41,702 INFO L134 CoverageAnalysis]: Checked inductivity of 47 backedges. 16 proven. 0 refuted. 0 times theorem prover too weak. 31 trivial. 0 not checked. [2025-03-04 02:59:41,704 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-04 02:59:41,705 INFO L136 FreeRefinementEngine]: Strategy FOX found an infeasible trace [2025-03-04 02:59:41,705 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [479837851] [2025-03-04 02:59:41,705 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [479837851] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-04 02:59:41,705 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-04 02:59:41,705 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2025-03-04 02:59:41,705 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2130518406] [2025-03-04 02:59:41,705 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-04 02:59:41,706 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2025-03-04 02:59:41,706 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FOX [2025-03-04 02:59:41,706 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2025-03-04 02:59:41,707 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2025-03-04 02:59:41,707 INFO L87 Difference]: Start difference. First operand 101 states and 136 transitions. Second operand has 7 states, 6 states have (on average 6.5) internal successors, (39), 7 states have internal predecessors, (39), 3 states have call successors, (11), 2 states have call predecessors, (11), 3 states have return successors, (9), 2 states have call predecessors, (9), 3 states have call successors, (9) [2025-03-04 02:59:41,854 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-04 02:59:41,855 INFO L93 Difference]: Finished difference Result 195 states and 264 transitions. [2025-03-04 02:59:41,855 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2025-03-04 02:59:41,855 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 6 states have (on average 6.5) internal successors, (39), 7 states have internal predecessors, (39), 3 states have call successors, (11), 2 states have call predecessors, (11), 3 states have return successors, (9), 2 states have call predecessors, (9), 3 states have call successors, (9) Word has length 74 [2025-03-04 02:59:41,855 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-04 02:59:41,856 INFO L225 Difference]: With dead ends: 195 [2025-03-04 02:59:41,856 INFO L226 Difference]: Without dead ends: 103 [2025-03-04 02:59:41,857 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 74 GetRequests, 68 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=15, Invalid=41, Unknown=0, NotChecked=0, Total=56 [2025-03-04 02:59:41,857 INFO L435 NwaCegarLoop]: 118 mSDtfsCounter, 25 mSDsluCounter, 525 mSDsCounter, 0 mSdLazyCounter, 85 mSolverCounterSat, 16 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 35 SdHoareTripleChecker+Valid, 643 SdHoareTripleChecker+Invalid, 101 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 16 IncrementalHoareTripleChecker+Valid, 85 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-04 02:59:41,858 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [35 Valid, 643 Invalid, 101 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [16 Valid, 85 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-04 02:59:41,858 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 103 states. [2025-03-04 02:59:41,866 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 103 to 101. [2025-03-04 02:59:41,867 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 101 states, 64 states have (on average 1.21875) internal successors, (78), 66 states have internal predecessors, (78), 28 states have call successors, (28), 7 states have call predecessors, (28), 8 states have return successors, (29), 27 states have call predecessors, (29), 27 states have call successors, (29) [2025-03-04 02:59:41,867 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 101 states to 101 states and 135 transitions. [2025-03-04 02:59:41,868 INFO L78 Accepts]: Start accepts. Automaton has 101 states and 135 transitions. Word has length 74 [2025-03-04 02:59:41,868 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-04 02:59:41,868 INFO L471 AbstractCegarLoop]: Abstraction has 101 states and 135 transitions. [2025-03-04 02:59:41,868 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 6 states have (on average 6.5) internal successors, (39), 7 states have internal predecessors, (39), 3 states have call successors, (11), 2 states have call predecessors, (11), 3 states have return successors, (9), 2 states have call predecessors, (9), 3 states have call successors, (9) [2025-03-04 02:59:41,868 INFO L276 IsEmpty]: Start isEmpty. Operand 101 states and 135 transitions. [2025-03-04 02:59:41,869 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 77 [2025-03-04 02:59:41,869 INFO L210 NwaCegarLoop]: Found error trace [2025-03-04 02:59:41,869 INFO L218 NwaCegarLoop]: trace histogram [5, 5, 5, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-04 02:59:41,877 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2025-03-04 02:59:42,069 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-04 02:59:42,069 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-04 02:59:42,070 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 02:59:42,070 INFO L85 PathProgramCache]: Analyzing trace with hash -1922868885, now seen corresponding path program 1 times [2025-03-04 02:59:42,070 INFO L118 FreeRefinementEngine]: Executing refinement strategy FOX [2025-03-04 02:59:42,070 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1493190228] [2025-03-04 02:59:42,070 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-04 02:59:42,071 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-04 02:59:42,071 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 02:59:42,072 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-04 02:59:42,073 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2025-03-04 02:59:42,187 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 76 statements into 1 equivalence classes. [2025-03-04 02:59:42,229 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 76 of 76 statements. [2025-03-04 02:59:42,229 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 02:59:42,229 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 02:59:42,233 INFO L256 TraceCheckSpWp]: Trace formula consists of 269 conjuncts, 9 conjuncts are in the unsatisfiable core [2025-03-04 02:59:42,235 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-04 02:59:42,313 INFO L134 CoverageAnalysis]: Checked inductivity of 47 backedges. 16 proven. 0 refuted. 0 times theorem prover too weak. 31 trivial. 0 not checked. [2025-03-04 02:59:42,316 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-04 02:59:42,316 INFO L136 FreeRefinementEngine]: Strategy FOX found an infeasible trace [2025-03-04 02:59:42,316 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1493190228] [2025-03-04 02:59:42,316 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1493190228] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-04 02:59:42,316 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-04 02:59:42,316 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2025-03-04 02:59:42,317 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [16573012] [2025-03-04 02:59:42,317 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-04 02:59:42,317 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2025-03-04 02:59:42,317 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FOX [2025-03-04 02:59:42,317 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2025-03-04 02:59:42,317 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=43, Unknown=0, NotChecked=0, Total=56 [2025-03-04 02:59:42,318 INFO L87 Difference]: Start difference. First operand 101 states and 135 transitions. Second operand has 8 states, 7 states have (on average 5.857142857142857) internal successors, (41), 8 states have internal predecessors, (41), 3 states have call successors, (11), 2 states have call predecessors, (11), 3 states have return successors, (9), 2 states have call predecessors, (9), 3 states have call successors, (9) [2025-03-04 02:59:42,506 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-04 02:59:42,506 INFO L93 Difference]: Finished difference Result 201 states and 272 transitions. [2025-03-04 02:59:42,507 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2025-03-04 02:59:42,507 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 7 states have (on average 5.857142857142857) internal successors, (41), 8 states have internal predecessors, (41), 3 states have call successors, (11), 2 states have call predecessors, (11), 3 states have return successors, (9), 2 states have call predecessors, (9), 3 states have call successors, (9) Word has length 76 [2025-03-04 02:59:42,507 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-04 02:59:42,508 INFO L225 Difference]: With dead ends: 201 [2025-03-04 02:59:42,508 INFO L226 Difference]: Without dead ends: 108 [2025-03-04 02:59:42,509 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 78 GetRequests, 69 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=25, Invalid=85, Unknown=0, NotChecked=0, Total=110 [2025-03-04 02:59:42,509 INFO L435 NwaCegarLoop]: 115 mSDtfsCounter, 34 mSDsluCounter, 624 mSDsCounter, 0 mSdLazyCounter, 116 mSolverCounterSat, 18 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 44 SdHoareTripleChecker+Valid, 739 SdHoareTripleChecker+Invalid, 134 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 18 IncrementalHoareTripleChecker+Valid, 116 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-04 02:59:42,509 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [44 Valid, 739 Invalid, 134 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [18 Valid, 116 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-04 02:59:42,510 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 108 states. [2025-03-04 02:59:42,516 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 108 to 102. [2025-03-04 02:59:42,517 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 102 states, 65 states have (on average 1.2153846153846153) internal successors, (79), 67 states have internal predecessors, (79), 28 states have call successors, (28), 7 states have call predecessors, (28), 8 states have return successors, (29), 27 states have call predecessors, (29), 27 states have call successors, (29) [2025-03-04 02:59:42,517 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 102 states to 102 states and 136 transitions. [2025-03-04 02:59:42,518 INFO L78 Accepts]: Start accepts. Automaton has 102 states and 136 transitions. Word has length 76 [2025-03-04 02:59:42,518 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-04 02:59:42,518 INFO L471 AbstractCegarLoop]: Abstraction has 102 states and 136 transitions. [2025-03-04 02:59:42,518 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 7 states have (on average 5.857142857142857) internal successors, (41), 8 states have internal predecessors, (41), 3 states have call successors, (11), 2 states have call predecessors, (11), 3 states have return successors, (9), 2 states have call predecessors, (9), 3 states have call successors, (9) [2025-03-04 02:59:42,518 INFO L276 IsEmpty]: Start isEmpty. Operand 102 states and 136 transitions. [2025-03-04 02:59:42,519 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 78 [2025-03-04 02:59:42,519 INFO L210 NwaCegarLoop]: Found error trace [2025-03-04 02:59:42,519 INFO L218 NwaCegarLoop]: trace histogram [5, 5, 5, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-04 02:59:42,527 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2025-03-04 02:59:42,723 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-04 02:59:42,723 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-04 02:59:42,723 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 02:59:42,723 INFO L85 PathProgramCache]: Analyzing trace with hash 1164406586, now seen corresponding path program 1 times [2025-03-04 02:59:42,724 INFO L118 FreeRefinementEngine]: Executing refinement strategy FOX [2025-03-04 02:59:42,724 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [63841904] [2025-03-04 02:59:42,724 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-04 02:59:42,724 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-04 02:59:42,724 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 02:59:42,726 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-04 02:59:42,727 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2025-03-04 02:59:42,835 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 77 statements into 1 equivalence classes. [2025-03-04 02:59:42,873 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 77 of 77 statements. [2025-03-04 02:59:42,873 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 02:59:42,873 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 02:59:42,877 INFO L256 TraceCheckSpWp]: Trace formula consists of 271 conjuncts, 2 conjuncts are in the unsatisfiable core [2025-03-04 02:59:42,879 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-04 02:59:42,895 INFO L134 CoverageAnalysis]: Checked inductivity of 47 backedges. 16 proven. 0 refuted. 0 times theorem prover too weak. 31 trivial. 0 not checked. [2025-03-04 02:59:42,895 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-04 02:59:42,895 INFO L136 FreeRefinementEngine]: Strategy FOX found an infeasible trace [2025-03-04 02:59:42,895 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [63841904] [2025-03-04 02:59:42,895 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [63841904] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-04 02:59:42,895 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-04 02:59:42,895 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2025-03-04 02:59:42,895 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [587092827] [2025-03-04 02:59:42,895 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-04 02:59:42,896 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2025-03-04 02:59:42,896 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FOX [2025-03-04 02:59:42,896 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2025-03-04 02:59:42,896 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2025-03-04 02:59:42,897 INFO L87 Difference]: Start difference. First operand 102 states and 136 transitions. Second operand has 3 states, 3 states have (on average 14.0) internal successors, (42), 3 states have internal predecessors, (42), 2 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) [2025-03-04 02:59:42,920 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-04 02:59:42,920 INFO L93 Difference]: Finished difference Result 196 states and 267 transitions. [2025-03-04 02:59:42,921 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2025-03-04 02:59:42,921 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 14.0) internal successors, (42), 3 states have internal predecessors, (42), 2 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) Word has length 77 [2025-03-04 02:59:42,921 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-04 02:59:42,922 INFO L225 Difference]: With dead ends: 196 [2025-03-04 02:59:42,922 INFO L226 Difference]: Without dead ends: 106 [2025-03-04 02:59:42,922 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 76 GetRequests, 75 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2025-03-04 02:59:42,923 INFO L435 NwaCegarLoop]: 126 mSDtfsCounter, 2 mSDsluCounter, 121 mSDsCounter, 0 mSdLazyCounter, 10 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3 SdHoareTripleChecker+Valid, 247 SdHoareTripleChecker+Invalid, 10 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 10 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-04 02:59:42,923 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [3 Valid, 247 Invalid, 10 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 10 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-04 02:59:42,924 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 106 states. [2025-03-04 02:59:42,930 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 106 to 103. [2025-03-04 02:59:42,931 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 103 states, 66 states have (on average 1.2121212121212122) internal successors, (80), 68 states have internal predecessors, (80), 28 states have call successors, (28), 7 states have call predecessors, (28), 8 states have return successors, (29), 27 states have call predecessors, (29), 27 states have call successors, (29) [2025-03-04 02:59:42,931 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 103 states to 103 states and 137 transitions. [2025-03-04 02:59:42,932 INFO L78 Accepts]: Start accepts. Automaton has 103 states and 137 transitions. Word has length 77 [2025-03-04 02:59:42,932 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-04 02:59:42,932 INFO L471 AbstractCegarLoop]: Abstraction has 103 states and 137 transitions. [2025-03-04 02:59:42,932 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 14.0) internal successors, (42), 3 states have internal predecessors, (42), 2 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) [2025-03-04 02:59:42,932 INFO L276 IsEmpty]: Start isEmpty. Operand 103 states and 137 transitions. [2025-03-04 02:59:42,933 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 86 [2025-03-04 02:59:42,933 INFO L210 NwaCegarLoop]: Found error trace [2025-03-04 02:59:42,933 INFO L218 NwaCegarLoop]: trace histogram [5, 5, 5, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-04 02:59:42,942 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2025-03-04 02:59:43,134 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-04 02:59:43,134 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-04 02:59:43,134 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 02:59:43,134 INFO L85 PathProgramCache]: Analyzing trace with hash -314597, now seen corresponding path program 1 times [2025-03-04 02:59:43,135 INFO L118 FreeRefinementEngine]: Executing refinement strategy FOX [2025-03-04 02:59:43,135 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1343726989] [2025-03-04 02:59:43,135 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-04 02:59:43,135 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-04 02:59:43,135 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 02:59:43,137 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-04 02:59:43,138 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2025-03-04 02:59:43,273 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 85 statements into 1 equivalence classes. [2025-03-04 02:59:43,318 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 85 of 85 statements. [2025-03-04 02:59:43,319 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 02:59:43,319 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 02:59:43,323 INFO L256 TraceCheckSpWp]: Trace formula consists of 291 conjuncts, 6 conjuncts are in the unsatisfiable core [2025-03-04 02:59:43,325 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-04 02:59:43,369 INFO L134 CoverageAnalysis]: Checked inductivity of 47 backedges. 27 proven. 0 refuted. 0 times theorem prover too weak. 20 trivial. 0 not checked. [2025-03-04 02:59:43,371 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-04 02:59:43,371 INFO L136 FreeRefinementEngine]: Strategy FOX found an infeasible trace [2025-03-04 02:59:43,371 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1343726989] [2025-03-04 02:59:43,371 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1343726989] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-04 02:59:43,371 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-04 02:59:43,371 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2025-03-04 02:59:43,371 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1831234033] [2025-03-04 02:59:43,371 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-04 02:59:43,372 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2025-03-04 02:59:43,372 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FOX [2025-03-04 02:59:43,372 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2025-03-04 02:59:43,372 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2025-03-04 02:59:43,372 INFO L87 Difference]: Start difference. First operand 103 states and 137 transitions. Second operand has 7 states, 6 states have (on average 8.5) internal successors, (51), 6 states have internal predecessors, (51), 3 states have call successors, (12), 2 states have call predecessors, (12), 4 states have return successors, (10), 3 states have call predecessors, (10), 3 states have call successors, (10) [2025-03-04 02:59:43,438 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-04 02:59:43,440 INFO L93 Difference]: Finished difference Result 197 states and 264 transitions. [2025-03-04 02:59:43,440 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2025-03-04 02:59:43,440 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 6 states have (on average 8.5) internal successors, (51), 6 states have internal predecessors, (51), 3 states have call successors, (12), 2 states have call predecessors, (12), 4 states have return successors, (10), 3 states have call predecessors, (10), 3 states have call successors, (10) Word has length 85 [2025-03-04 02:59:43,440 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-04 02:59:43,441 INFO L225 Difference]: With dead ends: 197 [2025-03-04 02:59:43,441 INFO L226 Difference]: Without dead ends: 106 [2025-03-04 02:59:43,441 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 84 GetRequests, 79 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2025-03-04 02:59:43,442 INFO L435 NwaCegarLoop]: 122 mSDtfsCounter, 0 mSDsluCounter, 590 mSDsCounter, 0 mSdLazyCounter, 57 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 712 SdHoareTripleChecker+Invalid, 58 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 57 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-04 02:59:43,442 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 712 Invalid, 58 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 57 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-04 02:59:43,442 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 106 states. [2025-03-04 02:59:43,447 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 106 to 104. [2025-03-04 02:59:43,447 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 104 states, 67 states have (on average 1.208955223880597) internal successors, (81), 69 states have internal predecessors, (81), 28 states have call successors, (28), 7 states have call predecessors, (28), 8 states have return successors, (29), 27 states have call predecessors, (29), 27 states have call successors, (29) [2025-03-04 02:59:43,448 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 104 states to 104 states and 138 transitions. [2025-03-04 02:59:43,448 INFO L78 Accepts]: Start accepts. Automaton has 104 states and 138 transitions. Word has length 85 [2025-03-04 02:59:43,449 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-04 02:59:43,449 INFO L471 AbstractCegarLoop]: Abstraction has 104 states and 138 transitions. [2025-03-04 02:59:43,449 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 6 states have (on average 8.5) internal successors, (51), 6 states have internal predecessors, (51), 3 states have call successors, (12), 2 states have call predecessors, (12), 4 states have return successors, (10), 3 states have call predecessors, (10), 3 states have call successors, (10) [2025-03-04 02:59:43,449 INFO L276 IsEmpty]: Start isEmpty. Operand 104 states and 138 transitions. [2025-03-04 02:59:43,449 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 88 [2025-03-04 02:59:43,450 INFO L210 NwaCegarLoop]: Found error trace [2025-03-04 02:59:43,450 INFO L218 NwaCegarLoop]: trace histogram [5, 5, 5, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-04 02:59:43,458 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2025-03-04 02:59:43,652 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-04 02:59:43,652 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-04 02:59:43,653 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 02:59:43,653 INFO L85 PathProgramCache]: Analyzing trace with hash 1068852629, now seen corresponding path program 1 times [2025-03-04 02:59:43,653 INFO L118 FreeRefinementEngine]: Executing refinement strategy FOX [2025-03-04 02:59:43,653 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [438588203] [2025-03-04 02:59:43,653 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-04 02:59:43,653 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-04 02:59:43,654 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 02:59:43,655 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-04 02:59:43,656 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2025-03-04 02:59:43,756 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 87 statements into 1 equivalence classes. [2025-03-04 02:59:43,797 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 87 of 87 statements. [2025-03-04 02:59:43,797 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 02:59:43,797 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 02:59:43,802 INFO L256 TraceCheckSpWp]: Trace formula consists of 295 conjuncts, 22 conjuncts are in the unsatisfiable core [2025-03-04 02:59:43,805 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-04 02:59:43,838 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 13 treesize of output 1 [2025-03-04 02:59:48,115 WARN L873 $PredicateComparison]: unable to prove that (or (exists ((|v_aws_linked_list_is_valid_aws_linked_list_is_valid_deep_~temp~0#1.base_BEFORE_CALL_1| (_ BitVec 64)) (|v_aws_linked_list_is_valid_aws_linked_list_is_valid_deep_~temp~0#1.offset_BEFORE_CALL_1| (_ BitVec 64))) (not (= (select (select |c_#memory_$Pointer$#2.base| |v_aws_linked_list_is_valid_aws_linked_list_is_valid_deep_~temp~0#1.base_BEFORE_CALL_1|) |v_aws_linked_list_is_valid_aws_linked_list_is_valid_deep_~temp~0#1.offset_BEFORE_CALL_1|) (_ bv0 64)))) (exists ((|v_aws_linked_list_is_valid_aws_linked_list_is_valid_deep_~temp~0#1.base_BEFORE_CALL_1| (_ BitVec 64)) (|v_aws_linked_list_is_valid_aws_linked_list_is_valid_deep_~temp~0#1.offset_BEFORE_CALL_1| (_ BitVec 64))) (not (= (_ bv0 64) (select (select |c_#memory_$Pointer$#2.offset| |v_aws_linked_list_is_valid_aws_linked_list_is_valid_deep_~temp~0#1.base_BEFORE_CALL_1|) |v_aws_linked_list_is_valid_aws_linked_list_is_valid_deep_~temp~0#1.offset_BEFORE_CALL_1|))))) is different from true [2025-03-04 02:59:48,335 INFO L134 CoverageAnalysis]: Checked inductivity of 48 backedges. 16 proven. 1 refuted. 0 times theorem prover too weak. 31 trivial. 0 not checked. [2025-03-04 02:59:48,335 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-04 02:59:48,621 INFO L134 CoverageAnalysis]: Checked inductivity of 48 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 47 trivial. 0 not checked. [2025-03-04 02:59:48,622 INFO L136 FreeRefinementEngine]: Strategy FOX found an infeasible trace [2025-03-04 02:59:48,622 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [438588203] [2025-03-04 02:59:48,622 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [438588203] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-04 02:59:48,622 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-04 02:59:48,622 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 8] total 17 [2025-03-04 02:59:48,622 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [524670292] [2025-03-04 02:59:48,622 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-04 02:59:48,623 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2025-03-04 02:59:48,623 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FOX [2025-03-04 02:59:48,623 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2025-03-04 02:59:48,623 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=44, Invalid=199, Unknown=1, NotChecked=28, Total=272 [2025-03-04 02:59:48,623 INFO L87 Difference]: Start difference. First operand 104 states and 138 transitions. Second operand has 17 states, 17 states have (on average 4.705882352941177) internal successors, (80), 17 states have internal predecessors, (80), 5 states have call successors, (21), 3 states have call predecessors, (21), 3 states have return successors, (19), 5 states have call predecessors, (19), 5 states have call successors, (19) [2025-03-04 02:59:50,336 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-04 02:59:50,336 INFO L93 Difference]: Finished difference Result 244 states and 335 transitions. [2025-03-04 02:59:50,336 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2025-03-04 02:59:50,337 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 17 states have (on average 4.705882352941177) internal successors, (80), 17 states have internal predecessors, (80), 5 states have call successors, (21), 3 states have call predecessors, (21), 3 states have return successors, (19), 5 states have call predecessors, (19), 5 states have call successors, (19) Word has length 87 [2025-03-04 02:59:50,337 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-04 02:59:50,338 INFO L225 Difference]: With dead ends: 244 [2025-03-04 02:59:50,338 INFO L226 Difference]: Without dead ends: 152 [2025-03-04 02:59:50,339 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 177 GetRequests, 156 SyntacticMatches, 1 SemanticMatches, 20 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 65 ImplicationChecksByTransitivity, 4.5s TimeCoverageRelationStatistics Valid=76, Invalid=347, Unknown=1, NotChecked=38, Total=462 [2025-03-04 02:59:50,339 INFO L435 NwaCegarLoop]: 122 mSDtfsCounter, 59 mSDsluCounter, 949 mSDsCounter, 0 mSdLazyCounter, 351 mSolverCounterSat, 11 mSolverCounterUnsat, 6 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 61 SdHoareTripleChecker+Valid, 1071 SdHoareTripleChecker+Invalid, 685 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 351 IncrementalHoareTripleChecker+Invalid, 6 IncrementalHoareTripleChecker+Unknown, 317 IncrementalHoareTripleChecker+Unchecked, 1.5s IncrementalHoareTripleChecker+Time [2025-03-04 02:59:50,339 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [61 Valid, 1071 Invalid, 685 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 351 Invalid, 6 Unknown, 317 Unchecked, 1.5s Time] [2025-03-04 02:59:50,340 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 152 states. [2025-03-04 02:59:50,346 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 152 to 122. [2025-03-04 02:59:50,347 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 122 states, 83 states have (on average 1.2409638554216869) internal successors, (103), 85 states have internal predecessors, (103), 29 states have call successors, (29), 8 states have call predecessors, (29), 9 states have return successors, (31), 28 states have call predecessors, (31), 28 states have call successors, (31) [2025-03-04 02:59:50,351 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 122 states to 122 states and 163 transitions. [2025-03-04 02:59:50,351 INFO L78 Accepts]: Start accepts. Automaton has 122 states and 163 transitions. Word has length 87 [2025-03-04 02:59:50,351 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-04 02:59:50,351 INFO L471 AbstractCegarLoop]: Abstraction has 122 states and 163 transitions. [2025-03-04 02:59:50,351 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 17 states have (on average 4.705882352941177) internal successors, (80), 17 states have internal predecessors, (80), 5 states have call successors, (21), 3 states have call predecessors, (21), 3 states have return successors, (19), 5 states have call predecessors, (19), 5 states have call successors, (19) [2025-03-04 02:59:50,351 INFO L276 IsEmpty]: Start isEmpty. Operand 122 states and 163 transitions. [2025-03-04 02:59:50,352 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 88 [2025-03-04 02:59:50,352 INFO L210 NwaCegarLoop]: Found error trace [2025-03-04 02:59:50,352 INFO L218 NwaCegarLoop]: trace histogram [5, 5, 5, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-04 02:59:50,360 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2025-03-04 02:59:50,556 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-04 02:59:50,556 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-04 02:59:50,556 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 02:59:50,556 INFO L85 PathProgramCache]: Analyzing trace with hash -601660940, now seen corresponding path program 1 times [2025-03-04 02:59:50,556 INFO L118 FreeRefinementEngine]: Executing refinement strategy FOX [2025-03-04 02:59:50,557 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1940347274] [2025-03-04 02:59:50,557 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-04 02:59:50,557 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-04 02:59:50,557 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 02:59:50,558 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-04 02:59:50,559 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2025-03-04 02:59:50,660 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 87 statements into 1 equivalence classes. [2025-03-04 02:59:50,698 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 87 of 87 statements. [2025-03-04 02:59:50,698 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 02:59:50,698 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 02:59:50,702 INFO L256 TraceCheckSpWp]: Trace formula consists of 292 conjuncts, 3 conjuncts are in the unsatisfiable core [2025-03-04 02:59:50,704 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-04 02:59:50,714 INFO L134 CoverageAnalysis]: Checked inductivity of 48 backedges. 16 proven. 0 refuted. 0 times theorem prover too weak. 32 trivial. 0 not checked. [2025-03-04 02:59:50,714 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-04 02:59:50,714 INFO L136 FreeRefinementEngine]: Strategy FOX found an infeasible trace [2025-03-04 02:59:50,714 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1940347274] [2025-03-04 02:59:50,714 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1940347274] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-04 02:59:50,714 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-04 02:59:50,714 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2025-03-04 02:59:50,714 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1573683547] [2025-03-04 02:59:50,714 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-04 02:59:50,715 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2025-03-04 02:59:50,715 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FOX [2025-03-04 02:59:50,715 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2025-03-04 02:59:50,715 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2025-03-04 02:59:50,715 INFO L87 Difference]: Start difference. First operand 122 states and 163 transitions. Second operand has 4 states, 4 states have (on average 12.5) internal successors, (50), 4 states have internal predecessors, (50), 2 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (10), 2 states have call predecessors, (10), 2 states have call successors, (10) [2025-03-04 02:59:50,735 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-04 02:59:50,736 INFO L93 Difference]: Finished difference Result 226 states and 308 transitions. [2025-03-04 02:59:50,736 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2025-03-04 02:59:50,737 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 12.5) internal successors, (50), 4 states have internal predecessors, (50), 2 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (10), 2 states have call predecessors, (10), 2 states have call successors, (10) Word has length 87 [2025-03-04 02:59:50,737 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-04 02:59:50,738 INFO L225 Difference]: With dead ends: 226 [2025-03-04 02:59:50,738 INFO L226 Difference]: Without dead ends: 116 [2025-03-04 02:59:50,738 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 86 GetRequests, 84 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2025-03-04 02:59:50,739 INFO L435 NwaCegarLoop]: 128 mSDtfsCounter, 0 mSDsluCounter, 245 mSDsCounter, 0 mSdLazyCounter, 16 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 373 SdHoareTripleChecker+Invalid, 17 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 16 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-04 02:59:50,739 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 373 Invalid, 17 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 16 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-04 02:59:50,739 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 116 states. [2025-03-04 02:59:50,748 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 116 to 116. [2025-03-04 02:59:50,748 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 116 states, 77 states have (on average 1.2207792207792207) internal successors, (94), 79 states have internal predecessors, (94), 29 states have call successors, (29), 8 states have call predecessors, (29), 9 states have return successors, (31), 28 states have call predecessors, (31), 28 states have call successors, (31) [2025-03-04 02:59:50,749 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 116 states to 116 states and 154 transitions. [2025-03-04 02:59:50,749 INFO L78 Accepts]: Start accepts. Automaton has 116 states and 154 transitions. Word has length 87 [2025-03-04 02:59:50,749 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-04 02:59:50,749 INFO L471 AbstractCegarLoop]: Abstraction has 116 states and 154 transitions. [2025-03-04 02:59:50,749 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 12.5) internal successors, (50), 4 states have internal predecessors, (50), 2 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (10), 2 states have call predecessors, (10), 2 states have call successors, (10) [2025-03-04 02:59:50,749 INFO L276 IsEmpty]: Start isEmpty. Operand 116 states and 154 transitions. [2025-03-04 02:59:50,750 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 89 [2025-03-04 02:59:50,750 INFO L210 NwaCegarLoop]: Found error trace [2025-03-04 02:59:50,750 INFO L218 NwaCegarLoop]: trace histogram [5, 5, 5, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-04 02:59:50,759 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2025-03-04 02:59:50,954 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-04 02:59:50,954 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-04 02:59:50,954 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 02:59:50,954 INFO L85 PathProgramCache]: Analyzing trace with hash -581506992, now seen corresponding path program 1 times [2025-03-04 02:59:50,955 INFO L118 FreeRefinementEngine]: Executing refinement strategy FOX [2025-03-04 02:59:50,955 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [173997202] [2025-03-04 02:59:50,955 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-04 02:59:50,955 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-04 02:59:50,955 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 02:59:50,957 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-04 02:59:50,958 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2025-03-04 02:59:51,059 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 88 statements into 1 equivalence classes. [2025-03-04 02:59:51,111 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 88 of 88 statements. [2025-03-04 02:59:51,111 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 02:59:51,111 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 02:59:51,116 INFO L256 TraceCheckSpWp]: Trace formula consists of 297 conjuncts, 58 conjuncts are in the unsatisfiable core [2025-03-04 02:59:51,121 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-04 02:59:51,131 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 10 treesize of output 8 [2025-03-04 02:59:51,288 INFO L349 Elim1Store]: treesize reduction 17, result has 29.2 percent of original size [2025-03-04 02:59:51,288 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 1 case distinctions, treesize of input 14 treesize of output 15 [2025-03-04 02:59:52,844 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 141 treesize of output 126 [2025-03-04 02:59:52,848 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-04 02:59:52,854 INFO L349 Elim1Store]: treesize reduction 7, result has 12.5 percent of original size [2025-03-04 02:59:52,854 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 3 new quantified variables, introduced 1 case distinctions, treesize of input 115 treesize of output 81 [2025-03-04 02:59:52,889 INFO L349 Elim1Store]: treesize reduction 114, result has 7.3 percent of original size [2025-03-04 02:59:52,890 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 2 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 5 new quantified variables, introduced 4 case distinctions, treesize of input 154 treesize of output 119 [2025-03-04 02:59:52,896 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 1 [2025-03-04 02:59:52,902 INFO L173 IndexEqualityManager]: detected equality via solver [2025-03-04 02:59:52,905 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 32 treesize of output 31 [2025-03-04 02:59:52,909 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 15 [2025-03-04 02:59:52,937 INFO L349 Elim1Store]: treesize reduction 25, result has 30.6 percent of original size [2025-03-04 02:59:52,938 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 31 treesize of output 37 [2025-03-04 02:59:52,944 INFO L173 IndexEqualityManager]: detected equality via solver [2025-03-04 02:59:52,944 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 52 treesize of output 19 [2025-03-04 02:59:52,955 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-04 02:59:52,955 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 19 treesize of output 23 [2025-03-04 02:59:53,814 INFO L349 Elim1Store]: treesize reduction 93, result has 17.7 percent of original size [2025-03-04 02:59:53,814 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 7 select indices, 7 select index equivalence classes, 3 disjoint index pairs (out of 21 index pairs), introduced 9 new quantified variables, introduced 21 case distinctions, treesize of input 185 treesize of output 114 [2025-03-04 02:59:53,963 INFO L134 CoverageAnalysis]: Checked inductivity of 49 backedges. 4 proven. 19 refuted. 0 times theorem prover too weak. 26 trivial. 0 not checked. [2025-03-04 02:59:53,963 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-04 02:59:54,677 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-04 02:59:54,677 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 2 case distinctions, treesize of input 115 treesize of output 108 [2025-03-04 02:59:54,699 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-04 02:59:54,700 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 344 treesize of output 342 [2025-03-04 02:59:54,713 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 331 treesize of output 323 [2025-03-04 02:59:54,748 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 4 [2025-03-04 02:59:54,778 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 186 treesize of output 180 [2025-03-04 02:59:57,163 INFO L349 Elim1Store]: treesize reduction 34, result has 58.5 percent of original size [2025-03-04 02:59:57,164 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 4 new quantified variables, introduced 7 case distinctions, treesize of input 10406 treesize of output 8282 [2025-03-04 02:59:57,352 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-04 02:59:57,353 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 0 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 1006 treesize of output 1000 [2025-03-04 02:59:57,395 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 1738 treesize of output 1626 [2025-03-04 02:59:58,286 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-04 02:59:58,286 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 1 case distinctions, treesize of input 7 treesize of output 6 [2025-03-04 02:59:58,373 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 4 [2025-03-04 02:59:58,379 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 4 [2025-03-04 02:59:58,403 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 4 [2025-03-04 02:59:58,410 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 4 [2025-03-04 02:59:58,770 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-04 02:59:58,770 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 11 treesize of output 15 [2025-03-04 02:59:58,784 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 4 [2025-03-04 02:59:58,804 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-04 02:59:58,804 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 44 treesize of output 44 [2025-03-04 02:59:58,836 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-04 02:59:58,836 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 622 treesize of output 582 [2025-03-04 02:59:58,964 WARN L214 Elim1Store]: Array PQE input equivalent to true [2025-03-04 02:59:59,008 INFO L349 Elim1Store]: treesize reduction 14, result has 61.1 percent of original size [2025-03-04 02:59:59,008 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 57 treesize of output 71 [2025-03-04 03:00:03,198 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-04 03:00:03,199 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 1420 treesize of output 1348 [2025-03-04 03:00:03,257 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-04 03:00:03,257 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 1 case distinctions, treesize of input 7 treesize of output 6 [2025-03-04 03:00:03,285 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-04 03:00:03,285 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 36 treesize of output 40 [2025-03-04 03:00:15,641 WARN L286 SmtUtils]: Spent 12.32s on a formula simplification. DAG size of input: 20 DAG size of output: 1 (called from [L 346] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.arrays.Elim1Store.elim1) [2025-03-04 03:00:15,641 INFO L349 Elim1Store]: treesize reduction 35, result has 2.8 percent of original size [2025-03-04 03:00:15,641 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 123 treesize of output 1 [2025-03-04 03:00:15,950 INFO L134 CoverageAnalysis]: Checked inductivity of 49 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 43 trivial. 0 not checked. [2025-03-04 03:00:15,950 INFO L136 FreeRefinementEngine]: Strategy FOX found an infeasible trace [2025-03-04 03:00:15,951 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [173997202] [2025-03-04 03:00:15,951 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [173997202] provided 1 perfect and 1 imperfect interpolant sequences [2025-03-04 03:00:15,951 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-03-04 03:00:15,951 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [15] imperfect sequences [19] total 32 [2025-03-04 03:00:15,951 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1016310016] [2025-03-04 03:00:15,951 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-04 03:00:15,951 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2025-03-04 03:00:15,951 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FOX [2025-03-04 03:00:15,951 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2025-03-04 03:00:15,952 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=84, Invalid=908, Unknown=0, NotChecked=0, Total=992 [2025-03-04 03:00:15,952 INFO L87 Difference]: Start difference. First operand 116 states and 154 transitions. Second operand has 15 states, 13 states have (on average 4.076923076923077) internal successors, (53), 12 states have internal predecessors, (53), 6 states have call successors, (12), 3 states have call predecessors, (12), 2 states have return successors, (10), 5 states have call predecessors, (10), 5 states have call successors, (10) [2025-03-04 03:00:33,785 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.17s for a HTC check with result INVALID. Formula has sorts [Array, Bool, BitVec], hasArrays=true, hasNonlinArith=false, quantifiers [] [2025-03-04 03:00:38,419 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.61s for a HTC check with result INVALID. Formula has sorts [Array, Bool, BitVec], hasArrays=true, hasNonlinArith=false, quantifiers []