./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/heap-manipulation/bubble_sort_linux-2.i --full-output --architecture 32bit -------------------------------------------------------------------------------- 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/heap-manipulation/bubble_sort_linux-2.i -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-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 32bit --witnessprinter.graph.data.programhash 3b13662719be51a1d3330a7f40f7706daa8c7b2d4044bc92f854095c09c7c129 --- Real Ultimate output --- This is Ultimate 0.3.0-?-8fc3dc6-m [2025-03-16 17:35:21,435 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-03-16 17:35:21,494 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2025-03-16 17:35:21,501 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-03-16 17:35:21,503 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-03-16 17:35:21,524 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-03-16 17:35:21,526 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-03-16 17:35:21,526 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-03-16 17:35:21,526 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-03-16 17:35:21,526 INFO L153 SettingsManager]: * Use memory slicer=true [2025-03-16 17:35:21,527 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2025-03-16 17:35:21,527 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2025-03-16 17:35:21,527 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-03-16 17:35:21,527 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-03-16 17:35:21,528 INFO L153 SettingsManager]: * Use SBE=true [2025-03-16 17:35:21,528 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-03-16 17:35:21,528 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2025-03-16 17:35:21,528 INFO L153 SettingsManager]: * sizeof long=4 [2025-03-16 17:35:21,528 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2025-03-16 17:35:21,528 INFO L153 SettingsManager]: * sizeof POINTER=4 [2025-03-16 17:35:21,528 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-03-16 17:35:21,528 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2025-03-16 17:35:21,529 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2025-03-16 17:35:21,529 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2025-03-16 17:35:21,529 INFO L153 SettingsManager]: * sizeof long double=12 [2025-03-16 17:35:21,529 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-03-16 17:35:21,529 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-03-16 17:35:21,529 INFO L153 SettingsManager]: * Use constant arrays=true [2025-03-16 17:35:21,529 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-03-16 17:35:21,529 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-03-16 17:35:21,529 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-03-16 17:35:21,529 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-03-16 17:35:21,529 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-16 17:35:21,529 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-03-16 17:35:21,530 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2025-03-16 17:35:21,530 INFO L153 SettingsManager]: * Compute procedure contracts=false [2025-03-16 17:35:21,530 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2025-03-16 17:35:21,530 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2025-03-16 17:35:21,530 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2025-03-16 17:35:21,530 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2025-03-16 17:35:21,530 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2025-03-16 17:35:21,530 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2025-03-16 17:35:21,530 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2025-03-16 17:35:21,531 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 -> 32bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> 3b13662719be51a1d3330a7f40f7706daa8c7b2d4044bc92f854095c09c7c129 [2025-03-16 17:35:21,752 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-03-16 17:35:21,758 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-03-16 17:35:21,761 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-03-16 17:35:21,762 INFO L270 PluginConnector]: Initializing CDTParser... [2025-03-16 17:35:21,762 INFO L274 PluginConnector]: CDTParser initialized [2025-03-16 17:35:21,763 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/heap-manipulation/bubble_sort_linux-2.i [2025-03-16 17:35:22,958 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/75ae5aa2c/081b6125147f42e3bdf1606a3610254f/FLAGed0ee5e1c [2025-03-16 17:35:23,253 INFO L384 CDTParser]: Found 1 translation units. [2025-03-16 17:35:23,253 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/heap-manipulation/bubble_sort_linux-2.i [2025-03-16 17:35:23,266 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/75ae5aa2c/081b6125147f42e3bdf1606a3610254f/FLAGed0ee5e1c [2025-03-16 17:35:23,531 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/75ae5aa2c/081b6125147f42e3bdf1606a3610254f [2025-03-16 17:35:23,533 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-03-16 17:35:23,534 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-03-16 17:35:23,535 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-03-16 17:35:23,535 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-03-16 17:35:23,538 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-03-16 17:35:23,539 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 16.03 05:35:23" (1/1) ... [2025-03-16 17:35:23,540 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@2e524359 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 05:35:23, skipping insertion in model container [2025-03-16 17:35:23,540 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 16.03 05:35:23" (1/1) ... [2025-03-16 17:35:23,565 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-03-16 17:35:23,780 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/heap-manipulation/bubble_sort_linux-2.i[33822,33835] [2025-03-16 17:35:23,820 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-16 17:35:23,828 INFO L200 MainTranslator]: Completed pre-run [2025-03-16 17:35:23,855 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/heap-manipulation/bubble_sort_linux-2.i[33822,33835] [2025-03-16 17:35:23,875 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-16 17:35:23,913 INFO L204 MainTranslator]: Completed translation [2025-03-16 17:35:23,914 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 05:35:23 WrapperNode [2025-03-16 17:35:23,914 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-03-16 17:35:23,916 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-03-16 17:35:23,916 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-03-16 17:35:23,917 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-03-16 17:35:23,921 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 05:35:23" (1/1) ... [2025-03-16 17:35:23,934 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 05:35:23" (1/1) ... [2025-03-16 17:35:23,948 INFO L138 Inliner]: procedures = 232, calls = 75, calls flagged for inlining = 10, calls inlined = 10, statements flattened = 114 [2025-03-16 17:35:23,948 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-03-16 17:35:23,949 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-03-16 17:35:23,949 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-03-16 17:35:23,949 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-03-16 17:35:23,954 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 05:35:23" (1/1) ... [2025-03-16 17:35:23,955 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 05:35:23" (1/1) ... [2025-03-16 17:35:23,957 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 05:35:23" (1/1) ... [2025-03-16 17:35:23,979 INFO L175 MemorySlicer]: Split 37 memory accesses to 2 slices as follows [2, 35]. 95 percent of accesses are in the largest equivalence class. The 4 initializations are split as follows [2, 2]. The 10 writes are split as follows [0, 10]. [2025-03-16 17:35:23,980 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 05:35:23" (1/1) ... [2025-03-16 17:35:23,980 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 05:35:23" (1/1) ... [2025-03-16 17:35:23,987 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 05:35:23" (1/1) ... [2025-03-16 17:35:23,989 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 05:35:23" (1/1) ... [2025-03-16 17:35:23,990 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 05:35:23" (1/1) ... [2025-03-16 17:35:23,991 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 05:35:23" (1/1) ... [2025-03-16 17:35:23,993 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-03-16 17:35:23,993 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2025-03-16 17:35:23,993 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2025-03-16 17:35:23,993 INFO L274 PluginConnector]: IcfgBuilder initialized [2025-03-16 17:35:23,994 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 05:35:23" (1/1) ... [2025-03-16 17:35:24,000 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-16 17:35:24,012 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 17:35:24,023 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-16 17:35:24,026 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-16 17:35:24,045 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$#0 [2025-03-16 17:35:24,045 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$#1 [2025-03-16 17:35:24,045 INFO L130 BoogieDeclarations]: Found specification of procedure inspect [2025-03-16 17:35:24,045 INFO L138 BoogieDeclarations]: Found implementation of procedure inspect [2025-03-16 17:35:24,045 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2025-03-16 17:35:24,045 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$#0 [2025-03-16 17:35:24,045 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$#1 [2025-03-16 17:35:24,045 INFO L130 BoogieDeclarations]: Found specification of procedure val_from_node [2025-03-16 17:35:24,045 INFO L138 BoogieDeclarations]: Found implementation of procedure val_from_node [2025-03-16 17:35:24,045 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#0 [2025-03-16 17:35:24,045 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#1 [2025-03-16 17:35:24,045 INFO L130 BoogieDeclarations]: Found specification of procedure fail [2025-03-16 17:35:24,045 INFO L138 BoogieDeclarations]: Found implementation of procedure fail [2025-03-16 17:35:24,045 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#0 [2025-03-16 17:35:24,045 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#1 [2025-03-16 17:35:24,045 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnHeap [2025-03-16 17:35:24,045 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2025-03-16 17:35:24,045 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$#0 [2025-03-16 17:35:24,046 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$#1 [2025-03-16 17:35:24,046 INFO L130 BoogieDeclarations]: Found specification of procedure list_add [2025-03-16 17:35:24,046 INFO L138 BoogieDeclarations]: Found implementation of procedure list_add [2025-03-16 17:35:24,046 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2025-03-16 17:35:24,046 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#1 [2025-03-16 17:35:24,046 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-03-16 17:35:24,046 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-03-16 17:35:24,189 INFO L256 CfgBuilder]: Building ICFG [2025-03-16 17:35:24,191 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2025-03-16 17:35:24,231 INFO L1322 $ProcedureCfgBuilder]: dead code at ProgramPoint L923: havoc #t~mem54; [2025-03-16 17:35:24,508 INFO L? ?]: Removed 40 outVars from TransFormulas that were not future-live. [2025-03-16 17:35:24,508 INFO L307 CfgBuilder]: Performing block encoding [2025-03-16 17:35:24,521 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-03-16 17:35:24,521 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2025-03-16 17:35:24,522 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 16.03 05:35:24 BoogieIcfgContainer [2025-03-16 17:35:24,522 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2025-03-16 17:35:24,523 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2025-03-16 17:35:24,523 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2025-03-16 17:35:24,526 INFO L274 PluginConnector]: TraceAbstraction initialized [2025-03-16 17:35:24,527 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 16.03 05:35:23" (1/3) ... [2025-03-16 17:35:24,527 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@198f8e1d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 16.03 05:35:24, skipping insertion in model container [2025-03-16 17:35:24,527 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 05:35:23" (2/3) ... [2025-03-16 17:35:24,527 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@198f8e1d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 16.03 05:35:24, skipping insertion in model container [2025-03-16 17:35:24,527 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 16.03 05:35:24" (3/3) ... [2025-03-16 17:35:24,528 INFO L128 eAbstractionObserver]: Analyzing ICFG bubble_sort_linux-2.i [2025-03-16 17:35:24,540 INFO L216 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2025-03-16 17:35:24,542 INFO L151 ceAbstractionStarter]: Applying trace abstraction to ICFG bubble_sort_linux-2.i that has 5 procedures, 110 locations, 1 initial locations, 23 loop locations, and 1 error locations. [2025-03-16 17:35:24,587 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2025-03-16 17:35:24,597 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;@5b7f333, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2025-03-16 17:35:24,597 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2025-03-16 17:35:24,602 INFO L276 IsEmpty]: Start isEmpty. Operand has 110 states, 81 states have (on average 1.8024691358024691) internal successors, (146), 100 states have internal predecessors, (146), 23 states have call successors, (23), 4 states have call predecessors, (23), 4 states have return successors, (23), 23 states have call predecessors, (23), 23 states have call successors, (23) [2025-03-16 17:35:24,606 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 9 [2025-03-16 17:35:24,607 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 17:35:24,607 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 17:35:24,607 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting failErr0ASSERT_VIOLATIONERROR_FUNCTION === [failErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 17:35:24,612 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 17:35:24,612 INFO L85 PathProgramCache]: Analyzing trace with hash 1839058348, now seen corresponding path program 1 times [2025-03-16 17:35:24,618 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 17:35:24,619 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1070720740] [2025-03-16 17:35:24,619 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 17:35:24,620 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 17:35:24,679 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 8 statements into 1 equivalence classes. [2025-03-16 17:35:24,683 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 8 of 8 statements. [2025-03-16 17:35:24,685 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 17:35:24,685 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 17:35:24,744 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-16 17:35:24,745 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 17:35:24,745 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1070720740] [2025-03-16 17:35:24,745 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1070720740] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-16 17:35:24,745 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-16 17:35:24,746 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2025-03-16 17:35:24,747 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2128565574] [2025-03-16 17:35:24,747 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-16 17:35:24,749 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2025-03-16 17:35:24,750 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 17:35:24,766 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2025-03-16 17:35:24,766 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2025-03-16 17:35:24,769 INFO L87 Difference]: Start difference. First operand has 110 states, 81 states have (on average 1.8024691358024691) internal successors, (146), 100 states have internal predecessors, (146), 23 states have call successors, (23), 4 states have call predecessors, (23), 4 states have return successors, (23), 23 states have call predecessors, (23), 23 states have call successors, (23) Second operand has 2 states, 2 states have (on average 3.0) internal successors, (6), 2 states have internal predecessors, (6), 1 states have call successors, (2), 1 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-03-16 17:35:24,800 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 17:35:24,801 INFO L93 Difference]: Finished difference Result 215 states and 380 transitions. [2025-03-16 17:35:24,801 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2025-03-16 17:35:24,802 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 3.0) internal successors, (6), 2 states have internal predecessors, (6), 1 states have call successors, (2), 1 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 8 [2025-03-16 17:35:24,803 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 17:35:24,807 INFO L225 Difference]: With dead ends: 215 [2025-03-16 17:35:24,807 INFO L226 Difference]: Without dead ends: 100 [2025-03-16 17:35:24,811 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 2 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-16 17:35:24,814 INFO L435 NwaCegarLoop]: 128 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, 128 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-16 17:35:24,816 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 128 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-16 17:35:24,827 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 100 states. [2025-03-16 17:35:24,844 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 100 to 100. [2025-03-16 17:35:24,846 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 100 states, 75 states have (on average 1.2666666666666666) internal successors, (95), 90 states have internal predecessors, (95), 21 states have call successors, (21), 4 states have call predecessors, (21), 3 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2025-03-16 17:35:24,851 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 100 states to 100 states and 121 transitions. [2025-03-16 17:35:24,855 INFO L78 Accepts]: Start accepts. Automaton has 100 states and 121 transitions. Word has length 8 [2025-03-16 17:35:24,855 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 17:35:24,855 INFO L471 AbstractCegarLoop]: Abstraction has 100 states and 121 transitions. [2025-03-16 17:35:24,856 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 3.0) internal successors, (6), 2 states have internal predecessors, (6), 1 states have call successors, (2), 1 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-03-16 17:35:24,856 INFO L276 IsEmpty]: Start isEmpty. Operand 100 states and 121 transitions. [2025-03-16 17:35:24,857 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2025-03-16 17:35:24,857 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 17:35:24,857 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 17:35:24,857 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2025-03-16 17:35:24,857 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting failErr0ASSERT_VIOLATIONERROR_FUNCTION === [failErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 17:35:24,858 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 17:35:24,858 INFO L85 PathProgramCache]: Analyzing trace with hash 1094066599, now seen corresponding path program 1 times [2025-03-16 17:35:24,858 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 17:35:24,858 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1184149510] [2025-03-16 17:35:24,858 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 17:35:24,858 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 17:35:24,889 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 18 statements into 1 equivalence classes. [2025-03-16 17:35:24,940 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 18 of 18 statements. [2025-03-16 17:35:24,941 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 17:35:24,942 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 17:35:25,180 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-16 17:35:25,181 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 17:35:25,181 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1184149510] [2025-03-16 17:35:25,181 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1184149510] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-16 17:35:25,181 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-16 17:35:25,181 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-16 17:35:25,181 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [390676506] [2025-03-16 17:35:25,181 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-16 17:35:25,182 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-16 17:35:25,182 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 17:35:25,183 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-16 17:35:25,183 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-16 17:35:25,183 INFO L87 Difference]: Start difference. First operand 100 states and 121 transitions. Second operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2025-03-16 17:35:25,327 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 17:35:25,327 INFO L93 Difference]: Finished difference Result 102 states and 122 transitions. [2025-03-16 17:35:25,329 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-16 17:35:25,329 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 18 [2025-03-16 17:35:25,329 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 17:35:25,330 INFO L225 Difference]: With dead ends: 102 [2025-03-16 17:35:25,330 INFO L226 Difference]: Without dead ends: 99 [2025-03-16 17:35:25,330 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=25, Unknown=0, NotChecked=0, Total=42 [2025-03-16 17:35:25,331 INFO L435 NwaCegarLoop]: 105 mSDtfsCounter, 169 mSDsluCounter, 125 mSDsCounter, 0 mSdLazyCounter, 49 mSolverCounterSat, 15 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 170 SdHoareTripleChecker+Valid, 230 SdHoareTripleChecker+Invalid, 64 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 15 IncrementalHoareTripleChecker+Valid, 49 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-16 17:35:25,331 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [170 Valid, 230 Invalid, 64 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [15 Valid, 49 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-16 17:35:25,332 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 99 states. [2025-03-16 17:35:25,346 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 99 to 99. [2025-03-16 17:35:25,347 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 99 states, 75 states have (on average 1.2533333333333334) internal successors, (94), 89 states have internal predecessors, (94), 20 states have call successors, (20), 4 states have call predecessors, (20), 3 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2025-03-16 17:35:25,348 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 99 states to 99 states and 119 transitions. [2025-03-16 17:35:25,349 INFO L78 Accepts]: Start accepts. Automaton has 99 states and 119 transitions. Word has length 18 [2025-03-16 17:35:25,351 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 17:35:25,351 INFO L471 AbstractCegarLoop]: Abstraction has 99 states and 119 transitions. [2025-03-16 17:35:25,351 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2025-03-16 17:35:25,351 INFO L276 IsEmpty]: Start isEmpty. Operand 99 states and 119 transitions. [2025-03-16 17:35:25,352 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2025-03-16 17:35:25,352 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 17:35:25,352 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 17:35:25,352 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2025-03-16 17:35:25,352 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting failErr0ASSERT_VIOLATIONERROR_FUNCTION === [failErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 17:35:25,353 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 17:35:25,354 INFO L85 PathProgramCache]: Analyzing trace with hash -1218901000, now seen corresponding path program 1 times [2025-03-16 17:35:25,354 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 17:35:25,354 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1781334424] [2025-03-16 17:35:25,354 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 17:35:25,354 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 17:35:25,372 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 21 statements into 1 equivalence classes. [2025-03-16 17:35:25,408 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 21 of 21 statements. [2025-03-16 17:35:25,408 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 17:35:25,409 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 17:35:25,791 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-16 17:35:25,791 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 17:35:25,791 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1781334424] [2025-03-16 17:35:25,791 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1781334424] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-16 17:35:25,791 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-16 17:35:25,791 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [10] imperfect sequences [] total 10 [2025-03-16 17:35:25,791 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1965363896] [2025-03-16 17:35:25,792 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-16 17:35:25,792 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2025-03-16 17:35:25,792 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 17:35:25,792 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2025-03-16 17:35:25,792 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=72, Unknown=0, NotChecked=0, Total=90 [2025-03-16 17:35:25,792 INFO L87 Difference]: Start difference. First operand 99 states and 119 transitions. Second operand has 10 states, 10 states have (on average 1.7) internal successors, (17), 7 states have internal predecessors, (17), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2025-03-16 17:35:26,320 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 17:35:26,320 INFO L93 Difference]: Finished difference Result 188 states and 225 transitions. [2025-03-16 17:35:26,321 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2025-03-16 17:35:26,321 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 1.7) internal successors, (17), 7 states have internal predecessors, (17), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 21 [2025-03-16 17:35:26,321 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 17:35:26,323 INFO L225 Difference]: With dead ends: 188 [2025-03-16 17:35:26,323 INFO L226 Difference]: Without dead ends: 182 [2025-03-16 17:35:26,324 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 18 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 17 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=62, Invalid=210, Unknown=0, NotChecked=0, Total=272 [2025-03-16 17:35:26,324 INFO L435 NwaCegarLoop]: 90 mSDtfsCounter, 346 mSDsluCounter, 446 mSDsCounter, 0 mSdLazyCounter, 428 mSolverCounterSat, 49 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 347 SdHoareTripleChecker+Valid, 536 SdHoareTripleChecker+Invalid, 477 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 49 IncrementalHoareTripleChecker+Valid, 428 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2025-03-16 17:35:26,324 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [347 Valid, 536 Invalid, 477 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [49 Valid, 428 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2025-03-16 17:35:26,326 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 182 states. [2025-03-16 17:35:26,356 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 182 to 162. [2025-03-16 17:35:26,356 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 162 states, 134 states have (on average 1.2611940298507462) internal successors, (169), 148 states have internal predecessors, (169), 23 states have call successors, (23), 6 states have call predecessors, (23), 4 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2025-03-16 17:35:26,360 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 162 states to 162 states and 199 transitions. [2025-03-16 17:35:26,362 INFO L78 Accepts]: Start accepts. Automaton has 162 states and 199 transitions. Word has length 21 [2025-03-16 17:35:26,362 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 17:35:26,363 INFO L471 AbstractCegarLoop]: Abstraction has 162 states and 199 transitions. [2025-03-16 17:35:26,363 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 1.7) internal successors, (17), 7 states have internal predecessors, (17), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2025-03-16 17:35:26,363 INFO L276 IsEmpty]: Start isEmpty. Operand 162 states and 199 transitions. [2025-03-16 17:35:26,363 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2025-03-16 17:35:26,363 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 17:35:26,363 INFO L218 NwaCegarLoop]: trace histogram [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-16 17:35:26,364 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2025-03-16 17:35:26,364 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting failErr0ASSERT_VIOLATIONERROR_FUNCTION === [failErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 17:35:26,364 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 17:35:26,364 INFO L85 PathProgramCache]: Analyzing trace with hash 1613821284, now seen corresponding path program 1 times [2025-03-16 17:35:26,364 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 17:35:26,364 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [422364776] [2025-03-16 17:35:26,364 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 17:35:26,364 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 17:35:26,378 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 24 statements into 1 equivalence classes. [2025-03-16 17:35:26,406 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 24 of 24 statements. [2025-03-16 17:35:26,406 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 17:35:26,407 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 17:35:27,076 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-16 17:35:27,078 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 17:35:27,078 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [422364776] [2025-03-16 17:35:27,078 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [422364776] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-16 17:35:27,078 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-16 17:35:27,078 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [10] imperfect sequences [] total 10 [2025-03-16 17:35:27,078 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [268608881] [2025-03-16 17:35:27,078 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-16 17:35:27,078 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2025-03-16 17:35:27,079 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 17:35:27,079 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2025-03-16 17:35:27,079 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=90, Unknown=0, NotChecked=0, Total=110 [2025-03-16 17:35:27,079 INFO L87 Difference]: Start difference. First operand 162 states and 199 transitions. Second operand has 11 states, 11 states have (on average 1.8181818181818181) internal successors, (20), 7 states have internal predecessors, (20), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2025-03-16 17:35:27,952 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 17:35:27,952 INFO L93 Difference]: Finished difference Result 260 states and 315 transitions. [2025-03-16 17:35:27,953 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2025-03-16 17:35:27,953 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 11 states have (on average 1.8181818181818181) internal successors, (20), 7 states have internal predecessors, (20), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 24 [2025-03-16 17:35:27,953 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 17:35:27,955 INFO L225 Difference]: With dead ends: 260 [2025-03-16 17:35:27,956 INFO L226 Difference]: Without dead ends: 257 [2025-03-16 17:35:27,956 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 17 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 17 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=56, Invalid=216, Unknown=0, NotChecked=0, Total=272 [2025-03-16 17:35:27,957 INFO L435 NwaCegarLoop]: 24 mSDtfsCounter, 301 mSDsluCounter, 155 mSDsCounter, 0 mSdLazyCounter, 942 mSolverCounterSat, 39 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 304 SdHoareTripleChecker+Valid, 179 SdHoareTripleChecker+Invalid, 981 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 39 IncrementalHoareTripleChecker+Valid, 942 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.7s IncrementalHoareTripleChecker+Time [2025-03-16 17:35:27,957 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [304 Valid, 179 Invalid, 981 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [39 Valid, 942 Invalid, 0 Unknown, 0 Unchecked, 0.7s Time] [2025-03-16 17:35:27,960 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 257 states. [2025-03-16 17:35:27,995 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 257 to 239. [2025-03-16 17:35:27,995 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 239 states, 204 states have (on average 1.2549019607843137) internal successors, (256), 219 states have internal predecessors, (256), 28 states have call successors, (28), 8 states have call predecessors, (28), 6 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2025-03-16 17:35:27,997 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 239 states to 239 states and 295 transitions. [2025-03-16 17:35:27,997 INFO L78 Accepts]: Start accepts. Automaton has 239 states and 295 transitions. Word has length 24 [2025-03-16 17:35:27,997 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 17:35:27,998 INFO L471 AbstractCegarLoop]: Abstraction has 239 states and 295 transitions. [2025-03-16 17:35:27,998 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 11 states have (on average 1.8181818181818181) internal successors, (20), 7 states have internal predecessors, (20), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2025-03-16 17:35:27,998 INFO L276 IsEmpty]: Start isEmpty. Operand 239 states and 295 transitions. [2025-03-16 17:35:27,998 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2025-03-16 17:35:27,998 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 17:35:27,998 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 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-16 17:35:27,999 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2025-03-16 17:35:27,999 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting failErr0ASSERT_VIOLATIONERROR_FUNCTION === [failErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 17:35:27,999 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 17:35:27,999 INFO L85 PathProgramCache]: Analyzing trace with hash -573818316, now seen corresponding path program 1 times [2025-03-16 17:35:27,999 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 17:35:28,000 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1126960935] [2025-03-16 17:35:28,000 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 17:35:28,000 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 17:35:28,010 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 27 statements into 1 equivalence classes. [2025-03-16 17:35:28,024 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 27 of 27 statements. [2025-03-16 17:35:28,024 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 17:35:28,024 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 17:35:28,485 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-16 17:35:28,485 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 17:35:28,485 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1126960935] [2025-03-16 17:35:28,485 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1126960935] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-16 17:35:28,485 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-16 17:35:28,485 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [10] imperfect sequences [] total 10 [2025-03-16 17:35:28,485 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1000584477] [2025-03-16 17:35:28,485 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-16 17:35:28,485 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2025-03-16 17:35:28,485 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 17:35:28,486 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2025-03-16 17:35:28,486 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=90, Unknown=0, NotChecked=0, Total=110 [2025-03-16 17:35:28,486 INFO L87 Difference]: Start difference. First operand 239 states and 295 transitions. Second operand has 11 states, 11 states have (on average 2.090909090909091) internal successors, (23), 7 states have internal predecessors, (23), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2025-03-16 17:35:29,177 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 17:35:29,177 INFO L93 Difference]: Finished difference Result 259 states and 313 transitions. [2025-03-16 17:35:29,178 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2025-03-16 17:35:29,178 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 11 states have (on average 2.090909090909091) internal successors, (23), 7 states have internal predecessors, (23), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 27 [2025-03-16 17:35:29,178 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 17:35:29,180 INFO L225 Difference]: With dead ends: 259 [2025-03-16 17:35:29,181 INFO L226 Difference]: Without dead ends: 256 [2025-03-16 17:35:29,181 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 17 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 18 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=54, Invalid=218, Unknown=0, NotChecked=0, Total=272 [2025-03-16 17:35:29,182 INFO L435 NwaCegarLoop]: 24 mSDtfsCounter, 340 mSDsluCounter, 155 mSDsCounter, 0 mSdLazyCounter, 942 mSolverCounterSat, 37 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 343 SdHoareTripleChecker+Valid, 179 SdHoareTripleChecker+Invalid, 979 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 37 IncrementalHoareTripleChecker+Valid, 942 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2025-03-16 17:35:29,183 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [343 Valid, 179 Invalid, 979 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [37 Valid, 942 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2025-03-16 17:35:29,183 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 256 states. [2025-03-16 17:35:29,206 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 256 to 239. [2025-03-16 17:35:29,206 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 239 states, 204 states have (on average 1.25) internal successors, (255), 219 states have internal predecessors, (255), 28 states have call successors, (28), 8 states have call predecessors, (28), 6 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2025-03-16 17:35:29,207 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 239 states to 239 states and 294 transitions. [2025-03-16 17:35:29,209 INFO L78 Accepts]: Start accepts. Automaton has 239 states and 294 transitions. Word has length 27 [2025-03-16 17:35:29,209 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 17:35:29,209 INFO L471 AbstractCegarLoop]: Abstraction has 239 states and 294 transitions. [2025-03-16 17:35:29,209 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 11 states have (on average 2.090909090909091) internal successors, (23), 7 states have internal predecessors, (23), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2025-03-16 17:35:29,210 INFO L276 IsEmpty]: Start isEmpty. Operand 239 states and 294 transitions. [2025-03-16 17:35:29,210 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2025-03-16 17:35:29,211 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 17:35:29,211 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 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-16 17:35:29,211 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4 [2025-03-16 17:35:29,211 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting failErr0ASSERT_VIOLATIONERROR_FUNCTION === [failErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 17:35:29,212 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 17:35:29,212 INFO L85 PathProgramCache]: Analyzing trace with hash -716255134, now seen corresponding path program 1 times [2025-03-16 17:35:29,212 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 17:35:29,212 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1967371522] [2025-03-16 17:35:29,212 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 17:35:29,212 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 17:35:29,236 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 30 statements into 1 equivalence classes. [2025-03-16 17:35:29,250 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 30 of 30 statements. [2025-03-16 17:35:29,250 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 17:35:29,250 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 17:35:29,891 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-16 17:35:29,892 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 17:35:29,892 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1967371522] [2025-03-16 17:35:29,892 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1967371522] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-16 17:35:29,893 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-16 17:35:29,893 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [13] imperfect sequences [] total 13 [2025-03-16 17:35:29,893 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [788902248] [2025-03-16 17:35:29,893 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-16 17:35:29,893 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2025-03-16 17:35:29,893 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 17:35:29,894 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2025-03-16 17:35:29,894 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=29, Invalid=153, Unknown=0, NotChecked=0, Total=182 [2025-03-16 17:35:29,894 INFO L87 Difference]: Start difference. First operand 239 states and 294 transitions. Second operand has 14 states, 14 states have (on average 1.8571428571428572) internal successors, (26), 10 states have internal predecessors, (26), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2025-03-16 17:35:30,975 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 17:35:30,979 INFO L93 Difference]: Finished difference Result 258 states and 311 transitions. [2025-03-16 17:35:30,979 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2025-03-16 17:35:30,979 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 1.8571428571428572) internal successors, (26), 10 states have internal predecessors, (26), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 30 [2025-03-16 17:35:30,979 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 17:35:30,981 INFO L225 Difference]: With dead ends: 258 [2025-03-16 17:35:30,981 INFO L226 Difference]: Without dead ends: 255 [2025-03-16 17:35:30,981 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 22 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 36 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=89, Invalid=373, Unknown=0, NotChecked=0, Total=462 [2025-03-16 17:35:30,982 INFO L435 NwaCegarLoop]: 24 mSDtfsCounter, 340 mSDsluCounter, 205 mSDsCounter, 0 mSdLazyCounter, 1235 mSolverCounterSat, 35 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 343 SdHoareTripleChecker+Valid, 229 SdHoareTripleChecker+Invalid, 1270 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 35 IncrementalHoareTripleChecker+Valid, 1235 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.9s IncrementalHoareTripleChecker+Time [2025-03-16 17:35:30,982 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [343 Valid, 229 Invalid, 1270 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [35 Valid, 1235 Invalid, 0 Unknown, 0 Unchecked, 0.9s Time] [2025-03-16 17:35:30,983 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 255 states. [2025-03-16 17:35:31,009 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 255 to 239. [2025-03-16 17:35:31,010 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 239 states, 204 states have (on average 1.2450980392156863) internal successors, (254), 219 states have internal predecessors, (254), 28 states have call successors, (28), 8 states have call predecessors, (28), 6 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2025-03-16 17:35:31,011 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 239 states to 239 states and 293 transitions. [2025-03-16 17:35:31,011 INFO L78 Accepts]: Start accepts. Automaton has 239 states and 293 transitions. Word has length 30 [2025-03-16 17:35:31,012 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 17:35:31,012 INFO L471 AbstractCegarLoop]: Abstraction has 239 states and 293 transitions. [2025-03-16 17:35:31,012 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 1.8571428571428572) internal successors, (26), 10 states have internal predecessors, (26), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2025-03-16 17:35:31,012 INFO L276 IsEmpty]: Start isEmpty. Operand 239 states and 293 transitions. [2025-03-16 17:35:31,012 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2025-03-16 17:35:31,012 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 17:35:31,013 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 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-16 17:35:31,013 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5 [2025-03-16 17:35:31,013 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting failErr0ASSERT_VIOLATIONERROR_FUNCTION === [failErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 17:35:31,013 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 17:35:31,013 INFO L85 PathProgramCache]: Analyzing trace with hash -628644655, now seen corresponding path program 1 times [2025-03-16 17:35:31,013 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 17:35:31,013 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [724066777] [2025-03-16 17:35:31,014 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 17:35:31,014 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 17:35:31,024 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 33 statements into 1 equivalence classes. [2025-03-16 17:35:31,046 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 33 of 33 statements. [2025-03-16 17:35:31,047 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 17:35:31,047 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 17:35:31,708 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-16 17:35:31,709 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 17:35:31,709 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [724066777] [2025-03-16 17:35:31,710 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [724066777] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-16 17:35:31,710 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-16 17:35:31,710 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [13] imperfect sequences [] total 13 [2025-03-16 17:35:31,710 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2126369924] [2025-03-16 17:35:31,710 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-16 17:35:31,710 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2025-03-16 17:35:31,710 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 17:35:31,711 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2025-03-16 17:35:31,711 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=28, Invalid=154, Unknown=0, NotChecked=0, Total=182 [2025-03-16 17:35:31,711 INFO L87 Difference]: Start difference. First operand 239 states and 293 transitions. Second operand has 14 states, 14 states have (on average 2.0714285714285716) internal successors, (29), 10 states have internal predecessors, (29), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2025-03-16 17:35:32,564 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 17:35:32,565 INFO L93 Difference]: Finished difference Result 257 states and 309 transitions. [2025-03-16 17:35:32,565 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2025-03-16 17:35:32,565 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 2.0714285714285716) internal successors, (29), 10 states have internal predecessors, (29), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 33 [2025-03-16 17:35:32,565 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 17:35:32,567 INFO L225 Difference]: With dead ends: 257 [2025-03-16 17:35:32,567 INFO L226 Difference]: Without dead ends: 254 [2025-03-16 17:35:32,567 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 22 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 34 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=84, Invalid=378, Unknown=0, NotChecked=0, Total=462 [2025-03-16 17:35:32,568 INFO L435 NwaCegarLoop]: 24 mSDtfsCounter, 333 mSDsluCounter, 169 mSDsCounter, 0 mSdLazyCounter, 1033 mSolverCounterSat, 33 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 336 SdHoareTripleChecker+Valid, 193 SdHoareTripleChecker+Invalid, 1066 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 33 IncrementalHoareTripleChecker+Valid, 1033 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2025-03-16 17:35:32,568 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [336 Valid, 193 Invalid, 1066 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [33 Valid, 1033 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2025-03-16 17:35:32,568 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 254 states. [2025-03-16 17:35:32,588 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 254 to 239. [2025-03-16 17:35:32,588 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 239 states, 204 states have (on average 1.2401960784313726) internal successors, (253), 219 states have internal predecessors, (253), 28 states have call successors, (28), 8 states have call predecessors, (28), 6 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2025-03-16 17:35:32,589 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 239 states to 239 states and 292 transitions. [2025-03-16 17:35:32,590 INFO L78 Accepts]: Start accepts. Automaton has 239 states and 292 transitions. Word has length 33 [2025-03-16 17:35:32,590 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 17:35:32,590 INFO L471 AbstractCegarLoop]: Abstraction has 239 states and 292 transitions. [2025-03-16 17:35:32,590 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 2.0714285714285716) internal successors, (29), 10 states have internal predecessors, (29), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2025-03-16 17:35:32,590 INFO L276 IsEmpty]: Start isEmpty. Operand 239 states and 292 transitions. [2025-03-16 17:35:32,591 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2025-03-16 17:35:32,591 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 17:35:32,591 INFO L218 NwaCegarLoop]: trace histogram [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] [2025-03-16 17:35:32,591 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6 [2025-03-16 17:35:32,591 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting failErr0ASSERT_VIOLATIONERROR_FUNCTION === [failErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 17:35:32,592 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 17:35:32,592 INFO L85 PathProgramCache]: Analyzing trace with hash 289122518, now seen corresponding path program 1 times [2025-03-16 17:35:32,592 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 17:35:32,592 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1579757597] [2025-03-16 17:35:32,592 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 17:35:32,592 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 17:35:32,609 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 35 statements into 1 equivalence classes. [2025-03-16 17:35:32,644 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 35 of 35 statements. [2025-03-16 17:35:32,644 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 17:35:32,645 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 17:35:33,498 INFO L134 CoverageAnalysis]: Checked inductivity of 11 backedges. 0 proven. 11 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-16 17:35:33,498 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 17:35:33,498 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1579757597] [2025-03-16 17:35:33,498 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1579757597] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 17:35:33,498 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [856270859] [2025-03-16 17:35:33,498 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 17:35:33,499 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 17:35:33,499 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 17:35:33,501 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-16 17:35:33,504 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-16 17:35:33,582 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 35 statements into 1 equivalence classes. [2025-03-16 17:35:33,620 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 35 of 35 statements. [2025-03-16 17:35:33,621 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 17:35:33,621 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 17:35:33,624 INFO L256 TraceCheckSpWp]: Trace formula consists of 295 conjuncts, 70 conjuncts are in the unsatisfiable core [2025-03-16 17:35:33,631 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 17:35:33,704 INFO L349 Elim1Store]: treesize reduction 20, result has 33.3 percent of original size [2025-03-16 17:35:33,705 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 19 treesize of output 16 [2025-03-16 17:35:33,783 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 16 treesize of output 11 [2025-03-16 17:35:33,788 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 16 treesize of output 11 [2025-03-16 17:35:34,046 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 22 treesize of output 25 [2025-03-16 17:35:34,088 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 9 treesize of output 12 [2025-03-16 17:35:34,106 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 9 treesize of output 12 [2025-03-16 17:35:34,176 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 27 treesize of output 17 [2025-03-16 17:35:34,179 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 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 17 treesize of output 18 [2025-03-16 17:35:34,222 INFO L349 Elim1Store]: treesize reduction 19, result has 20.8 percent of original size [2025-03-16 17:35:34,223 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 2 new quantified variables, introduced 1 case distinctions, treesize of input 36 treesize of output 33 [2025-03-16 17:35:34,283 INFO L349 Elim1Store]: treesize reduction 4, result has 50.0 percent of original size [2025-03-16 17:35:34,284 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-16 17:35:34,320 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 28 treesize of output 19 [2025-03-16 17:35:34,412 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-16 17:35:34,435 INFO L349 Elim1Store]: treesize reduction 66, result has 22.4 percent of original size [2025-03-16 17:35:34,435 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 2 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 4 new quantified variables, introduced 2 case distinctions, treesize of input 86 treesize of output 113 [2025-03-16 17:35:34,456 INFO L349 Elim1Store]: treesize reduction 17, result has 37.0 percent of original size [2025-03-16 17:35:34,456 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 2 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 55 treesize of output 35 [2025-03-16 17:35:34,460 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 60 treesize of output 41 [2025-03-16 17:35:34,503 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 17 treesize of output 12 [2025-03-16 17:35:34,617 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 16 treesize of output 8 [2025-03-16 17:35:34,640 INFO L134 CoverageAnalysis]: Checked inductivity of 11 backedges. 0 proven. 11 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-16 17:35:34,640 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 17:35:34,702 WARN L851 $PredicateComparison]: unable to prove that (forall ((v_ArrVal_395 (Array Int Int))) (not (= (select (select (store |c_#memory_$Pointer$#1.base| |c_ULTIMATE.start_gl_insert_~node~1#1.base| v_ArrVal_395) |c_~#gl_list~0.base|) (+ |c_~#gl_list~0.offset| 4)) |c_~#gl_list~0.base|))) is different from false [2025-03-16 17:35:34,737 WARN L851 $PredicateComparison]: unable to prove that (forall ((v_ArrVal_403 (Array Int Int)) (v_ArrVal_405 (Array Int Int)) (v_ArrVal_395 (Array Int Int)) (v_ArrVal_404 Int)) (not (= (select (select (store (let ((.cse0 (store |c_#memory_$Pointer$#1.base| (select (select |c_#memory_$Pointer$#1.base| |c_~#gl_list~0.base|) |c_~#gl_list~0.offset|) v_ArrVal_403))) (store .cse0 |c_~#gl_list~0.base| (store (select (store .cse0 |c_ULTIMATE.start_gl_insert_~node~1#1.base| v_ArrVal_405) |c_~#gl_list~0.base|) |c_~#gl_list~0.offset| v_ArrVal_404))) |c_ULTIMATE.start_gl_insert_~node~1#1.base| v_ArrVal_395) |c_~#gl_list~0.base|) (+ |c_~#gl_list~0.offset| 4)) |c_~#gl_list~0.base|))) is different from false [2025-03-16 17:35:34,739 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [856270859] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 17:35:34,739 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-16 17:35:34,739 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 16] total 29 [2025-03-16 17:35:34,739 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [26855465] [2025-03-16 17:35:34,739 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-16 17:35:34,739 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 30 states [2025-03-16 17:35:34,739 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 17:35:34,740 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 30 interpolants. [2025-03-16 17:35:34,740 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=108, Invalid=876, Unknown=16, NotChecked=122, Total=1122 [2025-03-16 17:35:34,740 INFO L87 Difference]: Start difference. First operand 239 states and 292 transitions. Second operand has 30 states, 29 states have (on average 1.9310344827586208) internal successors, (56), 19 states have internal predecessors, (56), 7 states have call successors, (7), 7 states have call predecessors, (7), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2025-03-16 17:35:37,241 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 17:35:37,242 INFO L93 Difference]: Finished difference Result 278 states and 327 transitions. [2025-03-16 17:35:37,243 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2025-03-16 17:35:37,243 INFO L78 Accepts]: Start accepts. Automaton has has 30 states, 29 states have (on average 1.9310344827586208) internal successors, (56), 19 states have internal predecessors, (56), 7 states have call successors, (7), 7 states have call predecessors, (7), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) Word has length 35 [2025-03-16 17:35:37,243 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 17:35:37,245 INFO L225 Difference]: With dead ends: 278 [2025-03-16 17:35:37,245 INFO L226 Difference]: Without dead ends: 275 [2025-03-16 17:35:37,246 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 90 GetRequests, 38 SyntacticMatches, 0 SemanticMatches, 52 ConstructedPredicates, 2 IntricatePredicates, 0 DeprecatedPredicates, 511 ImplicationChecksByTransitivity, 1.4s TimeCoverageRelationStatistics Valid=369, Invalid=2258, Unknown=33, NotChecked=202, Total=2862 [2025-03-16 17:35:37,247 INFO L435 NwaCegarLoop]: 23 mSDtfsCounter, 1000 mSDsluCounter, 294 mSDsCounter, 0 mSdLazyCounter, 2177 mSolverCounterSat, 194 mSolverCounterUnsat, 218 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1000 SdHoareTripleChecker+Valid, 317 SdHoareTripleChecker+Invalid, 2589 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 194 IncrementalHoareTripleChecker+Valid, 2177 IncrementalHoareTripleChecker+Invalid, 218 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.7s IncrementalHoareTripleChecker+Time [2025-03-16 17:35:37,247 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [1000 Valid, 317 Invalid, 2589 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [194 Valid, 2177 Invalid, 218 Unknown, 0 Unchecked, 1.7s Time] [2025-03-16 17:35:37,249 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 275 states. [2025-03-16 17:35:37,279 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 275 to 249. [2025-03-16 17:35:37,280 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 249 states, 211 states have (on average 1.2274881516587677) internal successors, (259), 227 states have internal predecessors, (259), 29 states have call successors, (29), 10 states have call predecessors, (29), 8 states have return successors, (12), 11 states have call predecessors, (12), 12 states have call successors, (12) [2025-03-16 17:35:37,281 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 249 states to 249 states and 300 transitions. [2025-03-16 17:35:37,282 INFO L78 Accepts]: Start accepts. Automaton has 249 states and 300 transitions. Word has length 35 [2025-03-16 17:35:37,282 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 17:35:37,282 INFO L471 AbstractCegarLoop]: Abstraction has 249 states and 300 transitions. [2025-03-16 17:35:37,282 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 30 states, 29 states have (on average 1.9310344827586208) internal successors, (56), 19 states have internal predecessors, (56), 7 states have call successors, (7), 7 states have call predecessors, (7), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2025-03-16 17:35:37,282 INFO L276 IsEmpty]: Start isEmpty. Operand 249 states and 300 transitions. [2025-03-16 17:35:37,283 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2025-03-16 17:35:37,283 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 17:35:37,283 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 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-16 17:35:37,290 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-16 17:35:37,487 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 17:35:37,487 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting failErr0ASSERT_VIOLATIONERROR_FUNCTION === [failErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 17:35:37,487 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 17:35:37,488 INFO L85 PathProgramCache]: Analyzing trace with hash -1969783874, now seen corresponding path program 1 times [2025-03-16 17:35:37,488 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 17:35:37,488 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [885883610] [2025-03-16 17:35:37,488 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 17:35:37,488 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 17:35:37,500 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 36 statements into 1 equivalence classes. [2025-03-16 17:35:37,512 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 36 of 36 statements. [2025-03-16 17:35:37,513 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 17:35:37,513 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 17:35:37,931 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-16 17:35:37,932 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 17:35:37,932 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [885883610] [2025-03-16 17:35:37,932 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [885883610] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-16 17:35:37,932 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-16 17:35:37,932 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [11] imperfect sequences [] total 11 [2025-03-16 17:35:37,932 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1850117011] [2025-03-16 17:35:37,932 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-16 17:35:37,933 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2025-03-16 17:35:37,933 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 17:35:37,933 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2025-03-16 17:35:37,933 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=22, Invalid=110, Unknown=0, NotChecked=0, Total=132 [2025-03-16 17:35:37,933 INFO L87 Difference]: Start difference. First operand 249 states and 300 transitions. Second operand has 12 states, 12 states have (on average 2.6666666666666665) internal successors, (32), 8 states have internal predecessors, (32), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2025-03-16 17:35:38,768 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 17:35:38,768 INFO L93 Difference]: Finished difference Result 263 states and 312 transitions. [2025-03-16 17:35:38,769 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2025-03-16 17:35:38,769 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 2.6666666666666665) internal successors, (32), 8 states have internal predecessors, (32), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 36 [2025-03-16 17:35:38,769 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 17:35:38,770 INFO L225 Difference]: With dead ends: 263 [2025-03-16 17:35:38,770 INFO L226 Difference]: Without dead ends: 260 [2025-03-16 17:35:38,771 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 25 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 65 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=105, Invalid=447, Unknown=0, NotChecked=0, Total=552 [2025-03-16 17:35:38,771 INFO L435 NwaCegarLoop]: 22 mSDtfsCounter, 401 mSDsluCounter, 162 mSDsCounter, 0 mSdLazyCounter, 965 mSolverCounterSat, 49 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 404 SdHoareTripleChecker+Valid, 184 SdHoareTripleChecker+Invalid, 1014 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 49 IncrementalHoareTripleChecker+Valid, 965 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2025-03-16 17:35:38,771 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [404 Valid, 184 Invalid, 1014 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [49 Valid, 965 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2025-03-16 17:35:38,772 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 260 states. [2025-03-16 17:35:38,802 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 260 to 249. [2025-03-16 17:35:38,802 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 249 states, 211 states have (on average 1.2227488151658767) internal successors, (258), 227 states have internal predecessors, (258), 29 states have call successors, (29), 10 states have call predecessors, (29), 8 states have return successors, (12), 11 states have call predecessors, (12), 12 states have call successors, (12) [2025-03-16 17:35:38,803 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 249 states to 249 states and 299 transitions. [2025-03-16 17:35:38,804 INFO L78 Accepts]: Start accepts. Automaton has 249 states and 299 transitions. Word has length 36 [2025-03-16 17:35:38,804 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 17:35:38,804 INFO L471 AbstractCegarLoop]: Abstraction has 249 states and 299 transitions. [2025-03-16 17:35:38,804 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 2.6666666666666665) internal successors, (32), 8 states have internal predecessors, (32), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2025-03-16 17:35:38,804 INFO L276 IsEmpty]: Start isEmpty. Operand 249 states and 299 transitions. [2025-03-16 17:35:38,804 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2025-03-16 17:35:38,804 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 17:35:38,805 INFO L218 NwaCegarLoop]: trace histogram [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] [2025-03-16 17:35:38,805 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8 [2025-03-16 17:35:38,805 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting failErr0ASSERT_VIOLATIONERROR_FUNCTION === [failErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 17:35:38,805 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 17:35:38,805 INFO L85 PathProgramCache]: Analyzing trace with hash 1779726722, now seen corresponding path program 1 times [2025-03-16 17:35:38,805 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 17:35:38,805 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2128149700] [2025-03-16 17:35:38,805 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 17:35:38,805 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 17:35:38,819 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 38 statements into 1 equivalence classes. [2025-03-16 17:35:38,841 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 38 of 38 statements. [2025-03-16 17:35:38,842 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 17:35:38,842 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 17:35:39,506 INFO L134 CoverageAnalysis]: Checked inductivity of 11 backedges. 0 proven. 11 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-16 17:35:39,506 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 17:35:39,506 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2128149700] [2025-03-16 17:35:39,507 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2128149700] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 17:35:39,507 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [788265387] [2025-03-16 17:35:39,507 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 17:35:39,507 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 17:35:39,507 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 17:35:39,509 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-16 17:35:39,510 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-16 17:35:39,584 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 38 statements into 1 equivalence classes. [2025-03-16 17:35:39,616 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 38 of 38 statements. [2025-03-16 17:35:39,616 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 17:35:39,616 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 17:35:39,618 INFO L256 TraceCheckSpWp]: Trace formula consists of 301 conjuncts, 80 conjuncts are in the unsatisfiable core [2025-03-16 17:35:39,625 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 17:35:39,657 INFO L349 Elim1Store]: treesize reduction 18, result has 35.7 percent of original size [2025-03-16 17:35:39,657 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 17 treesize of output 21 [2025-03-16 17:35:39,720 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 16 treesize of output 11 [2025-03-16 17:35:39,731 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 16 treesize of output 11 [2025-03-16 17:35:41,214 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 3 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 3 new quantified variables, introduced 0 case distinctions, treesize of input 137 treesize of output 125 [2025-03-16 17:35:41,228 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 2 new quantified variables, introduced 0 case distinctions, treesize of input 154 treesize of output 138 [2025-03-16 17:35:41,250 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 2 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 61 treesize of output 58 [2025-03-16 17:35:41,256 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 2 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 3 new quantified variables, introduced 0 case distinctions, treesize of input 53 treesize of output 56 [2025-03-16 17:35:41,263 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 21 treesize of output 25 [2025-03-16 17:35:41,267 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 56 treesize of output 35 [2025-03-16 17:35:41,272 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 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 17 treesize of output 18 [2025-03-16 17:35:41,280 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 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 21 treesize of output 7 [2025-03-16 17:35:41,391 INFO L349 Elim1Store]: treesize reduction 32, result has 30.4 percent of original size [2025-03-16 17:35:41,391 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 311 treesize of output 198 [2025-03-16 17:35:41,397 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 18 treesize of output 3 [2025-03-16 17:35:41,412 INFO L349 Elim1Store]: treesize reduction 19, result has 20.8 percent of original size [2025-03-16 17:35:41,412 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 2 new quantified variables, introduced 1 case distinctions, treesize of input 45 treesize of output 40 [2025-03-16 17:35:41,562 INFO L349 Elim1Store]: treesize reduction 24, result has 41.5 percent of original size [2025-03-16 17:35:41,562 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 4 select indices, 4 select index equivalence classes, 2 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 4 case distinctions, treesize of input 25 treesize of output 29 [2025-03-16 17:35:41,664 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 27 treesize of output 18 [2025-03-16 17:35:41,672 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 36 treesize of output 25 [2025-03-16 17:35:41,771 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-16 17:35:41,772 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-16 17:35:41,773 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-16 17:35:41,774 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 1 new quantified variables, introduced 0 case distinctions, treesize of input 44 treesize of output 39 [2025-03-16 17:35:41,777 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 25 treesize of output 14 [2025-03-16 17:35:41,783 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 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 28 treesize of output 12 [2025-03-16 17:35:41,821 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 16 treesize of output 11 [2025-03-16 17:35:41,967 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 15 treesize of output 7 [2025-03-16 17:35:41,991 INFO L134 CoverageAnalysis]: Checked inductivity of 11 backedges. 0 proven. 11 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-16 17:35:41,991 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 17:35:42,112 WARN L851 $PredicateComparison]: unable to prove that (forall ((v_ArrVal_617 (Array Int Int))) (< 0 (select (select (store |c_#memory_$Pointer$#1.offset| |c_ULTIMATE.start_gl_insert_~node~1#1.base| v_ArrVal_617) |c_~#gl_list~0.base|) (+ |c_~#gl_list~0.offset| 4)))) is different from false [2025-03-16 17:35:42,169 WARN L851 $PredicateComparison]: unable to prove that (forall ((v_ArrVal_627 (Array Int Int)) (v_ArrVal_626 (Array Int Int)) (v_ArrVal_617 (Array Int Int)) (v_ArrVal_625 Int)) (< 0 (select (select (store (let ((.cse0 (store |c_#memory_$Pointer$#1.offset| (select (select |c_#memory_$Pointer$#1.base| |c_~#gl_list~0.base|) |c_~#gl_list~0.offset|) v_ArrVal_626))) (store .cse0 |c_~#gl_list~0.base| (store (select (store .cse0 |c_ULTIMATE.start_gl_insert_~node~1#1.base| v_ArrVal_627) |c_~#gl_list~0.base|) |c_~#gl_list~0.offset| v_ArrVal_625))) |c_ULTIMATE.start_gl_insert_~node~1#1.base| v_ArrVal_617) |c_~#gl_list~0.base|) (+ |c_~#gl_list~0.offset| 4)))) is different from false [2025-03-16 17:35:42,170 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [788265387] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 17:35:42,171 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-16 17:35:42,171 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 15] total 28 [2025-03-16 17:35:42,171 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [617473171] [2025-03-16 17:35:42,171 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-16 17:35:42,171 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 29 states [2025-03-16 17:35:42,171 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 17:35:42,172 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 29 interpolants. [2025-03-16 17:35:42,172 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=105, Invalid=946, Unknown=13, NotChecked=126, Total=1190 [2025-03-16 17:35:42,172 INFO L87 Difference]: Start difference. First operand 249 states and 299 transitions. Second operand has 29 states, 29 states have (on average 2.1379310344827585) internal successors, (62), 18 states have internal predecessors, (62), 7 states have call successors, (7), 7 states have call predecessors, (7), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2025-03-16 17:35:46,267 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 17:35:46,267 INFO L93 Difference]: Finished difference Result 445 states and 527 transitions. [2025-03-16 17:35:46,269 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 31 states. [2025-03-16 17:35:46,269 INFO L78 Accepts]: Start accepts. Automaton has has 29 states, 29 states have (on average 2.1379310344827585) internal successors, (62), 18 states have internal predecessors, (62), 7 states have call successors, (7), 7 states have call predecessors, (7), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) Word has length 38 [2025-03-16 17:35:46,269 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 17:35:46,272 INFO L225 Difference]: With dead ends: 445 [2025-03-16 17:35:46,272 INFO L226 Difference]: Without dead ends: 442 [2025-03-16 17:35:46,274 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 101 GetRequests, 41 SyntacticMatches, 0 SemanticMatches, 60 ConstructedPredicates, 2 IntricatePredicates, 0 DeprecatedPredicates, 685 ImplicationChecksByTransitivity, 2.4s TimeCoverageRelationStatistics Valid=505, Invalid=3001, Unknown=42, NotChecked=234, Total=3782 [2025-03-16 17:35:46,275 INFO L435 NwaCegarLoop]: 23 mSDtfsCounter, 1667 mSDsluCounter, 326 mSDsCounter, 0 mSdLazyCounter, 2260 mSolverCounterSat, 255 mSolverCounterUnsat, 321 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1667 SdHoareTripleChecker+Valid, 349 SdHoareTripleChecker+Invalid, 2836 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 255 IncrementalHoareTripleChecker+Valid, 2260 IncrementalHoareTripleChecker+Invalid, 321 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.9s IncrementalHoareTripleChecker+Time [2025-03-16 17:35:46,275 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [1667 Valid, 349 Invalid, 2836 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [255 Valid, 2260 Invalid, 321 Unknown, 0 Unchecked, 2.9s Time] [2025-03-16 17:35:46,276 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 442 states. [2025-03-16 17:35:46,321 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 442 to 333. [2025-03-16 17:35:46,321 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 333 states, 287 states have (on average 1.2229965156794425) internal successors, (351), 303 states have internal predecessors, (351), 34 states have call successors, (34), 13 states have call predecessors, (34), 11 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2025-03-16 17:35:46,323 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 333 states to 333 states and 401 transitions. [2025-03-16 17:35:46,323 INFO L78 Accepts]: Start accepts. Automaton has 333 states and 401 transitions. Word has length 38 [2025-03-16 17:35:46,323 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 17:35:46,323 INFO L471 AbstractCegarLoop]: Abstraction has 333 states and 401 transitions. [2025-03-16 17:35:46,324 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 29 states, 29 states have (on average 2.1379310344827585) internal successors, (62), 18 states have internal predecessors, (62), 7 states have call successors, (7), 7 states have call predecessors, (7), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2025-03-16 17:35:46,324 INFO L276 IsEmpty]: Start isEmpty. Operand 333 states and 401 transitions. [2025-03-16 17:35:46,324 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 40 [2025-03-16 17:35:46,324 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 17:35:46,324 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 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-16 17:35:46,331 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-16 17:35:46,525 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,SelfDestructingSolverStorable9 [2025-03-16 17:35:46,525 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting failErr0ASSERT_VIOLATIONERROR_FUNCTION === [failErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 17:35:46,525 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 17:35:46,525 INFO L85 PathProgramCache]: Analyzing trace with hash 227634863, now seen corresponding path program 1 times [2025-03-16 17:35:46,525 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 17:35:46,525 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [481123734] [2025-03-16 17:35:46,525 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 17:35:46,525 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 17:35:46,534 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 39 statements into 1 equivalence classes. [2025-03-16 17:35:46,543 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 39 of 39 statements. [2025-03-16 17:35:46,543 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 17:35:46,543 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 17:35:47,083 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-16 17:35:47,084 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 17:35:47,084 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [481123734] [2025-03-16 17:35:47,084 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [481123734] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-16 17:35:47,084 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-16 17:35:47,084 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [12] imperfect sequences [] total 12 [2025-03-16 17:35:47,084 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1227184707] [2025-03-16 17:35:47,084 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-16 17:35:47,084 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2025-03-16 17:35:47,085 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 17:35:47,085 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2025-03-16 17:35:47,085 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=23, Invalid=133, Unknown=0, NotChecked=0, Total=156 [2025-03-16 17:35:47,085 INFO L87 Difference]: Start difference. First operand 333 states and 401 transitions. Second operand has 13 states, 13 states have (on average 2.6923076923076925) internal successors, (35), 9 states have internal predecessors, (35), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2025-03-16 17:35:48,005 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 17:35:48,005 INFO L93 Difference]: Finished difference Result 346 states and 412 transitions. [2025-03-16 17:35:48,008 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2025-03-16 17:35:48,008 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 2.6923076923076925) internal successors, (35), 9 states have internal predecessors, (35), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 39 [2025-03-16 17:35:48,009 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 17:35:48,010 INFO L225 Difference]: With dead ends: 346 [2025-03-16 17:35:48,010 INFO L226 Difference]: Without dead ends: 343 [2025-03-16 17:35:48,010 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 23 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 42 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=93, Invalid=413, Unknown=0, NotChecked=0, Total=506 [2025-03-16 17:35:48,011 INFO L435 NwaCegarLoop]: 24 mSDtfsCounter, 357 mSDsluCounter, 191 mSDsCounter, 0 mSdLazyCounter, 1150 mSolverCounterSat, 30 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 360 SdHoareTripleChecker+Valid, 215 SdHoareTripleChecker+Invalid, 1180 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 30 IncrementalHoareTripleChecker+Valid, 1150 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2025-03-16 17:35:48,011 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [360 Valid, 215 Invalid, 1180 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [30 Valid, 1150 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2025-03-16 17:35:48,011 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 343 states. [2025-03-16 17:35:48,051 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 343 to 333. [2025-03-16 17:35:48,052 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 333 states, 287 states have (on average 1.2195121951219512) internal successors, (350), 303 states have internal predecessors, (350), 34 states have call successors, (34), 13 states have call predecessors, (34), 11 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2025-03-16 17:35:48,053 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 333 states to 333 states and 400 transitions. [2025-03-16 17:35:48,053 INFO L78 Accepts]: Start accepts. Automaton has 333 states and 400 transitions. Word has length 39 [2025-03-16 17:35:48,054 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 17:35:48,055 INFO L471 AbstractCegarLoop]: Abstraction has 333 states and 400 transitions. [2025-03-16 17:35:48,055 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 2.6923076923076925) internal successors, (35), 9 states have internal predecessors, (35), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2025-03-16 17:35:48,055 INFO L276 IsEmpty]: Start isEmpty. Operand 333 states and 400 transitions. [2025-03-16 17:35:48,057 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 42 [2025-03-16 17:35:48,057 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 17:35:48,057 INFO L218 NwaCegarLoop]: trace histogram [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] [2025-03-16 17:35:48,058 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10 [2025-03-16 17:35:48,058 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting failErr0ASSERT_VIOLATIONERROR_FUNCTION === [failErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 17:35:48,058 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 17:35:48,058 INFO L85 PathProgramCache]: Analyzing trace with hash -1597135276, now seen corresponding path program 1 times [2025-03-16 17:35:48,058 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 17:35:48,058 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1731449084] [2025-03-16 17:35:48,058 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 17:35:48,058 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 17:35:48,072 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 41 statements into 1 equivalence classes. [2025-03-16 17:35:48,091 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 41 of 41 statements. [2025-03-16 17:35:48,091 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 17:35:48,092 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 17:35:49,158 INFO L134 CoverageAnalysis]: Checked inductivity of 11 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2025-03-16 17:35:49,158 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 17:35:49,158 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1731449084] [2025-03-16 17:35:49,158 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1731449084] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 17:35:49,158 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1597079940] [2025-03-16 17:35:49,158 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 17:35:49,158 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 17:35:49,159 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 17:35:49,160 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-16 17:35:49,161 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-16 17:35:49,248 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 41 statements into 1 equivalence classes. [2025-03-16 17:35:49,274 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 41 of 41 statements. [2025-03-16 17:35:49,274 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 17:35:49,274 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 17:35:49,277 INFO L256 TraceCheckSpWp]: Trace formula consists of 307 conjuncts, 111 conjuncts are in the unsatisfiable core [2025-03-16 17:35:49,282 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 17:35:49,301 INFO L349 Elim1Store]: treesize reduction 18, result has 35.7 percent of original size [2025-03-16 17:35:49,301 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 17 treesize of output 21 [2025-03-16 17:35:49,357 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 16 treesize of output 11 [2025-03-16 17:35:49,362 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 16 treesize of output 11 [2025-03-16 17:35:49,595 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 3 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 3 new quantified variables, introduced 0 case distinctions, treesize of input 65 treesize of output 61 [2025-03-16 17:35:49,600 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 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 14 treesize of output 18 [2025-03-16 17:35:49,603 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 2 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 3 new quantified variables, introduced 0 case distinctions, treesize of input 62 treesize of output 61 [2025-03-16 17:35:49,608 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 23 treesize of output 22 [2025-03-16 17:35:49,627 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 2 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 37 treesize of output 42 [2025-03-16 17:35:49,633 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 2 new quantified variables, introduced 0 case distinctions, treesize of input 41 treesize of output 43 [2025-03-16 17:35:49,717 INFO L349 Elim1Store]: treesize reduction 32, result has 13.5 percent of original size [2025-03-16 17:35:49,717 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 3 new quantified variables, introduced 2 case distinctions, treesize of input 233 treesize of output 164 [2025-03-16 17:35:49,722 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-16 17:35:49,724 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 25 treesize of output 12 [2025-03-16 17:35:49,727 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 21 [2025-03-16 17:35:49,735 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 31 treesize of output 29 [2025-03-16 17:35:49,743 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 27 treesize of output 18 [2025-03-16 17:35:49,882 INFO L349 Elim1Store]: treesize reduction 24, result has 41.5 percent of original size [2025-03-16 17:35:49,882 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 4 select indices, 4 select index equivalence classes, 2 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 4 case distinctions, treesize of input 25 treesize of output 29 [2025-03-16 17:35:49,970 INFO L349 Elim1Store]: treesize reduction 25, result has 16.7 percent of original size [2025-03-16 17:35:49,970 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 3 new quantified variables, introduced 2 case distinctions, treesize of input 58 treesize of output 45 [2025-03-16 17:35:49,981 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 23 treesize of output 16 [2025-03-16 17:35:50,708 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 22 treesize of output 25 [2025-03-16 17:35:50,738 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 9 treesize of output 12 [2025-03-16 17:35:50,767 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 9 treesize of output 12 [2025-03-16 17:35:50,893 INFO L349 Elim1Store]: treesize reduction 60, result has 10.4 percent of original size [2025-03-16 17:35:50,893 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 4 select indices, 4 select index equivalence classes, 4 disjoint index pairs (out of 6 index pairs), introduced 5 new quantified variables, introduced 8 case distinctions, treesize of input 244 treesize of output 64 [2025-03-16 17:35:50,901 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 2 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 60 treesize of output 64 [2025-03-16 17:35:50,904 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 2 new quantified variables, introduced 0 case distinctions, treesize of input 63 treesize of output 25 [2025-03-16 17:35:50,906 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 21 [2025-03-16 17:35:50,946 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 23 treesize of output 16 [2025-03-16 17:35:50,957 INFO L349 Elim1Store]: treesize reduction 25, result has 16.7 percent of original size [2025-03-16 17:35:50,957 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 3 new quantified variables, introduced 2 case distinctions, treesize of input 36 treesize of output 33 [2025-03-16 17:35:51,169 INFO L349 Elim1Store]: treesize reduction 22, result has 12.0 percent of original size [2025-03-16 17:35:51,170 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 4 new quantified variables, introduced 3 case distinctions, treesize of input 34 treesize of output 20 [2025-03-16 17:35:51,190 INFO L134 CoverageAnalysis]: Checked inductivity of 11 backedges. 0 proven. 11 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-16 17:35:51,190 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 17:35:51,231 WARN L851 $PredicateComparison]: unable to prove that (forall ((v_ArrVal_847 (Array Int Int)) (v_ArrVal_848 (Array Int Int))) (not (let ((.cse1 (store |c_#memory_$Pointer$#1.base| |c_ULTIMATE.start_gl_insert_~node~1#1.base| v_ArrVal_848)) (.cse2 (+ |c_~#gl_list~0.offset| 4))) (let ((.cse0 (select (select .cse1 |c_~#gl_list~0.base|) .cse2))) (= .cse0 (select (select .cse1 .cse0) (select (select (store |c_#memory_$Pointer$#1.offset| |c_ULTIMATE.start_gl_insert_~node~1#1.base| v_ArrVal_847) |c_~#gl_list~0.base|) .cse2))))))) is different from false [2025-03-16 17:35:51,339 WARN L851 $PredicateComparison]: unable to prove that (forall ((v_ArrVal_871 Int) (v_ArrVal_847 (Array Int Int)) (v_ArrVal_868 (Array Int Int)) (v_ArrVal_848 (Array Int Int)) (v_ArrVal_869 Int) (v_ArrVal_870 (Array Int Int)) (v_ArrVal_867 Int) (v_ArrVal_866 Int)) (not (let ((.cse4 (+ |c_ULTIMATE.start_gl_insert_~node~1#1.offset| 4)) (.cse2 (select (select |c_#memory_$Pointer$#1.base| |c_~#gl_list~0.base|) |c_~#gl_list~0.offset|)) (.cse3 (+ (select (select |c_#memory_$Pointer$#1.offset| |c_~#gl_list~0.base|) |c_~#gl_list~0.offset|) 4))) (let ((.cse0 (store (let ((.cse6 (store |c_#memory_$Pointer$#1.base| .cse2 (store (select |c_#memory_$Pointer$#1.base| .cse2) .cse3 v_ArrVal_869)))) (store .cse6 |c_~#gl_list~0.base| (store (select (store .cse6 |c_ULTIMATE.start_gl_insert_~node~1#1.base| (store (store (select .cse6 |c_ULTIMATE.start_gl_insert_~node~1#1.base|) .cse4 v_ArrVal_867) (+ |c_ULTIMATE.start_gl_insert_~node~1#1.offset| 8) v_ArrVal_871)) |c_~#gl_list~0.base|) |c_~#gl_list~0.offset| v_ArrVal_866))) |c_ULTIMATE.start_gl_insert_~node~1#1.base| v_ArrVal_848)) (.cse5 (+ |c_~#gl_list~0.offset| 4))) (let ((.cse1 (select (select .cse0 |c_~#gl_list~0.base|) .cse5))) (= (select (select .cse0 .cse1) (select (select (store (store (store |c_#memory_$Pointer$#1.offset| .cse2 v_ArrVal_868) |c_~#gl_list~0.base| (store (select (store (store |c_#memory_$Pointer$#1.offset| .cse2 (store (select |c_#memory_$Pointer$#1.offset| .cse2) .cse3 .cse4)) |c_ULTIMATE.start_gl_insert_~node~1#1.base| v_ArrVal_870) |c_~#gl_list~0.base|) |c_~#gl_list~0.offset| .cse4)) |c_ULTIMATE.start_gl_insert_~node~1#1.base| v_ArrVal_847) |c_~#gl_list~0.base|) .cse5)) .cse1)))))) is different from false [2025-03-16 17:35:51,341 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1597079940] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 17:35:51,341 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-16 17:35:51,341 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 17] total 30 [2025-03-16 17:35:51,341 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [505495367] [2025-03-16 17:35:51,341 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-16 17:35:51,341 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 31 states [2025-03-16 17:35:51,341 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 17:35:51,342 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 31 interpolants. [2025-03-16 17:35:51,342 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=116, Invalid=881, Unknown=3, NotChecked=122, Total=1122 [2025-03-16 17:35:51,342 INFO L87 Difference]: Start difference. First operand 333 states and 400 transitions. Second operand has 31 states, 30 states have (on average 2.2666666666666666) internal successors, (68), 21 states have internal predecessors, (68), 7 states have call successors, (7), 6 states have call predecessors, (7), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2025-03-16 17:35:53,867 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 17:35:53,867 INFO L93 Difference]: Finished difference Result 427 states and 507 transitions. [2025-03-16 17:35:53,867 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2025-03-16 17:35:53,868 INFO L78 Accepts]: Start accepts. Automaton has has 31 states, 30 states have (on average 2.2666666666666666) internal successors, (68), 21 states have internal predecessors, (68), 7 states have call successors, (7), 6 states have call predecessors, (7), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) Word has length 41 [2025-03-16 17:35:53,868 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 17:35:53,869 INFO L225 Difference]: With dead ends: 427 [2025-03-16 17:35:53,869 INFO L226 Difference]: Without dead ends: 424 [2025-03-16 17:35:53,870 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 96 GetRequests, 49 SyntacticMatches, 0 SemanticMatches, 47 ConstructedPredicates, 2 IntricatePredicates, 0 DeprecatedPredicates, 485 ImplicationChecksByTransitivity, 1.8s TimeCoverageRelationStatistics Valid=320, Invalid=1847, Unknown=3, NotChecked=182, Total=2352 [2025-03-16 17:35:53,870 INFO L435 NwaCegarLoop]: 25 mSDtfsCounter, 989 mSDsluCounter, 329 mSDsCounter, 0 mSdLazyCounter, 2366 mSolverCounterSat, 131 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 995 SdHoareTripleChecker+Valid, 354 SdHoareTripleChecker+Invalid, 2497 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 131 IncrementalHoareTripleChecker+Valid, 2366 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.8s IncrementalHoareTripleChecker+Time [2025-03-16 17:35:53,870 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [995 Valid, 354 Invalid, 2497 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [131 Valid, 2366 Invalid, 0 Unknown, 0 Unchecked, 1.8s Time] [2025-03-16 17:35:53,871 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 424 states. [2025-03-16 17:35:53,913 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 424 to 402. [2025-03-16 17:35:53,914 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 402 states, 350 states have (on average 1.22) internal successors, (427), 367 states have internal predecessors, (427), 38 states have call successors, (38), 15 states have call predecessors, (38), 13 states have return successors, (19), 19 states have call predecessors, (19), 19 states have call successors, (19) [2025-03-16 17:35:53,915 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 402 states to 402 states and 484 transitions. [2025-03-16 17:35:53,915 INFO L78 Accepts]: Start accepts. Automaton has 402 states and 484 transitions. Word has length 41 [2025-03-16 17:35:53,916 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 17:35:53,916 INFO L471 AbstractCegarLoop]: Abstraction has 402 states and 484 transitions. [2025-03-16 17:35:53,916 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 31 states, 30 states have (on average 2.2666666666666666) internal successors, (68), 21 states have internal predecessors, (68), 7 states have call successors, (7), 6 states have call predecessors, (7), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2025-03-16 17:35:53,916 INFO L276 IsEmpty]: Start isEmpty. Operand 402 states and 484 transitions. [2025-03-16 17:35:53,917 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 43 [2025-03-16 17:35:53,917 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 17:35:53,917 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 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-16 17:35:53,924 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-16 17:35:54,117 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 17:35:54,117 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting failErr0ASSERT_VIOLATIONERROR_FUNCTION === [failErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 17:35:54,118 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 17:35:54,118 INFO L85 PathProgramCache]: Analyzing trace with hash -367129733, now seen corresponding path program 1 times [2025-03-16 17:35:54,118 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 17:35:54,118 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [275625288] [2025-03-16 17:35:54,118 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 17:35:54,118 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 17:35:54,126 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 42 statements into 1 equivalence classes. [2025-03-16 17:35:54,135 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 42 of 42 statements. [2025-03-16 17:35:54,135 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 17:35:54,135 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-16 17:35:54,135 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-16 17:35:54,137 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 42 statements into 1 equivalence classes. [2025-03-16 17:35:54,145 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 42 of 42 statements. [2025-03-16 17:35:54,145 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 17:35:54,145 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-16 17:35:54,164 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-16 17:35:54,165 INFO L340 BasicCegarLoop]: Counterexample is feasible [2025-03-16 17:35:54,165 INFO L782 garLoopResultBuilder]: Registering result UNSAFE for location failErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2025-03-16 17:35:54,168 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable12 [2025-03-16 17:35:54,170 INFO L422 BasicCegarLoop]: Path program histogram: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 17:35:54,197 INFO L170 ceAbstractionStarter]: Computing trace abstraction results [2025-03-16 17:35:54,200 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 16.03 05:35:54 BoogieIcfgContainer [2025-03-16 17:35:54,201 INFO L131 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2025-03-16 17:35:54,202 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2025-03-16 17:35:54,202 INFO L270 PluginConnector]: Initializing Witness Printer... [2025-03-16 17:35:54,202 INFO L274 PluginConnector]: Witness Printer initialized [2025-03-16 17:35:54,202 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 16.03 05:35:24" (3/4) ... [2025-03-16 17:35:54,203 INFO L140 WitnessPrinter]: Generating witness for reachability counterexample [2025-03-16 17:35:54,247 INFO L127 tionWitnessGenerator]: Generated YAML witness of length 39. [2025-03-16 17:35:54,304 INFO L149 WitnessManager]: Wrote witness to /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/witness.graphml [2025-03-16 17:35:54,304 INFO L149 WitnessManager]: Wrote witness to /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/witness.yml [2025-03-16 17:35:54,304 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2025-03-16 17:35:54,305 INFO L158 Benchmark]: Toolchain (without parser) took 30770.79ms. Allocated memory was 142.6MB in the beginning and 570.4MB in the end (delta: 427.8MB). Free memory was 104.7MB in the beginning and 522.0MB in the end (delta: -417.3MB). Peak memory consumption was 334.2MB. Max. memory is 16.1GB. [2025-03-16 17:35:54,305 INFO L158 Benchmark]: CDTParser took 0.25ms. Allocated memory is still 201.3MB. Free memory is still 116.0MB. There was no memory consumed. Max. memory is 16.1GB. [2025-03-16 17:35:54,305 INFO L158 Benchmark]: CACSL2BoogieTranslator took 380.79ms. Allocated memory is still 142.6MB. Free memory was 103.9MB in the beginning and 77.2MB in the end (delta: 26.7MB). Peak memory consumption was 16.8MB. Max. memory is 16.1GB. [2025-03-16 17:35:54,306 INFO L158 Benchmark]: Boogie Procedure Inliner took 31.92ms. Allocated memory is still 142.6MB. Free memory was 77.2MB in the beginning and 75.7MB in the end (delta: 1.5MB). There was no memory consumed. Max. memory is 16.1GB. [2025-03-16 17:35:54,306 INFO L158 Benchmark]: Boogie Preprocessor took 44.17ms. Allocated memory is still 142.6MB. Free memory was 75.7MB in the beginning and 71.8MB in the end (delta: 3.8MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2025-03-16 17:35:54,306 INFO L158 Benchmark]: IcfgBuilder took 528.64ms. Allocated memory is still 142.6MB. Free memory was 71.8MB in the beginning and 46.7MB in the end (delta: 25.2MB). Peak memory consumption was 25.2MB. Max. memory is 16.1GB. [2025-03-16 17:35:54,306 INFO L158 Benchmark]: TraceAbstraction took 29678.20ms. Allocated memory was 142.6MB in the beginning and 570.4MB in the end (delta: 427.8MB). Free memory was 45.9MB in the beginning and 202.8MB in the end (delta: -156.9MB). Peak memory consumption was 275.4MB. Max. memory is 16.1GB. [2025-03-16 17:35:54,306 INFO L158 Benchmark]: Witness Printer took 102.53ms. Allocated memory is still 570.4MB. Free memory was 202.8MB in the beginning and 522.0MB in the end (delta: -319.2MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2025-03-16 17:35:54,308 INFO L338 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.25ms. Allocated memory is still 201.3MB. Free memory is still 116.0MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 380.79ms. Allocated memory is still 142.6MB. Free memory was 103.9MB in the beginning and 77.2MB in the end (delta: 26.7MB). Peak memory consumption was 16.8MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 31.92ms. Allocated memory is still 142.6MB. Free memory was 77.2MB in the beginning and 75.7MB in the end (delta: 1.5MB). There was no memory consumed. Max. memory is 16.1GB. * Boogie Preprocessor took 44.17ms. Allocated memory is still 142.6MB. Free memory was 75.7MB in the beginning and 71.8MB in the end (delta: 3.8MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * IcfgBuilder took 528.64ms. Allocated memory is still 142.6MB. Free memory was 71.8MB in the beginning and 46.7MB in the end (delta: 25.2MB). Peak memory consumption was 25.2MB. Max. memory is 16.1GB. * TraceAbstraction took 29678.20ms. Allocated memory was 142.6MB in the beginning and 570.4MB in the end (delta: 427.8MB). Free memory was 45.9MB in the beginning and 202.8MB in the end (delta: -156.9MB). Peak memory consumption was 275.4MB. Max. memory is 16.1GB. * Witness Printer took 102.53ms. Allocated memory is still 570.4MB. Free memory was 202.8MB in the beginning and 522.0MB in the end (delta: -319.2MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: ErrorAutomatonStatistics NumberErrorTraces: 0, NumberStatementsAllTraces: 0, NumberRelevantStatements: 0, 0.0s ErrorAutomatonConstructionTimeTotal, 0.0s FaulLocalizationTime, NumberStatementsFirstTrace: -1, TraceLengthAvg: 0, 0.0s ErrorAutomatonConstructionTimeAvg, 0.0s ErrorAutomatonDifferenceTimeAvg, 0.0s ErrorAutomatonDifferenceTimeTotal, NumberOfNoEnhancement: 0, NumberOfFiniteEnhancement: 0, NumberOfInfiniteEnhancement: 0 - CounterExampleResult [Line: 840]: a call to reach_error is reachable a call to reach_error is reachable We found a FailurePath: [L850] struct list_head gl_list = { &(gl_list), &(gl_list) }; [L850] struct list_head gl_list = { &(gl_list), &(gl_list) }; [L850] struct list_head gl_list = { &(gl_list), &(gl_list) }; [L949] CALL gl_read() [L911] COND TRUE __VERIFIER_nondet_int() [L909] CALL gl_insert(__VERIFIER_nondet_int()) [L899] struct node *node = malloc(sizeof *node); [L900] COND FALSE !(!node) VAL [gl_list={3:0}, node={5:0}, value=-1] [L902] node->value = value VAL [gl_list={3:0}] [L903] CALL list_add(&node->linkage, &gl_list) VAL [gl_list={3:0}] [L890] EXPR head->next [L890] CALL __list_add(new, head, head->next) [L878] next->prev = new [L879] new->next = next [L880] new->prev = prev [L881] prev->next = new [L890] RET __list_add(new, head, head->next) [L903] RET list_add(&node->linkage, &gl_list) VAL [gl_list={3:0}, node={5:0}] [L904] COND TRUE 0 [L904] (&node->nested)->next = (&node->nested) [L904] (&node->nested)->next = (&node->nested) VAL [gl_list={3:0}] [L904] COND FALSE !(0) VAL [gl_list={3:0}, node={5:0}] [L909] RET gl_insert(__VERIFIER_nondet_int()) [L911] COND FALSE !(__VERIFIER_nondet_int()) [L949] RET gl_read() [L950] CALL inspect(&gl_list) VAL [\old(head)={3:0}, gl_list={3:0}] [L853] COND FALSE !(!(head)) VAL [\old(head)={3:0}, gl_list={3:0}, head={3:0}] [L853] COND FALSE !(0) VAL [\old(head)={3:0}, gl_list={3:0}, head={3:0}] [L854] COND TRUE 0 [L854] EXPR head->next VAL [\old(head)={3:0}, gl_list={3:0}, head={3:0}] [L854] COND FALSE !(!(head->next != head)) [L854] COND FALSE !(0) VAL [\old(head)={3:0}, gl_list={3:0}, head={3:0}] [L855] COND TRUE 0 [L855] EXPR head->prev VAL [\old(head)={3:0}, gl_list={3:0}, head={3:0}] [L855] COND FALSE !(!(head->prev != head)) [L855] COND FALSE !(0) VAL [\old(head)={3:0}, gl_list={3:0}, head={3:0}] [L856] EXPR head->prev [L856] head = head->prev [L857] COND FALSE !(!(head)) VAL [\old(head)={3:0}, gl_list={3:0}, head={5:4}] [L857] COND FALSE !(0) VAL [\old(head)={3:0}, gl_list={3:0}, head={5:4}] [L858] COND TRUE 0 [L858] EXPR head->next VAL [\old(head)={3:0}, gl_list={3:0}, head={5:4}] [L858] COND FALSE !(!(head->next != head)) [L858] COND FALSE !(0) VAL [\old(head)={3:0}, gl_list={3:0}, head={5:4}] [L859] COND TRUE 0 [L859] EXPR head->prev VAL [\old(head)={3:0}, gl_list={3:0}, head={5:4}] [L859] COND FALSE !(!(head->prev != head)) [L859] COND FALSE !(0) VAL [\old(head)={3:0}, gl_list={3:0}, head={5:4}] [L860] const struct node *node = ((struct node *)((char *)(head)-(unsigned long)(&((struct node *)0)->linkage))); VAL [\old(head)={3:0}, gl_list={3:0}, head={5:4}, node={5:0}] [L861] COND FALSE !(!(node)) VAL [\old(head)={3:0}, gl_list={3:0}, head={5:4}, node={5:0}] [L861] COND FALSE !(0) VAL [\old(head)={3:0}, gl_list={3:0}, head={5:4}, node={5:0}] [L862] COND TRUE 0 [L862] EXPR node->nested.next VAL [\old(head)={3:0}, gl_list={3:0}, head={5:4}, node={5:0}] [L862] COND FALSE !(!(node->nested.next == &node->nested)) [L862] COND FALSE !(0) VAL [\old(head)={3:0}, gl_list={3:0}, head={5:4}, node={5:0}] [L863] COND TRUE 0 [L863] EXPR node->nested.prev VAL [\old(head)={3:0}, gl_list={3:0}, head={5:4}, node={5:0}] [L863] COND TRUE !(node->nested.prev == &node->nested) [L863] CALL fail() VAL [gl_list={3:0}] [L840] reach_error() VAL [gl_list={3:0}] - StatisticsResult: Ultimate Automizer benchmark data CFG has 5 procedures, 110 locations, 215 edges, 1 error locations. Started 1 CEGAR loops. OverallTime: 29.6s, OverallIterations: 13, TraceHistogramMax: 2, PathProgramHistogramMax: 1, EmptinessCheckTime: 0.0s, AutomataDifference: 15.2s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, HoareTripleCheckerStatistics: 539 mSolverCounterUnknown, 6269 SdHoareTripleChecker+Valid, 10.8s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 6243 mSDsluCounter, 3093 SdHoareTripleChecker+Invalid, 9.4s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 2557 mSDsCounter, 867 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 13547 IncrementalHoareTripleChecker+Invalid, 14953 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 867 mSolverCounterUnsat, 536 mSDtfsCounter, 13547 mSolverCounterSat, 0.1s SdHoareTripleChecker+Time, 539 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 440 GetRequests, 148 SyntacticMatches, 0 SemanticMatches, 292 ConstructedPredicates, 6 IntricatePredicates, 0 DeprecatedPredicates, 1910 ImplicationChecksByTransitivity, 7.4s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=402occurred in iteration=12, InterpolantAutomatonStates: 187, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.4s AutomataMinimizationTime, 12 MinimizatonAttempts, 264 StatesRemovedByMinimization, 10 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.1s SsaConstructionTime, 0.4s SatisfiabilityAnalysisTime, 12.4s InterpolantComputationTime, 506 NumberOfCodeBlocks, 506 NumberOfCodeBlocksAsserted, 16 NumberOfCheckSat, 449 ConstructedInterpolants, 22 QuantifiedInterpolants, 14262 SizeOfPredicates, 28 NumberOfNonLiveVariables, 903 ConjunctsInSsa, 261 ConjunctsInUnsatCore, 15 InterpolantComputations, 9 PerfectInterpolantSequences, 1/66 InterpolantCoveringCapability, INVARIANT_SYNTHESIS: No data available, INTERPOLANT_CONSOLIDATION: No data available, ABSTRACT_INTERPRETATION: No data available, PDR: No data available, ACCELERATED_INTERPOLATION: No data available, SIFA: No data available, ReuseStatistics: No data available, ConComCheckerStatistics: No data available RESULT: Ultimate proved your program to be incorrect! [2025-03-16 17:35:54,328 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Ended with exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Writing output log to file Ultimate.log Writing human readable error path to file UltimateCounterExample.errorpath Result: FALSE