./Ultimate.py --spec ../sv-benchmarks/c/properties/no-overflow.prp --file ../sv-benchmarks/c/recursified_nla-digbench/recursified_dijkstra.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for overflows Using default analysis Version 798a7b37 Calling Ultimate with: /root/.sdkman/candidates/java/21.0.5-tem/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.6.800.v20240513-1750.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/recursified_nla-digbench/recursified_dijkstra.c -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Overflow-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 ! overflow) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash 4a9aad6636e75eb788a44e63e1649ee5df89ecae877c31a886978a8e3fdd2e8f --- Real Ultimate output --- This is Ultimate 0.3.0-?-798a7b3-m [2025-03-04 11:31:47,339 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-03-04 11:31:47,396 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Overflow-32bit-Automizer_Default.epf [2025-03-04 11:31:47,400 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-03-04 11:31:47,400 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-03-04 11:31:47,412 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-03-04 11:31:47,417 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-03-04 11:31:47,417 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-03-04 11:31:47,417 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-03-04 11:31:47,417 INFO L153 SettingsManager]: * Use memory slicer=true [2025-03-04 11:31:47,417 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2025-03-04 11:31:47,417 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2025-03-04 11:31:47,417 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-03-04 11:31:47,417 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-03-04 11:31:47,417 INFO L153 SettingsManager]: * Use SBE=true [2025-03-04 11:31:47,418 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-03-04 11:31:47,418 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2025-03-04 11:31:47,418 INFO L153 SettingsManager]: * sizeof long=4 [2025-03-04 11:31:47,418 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2025-03-04 11:31:47,418 INFO L153 SettingsManager]: * sizeof POINTER=4 [2025-03-04 11:31:47,418 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-03-04 11:31:47,418 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2025-03-04 11:31:47,418 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2025-03-04 11:31:47,418 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2025-03-04 11:31:47,418 INFO L153 SettingsManager]: * Check absence of signed integer overflows=ASSERTandASSUME [2025-03-04 11:31:47,418 INFO L153 SettingsManager]: * Check unreachability of reach_error function=false [2025-03-04 11:31:47,418 INFO L153 SettingsManager]: * sizeof long double=12 [2025-03-04 11:31:47,418 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-03-04 11:31:47,418 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-03-04 11:31:47,418 INFO L153 SettingsManager]: * Use constant arrays=true [2025-03-04 11:31:47,418 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-03-04 11:31:47,418 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-03-04 11:31:47,419 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-03-04 11:31:47,419 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-03-04 11:31:47,419 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-04 11:31:47,419 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-03-04 11:31:47,419 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2025-03-04 11:31:47,419 INFO L153 SettingsManager]: * Compute procedure contracts=false [2025-03-04 11:31:47,419 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2025-03-04 11:31:47,419 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2025-03-04 11:31:47,419 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2025-03-04 11:31:47,419 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2025-03-04 11:31:47,419 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2025-03-04 11:31:47,419 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2025-03-04 11:31:47,419 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2025-03-04 11:31:47,419 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 ! overflow) ) 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 -> 4a9aad6636e75eb788a44e63e1649ee5df89ecae877c31a886978a8e3fdd2e8f [2025-03-04 11:31:47,660 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-03-04 11:31:47,666 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-03-04 11:31:47,668 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-03-04 11:31:47,671 INFO L270 PluginConnector]: Initializing CDTParser... [2025-03-04 11:31:47,672 INFO L274 PluginConnector]: CDTParser initialized [2025-03-04 11:31:47,673 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/recursified_nla-digbench/recursified_dijkstra.c [2025-03-04 11:31:48,879 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/96716cfec/52a05e0fdad5411380c933bd32959b2b/FLAG4d666b9a6 [2025-03-04 11:31:49,092 INFO L384 CDTParser]: Found 1 translation units. [2025-03-04 11:31:49,093 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursified_nla-digbench/recursified_dijkstra.c [2025-03-04 11:31:49,101 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/96716cfec/52a05e0fdad5411380c933bd32959b2b/FLAG4d666b9a6 [2025-03-04 11:31:49,113 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/96716cfec/52a05e0fdad5411380c933bd32959b2b [2025-03-04 11:31:49,115 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-03-04 11:31:49,116 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-03-04 11:31:49,117 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-03-04 11:31:49,117 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-03-04 11:31:49,120 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-03-04 11:31:49,121 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 04.03 11:31:49" (1/1) ... [2025-03-04 11:31:49,122 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@3b601451 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.03 11:31:49, skipping insertion in model container [2025-03-04 11:31:49,122 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 04.03 11:31:49" (1/1) ... [2025-03-04 11:31:49,137 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-03-04 11:31:49,282 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-04 11:31:49,294 INFO L200 MainTranslator]: Completed pre-run [2025-03-04 11:31:49,337 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-04 11:31:49,351 INFO L204 MainTranslator]: Completed translation [2025-03-04 11:31:49,351 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.03 11:31:49 WrapperNode [2025-03-04 11:31:49,352 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-03-04 11:31:49,353 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-03-04 11:31:49,353 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-03-04 11:31:49,353 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-03-04 11:31:49,357 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.03 11:31:49" (1/1) ... [2025-03-04 11:31:49,368 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.03 11:31:49" (1/1) ... [2025-03-04 11:31:49,394 INFO L138 Inliner]: procedures = 17, calls = 172, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 185 [2025-03-04 11:31:49,394 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-03-04 11:31:49,394 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-03-04 11:31:49,394 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-03-04 11:31:49,394 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-03-04 11:31:49,401 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.03 11:31:49" (1/1) ... [2025-03-04 11:31:49,401 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.03 11:31:49" (1/1) ... [2025-03-04 11:31:49,408 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.03 11:31:49" (1/1) ... [2025-03-04 11:31:49,426 INFO L175 MemorySlicer]: Split 138 memory accesses to 6 slices as follows [2, 22, 29, 30, 20, 35]. 25 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2, 0, 0, 0, 0, 0]. The 11 writes are split as follows [0, 2, 3, 2, 1, 3]. [2025-03-04 11:31:49,426 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.03 11:31:49" (1/1) ... [2025-03-04 11:31:49,427 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.03 11:31:49" (1/1) ... [2025-03-04 11:31:49,436 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.03 11:31:49" (1/1) ... [2025-03-04 11:31:49,437 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.03 11:31:49" (1/1) ... [2025-03-04 11:31:49,440 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.03 11:31:49" (1/1) ... [2025-03-04 11:31:49,442 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.03 11:31:49" (1/1) ... [2025-03-04 11:31:49,450 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-03-04 11:31:49,450 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2025-03-04 11:31:49,450 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2025-03-04 11:31:49,450 INFO L274 PluginConnector]: IcfgBuilder initialized [2025-03-04 11:31:49,451 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.03 11:31:49" (1/1) ... [2025-03-04 11:31:49,458 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-04 11:31:49,467 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 11:31:49,480 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2025-03-04 11:31:49,483 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2025-03-04 11:31:49,503 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2025-03-04 11:31:49,503 INFO L130 BoogieDeclarations]: Found specification of procedure func_to_recursive_line_28_to_32_0 [2025-03-04 11:31:49,503 INFO L138 BoogieDeclarations]: Found implementation of procedure func_to_recursive_line_28_to_32_0 [2025-03-04 11:31:49,503 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2025-03-04 11:31:49,503 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#1 [2025-03-04 11:31:49,503 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#2 [2025-03-04 11:31:49,503 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#3 [2025-03-04 11:31:49,503 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#4 [2025-03-04 11:31:49,503 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#5 [2025-03-04 11:31:49,503 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2025-03-04 11:31:49,503 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#0 [2025-03-04 11:31:49,503 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#1 [2025-03-04 11:31:49,503 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#2 [2025-03-04 11:31:49,503 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#3 [2025-03-04 11:31:49,503 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#4 [2025-03-04 11:31:49,503 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#5 [2025-03-04 11:31:49,503 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-03-04 11:31:49,503 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-03-04 11:31:49,503 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#0 [2025-03-04 11:31:49,503 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#1 [2025-03-04 11:31:49,503 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#2 [2025-03-04 11:31:49,503 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#3 [2025-03-04 11:31:49,503 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#4 [2025-03-04 11:31:49,504 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#5 [2025-03-04 11:31:49,504 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2025-03-04 11:31:49,504 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2025-03-04 11:31:49,504 INFO L130 BoogieDeclarations]: Found specification of procedure func_to_recursive_line_36_to_52_0 [2025-03-04 11:31:49,504 INFO L138 BoogieDeclarations]: Found implementation of procedure func_to_recursive_line_36_to_52_0 [2025-03-04 11:31:49,504 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2025-03-04 11:31:49,615 INFO L256 CfgBuilder]: Building ICFG [2025-03-04 11:31:49,617 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2025-03-04 11:31:50,764 INFO L1325 $ProcedureCfgBuilder]: dead code at ProgramPoint L108: call ULTIMATE.dealloc(main_~#n~0#1.base, main_~#n~0#1.offset);havoc main_~#n~0#1.base, main_~#n~0#1.offset;call ULTIMATE.dealloc(main_~#p~0#1.base, main_~#p~0#1.offset);havoc main_~#p~0#1.base, main_~#p~0#1.offset;call ULTIMATE.dealloc(main_~#q~0#1.base, main_~#q~0#1.offset);havoc main_~#q~0#1.base, main_~#q~0#1.offset;call ULTIMATE.dealloc(main_~#r~0#1.base, main_~#r~0#1.offset);havoc main_~#r~0#1.base, main_~#r~0#1.offset;call ULTIMATE.dealloc(main_~#h~0#1.base, main_~#h~0#1.offset);havoc main_~#h~0#1.base, main_~#h~0#1.offset; [2025-03-04 11:31:50,807 INFO L? ?]: Removed 1170 outVars from TransFormulas that were not future-live. [2025-03-04 11:31:50,807 INFO L307 CfgBuilder]: Performing block encoding [2025-03-04 11:31:50,828 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-03-04 11:31:50,830 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2025-03-04 11:31:50,830 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 04.03 11:31:50 BoogieIcfgContainer [2025-03-04 11:31:50,830 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2025-03-04 11:31:50,832 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2025-03-04 11:31:50,832 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2025-03-04 11:31:50,837 INFO L274 PluginConnector]: TraceAbstraction initialized [2025-03-04 11:31:50,837 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 04.03 11:31:49" (1/3) ... [2025-03-04 11:31:50,838 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4c176d0d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 04.03 11:31:50, skipping insertion in model container [2025-03-04 11:31:50,838 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.03 11:31:49" (2/3) ... [2025-03-04 11:31:50,838 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4c176d0d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 04.03 11:31:50, skipping insertion in model container [2025-03-04 11:31:50,838 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 04.03 11:31:50" (3/3) ... [2025-03-04 11:31:50,839 INFO L128 eAbstractionObserver]: Analyzing ICFG recursified_dijkstra.c [2025-03-04 11:31:50,848 INFO L216 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2025-03-04 11:31:50,849 INFO L151 ceAbstractionStarter]: Applying trace abstraction to ICFG recursified_dijkstra.c that has 4 procedures, 561 locations, 1 initial locations, 0 loop locations, and 258 error locations. [2025-03-04 11:31:50,904 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2025-03-04 11:31:50,914 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;@210a0e3, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2025-03-04 11:31:50,914 INFO L334 AbstractCegarLoop]: Starting to check reachability of 258 error locations. [2025-03-04 11:31:50,919 INFO L276 IsEmpty]: Start isEmpty. Operand has 561 states, 286 states have (on average 1.9230769230769231) internal successors, (550), 546 states have internal predecessors, (550), 13 states have call successors, (13), 3 states have call predecessors, (13), 3 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2025-03-04 11:31:50,923 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 8 [2025-03-04 11:31:50,924 INFO L210 NwaCegarLoop]: Found error trace [2025-03-04 11:31:50,924 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2025-03-04 11:31:50,925 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting func_to_recursive_line_28_to_32_0Err1ASSERT_VIOLATIONINTEGER_OVERFLOW === [func_to_recursive_line_36_to_52_0Err0ASSERT_VIOLATIONINTEGER_OVERFLOW, func_to_recursive_line_36_to_52_0Err1ASSERT_VIOLATIONINTEGER_OVERFLOW (and 256 more)] === [2025-03-04 11:31:50,928 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 11:31:50,928 INFO L85 PathProgramCache]: Analyzing trace with hash 828768651, now seen corresponding path program 1 times [2025-03-04 11:31:50,933 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-04 11:31:50,934 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1754959348] [2025-03-04 11:31:50,934 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-04 11:31:50,934 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-04 11:31:50,988 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 7 statements into 1 equivalence classes. [2025-03-04 11:31:51,014 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 7 of 7 statements. [2025-03-04 11:31:51,015 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 11:31:51,015 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 11:31:51,281 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-04 11:31:51,282 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-04 11:31:51,282 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1754959348] [2025-03-04 11:31:51,283 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1754959348] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-04 11:31:51,283 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-04 11:31:51,283 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-04 11:31:51,284 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [476760110] [2025-03-04 11:31:51,284 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-04 11:31:51,287 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2025-03-04 11:31:51,287 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-04 11:31:51,300 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2025-03-04 11:31:51,300 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2025-03-04 11:31:51,302 INFO L87 Difference]: Start difference. First operand has 561 states, 286 states have (on average 1.9230769230769231) internal successors, (550), 546 states have internal predecessors, (550), 13 states have call successors, (13), 3 states have call predecessors, (13), 3 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) Second operand has 6 states, 4 states have (on average 1.5) internal successors, (6), 5 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-03-04 11:31:51,556 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-04 11:31:51,556 INFO L93 Difference]: Finished difference Result 1120 states and 1163 transitions. [2025-03-04 11:31:51,557 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2025-03-04 11:31:51,558 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 4 states have (on average 1.5) internal successors, (6), 5 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 7 [2025-03-04 11:31:51,558 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-04 11:31:51,567 INFO L225 Difference]: With dead ends: 1120 [2025-03-04 11:31:51,567 INFO L226 Difference]: Without dead ends: 562 [2025-03-04 11:31:51,575 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=19, Invalid=37, Unknown=0, NotChecked=0, Total=56 [2025-03-04 11:31:51,576 INFO L435 NwaCegarLoop]: 566 mSDtfsCounter, 11 mSDsluCounter, 2164 mSDsCounter, 0 mSdLazyCounter, 128 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 2730 SdHoareTripleChecker+Invalid, 130 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 128 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-04 11:31:51,577 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 2730 Invalid, 130 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 128 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-04 11:31:51,589 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 562 states. [2025-03-04 11:31:51,618 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 562 to 561. [2025-03-04 11:31:51,619 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 561 states, 287 states have (on average 1.9094076655052266) internal successors, (548), 546 states have internal predecessors, (548), 12 states have call successors, (12), 4 states have call predecessors, (12), 4 states have return successors, (13), 12 states have call predecessors, (13), 12 states have call successors, (13) [2025-03-04 11:31:51,626 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 561 states to 561 states and 573 transitions. [2025-03-04 11:31:51,627 INFO L78 Accepts]: Start accepts. Automaton has 561 states and 573 transitions. Word has length 7 [2025-03-04 11:31:51,628 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-04 11:31:51,628 INFO L471 AbstractCegarLoop]: Abstraction has 561 states and 573 transitions. [2025-03-04 11:31:51,628 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 4 states have (on average 1.5) internal successors, (6), 5 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-03-04 11:31:51,628 INFO L276 IsEmpty]: Start isEmpty. Operand 561 states and 573 transitions. [2025-03-04 11:31:51,628 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2025-03-04 11:31:51,628 INFO L210 NwaCegarLoop]: Found error trace [2025-03-04 11:31:51,628 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-04 11:31:51,630 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2025-03-04 11:31:51,630 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting func_to_recursive_line_36_to_52_0Err185ASSERT_VIOLATIONINTEGER_OVERFLOW === [func_to_recursive_line_36_to_52_0Err0ASSERT_VIOLATIONINTEGER_OVERFLOW, func_to_recursive_line_36_to_52_0Err1ASSERT_VIOLATIONINTEGER_OVERFLOW (and 256 more)] === [2025-03-04 11:31:51,631 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 11:31:51,631 INFO L85 PathProgramCache]: Analyzing trace with hash 637776022, now seen corresponding path program 1 times [2025-03-04 11:31:51,631 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-04 11:31:51,632 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1436014515] [2025-03-04 11:31:51,632 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-04 11:31:51,632 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-04 11:31:51,643 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 12 statements into 1 equivalence classes. [2025-03-04 11:31:51,656 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 12 of 12 statements. [2025-03-04 11:31:51,656 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 11:31:51,656 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 11:31:51,777 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-04 11:31:51,777 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-04 11:31:51,778 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1436014515] [2025-03-04 11:31:51,778 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1436014515] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-04 11:31:51,778 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-04 11:31:51,778 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-04 11:31:51,778 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [851896969] [2025-03-04 11:31:51,778 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-04 11:31:51,778 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2025-03-04 11:31:51,779 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-04 11:31:51,779 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2025-03-04 11:31:51,779 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2025-03-04 11:31:51,779 INFO L87 Difference]: Start difference. First operand 561 states and 573 transitions. Second operand has 6 states, 4 states have (on average 2.25) internal successors, (9), 5 states have internal predecessors, (9), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2025-03-04 11:31:52,007 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-04 11:31:52,007 INFO L93 Difference]: Finished difference Result 1083 states and 1104 transitions. [2025-03-04 11:31:52,008 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2025-03-04 11:31:52,008 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 4 states have (on average 2.25) internal successors, (9), 5 states have internal predecessors, (9), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 12 [2025-03-04 11:31:52,009 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-04 11:31:52,012 INFO L225 Difference]: With dead ends: 1083 [2025-03-04 11:31:52,012 INFO L226 Difference]: Without dead ends: 1081 [2025-03-04 11:31:52,013 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=19, Invalid=37, Unknown=0, NotChecked=0, Total=56 [2025-03-04 11:31:52,014 INFO L435 NwaCegarLoop]: 534 mSDtfsCounter, 885 mSDsluCounter, 2093 mSDsCounter, 0 mSdLazyCounter, 195 mSolverCounterSat, 15 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 887 SdHoareTripleChecker+Valid, 2627 SdHoareTripleChecker+Invalid, 210 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 15 IncrementalHoareTripleChecker+Valid, 195 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-03-04 11:31:52,015 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [887 Valid, 2627 Invalid, 210 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [15 Valid, 195 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-03-04 11:31:52,019 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1081 states. [2025-03-04 11:31:52,043 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1081 to 754. [2025-03-04 11:31:52,046 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 754 states, 473 states have (on average 1.9217758985200846) internal successors, (909), 732 states have internal predecessors, (909), 18 states have call successors, (18), 5 states have call predecessors, (18), 5 states have return successors, (20), 18 states have call predecessors, (20), 18 states have call successors, (20) [2025-03-04 11:31:52,050 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 754 states to 754 states and 947 transitions. [2025-03-04 11:31:52,052 INFO L78 Accepts]: Start accepts. Automaton has 754 states and 947 transitions. Word has length 12 [2025-03-04 11:31:52,052 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-04 11:31:52,052 INFO L471 AbstractCegarLoop]: Abstraction has 754 states and 947 transitions. [2025-03-04 11:31:52,052 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 4 states have (on average 2.25) internal successors, (9), 5 states have internal predecessors, (9), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2025-03-04 11:31:52,052 INFO L276 IsEmpty]: Start isEmpty. Operand 754 states and 947 transitions. [2025-03-04 11:31:52,053 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 14 [2025-03-04 11:31:52,053 INFO L210 NwaCegarLoop]: Found error trace [2025-03-04 11:31:52,053 INFO L218 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1] [2025-03-04 11:31:52,054 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2025-03-04 11:31:52,054 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting func_to_recursive_line_28_to_32_0Err1ASSERT_VIOLATIONINTEGER_OVERFLOW === [func_to_recursive_line_36_to_52_0Err0ASSERT_VIOLATIONINTEGER_OVERFLOW, func_to_recursive_line_36_to_52_0Err1ASSERT_VIOLATIONINTEGER_OVERFLOW (and 256 more)] === [2025-03-04 11:31:52,054 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 11:31:52,054 INFO L85 PathProgramCache]: Analyzing trace with hash 1003650143, now seen corresponding path program 1 times [2025-03-04 11:31:52,054 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-04 11:31:52,054 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2079826925] [2025-03-04 11:31:52,054 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-04 11:31:52,055 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-04 11:31:52,065 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 13 statements into 1 equivalence classes. [2025-03-04 11:31:52,075 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 13 of 13 statements. [2025-03-04 11:31:52,075 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 11:31:52,075 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 11:31:52,304 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-04 11:31:52,304 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-04 11:31:52,304 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2079826925] [2025-03-04 11:31:52,304 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2079826925] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-04 11:31:52,304 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1349642694] [2025-03-04 11:31:52,304 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-04 11:31:52,304 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-04 11:31:52,304 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 11:31:52,307 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-04 11:31:52,309 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2025-03-04 11:31:52,364 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 13 statements into 1 equivalence classes. [2025-03-04 11:31:52,390 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 13 of 13 statements. [2025-03-04 11:31:52,390 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 11:31:52,390 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 11:31:52,393 INFO L256 TraceCheckSpWp]: Trace formula consists of 152 conjuncts, 27 conjuncts are in the unsatisfiable core [2025-03-04 11:31:52,398 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-04 11:31:52,426 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-03-04 11:31:52,471 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 21 treesize of output 13 [2025-03-04 11:31:52,554 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 26 treesize of output 14 [2025-03-04 11:31:52,562 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-04 11:31:52,562 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-04 11:31:52,669 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-04 11:31:52,670 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1349642694] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-04 11:31:52,670 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-04 11:31:52,670 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 8] total 18 [2025-03-04 11:31:52,670 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1901660188] [2025-03-04 11:31:52,670 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-04 11:31:52,670 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2025-03-04 11:31:52,670 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-04 11:31:52,670 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2025-03-04 11:31:52,671 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=62, Invalid=280, Unknown=0, NotChecked=0, Total=342 [2025-03-04 11:31:52,671 INFO L87 Difference]: Start difference. First operand 754 states and 947 transitions. Second operand has 19 states, 16 states have (on average 1.6875) internal successors, (27), 14 states have internal predecessors, (27), 5 states have call successors, (5), 5 states have call predecessors, (5), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-03-04 11:31:52,988 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-04 11:31:52,989 INFO L93 Difference]: Finished difference Result 760 states and 959 transitions. [2025-03-04 11:31:52,989 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2025-03-04 11:31:52,989 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 16 states have (on average 1.6875) internal successors, (27), 14 states have internal predecessors, (27), 5 states have call successors, (5), 5 states have call predecessors, (5), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 13 [2025-03-04 11:31:52,989 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-04 11:31:52,992 INFO L225 Difference]: With dead ends: 760 [2025-03-04 11:31:52,992 INFO L226 Difference]: Without dead ends: 759 [2025-03-04 11:31:52,992 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 38 GetRequests, 16 SyntacticMatches, 0 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 71 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=117, Invalid=435, Unknown=0, NotChecked=0, Total=552 [2025-03-04 11:31:52,994 INFO L435 NwaCegarLoop]: 560 mSDtfsCounter, 47 mSDsluCounter, 4258 mSDsCounter, 0 mSdLazyCounter, 299 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 47 SdHoareTripleChecker+Valid, 4818 SdHoareTripleChecker+Invalid, 312 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 299 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-03-04 11:31:52,995 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [47 Valid, 4818 Invalid, 312 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 299 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-03-04 11:31:52,997 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 759 states. [2025-03-04 11:31:53,010 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 759 to 755. [2025-03-04 11:31:53,012 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 755 states, 474 states have (on average 1.9177215189873418) internal successors, (909), 732 states have internal predecessors, (909), 18 states have call successors, (18), 5 states have call predecessors, (18), 6 states have return successors, (21), 18 states have call predecessors, (21), 18 states have call successors, (21) [2025-03-04 11:31:53,015 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 755 states to 755 states and 948 transitions. [2025-03-04 11:31:53,016 INFO L78 Accepts]: Start accepts. Automaton has 755 states and 948 transitions. Word has length 13 [2025-03-04 11:31:53,016 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-04 11:31:53,016 INFO L471 AbstractCegarLoop]: Abstraction has 755 states and 948 transitions. [2025-03-04 11:31:53,016 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 16 states have (on average 1.6875) internal successors, (27), 14 states have internal predecessors, (27), 5 states have call successors, (5), 5 states have call predecessors, (5), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-03-04 11:31:53,016 INFO L276 IsEmpty]: Start isEmpty. Operand 755 states and 948 transitions. [2025-03-04 11:31:53,017 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2025-03-04 11:31:53,017 INFO L210 NwaCegarLoop]: Found error trace [2025-03-04 11:31:53,017 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-04 11:31:53,024 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2025-03-04 11:31:53,221 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-04 11:31:53,221 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting func_to_recursive_line_36_to_52_0Err183ASSERT_VIOLATIONINTEGER_OVERFLOW === [func_to_recursive_line_36_to_52_0Err0ASSERT_VIOLATIONINTEGER_OVERFLOW, func_to_recursive_line_36_to_52_0Err1ASSERT_VIOLATIONINTEGER_OVERFLOW (and 256 more)] === [2025-03-04 11:31:53,222 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 11:31:53,222 INFO L85 PathProgramCache]: Analyzing trace with hash -1277554764, now seen corresponding path program 1 times [2025-03-04 11:31:53,222 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-04 11:31:53,222 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [974756614] [2025-03-04 11:31:53,222 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-04 11:31:53,222 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-04 11:31:53,232 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 14 statements into 1 equivalence classes. [2025-03-04 11:31:53,241 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 14 of 14 statements. [2025-03-04 11:31:53,242 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 11:31:53,243 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 11:31:53,440 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-04 11:31:53,440 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-04 11:31:53,441 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [974756614] [2025-03-04 11:31:53,441 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [974756614] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-04 11:31:53,441 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-04 11:31:53,441 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2025-03-04 11:31:53,441 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1248925949] [2025-03-04 11:31:53,441 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-04 11:31:53,441 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2025-03-04 11:31:53,441 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-04 11:31:53,441 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2025-03-04 11:31:53,441 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=43, Unknown=0, NotChecked=0, Total=56 [2025-03-04 11:31:53,442 INFO L87 Difference]: Start difference. First operand 755 states and 948 transitions. Second operand has 8 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 7 states have internal predecessors, (11), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2025-03-04 11:31:53,882 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-04 11:31:53,882 INFO L93 Difference]: Finished difference Result 1270 states and 1473 transitions. [2025-03-04 11:31:53,882 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2025-03-04 11:31:53,882 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 7 states have internal predecessors, (11), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 14 [2025-03-04 11:31:53,882 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-04 11:31:53,886 INFO L225 Difference]: With dead ends: 1270 [2025-03-04 11:31:53,886 INFO L226 Difference]: Without dead ends: 1268 [2025-03-04 11:31:53,887 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 12 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=41, Invalid=91, Unknown=0, NotChecked=0, Total=132 [2025-03-04 11:31:53,887 INFO L435 NwaCegarLoop]: 497 mSDtfsCounter, 1600 mSDsluCounter, 2571 mSDsCounter, 0 mSdLazyCounter, 488 mSolverCounterSat, 42 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1608 SdHoareTripleChecker+Valid, 3068 SdHoareTripleChecker+Invalid, 530 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 42 IncrementalHoareTripleChecker+Valid, 488 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2025-03-04 11:31:53,887 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [1608 Valid, 3068 Invalid, 530 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [42 Valid, 488 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2025-03-04 11:31:53,889 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1268 states. [2025-03-04 11:31:53,911 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1268 to 951. [2025-03-04 11:31:53,912 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 951 states, 661 states have (on average 1.91981845688351) internal successors, (1269), 919 states have internal predecessors, (1269), 25 states have call successors, (25), 6 states have call predecessors, (25), 8 states have return successors, (30), 25 states have call predecessors, (30), 25 states have call successors, (30) [2025-03-04 11:31:53,916 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 951 states to 951 states and 1324 transitions. [2025-03-04 11:31:53,917 INFO L78 Accepts]: Start accepts. Automaton has 951 states and 1324 transitions. Word has length 14 [2025-03-04 11:31:53,917 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-04 11:31:53,917 INFO L471 AbstractCegarLoop]: Abstraction has 951 states and 1324 transitions. [2025-03-04 11:31:53,918 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 7 states have internal predecessors, (11), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2025-03-04 11:31:53,918 INFO L276 IsEmpty]: Start isEmpty. Operand 951 states and 1324 transitions. [2025-03-04 11:31:53,918 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2025-03-04 11:31:53,918 INFO L210 NwaCegarLoop]: Found error trace [2025-03-04 11:31:53,918 INFO L218 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1] [2025-03-04 11:31:53,918 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2025-03-04 11:31:53,919 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting func_to_recursive_line_28_to_32_0Err0ASSERT_VIOLATIONINTEGER_OVERFLOW === [func_to_recursive_line_36_to_52_0Err0ASSERT_VIOLATIONINTEGER_OVERFLOW, func_to_recursive_line_36_to_52_0Err1ASSERT_VIOLATIONINTEGER_OVERFLOW (and 256 more)] === [2025-03-04 11:31:53,919 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 11:31:53,919 INFO L85 PathProgramCache]: Analyzing trace with hash 1048383727, now seen corresponding path program 1 times [2025-03-04 11:31:53,919 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-04 11:31:53,919 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [910201397] [2025-03-04 11:31:53,919 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-04 11:31:53,919 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-04 11:31:53,926 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 14 statements into 1 equivalence classes. [2025-03-04 11:31:53,932 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 14 of 14 statements. [2025-03-04 11:31:53,933 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 11:31:53,933 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 11:31:54,098 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 5 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-04 11:31:54,098 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-04 11:31:54,098 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [910201397] [2025-03-04 11:31:54,098 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [910201397] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-04 11:31:54,098 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [955633149] [2025-03-04 11:31:54,098 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-04 11:31:54,099 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-04 11:31:54,099 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 11:31:54,100 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-04 11:31:54,101 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2025-03-04 11:31:54,157 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 14 statements into 1 equivalence classes. [2025-03-04 11:31:54,172 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 14 of 14 statements. [2025-03-04 11:31:54,172 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 11:31:54,172 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 11:31:54,174 INFO L256 TraceCheckSpWp]: Trace formula consists of 153 conjuncts, 27 conjuncts are in the unsatisfiable core [2025-03-04 11:31:54,175 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-04 11:31:54,178 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-03-04 11:31:54,206 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 21 treesize of output 13 [2025-03-04 11:31:54,247 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 26 treesize of output 14 [2025-03-04 11:31:54,251 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 5 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-04 11:31:54,251 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-04 11:31:54,330 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 5 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-04 11:31:54,330 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [955633149] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-04 11:31:54,330 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-04 11:31:54,330 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 8] total 18 [2025-03-04 11:31:54,330 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [975060611] [2025-03-04 11:31:54,330 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-04 11:31:54,330 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2025-03-04 11:31:54,330 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-04 11:31:54,331 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2025-03-04 11:31:54,331 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=67, Invalid=275, Unknown=0, NotChecked=0, Total=342 [2025-03-04 11:31:54,331 INFO L87 Difference]: Start difference. First operand 951 states and 1324 transitions. Second operand has 19 states, 16 states have (on average 1.8125) internal successors, (29), 14 states have internal predecessors, (29), 5 states have call successors, (5), 5 states have call predecessors, (5), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-03-04 11:31:54,609 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-04 11:31:54,609 INFO L93 Difference]: Finished difference Result 982 states and 1363 transitions. [2025-03-04 11:31:54,609 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2025-03-04 11:31:54,610 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 16 states have (on average 1.8125) internal successors, (29), 14 states have internal predecessors, (29), 5 states have call successors, (5), 5 states have call predecessors, (5), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 14 [2025-03-04 11:31:54,610 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-04 11:31:54,613 INFO L225 Difference]: With dead ends: 982 [2025-03-04 11:31:54,613 INFO L226 Difference]: Without dead ends: 981 [2025-03-04 11:31:54,614 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 44 GetRequests, 18 SyntacticMatches, 0 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 142 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=170, Invalid=586, Unknown=0, NotChecked=0, Total=756 [2025-03-04 11:31:54,614 INFO L435 NwaCegarLoop]: 560 mSDtfsCounter, 71 mSDsluCounter, 3754 mSDsCounter, 0 mSdLazyCounter, 297 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 71 SdHoareTripleChecker+Valid, 4314 SdHoareTripleChecker+Invalid, 311 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 297 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-03-04 11:31:54,614 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [71 Valid, 4314 Invalid, 311 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 297 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-03-04 11:31:54,616 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 981 states. [2025-03-04 11:31:54,646 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 981 to 981. [2025-03-04 11:31:54,648 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 981 states, 682 states have (on average 1.8958944281524928) internal successors, (1293), 943 states have internal predecessors, (1293), 28 states have call successors, (28), 9 states have call predecessors, (28), 14 states have return successors, (39), 28 states have call predecessors, (39), 28 states have call successors, (39) [2025-03-04 11:31:54,652 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 981 states to 981 states and 1360 transitions. [2025-03-04 11:31:54,652 INFO L78 Accepts]: Start accepts. Automaton has 981 states and 1360 transitions. Word has length 14 [2025-03-04 11:31:54,652 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-04 11:31:54,652 INFO L471 AbstractCegarLoop]: Abstraction has 981 states and 1360 transitions. [2025-03-04 11:31:54,652 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 16 states have (on average 1.8125) internal successors, (29), 14 states have internal predecessors, (29), 5 states have call successors, (5), 5 states have call predecessors, (5), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-03-04 11:31:54,652 INFO L276 IsEmpty]: Start isEmpty. Operand 981 states and 1360 transitions. [2025-03-04 11:31:54,653 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2025-03-04 11:31:54,653 INFO L210 NwaCegarLoop]: Found error trace [2025-03-04 11:31:54,653 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] [2025-03-04 11:31:54,659 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2025-03-04 11:31:54,855 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-04 11:31:54,856 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting func_to_recursive_line_36_to_52_0Err181ASSERT_VIOLATIONINTEGER_OVERFLOW === [func_to_recursive_line_36_to_52_0Err0ASSERT_VIOLATIONINTEGER_OVERFLOW, func_to_recursive_line_36_to_52_0Err1ASSERT_VIOLATIONINTEGER_OVERFLOW (and 256 more)] === [2025-03-04 11:31:54,856 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 11:31:54,856 INFO L85 PathProgramCache]: Analyzing trace with hash 1213854565, now seen corresponding path program 1 times [2025-03-04 11:31:54,856 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-04 11:31:54,856 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1352304448] [2025-03-04 11:31:54,856 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-04 11:31:54,856 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-04 11:31:54,874 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 22 statements into 1 equivalence classes. [2025-03-04 11:31:54,891 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 22 of 22 statements. [2025-03-04 11:31:54,891 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 11:31:54,891 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-04 11:31:54,893 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [179305886] [2025-03-04 11:31:54,893 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-04 11:31:54,893 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-04 11:31:54,893 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 11:31:54,895 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-04 11:31:54,897 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2025-03-04 11:31:54,947 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 22 statements into 1 equivalence classes. [2025-03-04 11:31:54,967 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 22 of 22 statements. [2025-03-04 11:31:54,967 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 11:31:54,968 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 11:31:54,972 INFO L256 TraceCheckSpWp]: Trace formula consists of 192 conjuncts, 15 conjuncts are in the unsatisfiable core [2025-03-04 11:31:54,973 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-04 11:31:54,983 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-03-04 11:31:55,078 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-04 11:31:55,079 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-04 11:31:55,079 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-04 11:31:55,079 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1352304448] [2025-03-04 11:31:55,079 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-04 11:31:55,080 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [179305886] [2025-03-04 11:31:55,080 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [179305886] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-04 11:31:55,080 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-04 11:31:55,080 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2025-03-04 11:31:55,080 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1425009676] [2025-03-04 11:31:55,080 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-04 11:31:55,080 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2025-03-04 11:31:55,080 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-04 11:31:55,081 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2025-03-04 11:31:55,081 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=14, Invalid=28, Unknown=0, NotChecked=0, Total=42 [2025-03-04 11:31:55,081 INFO L87 Difference]: Start difference. First operand 981 states and 1360 transitions. Second operand has 7 states, 5 states have (on average 3.4) internal successors, (17), 6 states have internal predecessors, (17), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-03-04 11:31:55,328 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-04 11:31:55,329 INFO L93 Difference]: Finished difference Result 1316 states and 1521 transitions. [2025-03-04 11:31:55,329 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2025-03-04 11:31:55,329 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 5 states have (on average 3.4) internal successors, (17), 6 states have internal predecessors, (17), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 22 [2025-03-04 11:31:55,329 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-04 11:31:55,333 INFO L225 Difference]: With dead ends: 1316 [2025-03-04 11:31:55,333 INFO L226 Difference]: Without dead ends: 1315 [2025-03-04 11:31:55,334 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 23 GetRequests, 13 SyntacticMatches, 3 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=26, Invalid=46, Unknown=0, NotChecked=0, Total=72 [2025-03-04 11:31:55,334 INFO L435 NwaCegarLoop]: 523 mSDtfsCounter, 896 mSDsluCounter, 2222 mSDsCounter, 0 mSdLazyCounter, 228 mSolverCounterSat, 20 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 898 SdHoareTripleChecker+Valid, 2745 SdHoareTripleChecker+Invalid, 248 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 20 IncrementalHoareTripleChecker+Valid, 228 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-03-04 11:31:55,334 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [898 Valid, 2745 Invalid, 248 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [20 Valid, 228 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-03-04 11:31:55,335 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1315 states. [2025-03-04 11:31:55,353 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1315 to 1029. [2025-03-04 11:31:55,354 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1029 states, 727 states have (on average 1.892709766162311) internal successors, (1376), 988 states have internal predecessors, (1376), 30 states have call successors, (30), 10 states have call predecessors, (30), 15 states have return successors, (41), 30 states have call predecessors, (41), 30 states have call successors, (41) [2025-03-04 11:31:55,358 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1029 states to 1029 states and 1447 transitions. [2025-03-04 11:31:55,358 INFO L78 Accepts]: Start accepts. Automaton has 1029 states and 1447 transitions. Word has length 22 [2025-03-04 11:31:55,358 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-04 11:31:55,358 INFO L471 AbstractCegarLoop]: Abstraction has 1029 states and 1447 transitions. [2025-03-04 11:31:55,358 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 5 states have (on average 3.4) internal successors, (17), 6 states have internal predecessors, (17), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-03-04 11:31:55,358 INFO L276 IsEmpty]: Start isEmpty. Operand 1029 states and 1447 transitions. [2025-03-04 11:31:55,359 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2025-03-04 11:31:55,359 INFO L210 NwaCegarLoop]: Found error trace [2025-03-04 11:31:55,359 INFO L218 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-04 11:31:55,365 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2025-03-04 11:31:55,563 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-04 11:31:55,563 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting func_to_recursive_line_36_to_52_0Err183ASSERT_VIOLATIONINTEGER_OVERFLOW === [func_to_recursive_line_36_to_52_0Err0ASSERT_VIOLATIONINTEGER_OVERFLOW, func_to_recursive_line_36_to_52_0Err1ASSERT_VIOLATIONINTEGER_OVERFLOW (and 256 more)] === [2025-03-04 11:31:55,563 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 11:31:55,563 INFO L85 PathProgramCache]: Analyzing trace with hash -886637199, now seen corresponding path program 1 times [2025-03-04 11:31:55,563 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-04 11:31:55,563 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1654203249] [2025-03-04 11:31:55,563 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-04 11:31:55,563 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-04 11:31:55,570 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 22 statements into 1 equivalence classes. [2025-03-04 11:31:55,578 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 22 of 22 statements. [2025-03-04 11:31:55,578 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 11:31:55,578 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 11:31:55,845 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2025-03-04 11:31:55,845 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-04 11:31:55,845 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1654203249] [2025-03-04 11:31:55,845 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1654203249] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-04 11:31:55,845 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [725592921] [2025-03-04 11:31:55,845 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-04 11:31:55,845 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-04 11:31:55,846 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 11:31:55,847 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-04 11:31:55,849 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2025-03-04 11:31:55,898 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 22 statements into 1 equivalence classes. [2025-03-04 11:31:55,927 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 22 of 22 statements. [2025-03-04 11:31:55,928 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 11:31:55,928 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 11:31:55,929 INFO L256 TraceCheckSpWp]: Trace formula consists of 210 conjuncts, 50 conjuncts are in the unsatisfiable core [2025-03-04 11:31:55,931 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-04 11:31:55,936 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-03-04 11:31:55,941 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-03-04 11:31:56,168 WARN L873 $PredicateComparison]: unable to prove that (and (exists ((|v_ULTIMATE.start_main_~#p~0#1.base_BEFORE_CALL_3| Int) (|v_ULTIMATE.start_main_~#p~0#1.offset_BEFORE_CALL_3| Int)) (= (select (select |c_#memory_int#2| |v_ULTIMATE.start_main_~#p~0#1.base_BEFORE_CALL_3|) |v_ULTIMATE.start_main_~#p~0#1.offset_BEFORE_CALL_3|) 0)) (exists ((|v_func_to_recursive_line_28_to_32_0_#t~mem98_13| Int)) (let ((.cse0 (select |c_old(#memory_int#5)| |c_func_to_recursive_line_28_to_32_0_#in~q.base|))) (and (= |c_#memory_int#5| (store |c_old(#memory_int#5)| |c_func_to_recursive_line_28_to_32_0_#in~q.base| (store .cse0 |c_func_to_recursive_line_28_to_32_0_#in~q.offset| (* |v_func_to_recursive_line_28_to_32_0_#t~mem98_13| 4)))) (<= (select .cse0 |c_func_to_recursive_line_28_to_32_0_#in~q.offset|) |v_func_to_recursive_line_28_to_32_0_#t~mem98_13|))))) is different from true [2025-03-04 11:31:56,184 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 21 treesize of output 13 [2025-03-04 11:31:56,350 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 26 treesize of output 14 [2025-03-04 11:31:56,372 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 2 not checked. [2025-03-04 11:31:56,372 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-04 11:31:56,661 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [725592921] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-04 11:31:56,661 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-04 11:31:56,661 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 23 [2025-03-04 11:31:56,661 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [464027384] [2025-03-04 11:31:56,661 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-04 11:31:56,661 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 24 states [2025-03-04 11:31:56,661 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-04 11:31:56,661 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2025-03-04 11:31:56,662 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=89, Invalid=783, Unknown=2, NotChecked=56, Total=930 [2025-03-04 11:31:56,662 INFO L87 Difference]: Start difference. First operand 1029 states and 1447 transitions. Second operand has 24 states, 17 states have (on average 1.9411764705882353) internal successors, (33), 20 states have internal predecessors, (33), 6 states have call successors, (6), 4 states have call predecessors, (6), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2025-03-04 11:31:59,180 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-04 11:31:59,180 INFO L93 Difference]: Finished difference Result 2384 states and 2656 transitions. [2025-03-04 11:31:59,180 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2025-03-04 11:31:59,181 INFO L78 Accepts]: Start accepts. Automaton has has 24 states, 17 states have (on average 1.9411764705882353) internal successors, (33), 20 states have internal predecessors, (33), 6 states have call successors, (6), 4 states have call predecessors, (6), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) Word has length 22 [2025-03-04 11:31:59,181 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-04 11:31:59,189 INFO L225 Difference]: With dead ends: 2384 [2025-03-04 11:31:59,189 INFO L226 Difference]: Without dead ends: 2383 [2025-03-04 11:31:59,190 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 57 GetRequests, 15 SyntacticMatches, 1 SemanticMatches, 41 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 327 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=217, Invalid=1507, Unknown=2, NotChecked=80, Total=1806 [2025-03-04 11:31:59,191 INFO L435 NwaCegarLoop]: 1445 mSDtfsCounter, 2990 mSDsluCounter, 20183 mSDsCounter, 0 mSdLazyCounter, 3022 mSolverCounterSat, 74 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3008 SdHoareTripleChecker+Valid, 21628 SdHoareTripleChecker+Invalid, 5248 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 74 IncrementalHoareTripleChecker+Valid, 3022 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 2152 IncrementalHoareTripleChecker+Unchecked, 2.1s IncrementalHoareTripleChecker+Time [2025-03-04 11:31:59,191 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [3008 Valid, 21628 Invalid, 5248 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [74 Valid, 3022 Invalid, 0 Unknown, 2152 Unchecked, 2.1s Time] [2025-03-04 11:31:59,193 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2383 states. [2025-03-04 11:31:59,235 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2383 to 1469. [2025-03-04 11:31:59,237 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1469 states, 1146 states have (on average 1.9031413612565444) internal successors, (2181), 1407 states have internal predecessors, (2181), 46 states have call successors, (46), 13 states have call predecessors, (46), 20 states have return successors, (66), 48 states have call predecessors, (66), 46 states have call successors, (66) [2025-03-04 11:31:59,242 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1469 states to 1469 states and 2293 transitions. [2025-03-04 11:31:59,242 INFO L78 Accepts]: Start accepts. Automaton has 1469 states and 2293 transitions. Word has length 22 [2025-03-04 11:31:59,243 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-04 11:31:59,243 INFO L471 AbstractCegarLoop]: Abstraction has 1469 states and 2293 transitions. [2025-03-04 11:31:59,243 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 24 states, 17 states have (on average 1.9411764705882353) internal successors, (33), 20 states have internal predecessors, (33), 6 states have call successors, (6), 4 states have call predecessors, (6), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2025-03-04 11:31:59,243 INFO L276 IsEmpty]: Start isEmpty. Operand 1469 states and 2293 transitions. [2025-03-04 11:31:59,243 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2025-03-04 11:31:59,243 INFO L210 NwaCegarLoop]: Found error trace [2025-03-04 11:31:59,244 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] [2025-03-04 11:31:59,251 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2025-03-04 11:31:59,448 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-04 11:31:59,448 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting func_to_recursive_line_36_to_52_0Err180ASSERT_VIOLATIONINTEGER_OVERFLOW === [func_to_recursive_line_36_to_52_0Err0ASSERT_VIOLATIONINTEGER_OVERFLOW, func_to_recursive_line_36_to_52_0Err1ASSERT_VIOLATIONINTEGER_OVERFLOW (and 256 more)] === [2025-03-04 11:31:59,449 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 11:31:59,449 INFO L85 PathProgramCache]: Analyzing trace with hash -1025213802, now seen corresponding path program 1 times [2025-03-04 11:31:59,449 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-04 11:31:59,449 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1275914746] [2025-03-04 11:31:59,449 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-04 11:31:59,449 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-04 11:31:59,464 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 23 statements into 1 equivalence classes. [2025-03-04 11:31:59,474 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 23 of 23 statements. [2025-03-04 11:31:59,475 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 11:31:59,475 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-04 11:31:59,476 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [576904604] [2025-03-04 11:31:59,476 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-04 11:31:59,476 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-04 11:31:59,476 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 11:31:59,480 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-04 11:31:59,487 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2025-03-04 11:31:59,563 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 23 statements into 1 equivalence classes. [2025-03-04 11:31:59,592 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 23 of 23 statements. [2025-03-04 11:31:59,593 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 11:31:59,593 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 11:31:59,596 INFO L256 TraceCheckSpWp]: Trace formula consists of 193 conjuncts, 15 conjuncts are in the unsatisfiable core [2025-03-04 11:31:59,599 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-04 11:31:59,601 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-03-04 11:31:59,675 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-04 11:31:59,675 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-04 11:31:59,675 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-04 11:31:59,675 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1275914746] [2025-03-04 11:31:59,675 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-04 11:31:59,675 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [576904604] [2025-03-04 11:31:59,675 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [576904604] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-04 11:31:59,675 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-04 11:31:59,675 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2025-03-04 11:31:59,675 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [414286048] [2025-03-04 11:31:59,676 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-04 11:31:59,676 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2025-03-04 11:31:59,676 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-04 11:31:59,676 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2025-03-04 11:31:59,676 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=14, Invalid=28, Unknown=0, NotChecked=0, Total=42 [2025-03-04 11:31:59,676 INFO L87 Difference]: Start difference. First operand 1469 states and 2293 transitions. Second operand has 7 states, 5 states have (on average 3.6) internal successors, (18), 6 states have internal predecessors, (18), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-03-04 11:31:59,888 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-04 11:31:59,889 INFO L93 Difference]: Finished difference Result 1755 states and 2365 transitions. [2025-03-04 11:31:59,889 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2025-03-04 11:31:59,889 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 5 states have (on average 3.6) internal successors, (18), 6 states have internal predecessors, (18), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 23 [2025-03-04 11:31:59,889 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-04 11:31:59,896 INFO L225 Difference]: With dead ends: 1755 [2025-03-04 11:31:59,896 INFO L226 Difference]: Without dead ends: 1754 [2025-03-04 11:31:59,897 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 24 GetRequests, 14 SyntacticMatches, 3 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=26, Invalid=46, Unknown=0, NotChecked=0, Total=72 [2025-03-04 11:31:59,897 INFO L435 NwaCegarLoop]: 524 mSDtfsCounter, 893 mSDsluCounter, 2599 mSDsCounter, 0 mSdLazyCounter, 244 mSolverCounterSat, 20 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 895 SdHoareTripleChecker+Valid, 3123 SdHoareTripleChecker+Invalid, 264 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 20 IncrementalHoareTripleChecker+Valid, 244 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-03-04 11:31:59,898 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [895 Valid, 3123 Invalid, 264 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [20 Valid, 244 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-03-04 11:31:59,900 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1754 states. [2025-03-04 11:31:59,936 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1754 to 1469. [2025-03-04 11:31:59,938 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1469 states, 1146 states have (on average 1.899650959860384) internal successors, (2177), 1407 states have internal predecessors, (2177), 46 states have call successors, (46), 13 states have call predecessors, (46), 20 states have return successors, (66), 48 states have call predecessors, (66), 46 states have call successors, (66) [2025-03-04 11:31:59,942 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1469 states to 1469 states and 2289 transitions. [2025-03-04 11:31:59,943 INFO L78 Accepts]: Start accepts. Automaton has 1469 states and 2289 transitions. Word has length 23 [2025-03-04 11:31:59,943 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-04 11:31:59,943 INFO L471 AbstractCegarLoop]: Abstraction has 1469 states and 2289 transitions. [2025-03-04 11:31:59,943 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 5 states have (on average 3.6) internal successors, (18), 6 states have internal predecessors, (18), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-03-04 11:31:59,943 INFO L276 IsEmpty]: Start isEmpty. Operand 1469 states and 2289 transitions. [2025-03-04 11:31:59,944 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2025-03-04 11:31:59,944 INFO L210 NwaCegarLoop]: Found error trace [2025-03-04 11:31:59,944 INFO L218 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-04 11:31:59,950 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2025-03-04 11:32:00,144 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-04 11:32:00,145 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting func_to_recursive_line_36_to_52_0Err182ASSERT_VIOLATIONINTEGER_OVERFLOW === [func_to_recursive_line_36_to_52_0Err0ASSERT_VIOLATIONINTEGER_OVERFLOW, func_to_recursive_line_36_to_52_0Err1ASSERT_VIOLATIONINTEGER_OVERFLOW (and 256 more)] === [2025-03-04 11:32:00,145 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 11:32:00,145 INFO L85 PathProgramCache]: Analyzing trace with hash -1715949040, now seen corresponding path program 1 times [2025-03-04 11:32:00,145 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-04 11:32:00,146 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [789689647] [2025-03-04 11:32:00,146 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-04 11:32:00,146 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-04 11:32:00,152 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 23 statements into 1 equivalence classes. [2025-03-04 11:32:00,161 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 23 of 23 statements. [2025-03-04 11:32:00,161 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 11:32:00,161 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 11:32:00,437 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2025-03-04 11:32:00,437 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-04 11:32:00,437 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [789689647] [2025-03-04 11:32:00,437 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [789689647] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-04 11:32:00,437 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [520515860] [2025-03-04 11:32:00,437 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-04 11:32:00,437 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-04 11:32:00,437 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 11:32:00,439 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-04 11:32:00,441 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2025-03-04 11:32:00,494 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 23 statements into 1 equivalence classes. [2025-03-04 11:32:00,512 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 23 of 23 statements. [2025-03-04 11:32:00,512 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 11:32:00,512 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 11:32:00,513 INFO L256 TraceCheckSpWp]: Trace formula consists of 211 conjuncts, 50 conjuncts are in the unsatisfiable core [2025-03-04 11:32:00,515 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-04 11:32:00,530 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-03-04 11:32:00,536 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-03-04 11:32:00,685 WARN L873 $PredicateComparison]: unable to prove that (and (exists ((|v_func_to_recursive_line_28_to_32_0_#t~mem98_20| Int)) (let ((.cse0 (select |c_old(#memory_int#5)| |c_func_to_recursive_line_28_to_32_0_#in~q.base|))) (and (= |c_#memory_int#5| (store |c_old(#memory_int#5)| |c_func_to_recursive_line_28_to_32_0_#in~q.base| (store .cse0 |c_func_to_recursive_line_28_to_32_0_#in~q.offset| (* |v_func_to_recursive_line_28_to_32_0_#t~mem98_20| 4)))) (<= |v_func_to_recursive_line_28_to_32_0_#t~mem98_20| (select .cse0 |c_func_to_recursive_line_28_to_32_0_#in~q.offset|))))) (exists ((|v_ULTIMATE.start_main_~#p~0#1.offset_BEFORE_CALL_8| Int) (|v_ULTIMATE.start_main_~#p~0#1.base_BEFORE_CALL_8| Int)) (= (select (select |c_#memory_int#2| |v_ULTIMATE.start_main_~#p~0#1.base_BEFORE_CALL_8|) |v_ULTIMATE.start_main_~#p~0#1.offset_BEFORE_CALL_8|) 0))) is different from true [2025-03-04 11:32:00,705 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 21 treesize of output 13 [2025-03-04 11:32:00,834 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 26 treesize of output 14 [2025-03-04 11:32:00,854 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 2 not checked. [2025-03-04 11:32:00,854 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-04 11:32:01,121 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [520515860] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-04 11:32:01,121 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-04 11:32:01,121 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 22 [2025-03-04 11:32:01,121 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1364177292] [2025-03-04 11:32:01,121 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-04 11:32:01,122 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2025-03-04 11:32:01,122 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-04 11:32:01,122 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2025-03-04 11:32:01,122 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=97, Invalid=718, Unknown=1, NotChecked=54, Total=870 [2025-03-04 11:32:01,123 INFO L87 Difference]: Start difference. First operand 1469 states and 2289 transitions. Second operand has 23 states, 17 states have (on average 2.0) internal successors, (34), 19 states have internal predecessors, (34), 5 states have call successors, (6), 4 states have call predecessors, (6), 4 states have return successors, (4), 4 states have call predecessors, (4), 3 states have call successors, (4) [2025-03-04 11:32:03,064 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-04 11:32:03,065 INFO L93 Difference]: Finished difference Result 2080 states and 2523 transitions. [2025-03-04 11:32:03,065 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2025-03-04 11:32:03,065 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 17 states have (on average 2.0) internal successors, (34), 19 states have internal predecessors, (34), 5 states have call successors, (6), 4 states have call predecessors, (6), 4 states have return successors, (4), 4 states have call predecessors, (4), 3 states have call successors, (4) Word has length 23 [2025-03-04 11:32:03,066 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-04 11:32:03,073 INFO L225 Difference]: With dead ends: 2080 [2025-03-04 11:32:03,073 INFO L226 Difference]: Without dead ends: 2079 [2025-03-04 11:32:03,074 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 56 GetRequests, 18 SyntacticMatches, 1 SemanticMatches, 37 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 263 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=220, Invalid=1189, Unknown=1, NotChecked=72, Total=1482 [2025-03-04 11:32:03,075 INFO L435 NwaCegarLoop]: 971 mSDtfsCounter, 2850 mSDsluCounter, 13240 mSDsCounter, 0 mSdLazyCounter, 2370 mSolverCounterSat, 78 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2860 SdHoareTripleChecker+Valid, 14211 SdHoareTripleChecker+Invalid, 4083 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 78 IncrementalHoareTripleChecker+Valid, 2370 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 1635 IncrementalHoareTripleChecker+Unchecked, 1.5s IncrementalHoareTripleChecker+Time [2025-03-04 11:32:03,075 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [2860 Valid, 14211 Invalid, 4083 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [78 Valid, 2370 Invalid, 0 Unknown, 1635 Unchecked, 1.5s Time] [2025-03-04 11:32:03,078 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2079 states. [2025-03-04 11:32:03,110 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2079 to 1531. [2025-03-04 11:32:03,112 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1531 states, 1203 states have (on average 1.8985868661679135) internal successors, (2284), 1465 states have internal predecessors, (2284), 49 states have call successors, (49), 14 states have call predecessors, (49), 22 states have return successors, (71), 51 states have call predecessors, (71), 49 states have call successors, (71) [2025-03-04 11:32:03,116 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1531 states to 1531 states and 2404 transitions. [2025-03-04 11:32:03,117 INFO L78 Accepts]: Start accepts. Automaton has 1531 states and 2404 transitions. Word has length 23 [2025-03-04 11:32:03,117 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-04 11:32:03,117 INFO L471 AbstractCegarLoop]: Abstraction has 1531 states and 2404 transitions. [2025-03-04 11:32:03,117 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 17 states have (on average 2.0) internal successors, (34), 19 states have internal predecessors, (34), 5 states have call successors, (6), 4 states have call predecessors, (6), 4 states have return successors, (4), 4 states have call predecessors, (4), 3 states have call successors, (4) [2025-03-04 11:32:03,118 INFO L276 IsEmpty]: Start isEmpty. Operand 1531 states and 2404 transitions. [2025-03-04 11:32:03,118 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2025-03-04 11:32:03,118 INFO L210 NwaCegarLoop]: Found error trace [2025-03-04 11:32:03,118 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-04 11:32:03,124 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2025-03-04 11:32:03,323 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-04 11:32:03,323 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting func_to_recursive_line_36_to_52_0Err179ASSERT_VIOLATIONINTEGER_OVERFLOW === [func_to_recursive_line_36_to_52_0Err0ASSERT_VIOLATIONINTEGER_OVERFLOW, func_to_recursive_line_36_to_52_0Err1ASSERT_VIOLATIONINTEGER_OVERFLOW (and 256 more)] === [2025-03-04 11:32:03,323 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 11:32:03,323 INFO L85 PathProgramCache]: Analyzing trace with hash -1716856445, now seen corresponding path program 1 times [2025-03-04 11:32:03,323 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-04 11:32:03,323 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1180686064] [2025-03-04 11:32:03,323 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-04 11:32:03,323 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-04 11:32:03,333 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 24 statements into 1 equivalence classes. [2025-03-04 11:32:03,342 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 24 of 24 statements. [2025-03-04 11:32:03,342 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 11:32:03,342 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-04 11:32:03,344 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2082920023] [2025-03-04 11:32:03,344 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-04 11:32:03,344 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-04 11:32:03,344 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 11:32:03,346 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-04 11:32:03,348 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2025-03-04 11:32:03,405 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 24 statements into 1 equivalence classes. [2025-03-04 11:32:03,426 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 24 of 24 statements. [2025-03-04 11:32:03,426 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 11:32:03,426 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 11:32:03,432 INFO L256 TraceCheckSpWp]: Trace formula consists of 198 conjuncts, 58 conjuncts are in the unsatisfiable core [2025-03-04 11:32:03,434 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-04 11:32:03,439 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-03-04 11:32:03,442 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-03-04 11:32:03,453 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2025-03-04 11:32:03,743 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-04 11:32:03,744 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 33 treesize of output 29 [2025-03-04 11:32:03,767 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-04 11:32:03,767 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-04 11:32:03,767 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-04 11:32:03,767 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1180686064] [2025-03-04 11:32:03,767 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-04 11:32:03,767 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2082920023] [2025-03-04 11:32:03,767 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2082920023] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-04 11:32:03,767 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-04 11:32:03,767 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [12] imperfect sequences [] total 12 [2025-03-04 11:32:03,768 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [129379373] [2025-03-04 11:32:03,768 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-04 11:32:03,768 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2025-03-04 11:32:03,768 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-04 11:32:03,768 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2025-03-04 11:32:03,768 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=32, Invalid=124, Unknown=0, NotChecked=0, Total=156 [2025-03-04 11:32:03,769 INFO L87 Difference]: Start difference. First operand 1531 states and 2404 transitions. Second operand has 13 states, 11 states have (on average 1.7272727272727273) internal successors, (19), 11 states have internal predecessors, (19), 2 states have call successors, (3), 3 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-03-04 11:32:04,739 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-04 11:32:04,739 INFO L93 Difference]: Finished difference Result 1810 states and 2471 transitions. [2025-03-04 11:32:04,741 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2025-03-04 11:32:04,741 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 11 states have (on average 1.7272727272727273) internal successors, (19), 11 states have internal predecessors, (19), 2 states have call successors, (3), 3 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 24 [2025-03-04 11:32:04,741 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-04 11:32:04,746 INFO L225 Difference]: With dead ends: 1810 [2025-03-04 11:32:04,746 INFO L226 Difference]: Without dead ends: 1809 [2025-03-04 11:32:04,746 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 33 GetRequests, 11 SyntacticMatches, 1 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 41 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=121, Invalid=385, Unknown=0, NotChecked=0, Total=506 [2025-03-04 11:32:04,747 INFO L435 NwaCegarLoop]: 477 mSDtfsCounter, 2069 mSDsluCounter, 3481 mSDsCounter, 0 mSdLazyCounter, 781 mSolverCounterSat, 52 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2071 SdHoareTripleChecker+Valid, 3958 SdHoareTripleChecker+Invalid, 833 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 52 IncrementalHoareTripleChecker+Valid, 781 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2025-03-04 11:32:04,747 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [2071 Valid, 3958 Invalid, 833 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [52 Valid, 781 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2025-03-04 11:32:04,748 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1809 states. [2025-03-04 11:32:04,782 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1809 to 1535. [2025-03-04 11:32:04,783 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1535 states, 1206 states have (on average 1.8955223880597014) internal successors, (2286), 1468 states have internal predecessors, (2286), 49 states have call successors, (49), 15 states have call predecessors, (49), 23 states have return successors, (71), 51 states have call predecessors, (71), 49 states have call successors, (71) [2025-03-04 11:32:04,789 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1535 states to 1535 states and 2406 transitions. [2025-03-04 11:32:04,789 INFO L78 Accepts]: Start accepts. Automaton has 1535 states and 2406 transitions. Word has length 24 [2025-03-04 11:32:04,789 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-04 11:32:04,789 INFO L471 AbstractCegarLoop]: Abstraction has 1535 states and 2406 transitions. [2025-03-04 11:32:04,789 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 11 states have (on average 1.7272727272727273) internal successors, (19), 11 states have internal predecessors, (19), 2 states have call successors, (3), 3 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-03-04 11:32:04,789 INFO L276 IsEmpty]: Start isEmpty. Operand 1535 states and 2406 transitions. [2025-03-04 11:32:04,790 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2025-03-04 11:32:04,790 INFO L210 NwaCegarLoop]: Found error trace [2025-03-04 11:32:04,790 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] [2025-03-04 11:32:04,796 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2025-03-04 11:32:04,990 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-04 11:32:04,990 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting func_to_recursive_line_36_to_52_0Err178ASSERT_VIOLATIONINTEGER_OVERFLOW === [func_to_recursive_line_36_to_52_0Err0ASSERT_VIOLATIONINTEGER_OVERFLOW, func_to_recursive_line_36_to_52_0Err1ASSERT_VIOLATIONINTEGER_OVERFLOW (and 256 more)] === [2025-03-04 11:32:04,991 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 11:32:04,991 INFO L85 PathProgramCache]: Analyzing trace with hash -1682941900, now seen corresponding path program 1 times [2025-03-04 11:32:04,991 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-04 11:32:04,991 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [259725612] [2025-03-04 11:32:04,991 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-04 11:32:04,991 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-04 11:32:04,998 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 25 statements into 1 equivalence classes. [2025-03-04 11:32:05,005 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 25 of 25 statements. [2025-03-04 11:32:05,006 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 11:32:05,006 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-04 11:32:05,007 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [836865454] [2025-03-04 11:32:05,007 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-04 11:32:05,007 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-04 11:32:05,007 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 11:32:05,009 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-04 11:32:05,011 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2025-03-04 11:32:05,069 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 25 statements into 1 equivalence classes. [2025-03-04 11:32:05,089 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 25 of 25 statements. [2025-03-04 11:32:05,089 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 11:32:05,089 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 11:32:05,091 INFO L256 TraceCheckSpWp]: Trace formula consists of 199 conjuncts, 50 conjuncts are in the unsatisfiable core [2025-03-04 11:32:05,092 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-04 11:32:05,099 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2025-03-04 11:32:05,102 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2025-03-04 11:32:05,105 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-03-04 11:32:05,198 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-04 11:32:05,199 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 30 treesize of output 30 [2025-03-04 11:32:05,321 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-04 11:32:05,340 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-04 11:32:05,340 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-04 11:32:05,340 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-04 11:32:05,340 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [259725612] [2025-03-04 11:32:05,340 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-04 11:32:05,340 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [836865454] [2025-03-04 11:32:05,340 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [836865454] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-04 11:32:05,340 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-04 11:32:05,340 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [11] imperfect sequences [] total 11 [2025-03-04 11:32:05,340 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1182772956] [2025-03-04 11:32:05,340 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-04 11:32:05,341 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2025-03-04 11:32:05,341 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-04 11:32:05,341 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2025-03-04 11:32:05,341 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=105, Unknown=0, NotChecked=0, Total=132 [2025-03-04 11:32:05,341 INFO L87 Difference]: Start difference. First operand 1535 states and 2406 transitions. Second operand has 12 states, 9 states have (on average 2.2222222222222223) internal successors, (20), 9 states have internal predecessors, (20), 3 states have call successors, (3), 3 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-03-04 11:32:09,473 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.02s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2025-03-04 11:32:13,558 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2025-03-04 11:32:17,645 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2025-03-04 11:32:21,699 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.02s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2025-03-04 11:32:25,749 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2025-03-04 11:32:29,815 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2025-03-04 11:32:33,877 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2025-03-04 11:32:38,025 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2025-03-04 11:32:42,178 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2025-03-04 11:32:46,303 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2025-03-04 11:32:50,364 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2025-03-04 11:32:54,429 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2025-03-04 11:32:58,485 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2025-03-04 11:33:02,550 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.02s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2025-03-04 11:33:06,611 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2025-03-04 11:33:06,634 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-04 11:33:06,634 INFO L93 Difference]: Finished difference Result 1809 states and 2470 transitions. [2025-03-04 11:33:06,634 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2025-03-04 11:33:06,634 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 9 states have (on average 2.2222222222222223) internal successors, (20), 9 states have internal predecessors, (20), 3 states have call successors, (3), 3 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 25 [2025-03-04 11:33:06,635 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-04 11:33:06,639 INFO L225 Difference]: With dead ends: 1809 [2025-03-04 11:33:06,639 INFO L226 Difference]: Without dead ends: 1808 [2025-03-04 11:33:06,640 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 31 GetRequests, 13 SyntacticMatches, 1 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 43 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=70, Invalid=272, Unknown=0, NotChecked=0, Total=342 [2025-03-04 11:33:06,641 INFO L435 NwaCegarLoop]: 489 mSDtfsCounter, 1357 mSDsluCounter, 4169 mSDsCounter, 0 mSdLazyCounter, 809 mSolverCounterSat, 35 mSolverCounterUnsat, 15 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 60.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1359 SdHoareTripleChecker+Valid, 4658 SdHoareTripleChecker+Invalid, 859 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 35 IncrementalHoareTripleChecker+Valid, 809 IncrementalHoareTripleChecker+Invalid, 15 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 61.1s IncrementalHoareTripleChecker+Time [2025-03-04 11:33:06,641 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [1359 Valid, 4658 Invalid, 859 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [35 Valid, 809 Invalid, 15 Unknown, 0 Unchecked, 61.1s Time] [2025-03-04 11:33:06,642 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1808 states. [2025-03-04 11:33:06,673 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1808 to 1535. [2025-03-04 11:33:06,675 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1535 states, 1206 states have (on average 1.89469320066335) internal successors, (2285), 1468 states have internal predecessors, (2285), 49 states have call successors, (49), 15 states have call predecessors, (49), 23 states have return successors, (71), 51 states have call predecessors, (71), 49 states have call successors, (71) [2025-03-04 11:33:06,678 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1535 states to 1535 states and 2405 transitions. [2025-03-04 11:33:06,679 INFO L78 Accepts]: Start accepts. Automaton has 1535 states and 2405 transitions. Word has length 25 [2025-03-04 11:33:06,679 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-04 11:33:06,679 INFO L471 AbstractCegarLoop]: Abstraction has 1535 states and 2405 transitions. [2025-03-04 11:33:06,679 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 9 states have (on average 2.2222222222222223) internal successors, (20), 9 states have internal predecessors, (20), 3 states have call successors, (3), 3 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-03-04 11:33:06,679 INFO L276 IsEmpty]: Start isEmpty. Operand 1535 states and 2405 transitions. [2025-03-04 11:33:06,680 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2025-03-04 11:33:06,681 INFO L210 NwaCegarLoop]: Found error trace [2025-03-04 11:33:06,681 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] [2025-03-04 11:33:06,693 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2025-03-04 11:33:06,881 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2025-03-04 11:33:06,882 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting func_to_recursive_line_36_to_52_0Err177ASSERT_VIOLATIONINTEGER_OVERFLOW === [func_to_recursive_line_36_to_52_0Err0ASSERT_VIOLATIONINTEGER_OVERFLOW, func_to_recursive_line_36_to_52_0Err1ASSERT_VIOLATIONINTEGER_OVERFLOW (and 256 more)] === [2025-03-04 11:33:06,882 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 11:33:06,883 INFO L85 PathProgramCache]: Analyzing trace with hash -631591007, now seen corresponding path program 1 times [2025-03-04 11:33:06,883 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-04 11:33:06,883 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1666974876] [2025-03-04 11:33:06,883 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-04 11:33:06,883 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-04 11:33:06,891 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 26 statements into 1 equivalence classes. [2025-03-04 11:33:06,897 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 26 of 26 statements. [2025-03-04 11:33:06,897 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 11:33:06,898 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-04 11:33:06,898 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [548728129] [2025-03-04 11:33:06,898 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-04 11:33:06,898 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-04 11:33:06,898 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 11:33:06,900 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-04 11:33:06,902 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2025-03-04 11:33:06,957 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 26 statements into 1 equivalence classes. [2025-03-04 11:33:06,980 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 26 of 26 statements. [2025-03-04 11:33:06,980 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 11:33:06,980 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 11:33:06,981 INFO L256 TraceCheckSpWp]: Trace formula consists of 200 conjuncts, 16 conjuncts are in the unsatisfiable core [2025-03-04 11:33:06,982 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-04 11:33:06,985 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-03-04 11:33:07,079 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-04 11:33:07,079 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-04 11:33:07,079 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-04 11:33:07,079 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1666974876] [2025-03-04 11:33:07,079 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-04 11:33:07,079 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [548728129] [2025-03-04 11:33:07,079 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [548728129] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-04 11:33:07,080 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-04 11:33:07,080 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2025-03-04 11:33:07,080 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [499762362] [2025-03-04 11:33:07,080 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-04 11:33:07,080 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2025-03-04 11:33:07,080 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-04 11:33:07,080 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2025-03-04 11:33:07,080 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2025-03-04 11:33:07,080 INFO L87 Difference]: Start difference. First operand 1535 states and 2405 transitions. Second operand has 8 states, 6 states have (on average 3.5) internal successors, (21), 7 states have internal predecessors, (21), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-03-04 11:33:07,347 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-04 11:33:07,347 INFO L93 Difference]: Finished difference Result 1820 states and 2477 transitions. [2025-03-04 11:33:07,347 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2025-03-04 11:33:07,348 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 6 states have (on average 3.5) internal successors, (21), 7 states have internal predecessors, (21), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 26 [2025-03-04 11:33:07,348 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-04 11:33:07,353 INFO L225 Difference]: With dead ends: 1820 [2025-03-04 11:33:07,353 INFO L226 Difference]: Without dead ends: 1819 [2025-03-04 11:33:07,354 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 28 GetRequests, 16 SyntacticMatches, 3 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 13 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=38, Invalid=72, Unknown=0, NotChecked=0, Total=110 [2025-03-04 11:33:07,354 INFO L435 NwaCegarLoop]: 523 mSDtfsCounter, 1402 mSDsluCounter, 1698 mSDsCounter, 0 mSdLazyCounter, 203 mSolverCounterSat, 22 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1404 SdHoareTripleChecker+Valid, 2221 SdHoareTripleChecker+Invalid, 225 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 22 IncrementalHoareTripleChecker+Valid, 203 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-03-04 11:33:07,355 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [1404 Valid, 2221 Invalid, 225 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [22 Valid, 203 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-03-04 11:33:07,356 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1819 states. [2025-03-04 11:33:07,386 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1819 to 1535. [2025-03-04 11:33:07,387 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1535 states, 1206 states have (on average 1.8913764510779436) internal successors, (2281), 1468 states have internal predecessors, (2281), 49 states have call successors, (49), 15 states have call predecessors, (49), 23 states have return successors, (71), 51 states have call predecessors, (71), 49 states have call successors, (71) [2025-03-04 11:33:07,390 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1535 states to 1535 states and 2401 transitions. [2025-03-04 11:33:07,390 INFO L78 Accepts]: Start accepts. Automaton has 1535 states and 2401 transitions. Word has length 26 [2025-03-04 11:33:07,391 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-04 11:33:07,391 INFO L471 AbstractCegarLoop]: Abstraction has 1535 states and 2401 transitions. [2025-03-04 11:33:07,392 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 6 states have (on average 3.5) internal successors, (21), 7 states have internal predecessors, (21), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-03-04 11:33:07,392 INFO L276 IsEmpty]: Start isEmpty. Operand 1535 states and 2401 transitions. [2025-03-04 11:33:07,392 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2025-03-04 11:33:07,392 INFO L210 NwaCegarLoop]: Found error trace [2025-03-04 11:33:07,392 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-04 11:33:07,399 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2025-03-04 11:33:07,593 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11,10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-04 11:33:07,593 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting func_to_recursive_line_36_to_52_0Err176ASSERT_VIOLATIONINTEGER_OVERFLOW === [func_to_recursive_line_36_to_52_0Err0ASSERT_VIOLATIONINTEGER_OVERFLOW, func_to_recursive_line_36_to_52_0Err1ASSERT_VIOLATIONINTEGER_OVERFLOW (and 256 more)] === [2025-03-04 11:33:07,593 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 11:33:07,593 INFO L85 PathProgramCache]: Analyzing trace with hash 1895515602, now seen corresponding path program 1 times [2025-03-04 11:33:07,594 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-04 11:33:07,594 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1065321397] [2025-03-04 11:33:07,594 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-04 11:33:07,594 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-04 11:33:07,599 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 27 statements into 1 equivalence classes. [2025-03-04 11:33:07,606 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 27 of 27 statements. [2025-03-04 11:33:07,606 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 11:33:07,606 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-04 11:33:07,607 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1336975970] [2025-03-04 11:33:07,607 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-04 11:33:07,607 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-04 11:33:07,608 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 11:33:07,609 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-04 11:33:07,611 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2025-03-04 11:33:07,668 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 27 statements into 1 equivalence classes. [2025-03-04 11:33:07,686 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 27 of 27 statements. [2025-03-04 11:33:07,686 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 11:33:07,687 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 11:33:07,688 INFO L256 TraceCheckSpWp]: Trace formula consists of 201 conjuncts, 48 conjuncts are in the unsatisfiable core [2025-03-04 11:33:07,689 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-04 11:33:07,694 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-03-04 11:33:07,696 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-03-04 11:33:07,943 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-04 11:33:07,978 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-04 11:33:07,978 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-04 11:33:07,978 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-04 11:33:07,978 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1065321397] [2025-03-04 11:33:07,978 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-04 11:33:07,978 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1336975970] [2025-03-04 11:33:07,978 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1336975970] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-04 11:33:07,978 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-04 11:33:07,978 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [13] imperfect sequences [] total 13 [2025-03-04 11:33:07,978 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1718068965] [2025-03-04 11:33:07,978 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-04 11:33:07,978 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2025-03-04 11:33:07,978 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-04 11:33:07,979 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2025-03-04 11:33:07,979 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=37, Invalid=145, Unknown=0, NotChecked=0, Total=182 [2025-03-04 11:33:07,979 INFO L87 Difference]: Start difference. First operand 1535 states and 2401 transitions. Second operand has 14 states, 12 states have (on average 1.8333333333333333) internal successors, (22), 11 states have internal predecessors, (22), 2 states have call successors, (3), 3 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-03-04 11:33:08,893 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-04 11:33:08,893 INFO L93 Difference]: Finished difference Result 1807 states and 2465 transitions. [2025-03-04 11:33:08,893 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2025-03-04 11:33:08,893 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 12 states have (on average 1.8333333333333333) internal successors, (22), 11 states have internal predecessors, (22), 2 states have call successors, (3), 3 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 27 [2025-03-04 11:33:08,893 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-04 11:33:08,904 INFO L225 Difference]: With dead ends: 1807 [2025-03-04 11:33:08,904 INFO L226 Difference]: Without dead ends: 1806 [2025-03-04 11:33:08,905 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 37 GetRequests, 13 SyntacticMatches, 1 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 70 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=140, Invalid=460, Unknown=0, NotChecked=0, Total=600 [2025-03-04 11:33:08,905 INFO L435 NwaCegarLoop]: 483 mSDtfsCounter, 2067 mSDsluCounter, 4154 mSDsCounter, 0 mSdLazyCounter, 876 mSolverCounterSat, 51 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2069 SdHoareTripleChecker+Valid, 4637 SdHoareTripleChecker+Invalid, 927 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 51 IncrementalHoareTripleChecker+Valid, 876 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2025-03-04 11:33:08,905 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [2069 Valid, 4637 Invalid, 927 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [51 Valid, 876 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2025-03-04 11:33:08,906 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1806 states. [2025-03-04 11:33:08,933 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1806 to 1535. [2025-03-04 11:33:08,934 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1535 states, 1206 states have (on average 1.890547263681592) internal successors, (2280), 1468 states have internal predecessors, (2280), 49 states have call successors, (49), 15 states have call predecessors, (49), 23 states have return successors, (71), 51 states have call predecessors, (71), 49 states have call successors, (71) [2025-03-04 11:33:08,938 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1535 states to 1535 states and 2400 transitions. [2025-03-04 11:33:08,938 INFO L78 Accepts]: Start accepts. Automaton has 1535 states and 2400 transitions. Word has length 27 [2025-03-04 11:33:08,939 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-04 11:33:08,939 INFO L471 AbstractCegarLoop]: Abstraction has 1535 states and 2400 transitions. [2025-03-04 11:33:08,939 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 12 states have (on average 1.8333333333333333) internal successors, (22), 11 states have internal predecessors, (22), 2 states have call successors, (3), 3 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-03-04 11:33:08,939 INFO L276 IsEmpty]: Start isEmpty. Operand 1535 states and 2400 transitions. [2025-03-04 11:33:08,940 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2025-03-04 11:33:08,940 INFO L210 NwaCegarLoop]: Found error trace [2025-03-04 11:33:08,940 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] [2025-03-04 11:33:08,946 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2025-03-04 11:33:09,141 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2025-03-04 11:33:09,141 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting func_to_recursive_line_36_to_52_0Err175ASSERT_VIOLATIONINTEGER_OVERFLOW === [func_to_recursive_line_36_to_52_0Err0ASSERT_VIOLATIONINTEGER_OVERFLOW, func_to_recursive_line_36_to_52_0Err1ASSERT_VIOLATIONINTEGER_OVERFLOW (and 256 more)] === [2025-03-04 11:33:09,142 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 11:33:09,142 INFO L85 PathProgramCache]: Analyzing trace with hash -1368558145, now seen corresponding path program 1 times [2025-03-04 11:33:09,142 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-04 11:33:09,142 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [228703731] [2025-03-04 11:33:09,142 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-04 11:33:09,142 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-04 11:33:09,150 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 28 statements into 1 equivalence classes. [2025-03-04 11:33:09,157 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 28 of 28 statements. [2025-03-04 11:33:09,158 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 11:33:09,158 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-04 11:33:09,159 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1459078824] [2025-03-04 11:33:09,159 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-04 11:33:09,159 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-04 11:33:09,159 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 11:33:09,161 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-04 11:33:09,163 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2025-03-04 11:33:09,220 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 28 statements into 1 equivalence classes. [2025-03-04 11:33:09,239 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 28 of 28 statements. [2025-03-04 11:33:09,239 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 11:33:09,239 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 11:33:09,241 INFO L256 TraceCheckSpWp]: Trace formula consists of 206 conjuncts, 37 conjuncts are in the unsatisfiable core [2025-03-04 11:33:09,243 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-04 11:33:09,250 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-03-04 11:33:09,255 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2025-03-04 11:33:09,396 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 17 treesize of output 9 [2025-03-04 11:33:09,409 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-04 11:33:09,409 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-04 11:33:09,409 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-04 11:33:09,409 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [228703731] [2025-03-04 11:33:09,409 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-04 11:33:09,409 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1459078824] [2025-03-04 11:33:09,409 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1459078824] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-04 11:33:09,409 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-04 11:33:09,410 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2025-03-04 11:33:09,410 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [31549232] [2025-03-04 11:33:09,410 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-04 11:33:09,410 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2025-03-04 11:33:09,411 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-04 11:33:09,411 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2025-03-04 11:33:09,411 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=16, Invalid=40, Unknown=0, NotChecked=0, Total=56 [2025-03-04 11:33:09,411 INFO L87 Difference]: Start difference. First operand 1535 states and 2400 transitions. Second operand has 8 states, 6 states have (on average 3.8333333333333335) internal successors, (23), 7 states have internal predecessors, (23), 2 states have call successors, (3), 3 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-03-04 11:33:09,819 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-04 11:33:09,819 INFO L93 Difference]: Finished difference Result 1806 states and 2464 transitions. [2025-03-04 11:33:09,819 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2025-03-04 11:33:09,819 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 6 states have (on average 3.8333333333333335) internal successors, (23), 7 states have internal predecessors, (23), 2 states have call successors, (3), 3 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 28 [2025-03-04 11:33:09,819 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-04 11:33:09,823 INFO L225 Difference]: With dead ends: 1806 [2025-03-04 11:33:09,823 INFO L226 Difference]: Without dead ends: 1805 [2025-03-04 11:33:09,824 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 31 GetRequests, 19 SyntacticMatches, 2 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=44, Invalid=88, Unknown=0, NotChecked=0, Total=132 [2025-03-04 11:33:09,824 INFO L435 NwaCegarLoop]: 503 mSDtfsCounter, 1208 mSDsluCounter, 3010 mSDsCounter, 0 mSdLazyCounter, 433 mSolverCounterSat, 36 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1210 SdHoareTripleChecker+Valid, 3513 SdHoareTripleChecker+Invalid, 469 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 36 IncrementalHoareTripleChecker+Valid, 433 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2025-03-04 11:33:09,824 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [1210 Valid, 3513 Invalid, 469 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [36 Valid, 433 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2025-03-04 11:33:09,832 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1805 states. [2025-03-04 11:33:09,853 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1805 to 1535. [2025-03-04 11:33:09,854 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1535 states, 1206 states have (on average 1.8897180762852404) internal successors, (2279), 1468 states have internal predecessors, (2279), 49 states have call successors, (49), 15 states have call predecessors, (49), 23 states have return successors, (71), 51 states have call predecessors, (71), 49 states have call successors, (71) [2025-03-04 11:33:09,856 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1535 states to 1535 states and 2399 transitions. [2025-03-04 11:33:09,856 INFO L78 Accepts]: Start accepts. Automaton has 1535 states and 2399 transitions. Word has length 28 [2025-03-04 11:33:09,856 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-04 11:33:09,857 INFO L471 AbstractCegarLoop]: Abstraction has 1535 states and 2399 transitions. [2025-03-04 11:33:09,857 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 6 states have (on average 3.8333333333333335) internal successors, (23), 7 states have internal predecessors, (23), 2 states have call successors, (3), 3 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-03-04 11:33:09,857 INFO L276 IsEmpty]: Start isEmpty. Operand 1535 states and 2399 transitions. [2025-03-04 11:33:09,857 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2025-03-04 11:33:09,857 INFO L210 NwaCegarLoop]: Found error trace [2025-03-04 11:33:09,857 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] [2025-03-04 11:33:09,863 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2025-03-04 11:33:10,061 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2025-03-04 11:33:10,061 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting func_to_recursive_line_36_to_52_0Err174ASSERT_VIOLATIONINTEGER_OVERFLOW === [func_to_recursive_line_36_to_52_0Err0ASSERT_VIOLATIONINTEGER_OVERFLOW, func_to_recursive_line_36_to_52_0Err1ASSERT_VIOLATIONINTEGER_OVERFLOW (and 256 more)] === [2025-03-04 11:33:10,061 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 11:33:10,061 INFO L85 PathProgramCache]: Analyzing trace with hash 524370800, now seen corresponding path program 1 times [2025-03-04 11:33:10,061 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-04 11:33:10,061 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [163476231] [2025-03-04 11:33:10,061 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-04 11:33:10,061 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-04 11:33:10,067 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 29 statements into 1 equivalence classes. [2025-03-04 11:33:10,073 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 29 of 29 statements. [2025-03-04 11:33:10,073 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 11:33:10,073 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-04 11:33:10,074 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [317902771] [2025-03-04 11:33:10,074 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-04 11:33:10,074 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-04 11:33:10,074 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 11:33:10,098 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-04 11:33:10,106 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2025-03-04 11:33:10,161 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 29 statements into 1 equivalence classes. [2025-03-04 11:33:10,181 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 29 of 29 statements. [2025-03-04 11:33:10,181 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 11:33:10,181 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 11:33:10,182 INFO L256 TraceCheckSpWp]: Trace formula consists of 207 conjuncts, 67 conjuncts are in the unsatisfiable core [2025-03-04 11:33:10,184 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-04 11:33:10,186 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-03-04 11:33:10,189 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2025-03-04 11:33:10,194 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-03-04 11:33:10,198 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2025-03-04 11:33:10,284 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 19 treesize of output 11 [2025-03-04 11:33:10,434 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-04 11:33:10,451 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-04 11:33:10,451 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-04 11:33:10,451 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-04 11:33:10,453 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [163476231] [2025-03-04 11:33:10,453 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-04 11:33:10,453 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [317902771] [2025-03-04 11:33:10,453 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [317902771] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-04 11:33:10,453 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-04 11:33:10,453 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [12] imperfect sequences [] total 12 [2025-03-04 11:33:10,453 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [408367987] [2025-03-04 11:33:10,453 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-04 11:33:10,453 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2025-03-04 11:33:10,454 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-04 11:33:10,454 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2025-03-04 11:33:10,454 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=32, Invalid=124, Unknown=0, NotChecked=0, Total=156 [2025-03-04 11:33:10,454 INFO L87 Difference]: Start difference. First operand 1535 states and 2399 transitions. Second operand has 13 states, 11 states have (on average 2.1818181818181817) internal successors, (24), 11 states have internal predecessors, (24), 2 states have call successors, (3), 3 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-03-04 11:33:11,504 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-04 11:33:11,505 INFO L93 Difference]: Finished difference Result 1805 states and 2463 transitions. [2025-03-04 11:33:11,505 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2025-03-04 11:33:11,505 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 11 states have (on average 2.1818181818181817) internal successors, (24), 11 states have internal predecessors, (24), 2 states have call successors, (3), 3 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 29 [2025-03-04 11:33:11,505 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-04 11:33:11,510 INFO L225 Difference]: With dead ends: 1805 [2025-03-04 11:33:11,510 INFO L226 Difference]: Without dead ends: 1804 [2025-03-04 11:33:11,511 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 38 GetRequests, 16 SyntacticMatches, 1 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 41 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=121, Invalid=385, Unknown=0, NotChecked=0, Total=506 [2025-03-04 11:33:11,511 INFO L435 NwaCegarLoop]: 472 mSDtfsCounter, 1557 mSDsluCounter, 4405 mSDsCounter, 0 mSdLazyCounter, 1015 mSolverCounterSat, 43 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1559 SdHoareTripleChecker+Valid, 4877 SdHoareTripleChecker+Invalid, 1058 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 43 IncrementalHoareTripleChecker+Valid, 1015 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.8s IncrementalHoareTripleChecker+Time [2025-03-04 11:33:11,511 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [1559 Valid, 4877 Invalid, 1058 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [43 Valid, 1015 Invalid, 0 Unknown, 0 Unchecked, 0.8s Time] [2025-03-04 11:33:11,512 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1804 states. [2025-03-04 11:33:11,542 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1804 to 1535. [2025-03-04 11:33:11,545 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1535 states, 1206 states have (on average 1.8888888888888888) internal successors, (2278), 1468 states have internal predecessors, (2278), 49 states have call successors, (49), 15 states have call predecessors, (49), 23 states have return successors, (71), 51 states have call predecessors, (71), 49 states have call successors, (71) [2025-03-04 11:33:11,549 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1535 states to 1535 states and 2398 transitions. [2025-03-04 11:33:11,550 INFO L78 Accepts]: Start accepts. Automaton has 1535 states and 2398 transitions. Word has length 29 [2025-03-04 11:33:11,550 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-04 11:33:11,550 INFO L471 AbstractCegarLoop]: Abstraction has 1535 states and 2398 transitions. [2025-03-04 11:33:11,550 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 11 states have (on average 2.1818181818181817) internal successors, (24), 11 states have internal predecessors, (24), 2 states have call successors, (3), 3 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-03-04 11:33:11,551 INFO L276 IsEmpty]: Start isEmpty. Operand 1535 states and 2398 transitions. [2025-03-04 11:33:11,552 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2025-03-04 11:33:11,552 INFO L210 NwaCegarLoop]: Found error trace [2025-03-04 11:33:11,552 INFO L218 NwaCegarLoop]: trace histogram [3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-04 11:33:11,570 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Forceful destruction successful, exit code 0 [2025-03-04 11:33:11,752 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2025-03-04 11:33:11,752 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting func_to_recursive_line_36_to_52_0Err182ASSERT_VIOLATIONINTEGER_OVERFLOW === [func_to_recursive_line_36_to_52_0Err0ASSERT_VIOLATIONINTEGER_OVERFLOW, func_to_recursive_line_36_to_52_0Err1ASSERT_VIOLATIONINTEGER_OVERFLOW (and 256 more)] === [2025-03-04 11:33:11,753 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 11:33:11,753 INFO L85 PathProgramCache]: Analyzing trace with hash 672758579, now seen corresponding path program 2 times [2025-03-04 11:33:11,753 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-04 11:33:11,753 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2005370515] [2025-03-04 11:33:11,753 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-04 11:33:11,753 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-04 11:33:11,762 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 31 statements into 2 equivalence classes. [2025-03-04 11:33:11,770 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 31 of 31 statements. [2025-03-04 11:33:11,770 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-04 11:33:11,770 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 11:33:12,321 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 4 proven. 8 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2025-03-04 11:33:12,322 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-04 11:33:12,322 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2005370515] [2025-03-04 11:33:12,322 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2005370515] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-04 11:33:12,322 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [385244675] [2025-03-04 11:33:12,322 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-04 11:33:12,322 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-04 11:33:12,322 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 11:33:12,324 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-04 11:33:12,326 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2025-03-04 11:33:12,387 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 31 statements into 2 equivalence classes. [2025-03-04 11:33:12,407 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 31 of 31 statements. [2025-03-04 11:33:12,407 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-04 11:33:12,407 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 11:33:12,409 INFO L256 TraceCheckSpWp]: Trace formula consists of 244 conjuncts, 67 conjuncts are in the unsatisfiable core [2025-03-04 11:33:12,411 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-04 11:33:12,414 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-03-04 11:33:12,418 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-03-04 11:33:12,664 WARN L873 $PredicateComparison]: unable to prove that (and (exists ((|v_func_to_recursive_line_28_to_32_0_#t~mem98_27| Int)) (let ((.cse0 (select |c_old(#memory_int#5)| |c_func_to_recursive_line_28_to_32_0_#in~q.base|))) (and (<= |v_func_to_recursive_line_28_to_32_0_#t~mem98_27| (select .cse0 |c_func_to_recursive_line_28_to_32_0_#in~q.offset|)) (= |c_#memory_int#5| (store |c_old(#memory_int#5)| |c_func_to_recursive_line_28_to_32_0_#in~q.base| (store .cse0 |c_func_to_recursive_line_28_to_32_0_#in~q.offset| (* |v_func_to_recursive_line_28_to_32_0_#t~mem98_27| 4))))))) (exists ((|v_ULTIMATE.start_main_~#p~0#1.base_BEFORE_CALL_19| Int)) (= (select (select |c_#memory_int#2| |v_ULTIMATE.start_main_~#p~0#1.base_BEFORE_CALL_19|) 0) 0))) is different from true [2025-03-04 11:33:12,678 WARN L873 $PredicateComparison]: unable to prove that (and (exists ((|v_func_to_recursive_line_28_to_32_0_#t~mem98_29| Int)) (let ((.cse0 (select |c_old(#memory_int#5)| |c_func_to_recursive_line_28_to_32_0_#in~q.base|))) (and (= (store |c_old(#memory_int#5)| |c_func_to_recursive_line_28_to_32_0_#in~q.base| (store .cse0 |c_func_to_recursive_line_28_to_32_0_#in~q.offset| (* |v_func_to_recursive_line_28_to_32_0_#t~mem98_29| 4))) |c_#memory_int#5|) (<= |v_func_to_recursive_line_28_to_32_0_#t~mem98_29| (* (select .cse0 |c_func_to_recursive_line_28_to_32_0_#in~q.offset|) 4))))) (exists ((|v_ULTIMATE.start_main_~#p~0#1.base_BEFORE_CALL_19| Int)) (= (select (select |c_#memory_int#2| |v_ULTIMATE.start_main_~#p~0#1.base_BEFORE_CALL_19|) 0) 0))) is different from true [2025-03-04 11:33:12,711 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 21 treesize of output 13 [2025-03-04 11:33:12,887 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 26 treesize of output 14 [2025-03-04 11:33:12,922 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 8 trivial. 6 not checked. [2025-03-04 11:33:12,922 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-04 11:33:13,341 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [385244675] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-04 11:33:13,341 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-04 11:33:13,341 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 13] total 30 [2025-03-04 11:33:13,341 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [843205636] [2025-03-04 11:33:13,341 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-04 11:33:13,341 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 31 states [2025-03-04 11:33:13,341 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-04 11:33:13,342 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 31 interpolants. [2025-03-04 11:33:13,342 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=143, Invalid=1195, Unknown=2, NotChecked=142, Total=1482 [2025-03-04 11:33:13,342 INFO L87 Difference]: Start difference. First operand 1535 states and 2398 transitions. Second operand has 31 states, 23 states have (on average 1.7391304347826086) internal successors, (40), 27 states have internal predecessors, (40), 7 states have call successors, (7), 4 states have call predecessors, (7), 6 states have return successors, (6), 6 states have call predecessors, (6), 5 states have call successors, (6) [2025-03-04 11:33:15,438 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-04 11:33:15,438 INFO L93 Difference]: Finished difference Result 2139 states and 2632 transitions. [2025-03-04 11:33:15,439 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 25 states. [2025-03-04 11:33:15,439 INFO L78 Accepts]: Start accepts. Automaton has has 31 states, 23 states have (on average 1.7391304347826086) internal successors, (40), 27 states have internal predecessors, (40), 7 states have call successors, (7), 4 states have call predecessors, (7), 6 states have return successors, (6), 6 states have call predecessors, (6), 5 states have call successors, (6) Word has length 31 [2025-03-04 11:33:15,439 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-04 11:33:15,444 INFO L225 Difference]: With dead ends: 2139 [2025-03-04 11:33:15,444 INFO L226 Difference]: Without dead ends: 2138 [2025-03-04 11:33:15,445 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 80 GetRequests, 26 SyntacticMatches, 2 SemanticMatches, 52 ConstructedPredicates, 2 IntricatePredicates, 0 DeprecatedPredicates, 640 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=343, Invalid=2315, Unknown=2, NotChecked=202, Total=2862 [2025-03-04 11:33:15,445 INFO L435 NwaCegarLoop]: 964 mSDtfsCounter, 3136 mSDsluCounter, 11829 mSDsCounter, 0 mSdLazyCounter, 2149 mSolverCounterSat, 91 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3146 SdHoareTripleChecker+Valid, 12793 SdHoareTripleChecker+Invalid, 5516 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 91 IncrementalHoareTripleChecker+Valid, 2149 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 3276 IncrementalHoareTripleChecker+Unchecked, 1.5s IncrementalHoareTripleChecker+Time [2025-03-04 11:33:15,445 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [3146 Valid, 12793 Invalid, 5516 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [91 Valid, 2149 Invalid, 0 Unknown, 3276 Unchecked, 1.5s Time] [2025-03-04 11:33:15,446 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2138 states. [2025-03-04 11:33:15,470 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2138 to 1341. [2025-03-04 11:33:15,471 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1341 states, 1020 states have (on average 1.8833333333333333) internal successors, (1921), 1282 states have internal predecessors, (1921), 42 states have call successors, (42), 14 states have call predecessors, (42), 22 states have return successors, (63), 44 states have call predecessors, (63), 42 states have call successors, (63) [2025-03-04 11:33:15,474 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1341 states to 1341 states and 2026 transitions. [2025-03-04 11:33:15,474 INFO L78 Accepts]: Start accepts. Automaton has 1341 states and 2026 transitions. Word has length 31 [2025-03-04 11:33:15,474 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-04 11:33:15,474 INFO L471 AbstractCegarLoop]: Abstraction has 1341 states and 2026 transitions. [2025-03-04 11:33:15,474 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 31 states, 23 states have (on average 1.7391304347826086) internal successors, (40), 27 states have internal predecessors, (40), 7 states have call successors, (7), 4 states have call predecessors, (7), 6 states have return successors, (6), 6 states have call predecessors, (6), 5 states have call successors, (6) [2025-03-04 11:33:15,474 INFO L276 IsEmpty]: Start isEmpty. Operand 1341 states and 2026 transitions. [2025-03-04 11:33:15,475 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2025-03-04 11:33:15,475 INFO L210 NwaCegarLoop]: Found error trace [2025-03-04 11:33:15,475 INFO L218 NwaCegarLoop]: trace histogram [5, 5, 5, 5, 4, 4, 1, 1, 1, 1] [2025-03-04 11:33:15,481 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Ended with exit code 0 [2025-03-04 11:33:15,675 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable15 [2025-03-04 11:33:15,676 INFO L396 AbstractCegarLoop]: === Iteration 17 === Targeting func_to_recursive_line_28_to_32_0Err0ASSERT_VIOLATIONINTEGER_OVERFLOW === [func_to_recursive_line_36_to_52_0Err0ASSERT_VIOLATIONINTEGER_OVERFLOW, func_to_recursive_line_36_to_52_0Err1ASSERT_VIOLATIONINTEGER_OVERFLOW (and 256 more)] === [2025-03-04 11:33:15,676 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 11:33:15,676 INFO L85 PathProgramCache]: Analyzing trace with hash 1401162227, now seen corresponding path program 2 times [2025-03-04 11:33:15,676 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-04 11:33:15,676 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [721091950] [2025-03-04 11:33:15,676 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-04 11:33:15,676 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-04 11:33:15,682 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 32 statements into 2 equivalence classes. [2025-03-04 11:33:15,688 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 32 of 32 statements. [2025-03-04 11:33:15,688 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-04 11:33:15,688 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 11:33:16,202 INFO L134 CoverageAnalysis]: Checked inductivity of 56 backedges. 0 proven. 56 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-04 11:33:16,203 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-04 11:33:16,203 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [721091950] [2025-03-04 11:33:16,203 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [721091950] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-04 11:33:16,203 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1307790213] [2025-03-04 11:33:16,203 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-04 11:33:16,203 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-04 11:33:16,203 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 11:33:16,205 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-04 11:33:16,207 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2025-03-04 11:33:16,272 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 32 statements into 2 equivalence classes. [2025-03-04 11:33:16,295 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 32 of 32 statements. [2025-03-04 11:33:16,296 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-04 11:33:16,296 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 11:33:16,297 INFO L256 TraceCheckSpWp]: Trace formula consists of 246 conjuncts, 66 conjuncts are in the unsatisfiable core [2025-03-04 11:33:16,299 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-04 11:33:16,301 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-03-04 11:33:16,328 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 21 treesize of output 13 [2025-03-04 11:33:16,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 1 new quantified variables, introduced 0 case distinctions, treesize of input 39 treesize of output 23 [2025-03-04 11:33:16,513 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 45 treesize of output 29 [2025-03-04 11:33:16,609 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 39 treesize of output 23 [2025-03-04 11:33:16,668 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 26 treesize of output 14 [2025-03-04 11:33:16,672 INFO L134 CoverageAnalysis]: Checked inductivity of 56 backedges. 0 proven. 56 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-04 11:33:16,672 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-04 11:33:16,997 INFO L134 CoverageAnalysis]: Checked inductivity of 56 backedges. 0 proven. 56 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-04 11:33:16,997 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1307790213] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-04 11:33:16,997 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-04 11:33:16,997 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 17, 17] total 50 [2025-03-04 11:33:16,997 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1092065093] [2025-03-04 11:33:16,997 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-04 11:33:16,998 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 51 states [2025-03-04 11:33:16,998 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-04 11:33:16,998 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 51 interpolants. [2025-03-04 11:33:16,999 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=437, Invalid=2113, Unknown=0, NotChecked=0, Total=2550 [2025-03-04 11:33:16,999 INFO L87 Difference]: Start difference. First operand 1341 states and 2026 transitions. Second operand has 51 states, 48 states have (on average 1.5625) internal successors, (75), 37 states have internal predecessors, (75), 14 states have call successors, (14), 14 states have call predecessors, (14), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-03-04 11:33:17,954 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-04 11:33:17,954 INFO L93 Difference]: Finished difference Result 1402 states and 2110 transitions. [2025-03-04 11:33:17,955 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 48 states. [2025-03-04 11:33:17,955 INFO L78 Accepts]: Start accepts. Automaton has has 51 states, 48 states have (on average 1.5625) internal successors, (75), 37 states have internal predecessors, (75), 14 states have call successors, (14), 14 states have call predecessors, (14), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 32 [2025-03-04 11:33:17,955 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-04 11:33:17,958 INFO L225 Difference]: With dead ends: 1402 [2025-03-04 11:33:17,958 INFO L226 Difference]: Without dead ends: 1401 [2025-03-04 11:33:17,960 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 114 GetRequests, 39 SyntacticMatches, 0 SemanticMatches, 75 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2045 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=1131, Invalid=4721, Unknown=0, NotChecked=0, Total=5852 [2025-03-04 11:33:17,960 INFO L435 NwaCegarLoop]: 559 mSDtfsCounter, 217 mSDsluCounter, 5864 mSDsCounter, 0 mSdLazyCounter, 616 mSolverCounterSat, 39 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 217 SdHoareTripleChecker+Valid, 6423 SdHoareTripleChecker+Invalid, 655 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 39 IncrementalHoareTripleChecker+Valid, 616 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2025-03-04 11:33:17,960 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [217 Valid, 6423 Invalid, 655 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [39 Valid, 616 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2025-03-04 11:33:17,961 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1401 states. [2025-03-04 11:33:17,987 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1401 to 1401. [2025-03-04 11:33:17,988 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1401 states, 1062 states have (on average 1.8540489642184557) internal successors, (1969), 1330 states have internal predecessors, (1969), 48 states have call successors, (48), 20 states have call predecessors, (48), 34 states have return successors, (87), 50 states have call predecessors, (87), 48 states have call successors, (87) [2025-03-04 11:33:17,990 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1401 states to 1401 states and 2104 transitions. [2025-03-04 11:33:17,991 INFO L78 Accepts]: Start accepts. Automaton has 1401 states and 2104 transitions. Word has length 32 [2025-03-04 11:33:17,991 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-04 11:33:17,991 INFO L471 AbstractCegarLoop]: Abstraction has 1401 states and 2104 transitions. [2025-03-04 11:33:17,991 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 51 states, 48 states have (on average 1.5625) internal successors, (75), 37 states have internal predecessors, (75), 14 states have call successors, (14), 14 states have call predecessors, (14), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-03-04 11:33:17,991 INFO L276 IsEmpty]: Start isEmpty. Operand 1401 states and 2104 transitions. [2025-03-04 11:33:17,991 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2025-03-04 11:33:17,992 INFO L210 NwaCegarLoop]: Found error trace [2025-03-04 11:33:17,992 INFO L218 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-04 11:33:17,998 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Forceful destruction successful, exit code 0 [2025-03-04 11:33:18,196 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable16,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-04 11:33:18,196 INFO L396 AbstractCegarLoop]: === Iteration 18 === Targeting func_to_recursive_line_36_to_52_0Err179ASSERT_VIOLATIONINTEGER_OVERFLOW === [func_to_recursive_line_36_to_52_0Err0ASSERT_VIOLATIONINTEGER_OVERFLOW, func_to_recursive_line_36_to_52_0Err1ASSERT_VIOLATIONINTEGER_OVERFLOW (and 256 more)] === [2025-03-04 11:33:18,197 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 11:33:18,197 INFO L85 PathProgramCache]: Analyzing trace with hash -1471447296, now seen corresponding path program 1 times [2025-03-04 11:33:18,197 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-04 11:33:18,197 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1357441412] [2025-03-04 11:33:18,197 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-04 11:33:18,197 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-04 11:33:18,206 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 32 statements into 1 equivalence classes. [2025-03-04 11:33:18,211 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 32 of 32 statements. [2025-03-04 11:33:18,212 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 11:33:18,212 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-04 11:33:18,213 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1685626968] [2025-03-04 11:33:18,213 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-04 11:33:18,213 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-04 11:33:18,213 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 11:33:18,215 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-04 11:33:18,216 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2025-03-04 11:33:18,281 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 32 statements into 1 equivalence classes. [2025-03-04 11:33:18,302 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 32 of 32 statements. [2025-03-04 11:33:18,302 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 11:33:18,302 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 11:33:18,308 INFO L256 TraceCheckSpWp]: Trace formula consists of 231 conjuncts, 55 conjuncts are in the unsatisfiable core [2025-03-04 11:33:18,312 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-04 11:33:18,314 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2025-03-04 11:33:18,317 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-03-04 11:33:18,320 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2025-03-04 11:33:18,463 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 11 treesize of output 7 [2025-03-04 11:33:18,500 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-04 11:33:18,501 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 30 treesize of output 30 [2025-03-04 11:33:18,508 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 21 treesize of output 13 [2025-03-04 11:33:18,714 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 26 treesize of output 14 [2025-03-04 11:33:18,717 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-04 11:33:18,734 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2025-03-04 11:33:18,734 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-04 11:33:18,813 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-04 11:33:18,814 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1357441412] [2025-03-04 11:33:18,814 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-04 11:33:18,814 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1685626968] [2025-03-04 11:33:18,814 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1685626968] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-04 11:33:18,814 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-04 11:33:18,814 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12] total 12 [2025-03-04 11:33:18,814 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [964791922] [2025-03-04 11:33:18,814 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-04 11:33:18,814 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2025-03-04 11:33:18,814 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-04 11:33:18,814 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2025-03-04 11:33:18,814 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=35, Invalid=175, Unknown=0, NotChecked=0, Total=210 [2025-03-04 11:33:18,815 INFO L87 Difference]: Start difference. First operand 1401 states and 2104 transitions. Second operand has 13 states, 10 states have (on average 2.5) internal successors, (25), 11 states have internal predecessors, (25), 4 states have call successors, (4), 3 states have call predecessors, (4), 3 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2025-03-04 11:33:22,984 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0]