./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/aws-c-common/aws_linked_list_back_harness.i --full-output --architecture 64bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 8fc3dc66 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_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 baad12004cda93802c22774fa87dd5ddbc51e76f7e3c81692100acfcfda43c3a --- Real Ultimate output --- This is Ultimate 0.3.0-?-8fc3dc6-m [2025-03-17 07:15:34,687 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-03-17 07:15:34,766 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-64bit-Automizer_Default.epf [2025-03-17 07:15:34,773 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-03-17 07:15:34,773 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-03-17 07:15:34,803 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-03-17 07:15:34,803 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-03-17 07:15:34,803 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-03-17 07:15:34,803 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-03-17 07:15:34,803 INFO L153 SettingsManager]: * Use memory slicer=true [2025-03-17 07:15:34,807 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2025-03-17 07:15:34,808 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2025-03-17 07:15:34,808 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-03-17 07:15:34,808 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-03-17 07:15:34,808 INFO L153 SettingsManager]: * Use SBE=true [2025-03-17 07:15:34,808 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-03-17 07:15:34,808 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2025-03-17 07:15:34,808 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2025-03-17 07:15:34,808 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-03-17 07:15:34,808 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2025-03-17 07:15:34,808 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2025-03-17 07:15:34,808 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2025-03-17 07:15:34,808 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-03-17 07:15:34,808 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-03-17 07:15:34,808 INFO L153 SettingsManager]: * Use constant arrays=true [2025-03-17 07:15:34,809 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-03-17 07:15:34,809 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-03-17 07:15:34,809 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-03-17 07:15:34,809 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-03-17 07:15:34,809 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-17 07:15:34,809 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-03-17 07:15:34,809 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2025-03-17 07:15:34,809 INFO L153 SettingsManager]: * Compute procedure contracts=false [2025-03-17 07:15:34,809 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2025-03-17 07:15:34,809 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2025-03-17 07:15:34,809 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2025-03-17 07:15:34,809 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2025-03-17 07:15:34,809 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2025-03-17 07:15:34,809 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2025-03-17 07:15:34,809 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2025-03-17 07:15:34,809 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 -> baad12004cda93802c22774fa87dd5ddbc51e76f7e3c81692100acfcfda43c3a [2025-03-17 07:15:35,080 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-03-17 07:15:35,090 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-03-17 07:15:35,093 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-03-17 07:15:35,094 INFO L270 PluginConnector]: Initializing CDTParser... [2025-03-17 07:15:35,094 INFO L274 PluginConnector]: CDTParser initialized [2025-03-17 07:15:35,095 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_back_harness.i [2025-03-17 07:15:36,383 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/bdd4d39e8/ce6784a07c4d4991b0edc5c7c84dd784/FLAG5ed835d1e [2025-03-17 07:15:36,935 INFO L384 CDTParser]: Found 1 translation units. [2025-03-17 07:15:36,936 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/aws-c-common/aws_linked_list_back_harness.i [2025-03-17 07:15:36,986 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/bdd4d39e8/ce6784a07c4d4991b0edc5c7c84dd784/FLAG5ed835d1e [2025-03-17 07:15:37,011 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/bdd4d39e8/ce6784a07c4d4991b0edc5c7c84dd784 [2025-03-17 07:15:37,014 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-03-17 07:15:37,015 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-03-17 07:15:37,017 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-03-17 07:15:37,018 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-03-17 07:15:37,022 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-03-17 07:15:37,023 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 17.03 07:15:37" (1/1) ... [2025-03-17 07:15:37,025 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@6aec7605 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 07:15:37, skipping insertion in model container [2025-03-17 07:15:37,025 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 17.03 07:15:37" (1/1) ... [2025-03-17 07:15:37,114 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-03-17 07:15:37,357 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_back_harness.i[4494,4507] [2025-03-17 07:15:37,364 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_back_harness.i[4554,4567] [2025-03-17 07:15:37,868 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-17 07:15:37,869 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-17 07:15:37,869 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-17 07:15:37,871 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-17 07:15:37,872 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-17 07:15:37,882 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-17 07:15:37,883 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-17 07:15:37,884 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-17 07:15:37,885 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-17 07:15:37,887 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-17 07:15:37,888 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-17 07:15:37,888 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-17 07:15:37,888 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-17 07:15:38,211 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_back_harness.i[150650,150663] [2025-03-17 07:15:38,212 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-17 07:15:38,233 INFO L200 MainTranslator]: Completed pre-run [2025-03-17 07:15:38,244 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_back_harness.i[4494,4507] [2025-03-17 07:15:38,245 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_back_harness.i[4554,4567] [2025-03-17 07:15:38,300 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-17 07:15:38,301 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-17 07:15:38,301 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-17 07:15:38,301 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-17 07:15:38,302 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-17 07:15:38,311 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-17 07:15:38,311 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-17 07:15:38,312 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-17 07:15:38,312 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-17 07:15:38,313 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-17 07:15:38,313 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-17 07:15:38,313 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-17 07:15:38,313 WARN L1731 CHandler]: Possible shadowing of function index [2025-03-17 07:15:38,393 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_back_harness.i[150650,150663] [2025-03-17 07:15:38,397 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-17 07:15:38,539 INFO L204 MainTranslator]: Completed translation [2025-03-17 07:15:38,540 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 07:15:38 WrapperNode [2025-03-17 07:15:38,541 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-03-17 07:15:38,542 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-03-17 07:15:38,542 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-03-17 07:15:38,543 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-03-17 07:15:38,550 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 07:15:38" (1/1) ... [2025-03-17 07:15:38,597 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 07:15:38" (1/1) ... [2025-03-17 07:15:38,630 INFO L138 Inliner]: procedures = 668, calls = 1043, calls flagged for inlining = 51, calls inlined = 5, statements flattened = 129 [2025-03-17 07:15:38,631 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-03-17 07:15:38,633 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-03-17 07:15:38,633 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-03-17 07:15:38,633 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-03-17 07:15:38,640 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 07:15:38" (1/1) ... [2025-03-17 07:15:38,640 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 07:15:38" (1/1) ... [2025-03-17 07:15:38,645 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 07:15:38" (1/1) ... [2025-03-17 07:15:38,664 INFO L175 MemorySlicer]: Split 27 memory accesses to 3 slices as follows [2, 5, 20]. 74 percent of accesses are in the largest equivalence class. The 7 initializations are split as follows [2, 5, 0]. The 6 writes are split as follows [0, 0, 6]. [2025-03-17 07:15:38,666 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 07:15:38" (1/1) ... [2025-03-17 07:15:38,667 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 07:15:38" (1/1) ... [2025-03-17 07:15:38,682 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 07:15:38" (1/1) ... [2025-03-17 07:15:38,686 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 07:15:38" (1/1) ... [2025-03-17 07:15:38,689 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 07:15:38" (1/1) ... [2025-03-17 07:15:38,692 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 07:15:38" (1/1) ... [2025-03-17 07:15:38,696 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-03-17 07:15:38,699 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2025-03-17 07:15:38,699 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2025-03-17 07:15:38,699 INFO L274 PluginConnector]: IcfgBuilder initialized [2025-03-17 07:15:38,700 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 07:15:38" (1/1) ... [2025-03-17 07:15:38,709 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-17 07:15:38,721 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 07:15:38,734 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-17 07:15:38,738 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-17 07:15:38,760 INFO L130 BoogieDeclarations]: Found specification of procedure aws_linked_list_back [2025-03-17 07:15:38,760 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_linked_list_back [2025-03-17 07:15:38,761 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2025-03-17 07:15:38,761 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2025-03-17 07:15:38,761 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2025-03-17 07:15:38,761 INFO L130 BoogieDeclarations]: Found specification of procedure aws_linked_list_node_next_is_valid [2025-03-17 07:15:38,761 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_linked_list_node_next_is_valid [2025-03-17 07:15:38,762 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnHeap [2025-03-17 07:15:38,762 INFO L130 BoogieDeclarations]: Found specification of procedure aws_linked_list_is_valid [2025-03-17 07:15:38,762 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_linked_list_is_valid [2025-03-17 07:15:38,762 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2025-03-17 07:15:38,762 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$#0 [2025-03-17 07:15:38,762 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$#1 [2025-03-17 07:15:38,762 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$#2 [2025-03-17 07:15:38,762 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-03-17 07:15:38,762 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-03-17 07:15:38,762 INFO L130 BoogieDeclarations]: Found specification of procedure aws_linked_list_empty [2025-03-17 07:15:38,763 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_linked_list_empty [2025-03-17 07:15:38,763 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2025-03-17 07:15:38,763 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2025-03-17 07:15:38,763 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2025-03-17 07:15:38,764 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$#0 [2025-03-17 07:15:38,764 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$#1 [2025-03-17 07:15:38,764 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$#2 [2025-03-17 07:15:38,764 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$#0 [2025-03-17 07:15:38,764 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$#1 [2025-03-17 07:15:38,764 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$#2 [2025-03-17 07:15:38,764 INFO L130 BoogieDeclarations]: Found specification of procedure nondet_uint64_t [2025-03-17 07:15:38,764 INFO L138 BoogieDeclarations]: Found implementation of procedure nondet_uint64_t [2025-03-17 07:15:38,764 INFO L130 BoogieDeclarations]: Found specification of procedure aws_linked_list_node_prev_is_valid [2025-03-17 07:15:38,764 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_linked_list_node_prev_is_valid [2025-03-17 07:15:38,764 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2025-03-17 07:15:38,764 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#1 [2025-03-17 07:15:38,764 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#2 [2025-03-17 07:15:38,939 INFO L256 CfgBuilder]: Building ICFG [2025-03-17 07:15:38,941 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2025-03-17 07:15:39,008 INFO L1322 $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-17 07:15:39,011 INFO L1322 $ProcedureCfgBuilder]: dead code at ProgramPoint L266: havoc #t~nondet9; [2025-03-17 07:15:39,038 INFO L1322 $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-17 07:15:39,181 INFO L1322 $ProcedureCfgBuilder]: dead code at ProgramPoint L4700: havoc #t~ret311#1; [2025-03-17 07:15:39,193 INFO L1322 $ProcedureCfgBuilder]: dead code at ProgramPoint L4685: havoc #t~mem302.base, #t~mem302.offset; [2025-03-17 07:15:39,219 INFO L? ?]: Removed 55 outVars from TransFormulas that were not future-live. [2025-03-17 07:15:39,219 INFO L307 CfgBuilder]: Performing block encoding [2025-03-17 07:15:39,230 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-03-17 07:15:39,232 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2025-03-17 07:15:39,232 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 17.03 07:15:39 BoogieIcfgContainer [2025-03-17 07:15:39,232 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2025-03-17 07:15:39,234 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2025-03-17 07:15:39,234 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2025-03-17 07:15:39,237 INFO L274 PluginConnector]: TraceAbstraction initialized [2025-03-17 07:15:39,238 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 17.03 07:15:37" (1/3) ... [2025-03-17 07:15:39,238 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@45dd24e7 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 17.03 07:15:39, skipping insertion in model container [2025-03-17 07:15:39,238 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 07:15:38" (2/3) ... [2025-03-17 07:15:39,238 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@45dd24e7 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 17.03 07:15:39, skipping insertion in model container [2025-03-17 07:15:39,238 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 17.03 07:15:39" (3/3) ... [2025-03-17 07:15:39,239 INFO L128 eAbstractionObserver]: Analyzing ICFG aws_linked_list_back_harness.i [2025-03-17 07:15:39,252 INFO L216 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2025-03-17 07:15:39,254 INFO L151 ceAbstractionStarter]: Applying trace abstraction to ICFG aws_linked_list_back_harness.i that has 9 procedures, 93 locations, 1 initial locations, 2 loop locations, and 1 error locations. [2025-03-17 07:15:39,305 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2025-03-17 07:15:39,317 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;@38bab123, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2025-03-17 07:15:39,318 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2025-03-17 07:15:39,322 INFO L276 IsEmpty]: Start isEmpty. Operand has 93 states, 59 states have (on average 1.2881355932203389) internal successors, (76), 60 states have internal predecessors, (76), 24 states have call successors, (24), 8 states have call predecessors, (24), 8 states have return successors, (24), 24 states have call predecessors, (24), 24 states have call successors, (24) [2025-03-17 07:15:39,328 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 84 [2025-03-17 07:15:39,328 INFO L210 NwaCegarLoop]: Found error trace [2025-03-17 07:15:39,328 INFO L218 NwaCegarLoop]: trace histogram [6, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-17 07:15:39,329 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-17 07:15:39,332 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 07:15:39,332 INFO L85 PathProgramCache]: Analyzing trace with hash -466351013, now seen corresponding path program 1 times [2025-03-17 07:15:39,337 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 07:15:39,338 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1442577804] [2025-03-17 07:15:39,338 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 07:15:39,338 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 07:15:39,478 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 83 statements into 1 equivalence classes. [2025-03-17 07:15:39,494 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 83 of 83 statements. [2025-03-17 07:15:39,495 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 07:15:39,495 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 07:15:39,713 INFO L134 CoverageAnalysis]: Checked inductivity of 77 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 67 trivial. 0 not checked. [2025-03-17 07:15:39,714 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-17 07:15:39,714 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1442577804] [2025-03-17 07:15:39,714 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1442577804] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-17 07:15:39,714 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1273515143] [2025-03-17 07:15:39,714 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 07:15:39,714 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-17 07:15:39,715 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 07:15:39,717 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-17 07:15:39,719 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-17 07:15:39,845 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 83 statements into 1 equivalence classes. [2025-03-17 07:15:39,903 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 83 of 83 statements. [2025-03-17 07:15:39,904 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 07:15:39,904 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 07:15:39,907 INFO L256 TraceCheckSpWp]: Trace formula consists of 350 conjuncts, 1 conjuncts are in the unsatisfiable core [2025-03-17 07:15:39,911 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 07:15:39,930 INFO L134 CoverageAnalysis]: Checked inductivity of 77 backedges. 10 proven. 0 refuted. 0 times theorem prover too weak. 67 trivial. 0 not checked. [2025-03-17 07:15:39,931 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-17 07:15:39,931 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1273515143] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-17 07:15:39,931 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-03-17 07:15:39,931 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [2] total 2 [2025-03-17 07:15:39,933 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1612316562] [2025-03-17 07:15:39,933 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-17 07:15:39,938 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2025-03-17 07:15:39,938 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-17 07:15:39,954 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2025-03-17 07:15:39,954 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2025-03-17 07:15:39,956 INFO L87 Difference]: Start difference. First operand has 93 states, 59 states have (on average 1.2881355932203389) internal successors, (76), 60 states have internal predecessors, (76), 24 states have call successors, (24), 8 states have call predecessors, (24), 8 states have return successors, (24), 24 states have call predecessors, (24), 24 states have call successors, (24) Second operand has 2 states, 2 states have (on average 16.0) internal successors, (32), 2 states have internal predecessors, (32), 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-17 07:15:39,977 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-17 07:15:39,978 INFO L93 Difference]: Finished difference Result 179 states and 255 transitions. [2025-03-17 07:15:39,978 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2025-03-17 07:15:39,979 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 16.0) internal successors, (32), 2 states have internal predecessors, (32), 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 83 [2025-03-17 07:15:39,980 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-17 07:15:39,984 INFO L225 Difference]: With dead ends: 179 [2025-03-17 07:15:39,984 INFO L226 Difference]: Without dead ends: 90 [2025-03-17 07:15:39,987 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 84 GetRequests, 84 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-17 07:15:39,989 INFO L435 NwaCegarLoop]: 122 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, 122 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-17 07:15:39,989 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 122 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-17 07:15:39,998 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 90 states. [2025-03-17 07:15:40,013 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 90 to 90. [2025-03-17 07:15:40,014 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 90 states, 57 states have (on average 1.263157894736842) internal successors, (72), 58 states have internal predecessors, (72), 24 states have call successors, (24), 8 states have call predecessors, (24), 8 states have return successors, (23), 23 states have call predecessors, (23), 23 states have call successors, (23) [2025-03-17 07:15:40,018 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 90 states to 90 states and 119 transitions. [2025-03-17 07:15:40,019 INFO L78 Accepts]: Start accepts. Automaton has 90 states and 119 transitions. Word has length 83 [2025-03-17 07:15:40,020 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-17 07:15:40,020 INFO L471 AbstractCegarLoop]: Abstraction has 90 states and 119 transitions. [2025-03-17 07:15:40,020 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 16.0) internal successors, (32), 2 states have internal predecessors, (32), 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-17 07:15:40,020 INFO L276 IsEmpty]: Start isEmpty. Operand 90 states and 119 transitions. [2025-03-17 07:15:40,026 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 84 [2025-03-17 07:15:40,026 INFO L210 NwaCegarLoop]: Found error trace [2025-03-17 07:15:40,026 INFO L218 NwaCegarLoop]: trace histogram [6, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-17 07:15:40,037 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-17 07:15:40,227 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-17 07:15:40,227 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-17 07:15:40,228 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 07:15:40,228 INFO L85 PathProgramCache]: Analyzing trace with hash 1485800413, now seen corresponding path program 1 times [2025-03-17 07:15:40,228 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 07:15:40,228 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1699910999] [2025-03-17 07:15:40,228 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 07:15:40,228 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 07:15:40,272 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 83 statements into 1 equivalence classes. [2025-03-17 07:15:40,341 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 83 of 83 statements. [2025-03-17 07:15:40,342 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 07:15:40,342 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 07:15:40,913 INFO L134 CoverageAnalysis]: Checked inductivity of 77 backedges. 9 proven. 8 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2025-03-17 07:15:40,914 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-17 07:15:40,914 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1699910999] [2025-03-17 07:15:40,914 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1699910999] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-17 07:15:40,914 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [657177688] [2025-03-17 07:15:40,914 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 07:15:40,914 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-17 07:15:40,914 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 07:15:40,917 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-17 07:15:40,918 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-17 07:15:41,018 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 83 statements into 1 equivalence classes. [2025-03-17 07:15:41,064 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 83 of 83 statements. [2025-03-17 07:15:41,064 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 07:15:41,064 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 07:15:41,068 INFO L256 TraceCheckSpWp]: Trace formula consists of 350 conjuncts, 58 conjuncts are in the unsatisfiable core [2025-03-17 07:15:41,073 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 07:15:41,216 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 24 treesize of output 9 [2025-03-17 07:15:41,226 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 16 treesize of output 17 [2025-03-17 07:15:42,763 INFO L134 CoverageAnalysis]: Checked inductivity of 77 backedges. 44 proven. 16 refuted. 0 times theorem prover too weak. 17 trivial. 0 not checked. [2025-03-17 07:15:42,765 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-17 07:15:55,617 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 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 84 treesize of output 80 [2025-03-17 07:15:55,648 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-17 07:15:55,649 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-17 07:15:55,649 INFO L173 IndexEqualityManager]: detected equality via solver [2025-03-17 07:15:55,784 INFO L134 CoverageAnalysis]: Checked inductivity of 77 backedges. 31 proven. 0 refuted. 0 times theorem prover too weak. 46 trivial. 0 not checked. [2025-03-17 07:15:55,786 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [657177688] provided 1 perfect and 1 imperfect interpolant sequences [2025-03-17 07:15:55,786 INFO L185 FreeRefinementEngine]: Found 1 perfect and 2 imperfect interpolant sequences. [2025-03-17 07:15:55,786 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [17] imperfect sequences [6, 16] total 33 [2025-03-17 07:15:55,786 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [618538] [2025-03-17 07:15:55,786 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-17 07:15:55,787 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2025-03-17 07:15:55,787 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-17 07:15:55,787 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2025-03-17 07:15:55,788 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=105, Invalid=948, Unknown=3, NotChecked=0, Total=1056 [2025-03-17 07:15:55,788 INFO L87 Difference]: Start difference. First operand 90 states and 119 transitions. Second operand has 17 states, 15 states have (on average 2.6) internal successors, (39), 13 states have internal predecessors, (39), 7 states have call successors, (13), 3 states have call predecessors, (13), 4 states have return successors, (11), 7 states have call predecessors, (11), 7 states have call successors, (11) [2025-03-17 07:15:56,278 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-17 07:15:56,279 INFO L93 Difference]: Finished difference Result 163 states and 221 transitions. [2025-03-17 07:15:56,279 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2025-03-17 07:15:56,280 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 15 states have (on average 2.6) internal successors, (39), 13 states have internal predecessors, (39), 7 states have call successors, (13), 3 states have call predecessors, (13), 4 states have return successors, (11), 7 states have call predecessors, (11), 7 states have call successors, (11) Word has length 83 [2025-03-17 07:15:56,280 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-17 07:15:56,282 INFO L225 Difference]: With dead ends: 163 [2025-03-17 07:15:56,283 INFO L226 Difference]: Without dead ends: 91 [2025-03-17 07:15:56,285 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 172 GetRequests, 131 SyntacticMatches, 8 SemanticMatches, 33 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 297 ImplicationChecksByTransitivity, 13.3s TimeCoverageRelationStatistics Valid=115, Invalid=1072, Unknown=3, NotChecked=0, Total=1190 [2025-03-17 07:15:56,287 INFO L435 NwaCegarLoop]: 109 mSDtfsCounter, 4 mSDsluCounter, 1343 mSDsCounter, 0 mSdLazyCounter, 370 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 1452 SdHoareTripleChecker+Invalid, 374 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 370 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2025-03-17 07:15:56,287 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 1452 Invalid, 374 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 370 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2025-03-17 07:15:56,290 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 91 states. [2025-03-17 07:15:56,304 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 91 to 91. [2025-03-17 07:15:56,304 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 91 states, 58 states have (on average 1.2586206896551724) internal successors, (73), 59 states have internal predecessors, (73), 24 states have call successors, (24), 8 states have call predecessors, (24), 8 states have return successors, (23), 23 states have call predecessors, (23), 23 states have call successors, (23) [2025-03-17 07:15:56,305 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 91 states to 91 states and 120 transitions. [2025-03-17 07:15:56,305 INFO L78 Accepts]: Start accepts. Automaton has 91 states and 120 transitions. Word has length 83 [2025-03-17 07:15:56,310 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-17 07:15:56,310 INFO L471 AbstractCegarLoop]: Abstraction has 91 states and 120 transitions. [2025-03-17 07:15:56,310 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 15 states have (on average 2.6) internal successors, (39), 13 states have internal predecessors, (39), 7 states have call successors, (13), 3 states have call predecessors, (13), 4 states have return successors, (11), 7 states have call predecessors, (11), 7 states have call successors, (11) [2025-03-17 07:15:56,310 INFO L276 IsEmpty]: Start isEmpty. Operand 91 states and 120 transitions. [2025-03-17 07:15:56,312 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 85 [2025-03-17 07:15:56,312 INFO L210 NwaCegarLoop]: Found error trace [2025-03-17 07:15:56,312 INFO L218 NwaCegarLoop]: trace histogram [6, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-17 07:15:56,327 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-17 07:15:56,512 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,SelfDestructingSolverStorable1 [2025-03-17 07:15:56,513 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-17 07:15:56,513 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 07:15:56,513 INFO L85 PathProgramCache]: Analyzing trace with hash -623945750, now seen corresponding path program 1 times [2025-03-17 07:15:56,514 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 07:15:56,514 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [467714127] [2025-03-17 07:15:56,514 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 07:15:56,514 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 07:15:56,543 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 84 statements into 1 equivalence classes. [2025-03-17 07:15:56,578 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 84 of 84 statements. [2025-03-17 07:15:56,578 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 07:15:56,578 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 07:15:56,967 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 9 proven. 8 refuted. 0 times theorem prover too weak. 61 trivial. 0 not checked. [2025-03-17 07:15:56,971 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-17 07:15:56,971 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [467714127] [2025-03-17 07:15:56,971 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [467714127] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-17 07:15:56,971 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [83635645] [2025-03-17 07:15:56,971 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 07:15:56,971 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-17 07:15:56,971 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 07:15:56,973 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-17 07:15:56,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-17 07:15:57,069 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 84 statements into 1 equivalence classes. [2025-03-17 07:15:57,110 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 84 of 84 statements. [2025-03-17 07:15:57,110 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 07:15:57,110 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 07:15:57,113 INFO L256 TraceCheckSpWp]: Trace formula consists of 395 conjuncts, 54 conjuncts are in the unsatisfiable core [2025-03-17 07:15:57,121 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 07:15:57,129 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 6 treesize of output 5 [2025-03-17 07:15:57,219 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 18 treesize of output 19 [2025-03-17 07:15:57,237 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 24 treesize of output 9 [2025-03-17 07:15:57,275 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-17 07:15:57,277 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 2 new quantified variables, introduced 0 case distinctions, treesize of input 26 treesize of output 28 [2025-03-17 07:15:57,296 INFO L349 Elim1Store]: treesize reduction 13, result has 40.9 percent of original size [2025-03-17 07:15:57,296 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 1 case distinctions, treesize of input 18 treesize of output 17 [2025-03-17 07:15:57,302 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 7 treesize of output 3 [2025-03-17 07:15:57,312 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-17 07:15:57,313 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-17 07:15:57,314 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 35 treesize of output 40 [2025-03-17 07:15:57,326 INFO L349 Elim1Store]: treesize reduction 13, result has 40.9 percent of original size [2025-03-17 07:15:57,326 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 1 case distinctions, treesize of input 34 treesize of output 29 [2025-03-17 07:15:57,335 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-17 07:15:57,336 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-17 07:15:57,336 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 3 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 0 case distinctions, treesize of input 20 treesize of output 10 [2025-03-17 07:15:57,385 INFO L349 Elim1Store]: treesize reduction 4, result has 50.0 percent of original size [2025-03-17 07:15:57,385 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 11 treesize of output 11 [2025-03-17 07:15:57,477 INFO L349 Elim1Store]: treesize reduction 42, result has 20.8 percent of original size [2025-03-17 07:15:57,477 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 2 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 4 new quantified variables, introduced 2 case distinctions, treesize of input 124 treesize of output 126 [2025-03-17 07:15:57,489 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-17 07:15:57,490 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-17 07:15:57,492 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-17 07:15:57,494 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 3 select indices, 3 select index equivalence classes, 6 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 0 case distinctions, treesize of input 106 treesize of output 102 [2025-03-17 07:15:57,514 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-17 07:15:57,516 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 38 treesize of output 35 [2025-03-17 07:15:57,521 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 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 24 treesize of output 13 [2025-03-17 07:15:57,533 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 69 treesize of output 26 [2025-03-17 07:15:59,498 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 11 proven. 21 refuted. 0 times theorem prover too weak. 46 trivial. 0 not checked. [2025-03-17 07:15:59,498 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-17 07:15:59,823 WARN L851 $PredicateComparison]: unable to prove that (let ((.cse1 (+ |c_ULTIMATE.start_ensure_linked_list_is_allocated_~list#1.offset| 24)) (.cse2 (+ 16 |c_ULTIMATE.start_aws_linked_list_back_harness_~#list~0#1.offset|))) (and (forall ((v_ArrVal_249 (Array Int Int)) (v_ArrVal_245 Int)) (= (select (select (let ((.cse0 (store |c_#memory_$Pointer$#2.offset| |c_ULTIMATE.start_ensure_linked_list_is_allocated_~curr~0#1.base| v_ArrVal_249))) (store .cse0 |c_ULTIMATE.start_ensure_linked_list_is_allocated_~list#1.base| (store (select .cse0 |c_ULTIMATE.start_ensure_linked_list_is_allocated_~list#1.base|) .cse1 v_ArrVal_245))) |c_ULTIMATE.start_aws_linked_list_back_harness_~#list~0#1.base|) .cse2) 0)) (forall ((v_ArrVal_246 (Array Int Int))) (= (select (select (let ((.cse3 (store |c_#memory_$Pointer$#2.base| |c_ULTIMATE.start_ensure_linked_list_is_allocated_~curr~0#1.base| v_ArrVal_246))) (store .cse3 |c_ULTIMATE.start_ensure_linked_list_is_allocated_~list#1.base| (store (select .cse3 |c_ULTIMATE.start_ensure_linked_list_is_allocated_~list#1.base|) .cse1 |c_ULTIMATE.start_ensure_linked_list_is_allocated_~curr~0#1.base|))) |c_ULTIMATE.start_aws_linked_list_back_harness_~#list~0#1.base|) .cse2) 0)))) is different from false [2025-03-17 07:15:59,917 INFO L173 IndexEqualityManager]: detected equality via solver [2025-03-17 07:15:59,920 INFO L173 IndexEqualityManager]: detected equality via solver [2025-03-17 07:15:59,964 INFO L349 Elim1Store]: treesize reduction 86, result has 45.2 percent of original size [2025-03-17 07:15:59,964 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 3 disjoint index pairs (out of 0 index pairs), introduced 2 new quantified variables, introduced 4 case distinctions, treesize of input 173 treesize of output 202 [2025-03-17 07:15:59,982 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-17 07:15:59,982 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 222 treesize of output 222 [2025-03-17 07:15:59,989 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 189 treesize of output 177 [2025-03-17 07:15:59,998 INFO L173 IndexEqualityManager]: detected equality via solver [2025-03-17 07:15:59,998 INFO L173 IndexEqualityManager]: detected equality via solver [2025-03-17 07:16:00,047 INFO L349 Elim1Store]: treesize reduction 86, result has 45.2 percent of original size [2025-03-17 07:16:00,048 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 3 disjoint index pairs (out of 0 index pairs), introduced 2 new quantified variables, introduced 4 case distinctions, treesize of input 249 treesize of output 278 [2025-03-17 07:16:00,088 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-17 07:16:00,088 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 352 treesize of output 328 [2025-03-17 07:16:00,099 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 287 treesize of output 275 [2025-03-17 07:16:00,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 8 treesize of output 4 [2025-03-17 07:16:00,172 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-17 07:16:00,950 INFO L173 IndexEqualityManager]: detected equality via solver [2025-03-17 07:16:00,950 INFO L173 IndexEqualityManager]: detected equality via solver [2025-03-17 07:16:00,963 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-17 07:16:00,963 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 3 case distinctions, treesize of input 403 treesize of output 411 [2025-03-17 07:16:01,913 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-17 07:16:01,914 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 472 treesize of output 420 [2025-03-17 07:16:02,722 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [83635645] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-17 07:16:02,723 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-17 07:16:02,723 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 12] total 17 [2025-03-17 07:16:02,723 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [923908352] [2025-03-17 07:16:02,723 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-17 07:16:02,723 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2025-03-17 07:16:02,723 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-17 07:16:02,724 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2025-03-17 07:16:02,725 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=73, Invalid=529, Unknown=2, NotChecked=46, Total=650 [2025-03-17 07:16:02,725 INFO L87 Difference]: Start difference. First operand 91 states and 120 transitions. Second operand has 17 states, 16 states have (on average 4.875) internal successors, (78), 15 states have internal predecessors, (78), 7 states have call successors, (23), 5 states have call predecessors, (23), 6 states have return successors, (20), 7 states have call predecessors, (20), 7 states have call successors, (20) [2025-03-17 07:16:04,731 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-17 07:16:04,732 INFO L93 Difference]: Finished difference Result 258 states and 349 transitions. [2025-03-17 07:16:04,732 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2025-03-17 07:16:04,732 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 16 states have (on average 4.875) internal successors, (78), 15 states have internal predecessors, (78), 7 states have call successors, (23), 5 states have call predecessors, (23), 6 states have return successors, (20), 7 states have call predecessors, (20), 7 states have call successors, (20) Word has length 84 [2025-03-17 07:16:04,732 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-17 07:16:04,735 INFO L225 Difference]: With dead ends: 258 [2025-03-17 07:16:04,736 INFO L226 Difference]: Without dead ends: 178 [2025-03-17 07:16:04,737 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 184 GetRequests, 128 SyntacticMatches, 15 SemanticMatches, 41 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 310 ImplicationChecksByTransitivity, 2.1s TimeCoverageRelationStatistics Valid=205, Invalid=1519, Unknown=2, NotChecked=80, Total=1806 [2025-03-17 07:16:04,739 INFO L435 NwaCegarLoop]: 81 mSDtfsCounter, 230 mSDsluCounter, 930 mSDsCounter, 0 mSdLazyCounter, 802 mSolverCounterSat, 94 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 237 SdHoareTripleChecker+Valid, 1011 SdHoareTripleChecker+Invalid, 896 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 94 IncrementalHoareTripleChecker+Valid, 802 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.2s IncrementalHoareTripleChecker+Time [2025-03-17 07:16:04,739 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [237 Valid, 1011 Invalid, 896 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [94 Valid, 802 Invalid, 0 Unknown, 0 Unchecked, 1.2s Time] [2025-03-17 07:16:04,740 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 178 states. [2025-03-17 07:16:04,765 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 178 to 176. [2025-03-17 07:16:04,766 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 176 states, 112 states have (on average 1.2678571428571428) internal successors, (142), 116 states have internal predecessors, (142), 46 states have call successors, (46), 15 states have call predecessors, (46), 17 states have return successors, (48), 44 states have call predecessors, (48), 44 states have call successors, (48) [2025-03-17 07:16:04,770 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 176 states to 176 states and 236 transitions. [2025-03-17 07:16:04,770 INFO L78 Accepts]: Start accepts. Automaton has 176 states and 236 transitions. Word has length 84 [2025-03-17 07:16:04,770 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-17 07:16:04,770 INFO L471 AbstractCegarLoop]: Abstraction has 176 states and 236 transitions. [2025-03-17 07:16:04,771 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 16 states have (on average 4.875) internal successors, (78), 15 states have internal predecessors, (78), 7 states have call successors, (23), 5 states have call predecessors, (23), 6 states have return successors, (20), 7 states have call predecessors, (20), 7 states have call successors, (20) [2025-03-17 07:16:04,771 INFO L276 IsEmpty]: Start isEmpty. Operand 176 states and 236 transitions. [2025-03-17 07:16:04,772 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 86 [2025-03-17 07:16:04,773 INFO L210 NwaCegarLoop]: Found error trace [2025-03-17 07:16:04,773 INFO L218 NwaCegarLoop]: trace histogram [6, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 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-17 07:16:04,780 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-17 07:16:04,973 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-17 07:16:04,973 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-17 07:16:04,974 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 07:16:04,974 INFO L85 PathProgramCache]: Analyzing trace with hash 1169253827, now seen corresponding path program 1 times [2025-03-17 07:16:04,974 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 07:16:04,974 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [273560868] [2025-03-17 07:16:04,974 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 07:16:04,974 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 07:16:05,003 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 85 statements into 1 equivalence classes. [2025-03-17 07:16:05,015 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 85 of 85 statements. [2025-03-17 07:16:05,015 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 07:16:05,015 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 07:16:05,200 INFO L134 CoverageAnalysis]: Checked inductivity of 77 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 67 trivial. 0 not checked. [2025-03-17 07:16:05,201 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-17 07:16:05,201 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [273560868] [2025-03-17 07:16:05,201 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [273560868] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-17 07:16:05,201 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [395365642] [2025-03-17 07:16:05,201 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 07:16:05,201 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-17 07:16:05,201 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 07:16:05,221 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-17 07:16:05,241 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-17 07:16:05,332 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 85 statements into 1 equivalence classes. [2025-03-17 07:16:05,375 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 85 of 85 statements. [2025-03-17 07:16:05,376 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 07:16:05,376 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 07:16:05,378 INFO L256 TraceCheckSpWp]: Trace formula consists of 404 conjuncts, 9 conjuncts are in the unsatisfiable core [2025-03-17 07:16:05,380 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 07:16:05,462 INFO L134 CoverageAnalysis]: Checked inductivity of 77 backedges. 52 proven. 0 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2025-03-17 07:16:05,463 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-17 07:16:05,464 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [395365642] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-17 07:16:05,464 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-03-17 07:16:05,464 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [8] total 14 [2025-03-17 07:16:05,464 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1569377372] [2025-03-17 07:16:05,464 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-17 07:16:05,464 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2025-03-17 07:16:05,465 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-17 07:16:05,465 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2025-03-17 07:16:05,465 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=31, Invalid=151, Unknown=0, NotChecked=0, Total=182 [2025-03-17 07:16:05,465 INFO L87 Difference]: Start difference. First operand 176 states and 236 transitions. Second operand has 8 states, 7 states have (on average 7.0) internal successors, (49), 7 states have internal predecessors, (49), 4 states have call successors, (13), 3 states have call predecessors, (13), 3 states have return successors, (11), 3 states have call predecessors, (11), 4 states have call successors, (11) [2025-03-17 07:16:05,602 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-17 07:16:05,604 INFO L93 Difference]: Finished difference Result 339 states and 454 transitions. [2025-03-17 07:16:05,604 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2025-03-17 07:16:05,604 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 7 states have (on average 7.0) internal successors, (49), 7 states have internal predecessors, (49), 4 states have call successors, (13), 3 states have call predecessors, (13), 3 states have return successors, (11), 3 states have call predecessors, (11), 4 states have call successors, (11) Word has length 85 [2025-03-17 07:16:05,605 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-17 07:16:05,608 INFO L225 Difference]: With dead ends: 339 [2025-03-17 07:16:05,609 INFO L226 Difference]: Without dead ends: 180 [2025-03-17 07:16:05,610 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 93 GetRequests, 80 SyntacticMatches, 0 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 16 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=37, Invalid=173, Unknown=0, NotChecked=0, Total=210 [2025-03-17 07:16:05,611 INFO L435 NwaCegarLoop]: 106 mSDtfsCounter, 31 mSDsluCounter, 556 mSDsCounter, 0 mSdLazyCounter, 103 mSolverCounterSat, 24 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 40 SdHoareTripleChecker+Valid, 662 SdHoareTripleChecker+Invalid, 127 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 24 IncrementalHoareTripleChecker+Valid, 103 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-17 07:16:05,611 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [40 Valid, 662 Invalid, 127 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [24 Valid, 103 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-17 07:16:05,612 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 180 states. [2025-03-17 07:16:05,648 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 180 to 176. [2025-03-17 07:16:05,649 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 176 states, 112 states have (on average 1.25) internal successors, (140), 116 states have internal predecessors, (140), 46 states have call successors, (46), 15 states have call predecessors, (46), 17 states have return successors, (48), 44 states have call predecessors, (48), 44 states have call successors, (48) [2025-03-17 07:16:05,651 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 176 states to 176 states and 234 transitions. [2025-03-17 07:16:05,652 INFO L78 Accepts]: Start accepts. Automaton has 176 states and 234 transitions. Word has length 85 [2025-03-17 07:16:05,652 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-17 07:16:05,652 INFO L471 AbstractCegarLoop]: Abstraction has 176 states and 234 transitions. [2025-03-17 07:16:05,652 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 7 states have (on average 7.0) internal successors, (49), 7 states have internal predecessors, (49), 4 states have call successors, (13), 3 states have call predecessors, (13), 3 states have return successors, (11), 3 states have call predecessors, (11), 4 states have call successors, (11) [2025-03-17 07:16:05,652 INFO L276 IsEmpty]: Start isEmpty. Operand 176 states and 234 transitions. [2025-03-17 07:16:05,655 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 88 [2025-03-17 07:16:05,656 INFO L210 NwaCegarLoop]: Found error trace [2025-03-17 07:16:05,657 INFO L218 NwaCegarLoop]: trace histogram [6, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 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-17 07:16:05,664 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-17 07:16:05,857 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-17 07:16:05,858 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-17 07:16:05,859 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 07:16:05,859 INFO L85 PathProgramCache]: Analyzing trace with hash 1037307771, now seen corresponding path program 1 times [2025-03-17 07:16:05,859 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 07:16:05,859 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [562671939] [2025-03-17 07:16:05,859 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 07:16:05,859 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 07:16:05,886 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 87 statements into 1 equivalence classes. [2025-03-17 07:16:05,896 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 87 of 87 statements. [2025-03-17 07:16:05,896 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 07:16:05,897 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 07:16:06,140 INFO L134 CoverageAnalysis]: Checked inductivity of 77 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 67 trivial. 0 not checked. [2025-03-17 07:16:06,140 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-17 07:16:06,140 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [562671939] [2025-03-17 07:16:06,140 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [562671939] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-17 07:16:06,140 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [499041391] [2025-03-17 07:16:06,140 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 07:16:06,140 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-17 07:16:06,141 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 07:16:06,144 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-17 07:16:06,155 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-17 07:16:06,257 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 87 statements into 1 equivalence classes. [2025-03-17 07:16:06,305 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 87 of 87 statements. [2025-03-17 07:16:06,306 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 07:16:06,306 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 07:16:06,309 INFO L256 TraceCheckSpWp]: Trace formula consists of 411 conjuncts, 10 conjuncts are in the unsatisfiable core [2025-03-17 07:16:06,312 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 07:16:06,429 INFO L134 CoverageAnalysis]: Checked inductivity of 77 backedges. 52 proven. 0 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2025-03-17 07:16:06,429 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-17 07:16:06,429 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [499041391] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-17 07:16:06,429 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-03-17 07:16:06,430 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [9] total 16 [2025-03-17 07:16:06,430 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [466106377] [2025-03-17 07:16:06,430 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-17 07:16:06,430 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2025-03-17 07:16:06,430 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-17 07:16:06,431 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2025-03-17 07:16:06,431 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=210, Unknown=0, NotChecked=0, Total=240 [2025-03-17 07:16:06,431 INFO L87 Difference]: Start difference. First operand 176 states and 234 transitions. Second operand has 9 states, 8 states have (on average 6.375) internal successors, (51), 8 states have internal predecessors, (51), 4 states have call successors, (13), 3 states have call predecessors, (13), 3 states have return successors, (11), 3 states have call predecessors, (11), 4 states have call successors, (11) [2025-03-17 07:16:06,621 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-17 07:16:06,621 INFO L93 Difference]: Finished difference Result 351 states and 470 transitions. [2025-03-17 07:16:06,623 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2025-03-17 07:16:06,623 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 8 states have (on average 6.375) internal successors, (51), 8 states have internal predecessors, (51), 4 states have call successors, (13), 3 states have call predecessors, (13), 3 states have return successors, (11), 3 states have call predecessors, (11), 4 states have call successors, (11) Word has length 87 [2025-03-17 07:16:06,623 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-17 07:16:06,625 INFO L225 Difference]: With dead ends: 351 [2025-03-17 07:16:06,625 INFO L226 Difference]: Without dead ends: 190 [2025-03-17 07:16:06,626 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 98 GetRequests, 81 SyntacticMatches, 0 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 13 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=42, Invalid=300, Unknown=0, NotChecked=0, Total=342 [2025-03-17 07:16:06,626 INFO L435 NwaCegarLoop]: 103 mSDtfsCounter, 40 mSDsluCounter, 640 mSDsCounter, 0 mSdLazyCounter, 137 mSolverCounterSat, 26 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 49 SdHoareTripleChecker+Valid, 743 SdHoareTripleChecker+Invalid, 163 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 26 IncrementalHoareTripleChecker+Valid, 137 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-17 07:16:06,629 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [49 Valid, 743 Invalid, 163 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [26 Valid, 137 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-17 07:16:06,632 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 190 states. [2025-03-17 07:16:06,660 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 190 to 178. [2025-03-17 07:16:06,660 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 178 states, 114 states have (on average 1.2456140350877194) internal successors, (142), 118 states have internal predecessors, (142), 46 states have call successors, (46), 15 states have call predecessors, (46), 17 states have return successors, (48), 44 states have call predecessors, (48), 44 states have call successors, (48) [2025-03-17 07:16:06,665 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 178 states to 178 states and 236 transitions. [2025-03-17 07:16:06,666 INFO L78 Accepts]: Start accepts. Automaton has 178 states and 236 transitions. Word has length 87 [2025-03-17 07:16:06,666 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-17 07:16:06,666 INFO L471 AbstractCegarLoop]: Abstraction has 178 states and 236 transitions. [2025-03-17 07:16:06,666 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 8 states have (on average 6.375) internal successors, (51), 8 states have internal predecessors, (51), 4 states have call successors, (13), 3 states have call predecessors, (13), 3 states have return successors, (11), 3 states have call predecessors, (11), 4 states have call successors, (11) [2025-03-17 07:16:06,666 INFO L276 IsEmpty]: Start isEmpty. Operand 178 states and 236 transitions. [2025-03-17 07:16:06,667 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 89 [2025-03-17 07:16:06,667 INFO L210 NwaCegarLoop]: Found error trace [2025-03-17 07:16:06,667 INFO L218 NwaCegarLoop]: trace histogram [6, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 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-17 07:16:06,682 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-17 07:16:06,867 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-17 07:16:06,868 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-17 07:16:06,869 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 07:16:06,869 INFO L85 PathProgramCache]: Analyzing trace with hash -1907807360, now seen corresponding path program 1 times [2025-03-17 07:16:06,869 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 07:16:06,869 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [350132051] [2025-03-17 07:16:06,869 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 07:16:06,869 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 07:16:06,887 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 88 statements into 1 equivalence classes. [2025-03-17 07:16:06,898 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 88 of 88 statements. [2025-03-17 07:16:06,898 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 07:16:06,898 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 07:16:07,135 INFO L134 CoverageAnalysis]: Checked inductivity of 77 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 67 trivial. 0 not checked. [2025-03-17 07:16:07,135 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-17 07:16:07,135 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [350132051] [2025-03-17 07:16:07,135 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [350132051] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-17 07:16:07,136 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [188888707] [2025-03-17 07:16:07,136 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 07:16:07,136 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-17 07:16:07,136 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 07:16:07,138 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-17 07:16:07,140 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-17 07:16:07,234 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 88 statements into 1 equivalence classes. [2025-03-17 07:16:07,271 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 88 of 88 statements. [2025-03-17 07:16:07,271 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 07:16:07,271 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 07:16:07,273 INFO L256 TraceCheckSpWp]: Trace formula consists of 414 conjuncts, 2 conjuncts are in the unsatisfiable core [2025-03-17 07:16:07,275 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 07:16:07,289 INFO L134 CoverageAnalysis]: Checked inductivity of 77 backedges. 50 proven. 0 refuted. 0 times theorem prover too weak. 27 trivial. 0 not checked. [2025-03-17 07:16:07,290 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-17 07:16:07,290 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [188888707] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-17 07:16:07,290 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-03-17 07:16:07,290 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [9] total 10 [2025-03-17 07:16:07,290 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1435630175] [2025-03-17 07:16:07,290 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-17 07:16:07,290 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2025-03-17 07:16:07,290 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-17 07:16:07,291 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2025-03-17 07:16:07,292 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=73, Unknown=0, NotChecked=0, Total=90 [2025-03-17 07:16:07,292 INFO L87 Difference]: Start difference. First operand 178 states and 236 transitions. Second operand has 3 states, 3 states have (on average 17.0) internal successors, (51), 3 states have internal predecessors, (51), 2 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (11), 2 states have call predecessors, (11), 2 states have call successors, (11) [2025-03-17 07:16:07,320 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-17 07:16:07,321 INFO L93 Difference]: Finished difference Result 341 states and 460 transitions. [2025-03-17 07:16:07,321 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2025-03-17 07:16:07,321 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 17.0) internal successors, (51), 3 states have internal predecessors, (51), 2 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (11), 2 states have call predecessors, (11), 2 states have call successors, (11) Word has length 88 [2025-03-17 07:16:07,323 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-17 07:16:07,324 INFO L225 Difference]: With dead ends: 341 [2025-03-17 07:16:07,325 INFO L226 Difference]: Without dead ends: 186 [2025-03-17 07:16:07,325 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 96 GetRequests, 88 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=73, Unknown=0, NotChecked=0, Total=90 [2025-03-17 07:16:07,326 INFO L435 NwaCegarLoop]: 115 mSDtfsCounter, 2 mSDsluCounter, 110 mSDsCounter, 0 mSdLazyCounter, 10 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3 SdHoareTripleChecker+Valid, 225 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-17 07:16:07,327 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [3 Valid, 225 Invalid, 10 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 10 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-17 07:16:07,327 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 186 states. [2025-03-17 07:16:07,345 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 186 to 180. [2025-03-17 07:16:07,346 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 180 states, 116 states have (on average 1.2413793103448276) internal successors, (144), 120 states have internal predecessors, (144), 46 states have call successors, (46), 15 states have call predecessors, (46), 17 states have return successors, (48), 44 states have call predecessors, (48), 44 states have call successors, (48) [2025-03-17 07:16:07,348 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 180 states to 180 states and 238 transitions. [2025-03-17 07:16:07,349 INFO L78 Accepts]: Start accepts. Automaton has 180 states and 238 transitions. Word has length 88 [2025-03-17 07:16:07,349 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-17 07:16:07,349 INFO L471 AbstractCegarLoop]: Abstraction has 180 states and 238 transitions. [2025-03-17 07:16:07,349 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 17.0) internal successors, (51), 3 states have internal predecessors, (51), 2 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (11), 2 states have call predecessors, (11), 2 states have call successors, (11) [2025-03-17 07:16:07,350 INFO L276 IsEmpty]: Start isEmpty. Operand 180 states and 238 transitions. [2025-03-17 07:16:07,350 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 97 [2025-03-17 07:16:07,350 INFO L210 NwaCegarLoop]: Found error trace [2025-03-17 07:16:07,350 INFO L218 NwaCegarLoop]: trace histogram [6, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 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-17 07:16:07,358 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2025-03-17 07:16:07,551 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-17 07:16:07,551 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-17 07:16:07,551 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 07:16:07,552 INFO L85 PathProgramCache]: Analyzing trace with hash 2015169506, now seen corresponding path program 1 times [2025-03-17 07:16:07,552 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 07:16:07,552 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1891190687] [2025-03-17 07:16:07,552 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 07:16:07,552 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 07:16:07,573 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 96 statements into 1 equivalence classes. [2025-03-17 07:16:07,589 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 96 of 96 statements. [2025-03-17 07:16:07,589 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 07:16:07,589 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 07:16:08,087 INFO L134 CoverageAnalysis]: Checked inductivity of 77 backedges. 0 proven. 9 refuted. 0 times theorem prover too weak. 68 trivial. 0 not checked. [2025-03-17 07:16:08,087 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-17 07:16:08,087 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1891190687] [2025-03-17 07:16:08,087 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1891190687] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-17 07:16:08,087 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [14898885] [2025-03-17 07:16:08,087 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 07:16:08,087 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-17 07:16:08,088 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 07:16:08,091 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-17 07:16:08,092 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-17 07:16:08,190 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 96 statements into 1 equivalence classes. [2025-03-17 07:16:08,233 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 96 of 96 statements. [2025-03-17 07:16:08,233 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 07:16:08,233 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 07:16:08,236 INFO L256 TraceCheckSpWp]: Trace formula consists of 435 conjuncts, 32 conjuncts are in the unsatisfiable core [2025-03-17 07:16:08,238 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 07:16:08,378 INFO L134 CoverageAnalysis]: Checked inductivity of 77 backedges. 57 proven. 0 refuted. 0 times theorem prover too weak. 20 trivial. 0 not checked. [2025-03-17 07:16:08,378 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-17 07:16:08,378 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [14898885] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-17 07:16:08,378 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-03-17 07:16:08,378 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [10] imperfect sequences [11] total 19 [2025-03-17 07:16:08,378 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1054281411] [2025-03-17 07:16:08,378 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-17 07:16:08,378 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2025-03-17 07:16:08,378 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-17 07:16:08,379 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2025-03-17 07:16:08,379 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=40, Invalid=302, Unknown=0, NotChecked=0, Total=342 [2025-03-17 07:16:08,379 INFO L87 Difference]: Start difference. First operand 180 states and 238 transitions. Second operand has 10 states, 8 states have (on average 7.625) internal successors, (61), 8 states have internal predecessors, (61), 5 states have call successors, (14), 3 states have call predecessors, (14), 4 states have return successors, (12), 4 states have call predecessors, (12), 5 states have call successors, (12) [2025-03-17 07:16:08,517 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-17 07:16:08,518 INFO L93 Difference]: Finished difference Result 343 states and 454 transitions. [2025-03-17 07:16:08,519 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2025-03-17 07:16:08,519 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 8 states have (on average 7.625) internal successors, (61), 8 states have internal predecessors, (61), 5 states have call successors, (14), 3 states have call predecessors, (14), 4 states have return successors, (12), 4 states have call predecessors, (12), 5 states have call successors, (12) Word has length 96 [2025-03-17 07:16:08,520 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-17 07:16:08,522 INFO L225 Difference]: With dead ends: 343 [2025-03-17 07:16:08,522 INFO L226 Difference]: Without dead ends: 186 [2025-03-17 07:16:08,523 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 108 GetRequests, 89 SyntacticMatches, 0 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 28 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=50, Invalid=370, Unknown=0, NotChecked=0, Total=420 [2025-03-17 07:16:08,525 INFO L435 NwaCegarLoop]: 107 mSDtfsCounter, 17 mSDsluCounter, 692 mSDsCounter, 0 mSdLazyCounter, 101 mSolverCounterSat, 24 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 25 SdHoareTripleChecker+Valid, 799 SdHoareTripleChecker+Invalid, 125 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 24 IncrementalHoareTripleChecker+Valid, 101 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-17 07:16:08,526 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [25 Valid, 799 Invalid, 125 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [24 Valid, 101 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-17 07:16:08,526 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 186 states. [2025-03-17 07:16:08,544 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 186 to 182. [2025-03-17 07:16:08,545 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 182 states, 118 states have (on average 1.2372881355932204) internal successors, (146), 122 states have internal predecessors, (146), 46 states have call successors, (46), 15 states have call predecessors, (46), 17 states have return successors, (48), 44 states have call predecessors, (48), 44 states have call successors, (48) [2025-03-17 07:16:08,547 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 182 states to 182 states and 240 transitions. [2025-03-17 07:16:08,547 INFO L78 Accepts]: Start accepts. Automaton has 182 states and 240 transitions. Word has length 96 [2025-03-17 07:16:08,547 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-17 07:16:08,547 INFO L471 AbstractCegarLoop]: Abstraction has 182 states and 240 transitions. [2025-03-17 07:16:08,548 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 8 states have (on average 7.625) internal successors, (61), 8 states have internal predecessors, (61), 5 states have call successors, (14), 3 states have call predecessors, (14), 4 states have return successors, (12), 4 states have call predecessors, (12), 5 states have call successors, (12) [2025-03-17 07:16:08,548 INFO L276 IsEmpty]: Start isEmpty. Operand 182 states and 240 transitions. [2025-03-17 07:16:08,548 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 99 [2025-03-17 07:16:08,549 INFO L210 NwaCegarLoop]: Found error trace [2025-03-17 07:16:08,549 INFO L218 NwaCegarLoop]: trace histogram [6, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 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-17 07:16:08,556 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-17 07:16:08,749 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-17 07:16:08,750 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-17 07:16:08,750 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 07:16:08,750 INFO L85 PathProgramCache]: Analyzing trace with hash -1188024612, now seen corresponding path program 1 times [2025-03-17 07:16:08,751 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 07:16:08,751 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [776860198] [2025-03-17 07:16:08,751 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 07:16:08,751 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 07:16:08,774 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 98 statements into 1 equivalence classes. [2025-03-17 07:16:08,784 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 98 of 98 statements. [2025-03-17 07:16:08,785 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 07:16:08,785 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 07:16:09,143 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 68 trivial. 0 not checked. [2025-03-17 07:16:09,143 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-17 07:16:09,143 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [776860198] [2025-03-17 07:16:09,144 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [776860198] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-17 07:16:09,144 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [389551481] [2025-03-17 07:16:09,144 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 07:16:09,144 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-17 07:16:09,144 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 07:16:09,146 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-17 07:16:09,148 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-17 07:16:09,273 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 98 statements into 1 equivalence classes. [2025-03-17 07:16:09,323 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 98 of 98 statements. [2025-03-17 07:16:09,323 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 07:16:09,323 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 07:16:09,328 INFO L256 TraceCheckSpWp]: Trace formula consists of 442 conjuncts, 68 conjuncts are in the unsatisfiable core [2025-03-17 07:16:09,332 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 07:16:09,365 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 1 [2025-03-17 07:16:09,367 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 1 [2025-03-17 07:16:10,188 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 43 proven. 10 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2025-03-17 07:16:10,189 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-17 07:16:11,039 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 0 proven. 11 refuted. 0 times theorem prover too weak. 67 trivial. 0 not checked. [2025-03-17 07:16:11,040 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [389551481] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-17 07:16:11,041 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-17 07:16:11,041 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 22, 17] total 42 [2025-03-17 07:16:11,042 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1629939266] [2025-03-17 07:16:11,042 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-17 07:16:11,043 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 42 states [2025-03-17 07:16:11,043 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-17 07:16:11,043 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 42 interpolants. [2025-03-17 07:16:11,044 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=132, Invalid=1590, Unknown=0, NotChecked=0, Total=1722 [2025-03-17 07:16:11,044 INFO L87 Difference]: Start difference. First operand 182 states and 240 transitions. Second operand has 42 states, 41 states have (on average 3.292682926829268) internal successors, (135), 39 states have internal predecessors, (135), 11 states have call successors, (30), 4 states have call predecessors, (30), 8 states have return successors, (28), 10 states have call predecessors, (28), 11 states have call successors, (28) [2025-03-17 07:16:14,653 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-17 07:16:14,653 INFO L93 Difference]: Finished difference Result 829 states and 1205 transitions. [2025-03-17 07:16:14,654 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 63 states. [2025-03-17 07:16:14,654 INFO L78 Accepts]: Start accepts. Automaton has has 42 states, 41 states have (on average 3.292682926829268) internal successors, (135), 39 states have internal predecessors, (135), 11 states have call successors, (30), 4 states have call predecessors, (30), 8 states have return successors, (28), 10 states have call predecessors, (28), 11 states have call successors, (28) Word has length 98 [2025-03-17 07:16:14,655 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-17 07:16:14,663 INFO L225 Difference]: With dead ends: 829 [2025-03-17 07:16:14,663 INFO L226 Difference]: Without dead ends: 670 [2025-03-17 07:16:14,666 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 265 GetRequests, 169 SyntacticMatches, 6 SemanticMatches, 90 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1756 ImplicationChecksByTransitivity, 2.4s TimeCoverageRelationStatistics Valid=771, Invalid=7601, Unknown=0, NotChecked=0, Total=8372 [2025-03-17 07:16:14,667 INFO L435 NwaCegarLoop]: 127 mSDtfsCounter, 416 mSDsluCounter, 2917 mSDsCounter, 0 mSdLazyCounter, 3239 mSolverCounterSat, 166 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 428 SdHoareTripleChecker+Valid, 3044 SdHoareTripleChecker+Invalid, 3405 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 166 IncrementalHoareTripleChecker+Valid, 3239 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.0s IncrementalHoareTripleChecker+Time [2025-03-17 07:16:14,667 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [428 Valid, 3044 Invalid, 3405 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [166 Valid, 3239 Invalid, 0 Unknown, 0 Unchecked, 2.0s Time] [2025-03-17 07:16:14,668 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 670 states. [2025-03-17 07:16:14,736 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 670 to 482. [2025-03-17 07:16:14,737 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 482 states, 346 states have (on average 1.2947976878612717) internal successors, (448), 358 states have internal predecessors, (448), 94 states have call successors, (94), 31 states have call predecessors, (94), 41 states have return successors, (128), 92 states have call predecessors, (128), 90 states have call successors, (128) [2025-03-17 07:16:14,743 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 482 states to 482 states and 670 transitions. [2025-03-17 07:16:14,744 INFO L78 Accepts]: Start accepts. Automaton has 482 states and 670 transitions. Word has length 98 [2025-03-17 07:16:14,744 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-17 07:16:14,744 INFO L471 AbstractCegarLoop]: Abstraction has 482 states and 670 transitions. [2025-03-17 07:16:14,744 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 42 states, 41 states have (on average 3.292682926829268) internal successors, (135), 39 states have internal predecessors, (135), 11 states have call successors, (30), 4 states have call predecessors, (30), 8 states have return successors, (28), 10 states have call predecessors, (28), 11 states have call successors, (28) [2025-03-17 07:16:14,744 INFO L276 IsEmpty]: Start isEmpty. Operand 482 states and 670 transitions. [2025-03-17 07:16:14,745 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 99 [2025-03-17 07:16:14,745 INFO L210 NwaCegarLoop]: Found error trace [2025-03-17 07:16:14,745 INFO L218 NwaCegarLoop]: trace histogram [6, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 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-17 07:16:14,756 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-17 07:16:14,945 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,SelfDestructingSolverStorable7 [2025-03-17 07:16:14,946 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-17 07:16:14,947 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 07:16:14,947 INFO L85 PathProgramCache]: Analyzing trace with hash 1306854522, now seen corresponding path program 1 times [2025-03-17 07:16:14,947 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 07:16:14,947 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1136949340] [2025-03-17 07:16:14,947 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 07:16:14,947 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 07:16:14,966 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 98 statements into 1 equivalence classes. [2025-03-17 07:16:14,975 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 98 of 98 statements. [2025-03-17 07:16:14,975 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 07:16:14,975 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 07:16:15,049 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 71 trivial. 0 not checked. [2025-03-17 07:16:15,049 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-17 07:16:15,049 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1136949340] [2025-03-17 07:16:15,050 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1136949340] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-17 07:16:15,050 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [596919401] [2025-03-17 07:16:15,050 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 07:16:15,050 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-17 07:16:15,050 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 07:16:15,052 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-17 07:16:15,060 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-17 07:16:15,204 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 98 statements into 1 equivalence classes. [2025-03-17 07:16:15,251 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 98 of 98 statements. [2025-03-17 07:16:15,251 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 07:16:15,251 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 07:16:15,254 INFO L256 TraceCheckSpWp]: Trace formula consists of 446 conjuncts, 3 conjuncts are in the unsatisfiable core [2025-03-17 07:16:15,256 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 07:16:15,262 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 47 proven. 0 refuted. 0 times theorem prover too weak. 31 trivial. 0 not checked. [2025-03-17 07:16:15,262 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-17 07:16:15,262 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [596919401] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-17 07:16:15,263 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-03-17 07:16:15,263 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [4] total 4 [2025-03-17 07:16:15,263 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1615652941] [2025-03-17 07:16:15,263 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-17 07:16:15,263 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2025-03-17 07:16:15,264 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-17 07:16:15,264 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2025-03-17 07:16:15,264 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2025-03-17 07:16:15,264 INFO L87 Difference]: Start difference. First operand 482 states and 670 transitions. Second operand has 4 states, 4 states have (on average 14.5) internal successors, (58), 4 states have internal predecessors, (58), 2 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (12), 2 states have call predecessors, (12), 2 states have call successors, (12) [2025-03-17 07:16:15,315 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-17 07:16:15,316 INFO L93 Difference]: Finished difference Result 945 states and 1332 transitions. [2025-03-17 07:16:15,316 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2025-03-17 07:16:15,316 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 14.5) internal successors, (58), 4 states have internal predecessors, (58), 2 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (12), 2 states have call predecessors, (12), 2 states have call successors, (12) Word has length 98 [2025-03-17 07:16:15,317 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-17 07:16:15,322 INFO L225 Difference]: With dead ends: 945 [2025-03-17 07:16:15,322 INFO L226 Difference]: Without dead ends: 486 [2025-03-17 07:16:15,324 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 101 GetRequests, 99 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-17 07:16:15,325 INFO L435 NwaCegarLoop]: 118 mSDtfsCounter, 0 mSDsluCounter, 224 mSDsCounter, 0 mSdLazyCounter, 17 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 342 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-17 07:16:15,325 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 342 Invalid, 18 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 17 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-17 07:16:15,326 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 486 states. [2025-03-17 07:16:15,379 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 486 to 482. [2025-03-17 07:16:15,381 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 482 states, 346 states have (on average 1.277456647398844) internal successors, (442), 358 states have internal predecessors, (442), 94 states have call successors, (94), 31 states have call predecessors, (94), 41 states have return successors, (128), 92 states have call predecessors, (128), 90 states have call successors, (128) [2025-03-17 07:16:15,384 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 482 states to 482 states and 664 transitions. [2025-03-17 07:16:15,386 INFO L78 Accepts]: Start accepts. Automaton has 482 states and 664 transitions. Word has length 98 [2025-03-17 07:16:15,386 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-17 07:16:15,386 INFO L471 AbstractCegarLoop]: Abstraction has 482 states and 664 transitions. [2025-03-17 07:16:15,386 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 14.5) internal successors, (58), 4 states have internal predecessors, (58), 2 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (12), 2 states have call predecessors, (12), 2 states have call successors, (12) [2025-03-17 07:16:15,387 INFO L276 IsEmpty]: Start isEmpty. Operand 482 states and 664 transitions. [2025-03-17 07:16:15,390 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 99 [2025-03-17 07:16:15,391 INFO L210 NwaCegarLoop]: Found error trace [2025-03-17 07:16:15,391 INFO L218 NwaCegarLoop]: trace histogram [6, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 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-17 07:16:15,405 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-17 07:16:15,592 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-17 07:16:15,593 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-17 07:16:15,593 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 07:16:15,593 INFO L85 PathProgramCache]: Analyzing trace with hash 1407766489, now seen corresponding path program 1 times [2025-03-17 07:16:15,593 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 07:16:15,594 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1126678061] [2025-03-17 07:16:15,594 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 07:16:15,594 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 07:16:15,610 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 98 statements into 1 equivalence classes. [2025-03-17 07:16:15,616 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 98 of 98 statements. [2025-03-17 07:16:15,616 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 07:16:15,616 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 07:16:15,673 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 0 proven. 5 refuted. 0 times theorem prover too weak. 73 trivial. 0 not checked. [2025-03-17 07:16:15,674 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-17 07:16:15,674 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1126678061] [2025-03-17 07:16:15,674 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1126678061] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-17 07:16:15,674 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1333335089] [2025-03-17 07:16:15,674 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 07:16:15,674 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-17 07:16:15,674 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 07:16:15,679 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-17 07:16:15,681 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-17 07:16:15,812 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 98 statements into 1 equivalence classes. [2025-03-17 07:16:15,857 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 98 of 98 statements. [2025-03-17 07:16:15,857 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 07:16:15,857 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 07:16:15,861 INFO L256 TraceCheckSpWp]: Trace formula consists of 441 conjuncts, 3 conjuncts are in the unsatisfiable core [2025-03-17 07:16:15,863 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 07:16:15,869 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 49 proven. 0 refuted. 0 times theorem prover too weak. 29 trivial. 0 not checked. [2025-03-17 07:16:15,869 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-17 07:16:15,869 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1333335089] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-17 07:16:15,869 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-03-17 07:16:15,869 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [4] total 4 [2025-03-17 07:16:15,870 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1836663567] [2025-03-17 07:16:15,870 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-17 07:16:15,870 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2025-03-17 07:16:15,870 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-17 07:16:15,870 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2025-03-17 07:16:15,870 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2025-03-17 07:16:15,870 INFO L87 Difference]: Start difference. First operand 482 states and 664 transitions. Second operand has 4 states, 4 states have (on average 14.75) internal successors, (59), 4 states have internal predecessors, (59), 2 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (12), 2 states have call predecessors, (12), 2 states have call successors, (12) [2025-03-17 07:16:15,901 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-17 07:16:15,902 INFO L93 Difference]: Finished difference Result 672 states and 936 transitions. [2025-03-17 07:16:15,902 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2025-03-17 07:16:15,902 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 14.75) internal successors, (59), 4 states have internal predecessors, (59), 2 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (12), 2 states have call predecessors, (12), 2 states have call successors, (12) Word has length 98 [2025-03-17 07:16:15,903 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-17 07:16:15,905 INFO L225 Difference]: With dead ends: 672 [2025-03-17 07:16:15,906 INFO L226 Difference]: Without dead ends: 213 [2025-03-17 07:16:15,907 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 101 GetRequests, 99 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-17 07:16:15,908 INFO L435 NwaCegarLoop]: 117 mSDtfsCounter, 0 mSDsluCounter, 225 mSDsCounter, 0 mSdLazyCounter, 14 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 342 SdHoareTripleChecker+Invalid, 16 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 14 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-17 07:16:15,908 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 342 Invalid, 16 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 14 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-17 07:16:15,909 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 213 states. [2025-03-17 07:16:15,939 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 213 to 197. [2025-03-17 07:16:15,939 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 197 states, 131 states have (on average 1.2213740458015268) internal successors, (160), 135 states have internal predecessors, (160), 48 states have call successors, (48), 15 states have call predecessors, (48), 17 states have return successors, (50), 46 states have call predecessors, (50), 46 states have call successors, (50) [2025-03-17 07:16:15,940 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 197 states to 197 states and 258 transitions. [2025-03-17 07:16:15,941 INFO L78 Accepts]: Start accepts. Automaton has 197 states and 258 transitions. Word has length 98 [2025-03-17 07:16:15,941 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-17 07:16:15,941 INFO L471 AbstractCegarLoop]: Abstraction has 197 states and 258 transitions. [2025-03-17 07:16:15,941 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 14.75) internal successors, (59), 4 states have internal predecessors, (59), 2 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (12), 2 states have call predecessors, (12), 2 states have call successors, (12) [2025-03-17 07:16:15,941 INFO L276 IsEmpty]: Start isEmpty. Operand 197 states and 258 transitions. [2025-03-17 07:16:15,946 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 100 [2025-03-17 07:16:15,946 INFO L210 NwaCegarLoop]: Found error trace [2025-03-17 07:16:15,946 INFO L218 NwaCegarLoop]: trace histogram [6, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 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-17 07:16:15,959 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Ended with exit code 0 [2025-03-17 07:16:16,147 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2025-03-17 07:16:16,147 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-17 07:16:16,147 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 07:16:16,147 INFO L85 PathProgramCache]: Analyzing trace with hash 2121332799, now seen corresponding path program 1 times [2025-03-17 07:16:16,147 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 07:16:16,147 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1917166509] [2025-03-17 07:16:16,148 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 07:16:16,148 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 07:16:16,167 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 99 statements into 1 equivalence classes. [2025-03-17 07:16:16,176 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 99 of 99 statements. [2025-03-17 07:16:16,177 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 07:16:16,177 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 07:16:16,474 INFO L134 CoverageAnalysis]: Checked inductivity of 79 backedges. 0 proven. 12 refuted. 0 times theorem prover too weak. 67 trivial. 0 not checked. [2025-03-17 07:16:16,474 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-17 07:16:16,474 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1917166509] [2025-03-17 07:16:16,474 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1917166509] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-17 07:16:16,474 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [458524648] [2025-03-17 07:16:16,474 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 07:16:16,474 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-17 07:16:16,474 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 07:16:16,477 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-17 07:16:16,479 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2025-03-17 07:16:16,595 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 99 statements into 1 equivalence classes. [2025-03-17 07:16:16,636 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 99 of 99 statements. [2025-03-17 07:16:16,636 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 07:16:16,636 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 07:16:16,639 INFO L256 TraceCheckSpWp]: Trace formula consists of 445 conjuncts, 60 conjuncts are in the unsatisfiable core [2025-03-17 07:16:16,642 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 07:16:16,672 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-17 07:16:16,832 INFO L134 CoverageAnalysis]: Checked inductivity of 79 backedges. 52 proven. 2 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2025-03-17 07:16:16,833 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-17 07:16:17,256 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 56 treesize of output 52 [2025-03-17 07:16:17,278 INFO L134 CoverageAnalysis]: Checked inductivity of 79 backedges. 0 proven. 12 refuted. 0 times theorem prover too weak. 67 trivial. 0 not checked. [2025-03-17 07:16:17,279 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [458524648] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-17 07:16:17,279 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-17 07:16:17,279 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16, 16] total 33 [2025-03-17 07:16:17,279 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1892341345] [2025-03-17 07:16:17,279 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-17 07:16:17,279 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 33 states [2025-03-17 07:16:17,279 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-17 07:16:17,280 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 33 interpolants. [2025-03-17 07:16:17,280 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=108, Invalid=948, Unknown=0, NotChecked=0, Total=1056 [2025-03-17 07:16:17,280 INFO L87 Difference]: Start difference. First operand 197 states and 258 transitions. Second operand has 33 states, 30 states have (on average 3.966666666666667) internal successors, (119), 28 states have internal predecessors, (119), 11 states have call successors, (28), 4 states have call predecessors, (28), 5 states have return successors, (26), 9 states have call predecessors, (26), 11 states have call successors, (26) [2025-03-17 07:16:17,953 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-17 07:16:17,953 INFO L93 Difference]: Finished difference Result 483 states and 680 transitions. [2025-03-17 07:16:17,958 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 25 states. [2025-03-17 07:16:17,958 INFO L78 Accepts]: Start accepts. Automaton has has 33 states, 30 states have (on average 3.966666666666667) internal successors, (119), 28 states have internal predecessors, (119), 11 states have call successors, (28), 4 states have call predecessors, (28), 5 states have return successors, (26), 9 states have call predecessors, (26), 11 states have call successors, (26) Word has length 99 [2025-03-17 07:16:17,959 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-17 07:16:17,961 INFO L225 Difference]: With dead ends: 483 [2025-03-17 07:16:17,961 INFO L226 Difference]: Without dead ends: 293 [2025-03-17 07:16:17,963 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 227 GetRequests, 181 SyntacticMatches, 0 SemanticMatches, 46 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 414 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=264, Invalid=1992, Unknown=0, NotChecked=0, Total=2256 [2025-03-17 07:16:17,963 INFO L435 NwaCegarLoop]: 99 mSDtfsCounter, 156 mSDsluCounter, 1665 mSDsCounter, 0 mSdLazyCounter, 708 mSolverCounterSat, 68 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 167 SdHoareTripleChecker+Valid, 1764 SdHoareTripleChecker+Invalid, 776 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 68 IncrementalHoareTripleChecker+Valid, 708 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2025-03-17 07:16:17,963 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [167 Valid, 1764 Invalid, 776 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [68 Valid, 708 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2025-03-17 07:16:17,964 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 293 states. [2025-03-17 07:16:17,986 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 293 to 217. [2025-03-17 07:16:17,986 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 217 states, 149 states have (on average 1.2483221476510067) internal successors, (186), 151 states have internal predecessors, (186), 48 states have call successors, (48), 15 states have call predecessors, (48), 19 states have return successors, (58), 50 states have call predecessors, (58), 46 states have call successors, (58) [2025-03-17 07:16:17,988 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 217 states to 217 states and 292 transitions. [2025-03-17 07:16:17,990 INFO L78 Accepts]: Start accepts. Automaton has 217 states and 292 transitions. Word has length 99 [2025-03-17 07:16:17,990 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-17 07:16:17,990 INFO L471 AbstractCegarLoop]: Abstraction has 217 states and 292 transitions. [2025-03-17 07:16:17,990 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 33 states, 30 states have (on average 3.966666666666667) internal successors, (119), 28 states have internal predecessors, (119), 11 states have call successors, (28), 4 states have call predecessors, (28), 5 states have return successors, (26), 9 states have call predecessors, (26), 11 states have call successors, (26) [2025-03-17 07:16:17,991 INFO L276 IsEmpty]: Start isEmpty. Operand 217 states and 292 transitions. [2025-03-17 07:16:17,992 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 100 [2025-03-17 07:16:17,992 INFO L210 NwaCegarLoop]: Found error trace [2025-03-17 07:16:17,992 INFO L218 NwaCegarLoop]: trace histogram [6, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 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-17 07:16:18,005 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Ended with exit code 0 [2025-03-17 07:16:18,193 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2025-03-17 07:16:18,193 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-17 07:16:18,193 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 07:16:18,194 INFO L85 PathProgramCache]: Analyzing trace with hash -1933094368, now seen corresponding path program 1 times [2025-03-17 07:16:18,194 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 07:16:18,194 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [849480414] [2025-03-17 07:16:18,194 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 07:16:18,194 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 07:16:18,215 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 99 statements into 1 equivalence classes. [2025-03-17 07:16:18,272 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 99 of 99 statements. [2025-03-17 07:16:18,272 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 07:16:18,272 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 07:16:19,136 INFO L134 CoverageAnalysis]: Checked inductivity of 79 backedges. 0 proven. 8 refuted. 0 times theorem prover too weak. 71 trivial. 0 not checked. [2025-03-17 07:16:19,136 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-17 07:16:19,137 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [849480414] [2025-03-17 07:16:19,137 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [849480414] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-17 07:16:19,137 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [763878009] [2025-03-17 07:16:19,137 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 07:16:19,137 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-17 07:16:19,137 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 07:16:19,142 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-17 07:16:19,145 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2025-03-17 07:16:19,308 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 99 statements into 1 equivalence classes. [2025-03-17 07:16:19,362 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 99 of 99 statements. [2025-03-17 07:16:19,362 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 07:16:19,362 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 07:16:19,365 INFO L256 TraceCheckSpWp]: Trace formula consists of 454 conjuncts, 95 conjuncts are in the unsatisfiable core [2025-03-17 07:16:19,369 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 07:16:19,487 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-17 07:16:19,487 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 21 treesize of output 1 [2025-03-17 07:16:19,493 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-17 07:16:19,494 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-17 07:16:19,495 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 22 treesize of output 22 [2025-03-17 07:16:19,498 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-17 07:16:23,519 WARN L873 $PredicateComparison]: unable to prove that (exists ((|v_ULTIMATE.start_aws_linked_list_back_harness_~#list~0#1.base_BEFORE_CALL_42| Int)) (and (<= 2 |v_ULTIMATE.start_aws_linked_list_back_harness_~#list~0#1.base_BEFORE_CALL_42|) (<= (+ 2 (select (select |c_#memory_$Pointer$#2.base| |v_ULTIMATE.start_aws_linked_list_back_harness_~#list~0#1.base_BEFORE_CALL_42|) 24)) |v_ULTIMATE.start_aws_linked_list_back_harness_~#list~0#1.base_BEFORE_CALL_42|))) is different from true [2025-03-17 07:16:27,583 WARN L873 $PredicateComparison]: unable to prove that (exists ((|v_ULTIMATE.start_aws_linked_list_back_harness_~#list~0#1.base_BEFORE_CALL_43| Int)) (and (<= (+ 2 (select (select |c_#memory_$Pointer$#2.base| |v_ULTIMATE.start_aws_linked_list_back_harness_~#list~0#1.base_BEFORE_CALL_43|) 24)) |v_ULTIMATE.start_aws_linked_list_back_harness_~#list~0#1.base_BEFORE_CALL_43|) (<= 2 |v_ULTIMATE.start_aws_linked_list_back_harness_~#list~0#1.base_BEFORE_CALL_43|))) is different from true [2025-03-17 07:16:31,688 WARN L873 $PredicateComparison]: unable to prove that (exists ((v_aws_linked_list_back_~list.base_BEFORE_CALL_32 Int)) (and (<= (+ (select (select |c_#memory_$Pointer$#2.base| v_aws_linked_list_back_~list.base_BEFORE_CALL_32) 24) 2) v_aws_linked_list_back_~list.base_BEFORE_CALL_32) (<= 2 v_aws_linked_list_back_~list.base_BEFORE_CALL_32))) is different from true