./Ultimate.py --spec ../sv-benchmarks/c/properties/no-overflow.prp --file ../sv-benchmarks/c/recursive/Fibonacci05-overflow.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for overflows Using default analysis Version 8fc3dc66 Calling Ultimate with: /root/.sdkman/candidates/java/21.0.5-tem/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.6.800.v20240513-1750.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/recursive/Fibonacci05-overflow.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 7348520f04d4d9b10e62396a3389d8f9a2f3fbd69eb8f1a8953214a9bb54eb76 --- Real Ultimate output --- This is Ultimate 0.3.0-?-8fc3dc6-m [2025-03-17 15:44:14,354 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-03-17 15:44:14,412 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Overflow-32bit-Automizer_Default.epf [2025-03-17 15:44:14,415 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-03-17 15:44:14,416 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-03-17 15:44:14,437 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-03-17 15:44:14,437 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-03-17 15:44:14,437 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-03-17 15:44:14,438 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-03-17 15:44:14,438 INFO L153 SettingsManager]: * Use memory slicer=true [2025-03-17 15:44:14,438 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2025-03-17 15:44:14,438 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2025-03-17 15:44:14,438 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-03-17 15:44:14,438 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-03-17 15:44:14,438 INFO L153 SettingsManager]: * Use SBE=true [2025-03-17 15:44:14,438 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-03-17 15:44:14,438 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2025-03-17 15:44:14,438 INFO L153 SettingsManager]: * sizeof long=4 [2025-03-17 15:44:14,440 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2025-03-17 15:44:14,440 INFO L153 SettingsManager]: * sizeof POINTER=4 [2025-03-17 15:44:14,440 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-03-17 15:44:14,440 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2025-03-17 15:44:14,440 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2025-03-17 15:44:14,440 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2025-03-17 15:44:14,440 INFO L153 SettingsManager]: * Check absence of signed integer overflows=ASSERTandASSUME [2025-03-17 15:44:14,440 INFO L153 SettingsManager]: * Check unreachability of reach_error function=false [2025-03-17 15:44:14,441 INFO L153 SettingsManager]: * sizeof long double=12 [2025-03-17 15:44:14,441 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-03-17 15:44:14,441 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-03-17 15:44:14,441 INFO L153 SettingsManager]: * Use constant arrays=true [2025-03-17 15:44:14,441 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-03-17 15:44:14,441 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-03-17 15:44:14,442 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-03-17 15:44:14,442 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-03-17 15:44:14,442 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-17 15:44:14,442 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-03-17 15:44:14,442 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2025-03-17 15:44:14,442 INFO L153 SettingsManager]: * Compute procedure contracts=false [2025-03-17 15:44:14,442 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2025-03-17 15:44:14,442 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2025-03-17 15:44:14,442 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2025-03-17 15:44:14,442 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2025-03-17 15:44:14,443 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2025-03-17 15:44:14,443 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2025-03-17 15:44:14,443 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2025-03-17 15:44:14,443 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 -> 7348520f04d4d9b10e62396a3389d8f9a2f3fbd69eb8f1a8953214a9bb54eb76 [2025-03-17 15:44:14,660 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-03-17 15:44:14,665 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-03-17 15:44:14,666 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-03-17 15:44:14,668 INFO L270 PluginConnector]: Initializing CDTParser... [2025-03-17 15:44:14,668 INFO L274 PluginConnector]: CDTParser initialized [2025-03-17 15:44:14,670 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/recursive/Fibonacci05-overflow.c [2025-03-17 15:44:15,756 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/87b3f2317/be573938212e4a7cb9f84db6d97ae8c2/FLAG442952b47 [2025-03-17 15:44:15,930 INFO L384 CDTParser]: Found 1 translation units. [2025-03-17 15:44:15,931 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursive/Fibonacci05-overflow.c [2025-03-17 15:44:15,935 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/87b3f2317/be573938212e4a7cb9f84db6d97ae8c2/FLAG442952b47 [2025-03-17 15:44:15,944 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/87b3f2317/be573938212e4a7cb9f84db6d97ae8c2 [2025-03-17 15:44:15,946 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-03-17 15:44:15,947 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-03-17 15:44:15,947 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-03-17 15:44:15,948 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-03-17 15:44:15,950 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-03-17 15:44:15,951 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 17.03 03:44:15" (1/1) ... [2025-03-17 15:44:15,951 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@2310831d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 03:44:15, skipping insertion in model container [2025-03-17 15:44:15,951 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 17.03 03:44:15" (1/1) ... [2025-03-17 15:44:15,960 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-03-17 15:44:16,052 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-17 15:44:16,058 INFO L200 MainTranslator]: Completed pre-run [2025-03-17 15:44:16,065 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-17 15:44:16,076 INFO L204 MainTranslator]: Completed translation [2025-03-17 15:44:16,077 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 03:44:16 WrapperNode [2025-03-17 15:44:16,077 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-03-17 15:44:16,077 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-03-17 15:44:16,077 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-03-17 15:44:16,077 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-03-17 15:44:16,081 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 03:44:16" (1/1) ... [2025-03-17 15:44:16,086 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 03:44:16" (1/1) ... [2025-03-17 15:44:16,097 INFO L138 Inliner]: procedures = 13, calls = 11, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 24 [2025-03-17 15:44:16,098 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-03-17 15:44:16,098 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-03-17 15:44:16,099 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-03-17 15:44:16,099 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-03-17 15:44:16,104 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 03:44:16" (1/1) ... [2025-03-17 15:44:16,104 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 03:44:16" (1/1) ... [2025-03-17 15:44:16,105 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 03:44:16" (1/1) ... [2025-03-17 15:44:16,115 INFO L175 MemorySlicer]: Split 2 memory accesses to 1 slices as follows [2]. 100 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2]. The 0 writes are split as follows [0]. [2025-03-17 15:44:16,115 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 03:44:16" (1/1) ... [2025-03-17 15:44:16,115 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 03:44:16" (1/1) ... [2025-03-17 15:44:16,116 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 03:44:16" (1/1) ... [2025-03-17 15:44:16,116 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 03:44:16" (1/1) ... [2025-03-17 15:44:16,117 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 03:44:16" (1/1) ... [2025-03-17 15:44:16,117 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 03:44:16" (1/1) ... [2025-03-17 15:44:16,119 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-03-17 15:44:16,120 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2025-03-17 15:44:16,120 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2025-03-17 15:44:16,120 INFO L274 PluginConnector]: IcfgBuilder initialized [2025-03-17 15:44:16,121 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 03:44:16" (1/1) ... [2025-03-17 15:44:16,124 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-17 15:44:16,132 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 15:44:16,146 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2025-03-17 15:44:16,149 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2025-03-17 15:44:16,166 INFO L130 BoogieDeclarations]: Found specification of procedure fibonacci [2025-03-17 15:44:16,166 INFO L138 BoogieDeclarations]: Found implementation of procedure fibonacci [2025-03-17 15:44:16,166 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2025-03-17 15:44:16,166 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-03-17 15:44:16,166 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-03-17 15:44:16,166 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2025-03-17 15:44:16,208 INFO L256 CfgBuilder]: Building ICFG [2025-03-17 15:44:16,209 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2025-03-17 15:44:16,284 INFO L1322 $ProcedureCfgBuilder]: dead code at ProgramPoint L22: havoc #t~ret4;havoc #t~ret5; [2025-03-17 15:44:16,318 INFO L? ?]: Removed 14 outVars from TransFormulas that were not future-live. [2025-03-17 15:44:16,319 INFO L307 CfgBuilder]: Performing block encoding [2025-03-17 15:44:16,328 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-03-17 15:44:16,328 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2025-03-17 15:44:16,329 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 17.03 03:44:16 BoogieIcfgContainer [2025-03-17 15:44:16,329 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2025-03-17 15:44:16,331 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2025-03-17 15:44:16,331 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2025-03-17 15:44:16,335 INFO L274 PluginConnector]: TraceAbstraction initialized [2025-03-17 15:44:16,336 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 17.03 03:44:15" (1/3) ... [2025-03-17 15:44:16,337 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@494398be and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 17.03 03:44:16, skipping insertion in model container [2025-03-17 15:44:16,338 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 03:44:16" (2/3) ... [2025-03-17 15:44:16,338 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@494398be and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 17.03 03:44:16, skipping insertion in model container [2025-03-17 15:44:16,338 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 17.03 03:44:16" (3/3) ... [2025-03-17 15:44:16,339 INFO L128 eAbstractionObserver]: Analyzing ICFG Fibonacci05-overflow.c [2025-03-17 15:44:16,351 INFO L216 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2025-03-17 15:44:16,352 INFO L151 ceAbstractionStarter]: Applying trace abstraction to ICFG Fibonacci05-overflow.c that has 2 procedures, 28 locations, 1 initial locations, 0 loop locations, and 6 error locations. [2025-03-17 15:44:16,394 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2025-03-17 15:44:16,403 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;@147d4de3, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2025-03-17 15:44:16,404 INFO L334 AbstractCegarLoop]: Starting to check reachability of 6 error locations. [2025-03-17 15:44:16,408 INFO L276 IsEmpty]: Start isEmpty. Operand has 28 states, 17 states have (on average 1.5294117647058822) internal successors, (26), 23 states have internal predecessors, (26), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2025-03-17 15:44:16,412 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 7 [2025-03-17 15:44:16,412 INFO L210 NwaCegarLoop]: Found error trace [2025-03-17 15:44:16,413 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1] [2025-03-17 15:44:16,413 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting fibonacciErr5ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-03-17 15:44:16,416 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 15:44:16,417 INFO L85 PathProgramCache]: Analyzing trace with hash 1750717733, now seen corresponding path program 1 times [2025-03-17 15:44:16,422 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 15:44:16,423 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [256610131] [2025-03-17 15:44:16,424 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 15:44:16,424 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 15:44:16,464 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 6 statements into 1 equivalence classes. [2025-03-17 15:44:16,477 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 6 of 6 statements. [2025-03-17 15:44:16,477 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 15:44:16,477 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 15:44:16,530 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-17 15:44:16,530 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-17 15:44:16,530 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [256610131] [2025-03-17 15:44:16,532 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [256610131] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-17 15:44:16,532 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-17 15:44:16,532 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2025-03-17 15:44:16,533 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [234312092] [2025-03-17 15:44:16,534 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-17 15:44:16,536 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2025-03-17 15:44:16,537 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-17 15:44:16,549 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2025-03-17 15:44:16,550 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2025-03-17 15:44:16,551 INFO L87 Difference]: Start difference. First operand has 28 states, 17 states have (on average 1.5294117647058822) internal successors, (26), 23 states have internal predecessors, (26), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Second operand has 3 states, 2 states have (on average 2.5) internal successors, (5), 3 states have internal predecessors, (5), 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-17 15:44:16,594 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-17 15:44:16,595 INFO L93 Difference]: Finished difference Result 33 states and 38 transitions. [2025-03-17 15:44:16,597 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2025-03-17 15:44:16,598 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 2 states have (on average 2.5) internal successors, (5), 3 states have internal predecessors, (5), 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 6 [2025-03-17 15:44:16,599 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-17 15:44:16,603 INFO L225 Difference]: With dead ends: 33 [2025-03-17 15:44:16,603 INFO L226 Difference]: Without dead ends: 23 [2025-03-17 15:44:16,605 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2025-03-17 15:44:16,608 INFO L435 NwaCegarLoop]: 25 mSDtfsCounter, 11 mSDsluCounter, 11 mSDsCounter, 0 mSdLazyCounter, 13 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 36 SdHoareTripleChecker+Invalid, 14 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 13 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-17 15:44:16,610 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [13 Valid, 36 Invalid, 14 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 13 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-17 15:44:16,619 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 23 states. [2025-03-17 15:44:16,632 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 23 to 21. [2025-03-17 15:44:16,633 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 21 states, 13 states have (on average 1.4615384615384615) internal successors, (19), 17 states have internal predecessors, (19), 3 states have call successors, (3), 1 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-17 15:44:16,636 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 21 states to 21 states and 24 transitions. [2025-03-17 15:44:16,637 INFO L78 Accepts]: Start accepts. Automaton has 21 states and 24 transitions. Word has length 6 [2025-03-17 15:44:16,637 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-17 15:44:16,638 INFO L471 AbstractCegarLoop]: Abstraction has 21 states and 24 transitions. [2025-03-17 15:44:16,638 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 2 states have (on average 2.5) internal successors, (5), 3 states have internal predecessors, (5), 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-17 15:44:16,638 INFO L276 IsEmpty]: Start isEmpty. Operand 21 states and 24 transitions. [2025-03-17 15:44:16,639 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 8 [2025-03-17 15:44:16,639 INFO L210 NwaCegarLoop]: Found error trace [2025-03-17 15:44:16,639 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2025-03-17 15:44:16,639 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2025-03-17 15:44:16,640 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting fibonacciErr4ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-03-17 15:44:16,640 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 15:44:16,640 INFO L85 PathProgramCache]: Analyzing trace with hash -1562325140, now seen corresponding path program 1 times [2025-03-17 15:44:16,641 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 15:44:16,641 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1384841815] [2025-03-17 15:44:16,641 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 15:44:16,641 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 15:44:16,647 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 7 statements into 1 equivalence classes. [2025-03-17 15:44:16,656 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 7 of 7 statements. [2025-03-17 15:44:16,657 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 15:44:16,657 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 15:44:16,721 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-17 15:44:16,721 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-17 15:44:16,721 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1384841815] [2025-03-17 15:44:16,721 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1384841815] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-17 15:44:16,722 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-17 15:44:16,722 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2025-03-17 15:44:16,722 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1532909894] [2025-03-17 15:44:16,722 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-17 15:44:16,723 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-17 15:44:16,723 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-17 15:44:16,723 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-17 15:44:16,723 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-17 15:44:16,723 INFO L87 Difference]: Start difference. First operand 21 states and 24 transitions. Second operand has 5 states, 3 states have (on average 2.0) internal successors, (6), 3 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-17 15:44:16,773 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-17 15:44:16,773 INFO L93 Difference]: Finished difference Result 23 states and 27 transitions. [2025-03-17 15:44:16,774 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-17 15:44:16,774 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 3 states have (on average 2.0) internal successors, (6), 3 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-17 15:44:16,774 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-17 15:44:16,774 INFO L225 Difference]: With dead ends: 23 [2025-03-17 15:44:16,774 INFO L226 Difference]: Without dead ends: 21 [2025-03-17 15:44:16,775 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 0 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2025-03-17 15:44:16,775 INFO L435 NwaCegarLoop]: 12 mSDtfsCounter, 26 mSDsluCounter, 13 mSDsCounter, 0 mSdLazyCounter, 32 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 26 SdHoareTripleChecker+Valid, 25 SdHoareTripleChecker+Invalid, 39 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 32 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-17 15:44:16,775 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [26 Valid, 25 Invalid, 39 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 32 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-17 15:44:16,776 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 21 states. [2025-03-17 15:44:16,779 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 21 to 19. [2025-03-17 15:44:16,779 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 19 states, 13 states have (on average 1.3076923076923077) internal successors, (17), 15 states have internal predecessors, (17), 3 states have call successors, (3), 1 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-17 15:44:16,780 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 19 states to 19 states and 22 transitions. [2025-03-17 15:44:16,780 INFO L78 Accepts]: Start accepts. Automaton has 19 states and 22 transitions. Word has length 7 [2025-03-17 15:44:16,780 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-17 15:44:16,780 INFO L471 AbstractCegarLoop]: Abstraction has 19 states and 22 transitions. [2025-03-17 15:44:16,780 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 3 states have (on average 2.0) internal successors, (6), 3 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-17 15:44:16,780 INFO L276 IsEmpty]: Start isEmpty. Operand 19 states and 22 transitions. [2025-03-17 15:44:16,780 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2025-03-17 15:44:16,780 INFO L210 NwaCegarLoop]: Found error trace [2025-03-17 15:44:16,781 INFO L218 NwaCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-17 15:44:16,781 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2025-03-17 15:44:16,781 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-03-17 15:44:16,781 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 15:44:16,781 INFO L85 PathProgramCache]: Analyzing trace with hash 16039925, now seen corresponding path program 1 times [2025-03-17 15:44:16,781 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 15:44:16,781 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1065943178] [2025-03-17 15:44:16,781 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 15:44:16,781 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 15:44:16,790 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 22 statements into 1 equivalence classes. [2025-03-17 15:44:16,800 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 22 of 22 statements. [2025-03-17 15:44:16,800 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 15:44:16,800 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 15:44:16,906 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2025-03-17 15:44:16,907 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-17 15:44:16,907 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1065943178] [2025-03-17 15:44:16,907 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1065943178] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-17 15:44:16,907 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-17 15:44:16,907 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2025-03-17 15:44:16,907 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [114999050] [2025-03-17 15:44:16,907 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-17 15:44:16,908 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-17 15:44:16,908 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-17 15:44:16,908 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-17 15:44:16,909 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2025-03-17 15:44:16,909 INFO L87 Difference]: Start difference. First operand 19 states and 22 transitions. Second operand has 5 states, 4 states have (on average 3.25) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (3), 1 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-17 15:44:16,941 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-17 15:44:16,941 INFO L93 Difference]: Finished difference Result 33 states and 41 transitions. [2025-03-17 15:44:16,944 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-17 15:44:16,944 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 3.25) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (3), 1 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-17 15:44:16,944 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-17 15:44:16,945 INFO L225 Difference]: With dead ends: 33 [2025-03-17 15:44:16,945 INFO L226 Difference]: Without dead ends: 31 [2025-03-17 15:44:16,945 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2025-03-17 15:44:16,945 INFO L435 NwaCegarLoop]: 16 mSDtfsCounter, 4 mSDsluCounter, 33 mSDsCounter, 0 mSdLazyCounter, 23 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 49 SdHoareTripleChecker+Invalid, 25 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 23 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-17 15:44:16,946 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [5 Valid, 49 Invalid, 25 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 23 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-17 15:44:16,946 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 31 states. [2025-03-17 15:44:16,951 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 31 to 28. [2025-03-17 15:44:16,951 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 28 states, 20 states have (on average 1.2) internal successors, (24), 22 states have internal predecessors, (24), 4 states have call successors, (4), 1 states have call predecessors, (4), 2 states have return successors, (6), 4 states have call predecessors, (6), 3 states have call successors, (6) [2025-03-17 15:44:16,955 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 28 states to 28 states and 34 transitions. [2025-03-17 15:44:16,955 INFO L78 Accepts]: Start accepts. Automaton has 28 states and 34 transitions. Word has length 22 [2025-03-17 15:44:16,955 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-17 15:44:16,955 INFO L471 AbstractCegarLoop]: Abstraction has 28 states and 34 transitions. [2025-03-17 15:44:16,955 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 3.25) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (3), 1 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-17 15:44:16,955 INFO L276 IsEmpty]: Start isEmpty. Operand 28 states and 34 transitions. [2025-03-17 15:44:16,956 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2025-03-17 15:44:16,956 INFO L210 NwaCegarLoop]: Found error trace [2025-03-17 15:44:16,956 INFO L218 NwaCegarLoop]: trace histogram [4, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-17 15:44:16,957 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2025-03-17 15:44:16,957 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-03-17 15:44:16,958 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 15:44:16,958 INFO L85 PathProgramCache]: Analyzing trace with hash 645090427, now seen corresponding path program 1 times [2025-03-17 15:44:16,958 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 15:44:16,958 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1018251232] [2025-03-17 15:44:16,958 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 15:44:16,958 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 15:44:16,969 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 29 statements into 1 equivalence classes. [2025-03-17 15:44:16,978 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 29 of 29 statements. [2025-03-17 15:44:16,978 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 15:44:16,978 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 15:44:17,111 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2025-03-17 15:44:17,112 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-17 15:44:17,112 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1018251232] [2025-03-17 15:44:17,112 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1018251232] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-17 15:44:17,112 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1344733512] [2025-03-17 15:44:17,112 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 15:44:17,112 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-17 15:44:17,112 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 15:44:17,114 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-17 15:44:17,116 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2025-03-17 15:44:17,138 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 29 statements into 1 equivalence classes. [2025-03-17 15:44:17,154 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 29 of 29 statements. [2025-03-17 15:44:17,154 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 15:44:17,154 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 15:44:17,155 INFO L256 TraceCheckSpWp]: Trace formula consists of 76 conjuncts, 6 conjuncts are in the unsatisfiable core [2025-03-17 15:44:17,158 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 15:44:17,249 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 6 proven. 3 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2025-03-17 15:44:17,249 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-17 15:44:17,392 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 6 proven. 3 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2025-03-17 15:44:17,394 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1344733512] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-17 15:44:17,394 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-17 15:44:17,394 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 7, 7] total 15 [2025-03-17 15:44:17,394 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1213508650] [2025-03-17 15:44:17,394 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-17 15:44:17,395 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2025-03-17 15:44:17,396 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-17 15:44:17,396 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2025-03-17 15:44:17,397 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=35, Invalid=175, Unknown=0, NotChecked=0, Total=210 [2025-03-17 15:44:17,397 INFO L87 Difference]: Start difference. First operand 28 states and 34 transitions. Second operand has 15 states, 15 states have (on average 2.3333333333333335) internal successors, (35), 15 states have internal predecessors, (35), 4 states have call successors, (5), 1 states have call predecessors, (5), 5 states have return successors, (6), 5 states have call predecessors, (6), 4 states have call successors, (6) [2025-03-17 15:44:17,620 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-17 15:44:17,620 INFO L93 Difference]: Finished difference Result 89 states and 127 transitions. [2025-03-17 15:44:17,621 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2025-03-17 15:44:17,621 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 15 states have (on average 2.3333333333333335) internal successors, (35), 15 states have internal predecessors, (35), 4 states have call successors, (5), 1 states have call predecessors, (5), 5 states have return successors, (6), 5 states have call predecessors, (6), 4 states have call successors, (6) Word has length 29 [2025-03-17 15:44:17,621 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-17 15:44:17,623 INFO L225 Difference]: With dead ends: 89 [2025-03-17 15:44:17,623 INFO L226 Difference]: Without dead ends: 63 [2025-03-17 15:44:17,624 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 70 GetRequests, 48 SyntacticMatches, 1 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 42 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=111, Invalid=395, Unknown=0, NotChecked=0, Total=506 [2025-03-17 15:44:17,626 INFO L435 NwaCegarLoop]: 11 mSDtfsCounter, 106 mSDsluCounter, 70 mSDsCounter, 0 mSdLazyCounter, 187 mSolverCounterSat, 49 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 106 SdHoareTripleChecker+Valid, 81 SdHoareTripleChecker+Invalid, 236 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 49 IncrementalHoareTripleChecker+Valid, 187 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-17 15:44:17,627 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [106 Valid, 81 Invalid, 236 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [49 Valid, 187 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-17 15:44:17,627 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 63 states. [2025-03-17 15:44:17,635 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 63 to 51. [2025-03-17 15:44:17,635 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 51 states, 37 states have (on average 1.1081081081081081) internal successors, (41), 40 states have internal predecessors, (41), 7 states have call successors, (7), 2 states have call predecessors, (7), 5 states have return successors, (18), 8 states have call predecessors, (18), 6 states have call successors, (18) [2025-03-17 15:44:17,636 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 51 states to 51 states and 66 transitions. [2025-03-17 15:44:17,636 INFO L78 Accepts]: Start accepts. Automaton has 51 states and 66 transitions. Word has length 29 [2025-03-17 15:44:17,636 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-17 15:44:17,636 INFO L471 AbstractCegarLoop]: Abstraction has 51 states and 66 transitions. [2025-03-17 15:44:17,637 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 2.3333333333333335) internal successors, (35), 15 states have internal predecessors, (35), 4 states have call successors, (5), 1 states have call predecessors, (5), 5 states have return successors, (6), 5 states have call predecessors, (6), 4 states have call successors, (6) [2025-03-17 15:44:17,637 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 66 transitions. [2025-03-17 15:44:17,637 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2025-03-17 15:44:17,637 INFO L210 NwaCegarLoop]: Found error trace [2025-03-17 15:44:17,637 INFO L218 NwaCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-17 15:44:17,643 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2025-03-17 15:44:17,841 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-17 15:44:17,841 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-03-17 15:44:17,841 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 15:44:17,842 INFO L85 PathProgramCache]: Analyzing trace with hash 1677862848, now seen corresponding path program 2 times [2025-03-17 15:44:17,842 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 15:44:17,842 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [329965929] [2025-03-17 15:44:17,842 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-17 15:44:17,842 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 15:44:17,846 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 23 statements into 2 equivalence classes. [2025-03-17 15:44:17,853 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 23 of 23 statements. [2025-03-17 15:44:17,853 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-17 15:44:17,853 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 15:44:17,923 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2025-03-17 15:44:17,923 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-17 15:44:17,923 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [329965929] [2025-03-17 15:44:17,923 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [329965929] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-17 15:44:17,923 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [917305390] [2025-03-17 15:44:17,923 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-17 15:44:17,923 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-17 15:44:17,923 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 15:44:17,926 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-17 15:44:17,927 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2025-03-17 15:44:17,948 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 23 statements into 2 equivalence classes. [2025-03-17 15:44:17,958 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 23 of 23 statements. [2025-03-17 15:44:17,958 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-17 15:44:17,958 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 15:44:17,958 INFO L256 TraceCheckSpWp]: Trace formula consists of 66 conjuncts, 4 conjuncts are in the unsatisfiable core [2025-03-17 15:44:17,959 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 15:44:18,001 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2025-03-17 15:44:18,002 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-17 15:44:18,002 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [917305390] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-17 15:44:18,002 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-03-17 15:44:18,002 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [5] total 7 [2025-03-17 15:44:18,002 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1498477095] [2025-03-17 15:44:18,002 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-17 15:44:18,002 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-17 15:44:18,002 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-17 15:44:18,002 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-17 15:44:18,003 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=38, Unknown=0, NotChecked=0, Total=56 [2025-03-17 15:44:18,003 INFO L87 Difference]: Start difference. First operand 51 states and 66 transitions. Second operand has 5 states, 4 states have (on average 3.75) internal successors, (15), 5 states have internal predecessors, (15), 2 states have call successors, (3), 1 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-17 15:44:18,029 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-17 15:44:18,029 INFO L93 Difference]: Finished difference Result 58 states and 74 transitions. [2025-03-17 15:44:18,029 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-17 15:44:18,029 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 3.75) internal successors, (15), 5 states have internal predecessors, (15), 2 states have call successors, (3), 1 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 23 [2025-03-17 15:44:18,030 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-17 15:44:18,031 INFO L225 Difference]: With dead ends: 58 [2025-03-17 15:44:18,031 INFO L226 Difference]: Without dead ends: 57 [2025-03-17 15:44:18,031 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 27 GetRequests, 20 SyntacticMatches, 1 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=18, Invalid=38, Unknown=0, NotChecked=0, Total=56 [2025-03-17 15:44:18,031 INFO L435 NwaCegarLoop]: 16 mSDtfsCounter, 4 mSDsluCounter, 29 mSDsCounter, 0 mSdLazyCounter, 20 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 45 SdHoareTripleChecker+Invalid, 22 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 20 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-17 15:44:18,031 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [5 Valid, 45 Invalid, 22 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 20 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-17 15:44:18,032 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 57 states. [2025-03-17 15:44:18,037 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 57 to 53. [2025-03-17 15:44:18,037 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 53 states, 39 states have (on average 1.1025641025641026) internal successors, (43), 41 states have internal predecessors, (43), 7 states have call successors, (7), 2 states have call predecessors, (7), 5 states have return successors, (18), 9 states have call predecessors, (18), 6 states have call successors, (18) [2025-03-17 15:44:18,038 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 53 states to 53 states and 68 transitions. [2025-03-17 15:44:18,038 INFO L78 Accepts]: Start accepts. Automaton has 53 states and 68 transitions. Word has length 23 [2025-03-17 15:44:18,038 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-17 15:44:18,038 INFO L471 AbstractCegarLoop]: Abstraction has 53 states and 68 transitions. [2025-03-17 15:44:18,038 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 3.75) internal successors, (15), 5 states have internal predecessors, (15), 2 states have call successors, (3), 1 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-17 15:44:18,038 INFO L276 IsEmpty]: Start isEmpty. Operand 53 states and 68 transitions. [2025-03-17 15:44:18,038 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2025-03-17 15:44:18,039 INFO L210 NwaCegarLoop]: Found error trace [2025-03-17 15:44:18,039 INFO L218 NwaCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-17 15:44:18,044 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2025-03-17 15:44:18,239 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-17 15:44:18,240 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-03-17 15:44:18,240 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 15:44:18,240 INFO L85 PathProgramCache]: Analyzing trace with hash 474140709, now seen corresponding path program 1 times [2025-03-17 15:44:18,240 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 15:44:18,240 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1888992983] [2025-03-17 15:44:18,240 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 15:44:18,240 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 15:44:18,244 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 24 statements into 1 equivalence classes. [2025-03-17 15:44:18,249 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 24 of 24 statements. [2025-03-17 15:44:18,249 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 15:44:18,249 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 15:44:18,302 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2025-03-17 15:44:18,302 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-17 15:44:18,302 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1888992983] [2025-03-17 15:44:18,302 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1888992983] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-17 15:44:18,302 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [328434640] [2025-03-17 15:44:18,302 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 15:44:18,302 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-17 15:44:18,302 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 15:44:18,304 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-17 15:44:18,306 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2025-03-17 15:44:18,325 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 24 statements into 1 equivalence classes. [2025-03-17 15:44:18,331 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 24 of 24 statements. [2025-03-17 15:44:18,331 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 15:44:18,331 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 15:44:18,332 INFO L256 TraceCheckSpWp]: Trace formula consists of 67 conjuncts, 5 conjuncts are in the unsatisfiable core [2025-03-17 15:44:18,333 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 15:44:18,381 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2025-03-17 15:44:18,381 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-17 15:44:18,381 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [328434640] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-17 15:44:18,381 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-03-17 15:44:18,381 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [5] total 9 [2025-03-17 15:44:18,381 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1711055087] [2025-03-17 15:44:18,381 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-17 15:44:18,381 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2025-03-17 15:44:18,381 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-17 15:44:18,382 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2025-03-17 15:44:18,382 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=64, Unknown=0, NotChecked=0, Total=90 [2025-03-17 15:44:18,382 INFO L87 Difference]: Start difference. First operand 53 states and 68 transitions. Second operand has 6 states, 5 states have (on average 3.2) internal successors, (16), 6 states have internal predecessors, (16), 2 states have call successors, (3), 1 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-17 15:44:18,412 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-17 15:44:18,413 INFO L93 Difference]: Finished difference Result 80 states and 115 transitions. [2025-03-17 15:44:18,413 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2025-03-17 15:44:18,413 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 3.2) internal successors, (16), 6 states have internal predecessors, (16), 2 states have call successors, (3), 1 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-17 15:44:18,413 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-17 15:44:18,414 INFO L225 Difference]: With dead ends: 80 [2025-03-17 15:44:18,414 INFO L226 Difference]: Without dead ends: 79 [2025-03-17 15:44:18,414 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 28 GetRequests, 20 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 12 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=26, Invalid=64, Unknown=0, NotChecked=0, Total=90 [2025-03-17 15:44:18,415 INFO L435 NwaCegarLoop]: 16 mSDtfsCounter, 2 mSDsluCounter, 46 mSDsCounter, 0 mSdLazyCounter, 28 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 62 SdHoareTripleChecker+Invalid, 29 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 28 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-17 15:44:18,415 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 62 Invalid, 29 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 28 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-17 15:44:18,415 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 79 states. [2025-03-17 15:44:18,423 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 79 to 62. [2025-03-17 15:44:18,423 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 62 states, 46 states have (on average 1.0869565217391304) internal successors, (50), 48 states have internal predecessors, (50), 8 states have call successors, (8), 2 states have call predecessors, (8), 6 states have return successors, (27), 11 states have call predecessors, (27), 7 states have call successors, (27) [2025-03-17 15:44:18,424 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 62 states to 62 states and 85 transitions. [2025-03-17 15:44:18,425 INFO L78 Accepts]: Start accepts. Automaton has 62 states and 85 transitions. Word has length 24 [2025-03-17 15:44:18,426 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-17 15:44:18,426 INFO L471 AbstractCegarLoop]: Abstraction has 62 states and 85 transitions. [2025-03-17 15:44:18,426 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 3.2) internal successors, (16), 6 states have internal predecessors, (16), 2 states have call successors, (3), 1 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-17 15:44:18,426 INFO L276 IsEmpty]: Start isEmpty. Operand 62 states and 85 transitions. [2025-03-17 15:44:18,427 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2025-03-17 15:44:18,427 INFO L210 NwaCegarLoop]: Found error trace [2025-03-17 15:44:18,427 INFO L218 NwaCegarLoop]: trace histogram [6, 5, 4, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1] [2025-03-17 15:44:18,433 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-17 15:44:18,627 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-17 15:44:18,628 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-03-17 15:44:18,628 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 15:44:18,628 INFO L85 PathProgramCache]: Analyzing trace with hash 627457084, now seen corresponding path program 1 times [2025-03-17 15:44:18,628 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 15:44:18,628 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [635461352] [2025-03-17 15:44:18,628 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 15:44:18,628 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 15:44:18,632 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 50 statements into 1 equivalence classes. [2025-03-17 15:44:18,636 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 50 of 50 statements. [2025-03-17 15:44:18,637 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 15:44:18,637 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 15:44:18,747 INFO L134 CoverageAnalysis]: Checked inductivity of 68 backedges. 2 proven. 15 refuted. 0 times theorem prover too weak. 51 trivial. 0 not checked. [2025-03-17 15:44:18,747 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-17 15:44:18,747 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [635461352] [2025-03-17 15:44:18,747 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [635461352] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-17 15:44:18,747 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [184942280] [2025-03-17 15:44:18,747 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 15:44:18,747 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-17 15:44:18,747 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 15:44:18,749 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-17 15:44:18,750 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2025-03-17 15:44:18,769 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 50 statements into 1 equivalence classes. [2025-03-17 15:44:18,780 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 50 of 50 statements. [2025-03-17 15:44:18,780 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 15:44:18,780 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 15:44:18,780 INFO L256 TraceCheckSpWp]: Trace formula consists of 114 conjuncts, 9 conjuncts are in the unsatisfiable core [2025-03-17 15:44:18,782 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 15:44:18,839 INFO L134 CoverageAnalysis]: Checked inductivity of 68 backedges. 2 proven. 7 refuted. 0 times theorem prover too weak. 59 trivial. 0 not checked. [2025-03-17 15:44:18,839 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-17 15:44:18,999 INFO L134 CoverageAnalysis]: Checked inductivity of 68 backedges. 6 proven. 7 refuted. 0 times theorem prover too weak. 55 trivial. 0 not checked. [2025-03-17 15:44:18,999 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [184942280] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-17 15:44:19,000 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-17 15:44:19,000 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 6, 7] total 15 [2025-03-17 15:44:19,000 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1697615558] [2025-03-17 15:44:19,001 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-17 15:44:19,001 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2025-03-17 15:44:19,001 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-17 15:44:19,001 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2025-03-17 15:44:19,002 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=62, Invalid=178, Unknown=0, NotChecked=0, Total=240 [2025-03-17 15:44:19,002 INFO L87 Difference]: Start difference. First operand 62 states and 85 transitions. Second operand has 16 states, 15 states have (on average 2.8666666666666667) internal successors, (43), 16 states have internal predecessors, (43), 4 states have call successors, (5), 1 states have call predecessors, (5), 5 states have return successors, (9), 9 states have call predecessors, (9), 4 states have call successors, (9) [2025-03-17 15:44:19,160 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-17 15:44:19,161 INFO L93 Difference]: Finished difference Result 139 states and 215 transitions. [2025-03-17 15:44:19,162 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2025-03-17 15:44:19,163 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 15 states have (on average 2.8666666666666667) internal successors, (43), 16 states have internal predecessors, (43), 4 states have call successors, (5), 1 states have call predecessors, (5), 5 states have return successors, (9), 9 states have call predecessors, (9), 4 states have call successors, (9) Word has length 50 [2025-03-17 15:44:19,163 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-17 15:44:19,164 INFO L225 Difference]: With dead ends: 139 [2025-03-17 15:44:19,165 INFO L226 Difference]: Without dead ends: 137 [2025-03-17 15:44:19,165 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 113 GetRequests, 91 SyntacticMatches, 2 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 110 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=126, Invalid=336, Unknown=0, NotChecked=0, Total=462 [2025-03-17 15:44:19,166 INFO L435 NwaCegarLoop]: 23 mSDtfsCounter, 16 mSDsluCounter, 103 mSDsCounter, 0 mSdLazyCounter, 131 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 22 SdHoareTripleChecker+Valid, 126 SdHoareTripleChecker+Invalid, 137 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 131 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-17 15:44:19,166 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [22 Valid, 126 Invalid, 137 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 131 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-17 15:44:19,166 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 137 states. [2025-03-17 15:44:19,183 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 137 to 96. [2025-03-17 15:44:19,183 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 96 states, 74 states have (on average 1.0810810810810811) internal successors, (80), 73 states have internal predecessors, (80), 11 states have call successors, (11), 2 states have call predecessors, (11), 9 states have return successors, (66), 20 states have call predecessors, (66), 10 states have call successors, (66) [2025-03-17 15:44:19,185 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 96 states to 96 states and 157 transitions. [2025-03-17 15:44:19,185 INFO L78 Accepts]: Start accepts. Automaton has 96 states and 157 transitions. Word has length 50 [2025-03-17 15:44:19,185 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-17 15:44:19,185 INFO L471 AbstractCegarLoop]: Abstraction has 96 states and 157 transitions. [2025-03-17 15:44:19,185 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 15 states have (on average 2.8666666666666667) internal successors, (43), 16 states have internal predecessors, (43), 4 states have call successors, (5), 1 states have call predecessors, (5), 5 states have return successors, (9), 9 states have call predecessors, (9), 4 states have call successors, (9) [2025-03-17 15:44:19,185 INFO L276 IsEmpty]: Start isEmpty. Operand 96 states and 157 transitions. [2025-03-17 15:44:19,189 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 117 [2025-03-17 15:44:19,190 INFO L210 NwaCegarLoop]: Found error trace [2025-03-17 15:44:19,190 INFO L218 NwaCegarLoop]: trace histogram [13, 11, 10, 6, 6, 6, 6, 6, 6, 6, 6, 6, 5, 5, 4, 4, 4, 3, 1, 1, 1] [2025-03-17 15:44:19,196 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2025-03-17 15:44:19,394 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-17 15:44:19,394 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-03-17 15:44:19,395 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 15:44:19,395 INFO L85 PathProgramCache]: Analyzing trace with hash -35150195, now seen corresponding path program 1 times [2025-03-17 15:44:19,395 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 15:44:19,395 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1816838919] [2025-03-17 15:44:19,395 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 15:44:19,395 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 15:44:19,401 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 116 statements into 1 equivalence classes. [2025-03-17 15:44:19,415 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 116 of 116 statements. [2025-03-17 15:44:19,415 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 15:44:19,415 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 15:44:19,529 INFO L134 CoverageAnalysis]: Checked inductivity of 442 backedges. 42 proven. 155 refuted. 0 times theorem prover too weak. 245 trivial. 0 not checked. [2025-03-17 15:44:19,529 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-17 15:44:19,530 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1816838919] [2025-03-17 15:44:19,530 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1816838919] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-17 15:44:19,530 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [154026220] [2025-03-17 15:44:19,530 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 15:44:19,530 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-17 15:44:19,530 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 15:44:19,532 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-17 15:44:19,533 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2025-03-17 15:44:19,558 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 116 statements into 1 equivalence classes. [2025-03-17 15:44:19,579 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 116 of 116 statements. [2025-03-17 15:44:19,579 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 15:44:19,579 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 15:44:19,582 INFO L256 TraceCheckSpWp]: Trace formula consists of 238 conjuncts, 10 conjuncts are in the unsatisfiable core [2025-03-17 15:44:19,584 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 15:44:19,653 INFO L134 CoverageAnalysis]: Checked inductivity of 442 backedges. 271 proven. 67 refuted. 0 times theorem prover too weak. 104 trivial. 0 not checked. [2025-03-17 15:44:19,653 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-17 15:44:19,861 INFO L134 CoverageAnalysis]: Checked inductivity of 442 backedges. 51 proven. 202 refuted. 0 times theorem prover too weak. 189 trivial. 0 not checked. [2025-03-17 15:44:19,861 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [154026220] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-17 15:44:19,861 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-17 15:44:19,862 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 9, 10] total 13 [2025-03-17 15:44:19,862 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1448360935] [2025-03-17 15:44:19,862 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-17 15:44:19,862 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2025-03-17 15:44:19,862 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-17 15:44:19,863 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2025-03-17 15:44:19,863 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=34, Invalid=122, Unknown=0, NotChecked=0, Total=156 [2025-03-17 15:44:19,863 INFO L87 Difference]: Start difference. First operand 96 states and 157 transitions. Second operand has 13 states, 13 states have (on average 5.846153846153846) internal successors, (76), 13 states have internal predecessors, (76), 8 states have call successors, (14), 3 states have call predecessors, (14), 5 states have return successors, (13), 5 states have call predecessors, (13), 7 states have call successors, (13) [2025-03-17 15:44:19,978 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-17 15:44:19,979 INFO L93 Difference]: Finished difference Result 222 states and 399 transitions. [2025-03-17 15:44:19,980 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2025-03-17 15:44:19,980 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 5.846153846153846) internal successors, (76), 13 states have internal predecessors, (76), 8 states have call successors, (14), 3 states have call predecessors, (14), 5 states have return successors, (13), 5 states have call predecessors, (13), 7 states have call successors, (13) Word has length 116 [2025-03-17 15:44:19,981 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-17 15:44:19,983 INFO L225 Difference]: With dead ends: 222 [2025-03-17 15:44:19,985 INFO L226 Difference]: Without dead ends: 128 [2025-03-17 15:44:19,988 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 250 GetRequests, 226 SyntacticMatches, 6 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 49 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=113, Invalid=267, Unknown=0, NotChecked=0, Total=380 [2025-03-17 15:44:19,989 INFO L435 NwaCegarLoop]: 14 mSDtfsCounter, 96 mSDsluCounter, 42 mSDsCounter, 0 mSdLazyCounter, 96 mSolverCounterSat, 34 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 96 SdHoareTripleChecker+Valid, 56 SdHoareTripleChecker+Invalid, 130 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 34 IncrementalHoareTripleChecker+Valid, 96 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-17 15:44:19,990 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [96 Valid, 56 Invalid, 130 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [34 Valid, 96 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-17 15:44:19,990 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 128 states. [2025-03-17 15:44:20,008 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 128 to 108. [2025-03-17 15:44:20,008 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 108 states, 84 states have (on average 1.0833333333333333) internal successors, (91), 82 states have internal predecessors, (91), 12 states have call successors, (12), 3 states have call predecessors, (12), 10 states have return successors, (75), 22 states have call predecessors, (75), 11 states have call successors, (75) [2025-03-17 15:44:20,010 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 108 states to 108 states and 178 transitions. [2025-03-17 15:44:20,010 INFO L78 Accepts]: Start accepts. Automaton has 108 states and 178 transitions. Word has length 116 [2025-03-17 15:44:20,010 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-17 15:44:20,010 INFO L471 AbstractCegarLoop]: Abstraction has 108 states and 178 transitions. [2025-03-17 15:44:20,010 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 5.846153846153846) internal successors, (76), 13 states have internal predecessors, (76), 8 states have call successors, (14), 3 states have call predecessors, (14), 5 states have return successors, (13), 5 states have call predecessors, (13), 7 states have call successors, (13) [2025-03-17 15:44:20,012 INFO L276 IsEmpty]: Start isEmpty. Operand 108 states and 178 transitions. [2025-03-17 15:44:20,014 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 172 [2025-03-17 15:44:20,015 INFO L210 NwaCegarLoop]: Found error trace [2025-03-17 15:44:20,015 INFO L218 NwaCegarLoop]: trace histogram [19, 17, 11, 9, 9, 9, 9, 9, 9, 9, 9, 9, 8, 8, 8, 7, 7, 2, 1, 1, 1] [2025-03-17 15:44:20,021 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2025-03-17 15:44:20,219 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-17 15:44:20,219 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-03-17 15:44:20,219 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 15:44:20,219 INFO L85 PathProgramCache]: Analyzing trace with hash -1629212256, now seen corresponding path program 2 times [2025-03-17 15:44:20,219 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 15:44:20,219 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [699716540] [2025-03-17 15:44:20,220 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-17 15:44:20,220 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 15:44:20,226 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 171 statements into 2 equivalence classes. [2025-03-17 15:44:20,237 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 171 of 171 statements. [2025-03-17 15:44:20,237 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-17 15:44:20,237 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 15:44:20,397 INFO L134 CoverageAnalysis]: Checked inductivity of 998 backedges. 94 proven. 274 refuted. 0 times theorem prover too weak. 630 trivial. 0 not checked. [2025-03-17 15:44:20,398 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-17 15:44:20,398 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [699716540] [2025-03-17 15:44:20,398 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [699716540] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-17 15:44:20,398 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [584576775] [2025-03-17 15:44:20,398 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-17 15:44:20,398 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-17 15:44:20,398 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 15:44:20,400 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-17 15:44:20,401 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2025-03-17 15:44:20,429 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 171 statements into 2 equivalence classes. [2025-03-17 15:44:20,460 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 171 of 171 statements. [2025-03-17 15:44:20,460 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-17 15:44:20,460 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 15:44:20,461 INFO L256 TraceCheckSpWp]: Trace formula consists of 339 conjuncts, 8 conjuncts are in the unsatisfiable core [2025-03-17 15:44:20,464 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 15:44:20,517 INFO L134 CoverageAnalysis]: Checked inductivity of 998 backedges. 441 proven. 15 refuted. 0 times theorem prover too weak. 542 trivial. 0 not checked. [2025-03-17 15:44:20,517 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-17 15:44:20,816 INFO L134 CoverageAnalysis]: Checked inductivity of 998 backedges. 95 proven. 322 refuted. 0 times theorem prover too weak. 581 trivial. 0 not checked. [2025-03-17 15:44:20,817 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [584576775] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-17 15:44:20,817 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-17 15:44:20,817 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 8, 9] total 14 [2025-03-17 15:44:20,817 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1254129912] [2025-03-17 15:44:20,817 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-17 15:44:20,818 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2025-03-17 15:44:20,818 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-17 15:44:20,831 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2025-03-17 15:44:20,832 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=47, Invalid=135, Unknown=0, NotChecked=0, Total=182 [2025-03-17 15:44:20,832 INFO L87 Difference]: Start difference. First operand 108 states and 178 transitions. Second operand has 14 states, 14 states have (on average 4.857142857142857) internal successors, (68), 14 states have internal predecessors, (68), 7 states have call successors, (13), 2 states have call predecessors, (13), 5 states have return successors, (14), 5 states have call predecessors, (14), 7 states have call successors, (14) [2025-03-17 15:44:20,911 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-17 15:44:20,912 INFO L93 Difference]: Finished difference Result 165 states and 274 transitions. [2025-03-17 15:44:20,913 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2025-03-17 15:44:20,913 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 4.857142857142857) internal successors, (68), 14 states have internal predecessors, (68), 7 states have call successors, (13), 2 states have call predecessors, (13), 5 states have return successors, (14), 5 states have call predecessors, (14), 7 states have call successors, (14) Word has length 171 [2025-03-17 15:44:20,913 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-17 15:44:20,914 INFO L225 Difference]: With dead ends: 165 [2025-03-17 15:44:20,914 INFO L226 Difference]: Without dead ends: 59 [2025-03-17 15:44:20,915 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 354 GetRequests, 334 SyntacticMatches, 4 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 55 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=96, Invalid=210, Unknown=0, NotChecked=0, Total=306 [2025-03-17 15:44:20,919 INFO L435 NwaCegarLoop]: 20 mSDtfsCounter, 28 mSDsluCounter, 32 mSDsCounter, 0 mSdLazyCounter, 78 mSolverCounterSat, 12 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 28 SdHoareTripleChecker+Valid, 52 SdHoareTripleChecker+Invalid, 90 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 78 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-17 15:44:20,919 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [28 Valid, 52 Invalid, 90 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 78 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-17 15:44:20,919 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 59 states. [2025-03-17 15:44:20,922 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 59 to 59. [2025-03-17 15:44:20,925 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 59 states, 46 states have (on average 1.108695652173913) internal successors, (51), 44 states have internal predecessors, (51), 6 states have call successors, (6), 4 states have call predecessors, (6), 5 states have return successors, (14), 10 states have call predecessors, (14), 5 states have call successors, (14) [2025-03-17 15:44:20,926 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 59 states to 59 states and 71 transitions. [2025-03-17 15:44:20,926 INFO L78 Accepts]: Start accepts. Automaton has 59 states and 71 transitions. Word has length 171 [2025-03-17 15:44:20,926 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-17 15:44:20,926 INFO L471 AbstractCegarLoop]: Abstraction has 59 states and 71 transitions. [2025-03-17 15:44:20,926 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 4.857142857142857) internal successors, (68), 14 states have internal predecessors, (68), 7 states have call successors, (13), 2 states have call predecessors, (13), 5 states have return successors, (14), 5 states have call predecessors, (14), 7 states have call successors, (14) [2025-03-17 15:44:20,926 INFO L276 IsEmpty]: Start isEmpty. Operand 59 states and 71 transitions. [2025-03-17 15:44:20,927 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 143 [2025-03-17 15:44:20,927 INFO L210 NwaCegarLoop]: Found error trace [2025-03-17 15:44:20,927 INFO L218 NwaCegarLoop]: trace histogram [16, 13, 13, 8, 8, 8, 8, 7, 7, 7, 7, 7, 6, 6, 5, 5, 5, 3, 1, 1, 1] [2025-03-17 15:44:20,934 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2025-03-17 15:44:21,127 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-17 15:44:21,128 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-03-17 15:44:21,128 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 15:44:21,128 INFO L85 PathProgramCache]: Analyzing trace with hash 1486378788, now seen corresponding path program 3 times [2025-03-17 15:44:21,128 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 15:44:21,128 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [406566956] [2025-03-17 15:44:21,128 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-17 15:44:21,128 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 15:44:21,134 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 142 statements into 12 equivalence classes. [2025-03-17 15:44:21,141 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) and asserted 49 of 142 statements. [2025-03-17 15:44:21,141 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2025-03-17 15:44:21,141 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 15:44:21,231 INFO L134 CoverageAnalysis]: Checked inductivity of 682 backedges. 119 proven. 8 refuted. 0 times theorem prover too weak. 555 trivial. 0 not checked. [2025-03-17 15:44:21,231 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-17 15:44:21,231 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [406566956] [2025-03-17 15:44:21,231 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [406566956] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-17 15:44:21,231 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [226954863] [2025-03-17 15:44:21,232 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-17 15:44:21,232 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-17 15:44:21,232 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 15:44:21,233 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-17 15:44:21,235 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2025-03-17 15:44:21,261 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 142 statements into 12 equivalence classes. [2025-03-17 15:44:21,272 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) and asserted 49 of 142 statements. [2025-03-17 15:44:21,273 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2025-03-17 15:44:21,273 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 15:44:21,274 INFO L256 TraceCheckSpWp]: Trace formula consists of 113 conjuncts, 8 conjuncts are in the unsatisfiable core [2025-03-17 15:44:21,279 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 15:44:21,341 INFO L134 CoverageAnalysis]: Checked inductivity of 682 backedges. 121 proven. 4 refuted. 0 times theorem prover too weak. 557 trivial. 0 not checked. [2025-03-17 15:44:21,342 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-17 15:44:21,525 INFO L134 CoverageAnalysis]: Checked inductivity of 682 backedges. 121 proven. 4 refuted. 0 times theorem prover too weak. 557 trivial. 0 not checked. [2025-03-17 15:44:21,525 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [226954863] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-17 15:44:21,525 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-17 15:44:21,525 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 7, 7] total 15 [2025-03-17 15:44:21,525 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [629287999] [2025-03-17 15:44:21,525 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-17 15:44:21,525 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2025-03-17 15:44:21,525 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-17 15:44:21,526 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2025-03-17 15:44:21,526 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=60, Invalid=180, Unknown=0, NotChecked=0, Total=240 [2025-03-17 15:44:21,526 INFO L87 Difference]: Start difference. First operand 59 states and 71 transitions. Second operand has 16 states, 15 states have (on average 3.3333333333333335) internal successors, (50), 16 states have internal predecessors, (50), 5 states have call successors, (7), 1 states have call predecessors, (7), 5 states have return successors, (10), 9 states have call predecessors, (10), 5 states have call successors, (10) [2025-03-17 15:44:21,579 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-17 15:44:21,580 INFO L93 Difference]: Finished difference Result 59 states and 71 transitions. [2025-03-17 15:44:21,580 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2025-03-17 15:44:21,580 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 15 states have (on average 3.3333333333333335) internal successors, (50), 16 states have internal predecessors, (50), 5 states have call successors, (7), 1 states have call predecessors, (7), 5 states have return successors, (10), 9 states have call predecessors, (10), 5 states have call successors, (10) Word has length 142 [2025-03-17 15:44:21,580 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-17 15:44:21,581 INFO L225 Difference]: With dead ends: 59 [2025-03-17 15:44:21,582 INFO L226 Difference]: Without dead ends: 58 [2025-03-17 15:44:21,582 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 292 GetRequests, 272 SyntacticMatches, 4 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 109 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=82, Invalid=224, Unknown=0, NotChecked=0, Total=306 [2025-03-17 15:44:21,582 INFO L435 NwaCegarLoop]: 18 mSDtfsCounter, 4 mSDsluCounter, 144 mSDsCounter, 0 mSdLazyCounter, 71 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 162 SdHoareTripleChecker+Invalid, 72 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 71 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-17 15:44:21,583 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [5 Valid, 162 Invalid, 72 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 71 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-17 15:44:21,584 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 58 states. [2025-03-17 15:44:21,588 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 58 to 54. [2025-03-17 15:44:21,590 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 54 states, 42 states have (on average 1.0714285714285714) internal successors, (45), 41 states have internal predecessors, (45), 6 states have call successors, (6), 4 states have call predecessors, (6), 5 states have return successors, (14), 8 states have call predecessors, (14), 5 states have call successors, (14) [2025-03-17 15:44:21,590 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 65 transitions. [2025-03-17 15:44:21,591 INFO L78 Accepts]: Start accepts. Automaton has 54 states and 65 transitions. Word has length 142 [2025-03-17 15:44:21,591 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-17 15:44:21,591 INFO L471 AbstractCegarLoop]: Abstraction has 54 states and 65 transitions. [2025-03-17 15:44:21,591 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 15 states have (on average 3.3333333333333335) internal successors, (50), 16 states have internal predecessors, (50), 5 states have call successors, (7), 1 states have call predecessors, (7), 5 states have return successors, (10), 9 states have call predecessors, (10), 5 states have call successors, (10) [2025-03-17 15:44:21,592 INFO L276 IsEmpty]: Start isEmpty. Operand 54 states and 65 transitions. [2025-03-17 15:44:21,593 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 104 [2025-03-17 15:44:21,593 INFO L210 NwaCegarLoop]: Found error trace [2025-03-17 15:44:21,593 INFO L218 NwaCegarLoop]: trace histogram [11, 10, 9, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 4, 2, 1, 1, 1] [2025-03-17 15:44:21,600 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-17 15:44:21,793 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-17 15:44:21,794 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-03-17 15:44:21,794 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 15:44:21,794 INFO L85 PathProgramCache]: Analyzing trace with hash 351317980, now seen corresponding path program 2 times [2025-03-17 15:44:21,794 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 15:44:21,794 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1752947520] [2025-03-17 15:44:21,794 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-17 15:44:21,794 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 15:44:21,798 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 103 statements into 2 equivalence classes. [2025-03-17 15:44:21,805 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 103 of 103 statements. [2025-03-17 15:44:21,806 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-17 15:44:21,806 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 15:44:21,952 INFO L134 CoverageAnalysis]: Checked inductivity of 336 backedges. 72 proven. 159 refuted. 0 times theorem prover too weak. 105 trivial. 0 not checked. [2025-03-17 15:44:21,952 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-17 15:44:21,952 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1752947520] [2025-03-17 15:44:21,952 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1752947520] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-17 15:44:21,953 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1449564230] [2025-03-17 15:44:21,953 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-17 15:44:21,953 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-17 15:44:21,953 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 15:44:21,955 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-17 15:44:21,957 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2025-03-17 15:44:21,982 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 103 statements into 2 equivalence classes. [2025-03-17 15:44:21,999 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 103 of 103 statements. [2025-03-17 15:44:21,999 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-17 15:44:21,999 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 15:44:22,000 INFO L256 TraceCheckSpWp]: Trace formula consists of 213 conjuncts, 14 conjuncts are in the unsatisfiable core [2025-03-17 15:44:22,002 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 15:44:22,086 INFO L134 CoverageAnalysis]: Checked inductivity of 336 backedges. 82 proven. 158 refuted. 0 times theorem prover too weak. 96 trivial. 0 not checked. [2025-03-17 15:44:22,086 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-17 15:44:22,591 INFO L134 CoverageAnalysis]: Checked inductivity of 336 backedges. 82 proven. 174 refuted. 0 times theorem prover too weak. 80 trivial. 0 not checked. [2025-03-17 15:44:22,592 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1449564230] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-17 15:44:22,592 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-17 15:44:22,592 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 11, 15] total 20 [2025-03-17 15:44:22,592 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1708869299] [2025-03-17 15:44:22,592 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-17 15:44:22,593 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2025-03-17 15:44:22,593 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-17 15:44:22,593 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2025-03-17 15:44:22,593 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=76, Invalid=304, Unknown=0, NotChecked=0, Total=380 [2025-03-17 15:44:22,593 INFO L87 Difference]: Start difference. First operand 54 states and 65 transitions. Second operand has 20 states, 20 states have (on average 4.55) internal successors, (91), 20 states have internal predecessors, (91), 13 states have call successors, (15), 1 states have call predecessors, (15), 7 states have return successors, (16), 7 states have call predecessors, (16), 13 states have call successors, (16) [2025-03-17 15:44:22,806 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-17 15:44:22,807 INFO L93 Difference]: Finished difference Result 132 states and 167 transitions. [2025-03-17 15:44:22,807 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2025-03-17 15:44:22,807 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 20 states have (on average 4.55) internal successors, (91), 20 states have internal predecessors, (91), 13 states have call successors, (15), 1 states have call predecessors, (15), 7 states have return successors, (16), 7 states have call predecessors, (16), 13 states have call successors, (16) Word has length 103 [2025-03-17 15:44:22,807 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-17 15:44:22,808 INFO L225 Difference]: With dead ends: 132 [2025-03-17 15:44:22,808 INFO L226 Difference]: Without dead ends: 82 [2025-03-17 15:44:22,809 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 235 GetRequests, 198 SyntacticMatches, 7 SemanticMatches, 30 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 179 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=281, Invalid=711, Unknown=0, NotChecked=0, Total=992 [2025-03-17 15:44:22,809 INFO L435 NwaCegarLoop]: 20 mSDtfsCounter, 148 mSDsluCounter, 57 mSDsCounter, 0 mSdLazyCounter, 170 mSolverCounterSat, 89 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 148 SdHoareTripleChecker+Valid, 77 SdHoareTripleChecker+Invalid, 259 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 89 IncrementalHoareTripleChecker+Valid, 170 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-17 15:44:22,809 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [148 Valid, 77 Invalid, 259 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [89 Valid, 170 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-17 15:44:22,809 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 82 states. [2025-03-17 15:44:22,828 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 82 to 72. [2025-03-17 15:44:22,828 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 72 states, 57 states have (on average 1.087719298245614) internal successors, (62), 55 states have internal predecessors, (62), 8 states have call successors, (8), 5 states have call predecessors, (8), 6 states have return successors, (17), 11 states have call predecessors, (17), 7 states have call successors, (17) [2025-03-17 15:44:22,829 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 72 states to 72 states and 87 transitions. [2025-03-17 15:44:22,829 INFO L78 Accepts]: Start accepts. Automaton has 72 states and 87 transitions. Word has length 103 [2025-03-17 15:44:22,829 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-17 15:44:22,829 INFO L471 AbstractCegarLoop]: Abstraction has 72 states and 87 transitions. [2025-03-17 15:44:22,830 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 20 states have (on average 4.55) internal successors, (91), 20 states have internal predecessors, (91), 13 states have call successors, (15), 1 states have call predecessors, (15), 7 states have return successors, (16), 7 states have call predecessors, (16), 13 states have call successors, (16) [2025-03-17 15:44:22,830 INFO L276 IsEmpty]: Start isEmpty. Operand 72 states and 87 transitions. [2025-03-17 15:44:22,830 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 85 [2025-03-17 15:44:22,830 INFO L210 NwaCegarLoop]: Found error trace [2025-03-17 15:44:22,830 INFO L218 NwaCegarLoop]: trace histogram [9, 8, 8, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 1, 1, 1, 1] [2025-03-17 15:44:22,837 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2025-03-17 15:44:23,031 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-17 15:44:23,031 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-03-17 15:44:23,033 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 15:44:23,034 INFO L85 PathProgramCache]: Analyzing trace with hash 1998624285, now seen corresponding path program 3 times [2025-03-17 15:44:23,034 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 15:44:23,034 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [915336861] [2025-03-17 15:44:23,034 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-17 15:44:23,034 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 15:44:23,037 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 84 statements into 7 equivalence classes. [2025-03-17 15:44:23,043 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) and asserted 78 of 84 statements. [2025-03-17 15:44:23,043 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2025-03-17 15:44:23,043 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 15:44:23,136 INFO L134 CoverageAnalysis]: Checked inductivity of 216 backedges. 89 proven. 48 refuted. 0 times theorem prover too weak. 79 trivial. 0 not checked. [2025-03-17 15:44:23,136 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-17 15:44:23,136 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [915336861] [2025-03-17 15:44:23,136 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [915336861] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-17 15:44:23,136 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [806502534] [2025-03-17 15:44:23,137 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-17 15:44:23,137 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-17 15:44:23,137 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 15:44:23,138 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-17 15:44:23,140 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2025-03-17 15:44:23,166 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 84 statements into 7 equivalence classes. [2025-03-17 15:44:23,181 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) and asserted 78 of 84 statements. [2025-03-17 15:44:23,181 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2025-03-17 15:44:23,181 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 15:44:23,182 INFO L256 TraceCheckSpWp]: Trace formula consists of 168 conjuncts, 8 conjuncts are in the unsatisfiable core [2025-03-17 15:44:23,183 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 15:44:23,221 INFO L134 CoverageAnalysis]: Checked inductivity of 216 backedges. 130 proven. 20 refuted. 0 times theorem prover too weak. 66 trivial. 0 not checked. [2025-03-17 15:44:23,222 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-17 15:44:23,432 INFO L134 CoverageAnalysis]: Checked inductivity of 216 backedges. 95 proven. 36 refuted. 0 times theorem prover too weak. 85 trivial. 0 not checked. [2025-03-17 15:44:23,432 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [806502534] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-17 15:44:23,432 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-17 15:44:23,432 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 8, 9] total 16 [2025-03-17 15:44:23,432 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1891246726] [2025-03-17 15:44:23,432 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-17 15:44:23,433 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2025-03-17 15:44:23,433 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-17 15:44:23,433 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2025-03-17 15:44:23,433 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=58, Invalid=182, Unknown=0, NotChecked=0, Total=240 [2025-03-17 15:44:23,434 INFO L87 Difference]: Start difference. First operand 72 states and 87 transitions. Second operand has 16 states, 16 states have (on average 4.9375) internal successors, (79), 16 states have internal predecessors, (79), 7 states have call successors, (13), 2 states have call predecessors, (13), 6 states have return successors, (15), 8 states have call predecessors, (15), 7 states have call successors, (15) [2025-03-17 15:44:23,533 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-17 15:44:23,533 INFO L93 Difference]: Finished difference Result 131 states and 161 transitions. [2025-03-17 15:44:23,533 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2025-03-17 15:44:23,534 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 16 states have (on average 4.9375) internal successors, (79), 16 states have internal predecessors, (79), 7 states have call successors, (13), 2 states have call predecessors, (13), 6 states have return successors, (15), 8 states have call predecessors, (15), 7 states have call successors, (15) Word has length 84 [2025-03-17 15:44:23,534 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-17 15:44:23,534 INFO L225 Difference]: With dead ends: 131 [2025-03-17 15:44:23,534 INFO L226 Difference]: Without dead ends: 63 [2025-03-17 15:44:23,535 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 184 GetRequests, 160 SyntacticMatches, 4 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 111 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=137, Invalid=325, Unknown=0, NotChecked=0, Total=462 [2025-03-17 15:44:23,535 INFO L435 NwaCegarLoop]: 25 mSDtfsCounter, 40 mSDsluCounter, 49 mSDsCounter, 0 mSdLazyCounter, 131 mSolverCounterSat, 22 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 40 SdHoareTripleChecker+Valid, 74 SdHoareTripleChecker+Invalid, 153 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 22 IncrementalHoareTripleChecker+Valid, 131 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-17 15:44:23,535 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [40 Valid, 74 Invalid, 153 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [22 Valid, 131 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-17 15:44:23,536 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 63 states. [2025-03-17 15:44:23,538 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 63 to 63. [2025-03-17 15:44:23,538 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 63 states, 50 states have (on average 1.06) internal successors, (53), 48 states have internal predecessors, (53), 7 states have call successors, (7), 6 states have call predecessors, (7), 5 states have return successors, (11), 8 states have call predecessors, (11), 6 states have call successors, (11) [2025-03-17 15:44:23,539 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 63 states to 63 states and 71 transitions. [2025-03-17 15:44:23,539 INFO L78 Accepts]: Start accepts. Automaton has 63 states and 71 transitions. Word has length 84 [2025-03-17 15:44:23,539 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-17 15:44:23,539 INFO L471 AbstractCegarLoop]: Abstraction has 63 states and 71 transitions. [2025-03-17 15:44:23,539 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 16 states have (on average 4.9375) internal successors, (79), 16 states have internal predecessors, (79), 7 states have call successors, (13), 2 states have call predecessors, (13), 6 states have return successors, (15), 8 states have call predecessors, (15), 7 states have call successors, (15) [2025-03-17 15:44:23,540 INFO L276 IsEmpty]: Start isEmpty. Operand 63 states and 71 transitions. [2025-03-17 15:44:23,540 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 123 [2025-03-17 15:44:23,540 INFO L210 NwaCegarLoop]: Found error trace [2025-03-17 15:44:23,540 INFO L218 NwaCegarLoop]: trace histogram [13, 12, 10, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 5, 4, 3, 1, 1, 1] [2025-03-17 15:44:23,560 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-17 15:44:23,741 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-17 15:44:23,741 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-03-17 15:44:23,742 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 15:44:23,742 INFO L85 PathProgramCache]: Analyzing trace with hash 1958505003, now seen corresponding path program 4 times [2025-03-17 15:44:23,742 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 15:44:23,742 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1190581346] [2025-03-17 15:44:23,742 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-03-17 15:44:23,742 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 15:44:23,746 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 122 statements into 2 equivalence classes. [2025-03-17 15:44:23,749 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) and asserted 73 of 122 statements. [2025-03-17 15:44:23,749 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) [2025-03-17 15:44:23,749 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 15:44:23,852 INFO L134 CoverageAnalysis]: Checked inductivity of 483 backedges. 147 proven. 168 refuted. 0 times theorem prover too weak. 168 trivial. 0 not checked. [2025-03-17 15:44:23,852 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-17 15:44:23,853 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1190581346] [2025-03-17 15:44:23,853 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1190581346] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-17 15:44:23,853 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [250032966] [2025-03-17 15:44:23,853 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-03-17 15:44:23,853 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-17 15:44:23,853 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 15:44:23,855 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-17 15:44:23,856 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2025-03-17 15:44:23,885 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 122 statements into 2 equivalence classes. [2025-03-17 15:44:23,896 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) and asserted 73 of 122 statements. [2025-03-17 15:44:23,896 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) [2025-03-17 15:44:23,896 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 15:44:23,897 INFO L256 TraceCheckSpWp]: Trace formula consists of 157 conjuncts, 14 conjuncts are in the unsatisfiable core [2025-03-17 15:44:23,899 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 15:44:23,969 INFO L134 CoverageAnalysis]: Checked inductivity of 483 backedges. 143 proven. 182 refuted. 0 times theorem prover too weak. 158 trivial. 0 not checked. [2025-03-17 15:44:23,969 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-17 15:44:24,473 INFO L134 CoverageAnalysis]: Checked inductivity of 483 backedges. 143 proven. 202 refuted. 0 times theorem prover too weak. 138 trivial. 0 not checked. [2025-03-17 15:44:24,474 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [250032966] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-17 15:44:24,474 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-17 15:44:24,474 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 11, 15] total 20 [2025-03-17 15:44:24,474 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [499053071] [2025-03-17 15:44:24,474 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-17 15:44:24,474 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2025-03-17 15:44:24,474 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-17 15:44:24,474 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2025-03-17 15:44:24,475 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=83, Invalid=297, Unknown=0, NotChecked=0, Total=380 [2025-03-17 15:44:24,475 INFO L87 Difference]: Start difference. First operand 63 states and 71 transitions. Second operand has 20 states, 20 states have (on average 4.85) internal successors, (97), 20 states have internal predecessors, (97), 13 states have call successors, (16), 1 states have call predecessors, (16), 7 states have return successors, (18), 8 states have call predecessors, (18), 13 states have call successors, (18) [2025-03-17 15:44:24,655 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-17 15:44:24,655 INFO L93 Difference]: Finished difference Result 130 states and 155 transitions. [2025-03-17 15:44:24,656 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2025-03-17 15:44:24,656 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 20 states have (on average 4.85) internal successors, (97), 20 states have internal predecessors, (97), 13 states have call successors, (16), 1 states have call predecessors, (16), 7 states have return successors, (18), 8 states have call predecessors, (18), 13 states have call successors, (18) Word has length 122 [2025-03-17 15:44:24,656 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-17 15:44:24,656 INFO L225 Difference]: With dead ends: 130 [2025-03-17 15:44:24,656 INFO L226 Difference]: Without dead ends: 71 [2025-03-17 15:44:24,657 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 267 GetRequests, 233 SyntacticMatches, 7 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 197 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=229, Invalid=583, Unknown=0, NotChecked=0, Total=812 [2025-03-17 15:44:24,657 INFO L435 NwaCegarLoop]: 32 mSDtfsCounter, 49 mSDsluCounter, 83 mSDsCounter, 0 mSdLazyCounter, 240 mSolverCounterSat, 33 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 49 SdHoareTripleChecker+Valid, 115 SdHoareTripleChecker+Invalid, 273 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 33 IncrementalHoareTripleChecker+Valid, 240 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-17 15:44:24,658 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [49 Valid, 115 Invalid, 273 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [33 Valid, 240 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-17 15:44:24,658 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 71 states. [2025-03-17 15:44:24,661 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 71 to 69. [2025-03-17 15:44:24,661 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 69 states, 55 states have (on average 1.0545454545454545) internal successors, (58), 53 states have internal predecessors, (58), 8 states have call successors, (8), 7 states have call predecessors, (8), 5 states have return successors, (13), 8 states have call predecessors, (13), 7 states have call successors, (13) [2025-03-17 15:44:24,661 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 69 states to 69 states and 79 transitions. [2025-03-17 15:44:24,661 INFO L78 Accepts]: Start accepts. Automaton has 69 states and 79 transitions. Word has length 122 [2025-03-17 15:44:24,661 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-17 15:44:24,661 INFO L471 AbstractCegarLoop]: Abstraction has 69 states and 79 transitions. [2025-03-17 15:44:24,662 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 20 states have (on average 4.85) internal successors, (97), 20 states have internal predecessors, (97), 13 states have call successors, (16), 1 states have call predecessors, (16), 7 states have return successors, (18), 8 states have call predecessors, (18), 13 states have call successors, (18) [2025-03-17 15:44:24,662 INFO L276 IsEmpty]: Start isEmpty. Operand 69 states and 79 transitions. [2025-03-17 15:44:24,662 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 143 [2025-03-17 15:44:24,662 INFO L210 NwaCegarLoop]: Found error trace [2025-03-17 15:44:24,662 INFO L218 NwaCegarLoop]: trace histogram [15, 14, 12, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 6, 5, 3, 1, 1, 1] [2025-03-17 15:44:24,668 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Ended with exit code 0 [2025-03-17 15:44:24,867 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-17 15:44:24,867 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-03-17 15:44:24,867 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 15:44:24,867 INFO L85 PathProgramCache]: Analyzing trace with hash -918115453, now seen corresponding path program 5 times [2025-03-17 15:44:24,867 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 15:44:24,867 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [976750576] [2025-03-17 15:44:24,867 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2025-03-17 15:44:24,868 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 15:44:24,872 INFO L108 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 partitioned 142 statements into 12 equivalence classes. [2025-03-17 15:44:24,881 INFO L111 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 12 check-sat command(s) and asserted 142 of 142 statements. [2025-03-17 15:44:24,882 INFO L114 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 12 check-sat command(s) [2025-03-17 15:44:24,882 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 15:44:25,284 INFO L134 CoverageAnalysis]: Checked inductivity of 668 backedges. 97 proven. 183 refuted. 0 times theorem prover too weak. 388 trivial. 0 not checked. [2025-03-17 15:44:25,284 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-17 15:44:25,284 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [976750576] [2025-03-17 15:44:25,285 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [976750576] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-17 15:44:25,285 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [382826360] [2025-03-17 15:44:25,285 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2025-03-17 15:44:25,285 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-17 15:44:25,285 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 15:44:25,287 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-17 15:44:25,289 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2025-03-17 15:44:25,322 INFO L108 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 partitioned 142 statements into 12 equivalence classes. [2025-03-17 15:44:25,348 INFO L111 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 12 check-sat command(s) and asserted 142 of 142 statements. [2025-03-17 15:44:25,348 INFO L114 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 12 check-sat command(s) [2025-03-17 15:44:25,348 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 15:44:25,349 INFO L256 TraceCheckSpWp]: Trace formula consists of 285 conjuncts, 29 conjuncts are in the unsatisfiable core [2025-03-17 15:44:25,351 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 15:44:25,481 INFO L134 CoverageAnalysis]: Checked inductivity of 668 backedges. 78 proven. 135 refuted. 0 times theorem prover too weak. 455 trivial. 0 not checked. [2025-03-17 15:44:25,481 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-17 15:44:26,320 INFO L134 CoverageAnalysis]: Checked inductivity of 668 backedges. 144 proven. 128 refuted. 0 times theorem prover too weak. 396 trivial. 0 not checked. [2025-03-17 15:44:26,320 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [382826360] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-17 15:44:26,320 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-17 15:44:26,320 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 12, 17] total 32 [2025-03-17 15:44:26,320 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1054839394] [2025-03-17 15:44:26,320 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-17 15:44:26,321 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 33 states [2025-03-17 15:44:26,321 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-17 15:44:26,321 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 33 interpolants. [2025-03-17 15:44:26,322 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=254, Invalid=802, Unknown=0, NotChecked=0, Total=1056 [2025-03-17 15:44:26,322 INFO L87 Difference]: Start difference. First operand 69 states and 79 transitions. Second operand has 33 states, 32 states have (on average 2.6875) internal successors, (86), 33 states have internal predecessors, (86), 8 states have call successors, (9), 1 states have call predecessors, (9), 9 states have return successors, (23), 22 states have call predecessors, (23), 8 states have call successors, (23) [2025-03-17 15:44:26,483 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-17 15:44:26,483 INFO L93 Difference]: Finished difference Result 115 states and 154 transitions. [2025-03-17 15:44:26,483 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2025-03-17 15:44:26,484 INFO L78 Accepts]: Start accepts. Automaton has has 33 states, 32 states have (on average 2.6875) internal successors, (86), 33 states have internal predecessors, (86), 8 states have call successors, (9), 1 states have call predecessors, (9), 9 states have return successors, (23), 22 states have call predecessors, (23), 8 states have call successors, (23) Word has length 142 [2025-03-17 15:44:26,484 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-17 15:44:26,485 INFO L225 Difference]: With dead ends: 115 [2025-03-17 15:44:26,485 INFO L226 Difference]: Without dead ends: 114 [2025-03-17 15:44:26,485 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 317 GetRequests, 266 SyntacticMatches, 14 SemanticMatches, 37 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 782 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=357, Invalid=1125, Unknown=0, NotChecked=0, Total=1482 [2025-03-17 15:44:26,486 INFO L435 NwaCegarLoop]: 18 mSDtfsCounter, 24 mSDsluCounter, 111 mSDsCounter, 0 mSdLazyCounter, 126 mSolverCounterSat, 12 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 32 SdHoareTripleChecker+Valid, 129 SdHoareTripleChecker+Invalid, 138 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 126 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-17 15:44:26,486 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [32 Valid, 129 Invalid, 138 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 126 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-17 15:44:26,486 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 114 states. [2025-03-17 15:44:26,492 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 114 to 96. [2025-03-17 15:44:26,494 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 96 states, 76 states have (on average 1.0394736842105263) internal successors, (79), 74 states have internal predecessors, (79), 11 states have call successors, (11), 7 states have call predecessors, (11), 8 states have return successors, (37), 14 states have call predecessors, (37), 10 states have call successors, (37) [2025-03-17 15:44:26,496 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 96 states to 96 states and 127 transitions. [2025-03-17 15:44:26,497 INFO L78 Accepts]: Start accepts. Automaton has 96 states and 127 transitions. Word has length 142 [2025-03-17 15:44:26,497 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-17 15:44:26,497 INFO L471 AbstractCegarLoop]: Abstraction has 96 states and 127 transitions. [2025-03-17 15:44:26,497 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 33 states, 32 states have (on average 2.6875) internal successors, (86), 33 states have internal predecessors, (86), 8 states have call successors, (9), 1 states have call predecessors, (9), 9 states have return successors, (23), 22 states have call predecessors, (23), 8 states have call successors, (23) [2025-03-17 15:44:26,497 INFO L276 IsEmpty]: Start isEmpty. Operand 96 states and 127 transitions. [2025-03-17 15:44:26,499 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 339 [2025-03-17 15:44:26,500 INFO L210 NwaCegarLoop]: Found error trace [2025-03-17 15:44:26,500 INFO L218 NwaCegarLoop]: trace histogram [35, 34, 28, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 16, 11, 7, 1, 1, 1] [2025-03-17 15:44:26,506 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-17 15:44:26,705 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-17 15:44:26,706 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-03-17 15:44:26,706 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 15:44:26,707 INFO L85 PathProgramCache]: Analyzing trace with hash 651195651, now seen corresponding path program 6 times [2025-03-17 15:44:26,707 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 15:44:26,707 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1033772251] [2025-03-17 15:44:26,707 INFO L95 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2025-03-17 15:44:26,707 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 15:44:26,715 INFO L108 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE partitioned 338 statements into 27 equivalence classes. [2025-03-17 15:44:26,740 INFO L111 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 18 check-sat command(s) and asserted 241 of 338 statements. [2025-03-17 15:44:26,741 INFO L114 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 18 check-sat command(s) [2025-03-17 15:44:26,741 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 15:44:26,969 INFO L134 CoverageAnalysis]: Checked inductivity of 4050 backedges. 439 proven. 1002 refuted. 0 times theorem prover too weak. 2609 trivial. 0 not checked. [2025-03-17 15:44:26,969 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-17 15:44:26,969 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1033772251] [2025-03-17 15:44:26,969 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1033772251] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-17 15:44:26,969 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [147827952] [2025-03-17 15:44:26,970 INFO L95 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2025-03-17 15:44:26,970 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-17 15:44:26,970 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 15:44:26,971 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-17 15:44:26,973 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2025-03-17 15:44:27,024 INFO L108 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE partitioned 338 statements into 27 equivalence classes. [2025-03-17 15:44:27,067 INFO L111 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 18 check-sat command(s) and asserted 241 of 338 statements. [2025-03-17 15:44:27,067 INFO L114 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 18 check-sat command(s) [2025-03-17 15:44:27,067 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 15:44:27,069 INFO L256 TraceCheckSpWp]: Trace formula consists of 472 conjuncts, 15 conjuncts are in the unsatisfiable core [2025-03-17 15:44:27,071 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 15:44:27,175 INFO L134 CoverageAnalysis]: Checked inductivity of 4050 backedges. 442 proven. 1021 refuted. 0 times theorem prover too weak. 2587 trivial. 0 not checked. [2025-03-17 15:44:27,176 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-17 15:44:27,872 INFO L134 CoverageAnalysis]: Checked inductivity of 4050 backedges. 444 proven. 1035 refuted. 0 times theorem prover too weak. 2571 trivial. 0 not checked. [2025-03-17 15:44:27,872 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [147827952] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-17 15:44:27,872 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-17 15:44:27,873 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 12, 16] total 23 [2025-03-17 15:44:27,873 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1469638494] [2025-03-17 15:44:27,873 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-17 15:44:27,873 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2025-03-17 15:44:27,873 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-17 15:44:27,874 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2025-03-17 15:44:27,874 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=103, Invalid=403, Unknown=0, NotChecked=0, Total=506 [2025-03-17 15:44:27,874 INFO L87 Difference]: Start difference. First operand 96 states and 127 transitions. Second operand has 23 states, 23 states have (on average 4.826086956521739) internal successors, (111), 23 states have internal predecessors, (111), 13 states have call successors, (19), 1 states have call predecessors, (19), 8 states have return successors, (22), 11 states have call predecessors, (22), 13 states have call successors, (22) [2025-03-17 15:44:28,181 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-17 15:44:28,181 INFO L93 Difference]: Finished difference Result 219 states and 311 transitions. [2025-03-17 15:44:28,181 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 25 states. [2025-03-17 15:44:28,181 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 23 states have (on average 4.826086956521739) internal successors, (111), 23 states have internal predecessors, (111), 13 states have call successors, (19), 1 states have call predecessors, (19), 8 states have return successors, (22), 11 states have call predecessors, (22), 13 states have call successors, (22) Word has length 338 [2025-03-17 15:44:28,182 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-17 15:44:28,183 INFO L225 Difference]: With dead ends: 219 [2025-03-17 15:44:28,183 INFO L226 Difference]: Without dead ends: 114 [2025-03-17 15:44:28,184 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 710 GetRequests, 664 SyntacticMatches, 7 SemanticMatches, 39 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 370 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=451, Invalid=1189, Unknown=0, NotChecked=0, Total=1640 [2025-03-17 15:44:28,184 INFO L435 NwaCegarLoop]: 28 mSDtfsCounter, 132 mSDsluCounter, 92 mSDsCounter, 0 mSdLazyCounter, 356 mSolverCounterSat, 62 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 132 SdHoareTripleChecker+Valid, 120 SdHoareTripleChecker+Invalid, 418 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 62 IncrementalHoareTripleChecker+Valid, 356 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-03-17 15:44:28,184 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [132 Valid, 120 Invalid, 418 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [62 Valid, 356 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-03-17 15:44:28,185 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 114 states. [2025-03-17 15:44:28,193 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 114 to 111. [2025-03-17 15:44:28,194 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 111 states, 89 states have (on average 1.0449438202247192) internal successors, (93), 86 states have internal predecessors, (93), 13 states have call successors, (13), 10 states have call predecessors, (13), 8 states have return successors, (35), 14 states have call predecessors, (35), 12 states have call successors, (35) [2025-03-17 15:44:28,195 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 111 states to 111 states and 141 transitions. [2025-03-17 15:44:28,195 INFO L78 Accepts]: Start accepts. Automaton has 111 states and 141 transitions. Word has length 338 [2025-03-17 15:44:28,195 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-17 15:44:28,196 INFO L471 AbstractCegarLoop]: Abstraction has 111 states and 141 transitions. [2025-03-17 15:44:28,196 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 23 states have (on average 4.826086956521739) internal successors, (111), 23 states have internal predecessors, (111), 13 states have call successors, (19), 1 states have call predecessors, (19), 8 states have return successors, (22), 11 states have call predecessors, (22), 13 states have call successors, (22) [2025-03-17 15:44:28,197 INFO L276 IsEmpty]: Start isEmpty. Operand 111 states and 141 transitions. [2025-03-17 15:44:28,198 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 300 [2025-03-17 15:44:28,198 INFO L210 NwaCegarLoop]: Found error trace [2025-03-17 15:44:28,199 INFO L218 NwaCegarLoop]: trace histogram [31, 30, 25, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 14, 10, 6, 1, 1, 1] [2025-03-17 15:44:28,205 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-17 15:44:28,399 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-17 15:44:28,399 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-03-17 15:44:28,400 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 15:44:28,400 INFO L85 PathProgramCache]: Analyzing trace with hash 140986160, now seen corresponding path program 7 times [2025-03-17 15:44:28,400 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 15:44:28,400 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1761342942] [2025-03-17 15:44:28,400 INFO L95 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2025-03-17 15:44:28,400 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 15:44:28,407 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 299 statements into 1 equivalence classes. [2025-03-17 15:44:28,418 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 299 of 299 statements. [2025-03-17 15:44:28,418 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 15:44:28,418 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 15:44:28,710 INFO L134 CoverageAnalysis]: Checked inductivity of 3150 backedges. 484 proven. 1076 refuted. 0 times theorem prover too weak. 1590 trivial. 0 not checked. [2025-03-17 15:44:28,710 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-17 15:44:28,710 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1761342942] [2025-03-17 15:44:28,710 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1761342942] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-17 15:44:28,710 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1565438631] [2025-03-17 15:44:28,710 INFO L95 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2025-03-17 15:44:28,711 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-17 15:44:28,711 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 15:44:28,712 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-17 15:44:28,714 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-17 15:44:28,763 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 299 statements into 1 equivalence classes. [2025-03-17 15:44:28,803 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 299 of 299 statements. [2025-03-17 15:44:28,803 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 15:44:28,803 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 15:44:28,808 INFO L256 TraceCheckSpWp]: Trace formula consists of 575 conjuncts, 22 conjuncts are in the unsatisfiable core [2025-03-17 15:44:28,810 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 15:44:28,933 INFO L134 CoverageAnalysis]: Checked inductivity of 3150 backedges. 569 proven. 1181 refuted. 0 times theorem prover too weak. 1400 trivial. 0 not checked. [2025-03-17 15:44:28,934 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-17 15:44:30,107 INFO L134 CoverageAnalysis]: Checked inductivity of 3150 backedges. 569 proven. 1253 refuted. 0 times theorem prover too weak. 1328 trivial. 0 not checked. [2025-03-17 15:44:30,108 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1565438631] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-17 15:44:30,108 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-17 15:44:30,108 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 15, 23] total 28 [2025-03-17 15:44:30,108 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [365487391] [2025-03-17 15:44:30,108 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-17 15:44:30,108 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 28 states [2025-03-17 15:44:30,108 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-17 15:44:30,109 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 28 interpolants. [2025-03-17 15:44:30,109 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=134, Invalid=622, Unknown=0, NotChecked=0, Total=756 [2025-03-17 15:44:30,109 INFO L87 Difference]: Start difference. First operand 111 states and 141 transitions. Second operand has 28 states, 28 states have (on average 5.285714285714286) internal successors, (148), 28 states have internal predecessors, (148), 21 states have call successors, (25), 1 states have call predecessors, (25), 11 states have return successors, (32), 13 states have call predecessors, (32), 21 states have call successors, (32) [2025-03-17 15:44:30,455 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-17 15:44:30,456 INFO L93 Difference]: Finished difference Result 258 states and 351 transitions. [2025-03-17 15:44:30,456 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2025-03-17 15:44:30,456 INFO L78 Accepts]: Start accepts. Automaton has has 28 states, 28 states have (on average 5.285714285714286) internal successors, (148), 28 states have internal predecessors, (148), 21 states have call successors, (25), 1 states have call predecessors, (25), 11 states have return successors, (32), 13 states have call predecessors, (32), 21 states have call successors, (32) Word has length 299 [2025-03-17 15:44:30,457 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-17 15:44:30,458 INFO L225 Difference]: With dead ends: 258 [2025-03-17 15:44:30,458 INFO L226 Difference]: Without dead ends: 151 [2025-03-17 15:44:30,459 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 641 GetRequests, 583 SyntacticMatches, 11 SemanticMatches, 47 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 544 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=604, Invalid=1748, Unknown=0, NotChecked=0, Total=2352 [2025-03-17 15:44:30,459 INFO L435 NwaCegarLoop]: 34 mSDtfsCounter, 253 mSDsluCounter, 118 mSDsCounter, 0 mSdLazyCounter, 389 mSolverCounterSat, 114 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 253 SdHoareTripleChecker+Valid, 152 SdHoareTripleChecker+Invalid, 503 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 114 IncrementalHoareTripleChecker+Valid, 389 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-03-17 15:44:30,460 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [253 Valid, 152 Invalid, 503 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [114 Valid, 389 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-03-17 15:44:30,460 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 151 states. [2025-03-17 15:44:30,465 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 151 to 129. [2025-03-17 15:44:30,466 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 129 states, 104 states have (on average 1.0480769230769231) internal successors, (109), 100 states have internal predecessors, (109), 15 states have call successors, (15), 11 states have call predecessors, (15), 9 states have return successors, (37), 17 states have call predecessors, (37), 14 states have call successors, (37) [2025-03-17 15:44:30,466 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 129 states to 129 states and 161 transitions. [2025-03-17 15:44:30,467 INFO L78 Accepts]: Start accepts. Automaton has 129 states and 161 transitions. Word has length 299 [2025-03-17 15:44:30,467 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-17 15:44:30,467 INFO L471 AbstractCegarLoop]: Abstraction has 129 states and 161 transitions. [2025-03-17 15:44:30,467 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 28 states, 28 states have (on average 5.285714285714286) internal successors, (148), 28 states have internal predecessors, (148), 21 states have call successors, (25), 1 states have call predecessors, (25), 11 states have return successors, (32), 13 states have call predecessors, (32), 21 states have call successors, (32) [2025-03-17 15:44:30,467 INFO L276 IsEmpty]: Start isEmpty. Operand 129 states and 161 transitions. [2025-03-17 15:44:30,469 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 300 [2025-03-17 15:44:30,469 INFO L210 NwaCegarLoop]: Found error trace [2025-03-17 15:44:30,469 INFO L218 NwaCegarLoop]: trace histogram [31, 30, 25, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 14, 10, 6, 1, 1, 1] [2025-03-17 15:44:30,475 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-17 15:44:30,669 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-17 15:44:30,670 INFO L396 AbstractCegarLoop]: === Iteration 17 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-03-17 15:44:30,670 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 15:44:30,670 INFO L85 PathProgramCache]: Analyzing trace with hash 587176008, now seen corresponding path program 8 times [2025-03-17 15:44:30,670 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 15:44:30,670 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [754004146] [2025-03-17 15:44:30,670 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-17 15:44:30,670 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 15:44:30,677 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 299 statements into 2 equivalence classes. [2025-03-17 15:44:30,699 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 299 of 299 statements. [2025-03-17 15:44:30,699 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-17 15:44:30,699 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 15:44:30,949 INFO L134 CoverageAnalysis]: Checked inductivity of 3150 backedges. 522 proven. 990 refuted. 0 times theorem prover too weak. 1638 trivial. 0 not checked. [2025-03-17 15:44:30,949 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-17 15:44:30,949 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [754004146] [2025-03-17 15:44:30,949 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [754004146] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-17 15:44:30,949 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1566620667] [2025-03-17 15:44:30,949 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-17 15:44:30,949 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-17 15:44:30,949 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 15:44:30,951 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-17 15:44:30,953 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-17 15:44:31,011 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 299 statements into 2 equivalence classes. [2025-03-17 15:44:31,056 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 299 of 299 statements. [2025-03-17 15:44:31,056 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-17 15:44:31,056 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 15:44:31,058 INFO L256 TraceCheckSpWp]: Trace formula consists of 575 conjuncts, 18 conjuncts are in the unsatisfiable core [2025-03-17 15:44:31,061 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 15:44:31,160 INFO L134 CoverageAnalysis]: Checked inductivity of 3150 backedges. 1787 proven. 484 refuted. 0 times theorem prover too weak. 879 trivial. 0 not checked. [2025-03-17 15:44:31,160 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-17 15:44:32,193 INFO L134 CoverageAnalysis]: Checked inductivity of 3150 backedges. 517 proven. 1101 refuted. 0 times theorem prover too weak. 1532 trivial. 0 not checked. [2025-03-17 15:44:32,193 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1566620667] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-17 15:44:32,193 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-17 15:44:32,193 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 13, 19] total 24 [2025-03-17 15:44:32,193 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1605757942] [2025-03-17 15:44:32,193 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-17 15:44:32,194 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 24 states [2025-03-17 15:44:32,194 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-17 15:44:32,194 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2025-03-17 15:44:32,195 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=111, Invalid=441, Unknown=0, NotChecked=0, Total=552 [2025-03-17 15:44:32,195 INFO L87 Difference]: Start difference. First operand 129 states and 161 transitions. Second operand has 24 states, 24 states have (on average 5.541666666666667) internal successors, (133), 24 states have internal predecessors, (133), 18 states have call successors, (23), 2 states have call predecessors, (23), 10 states have return successors, (28), 10 states have call predecessors, (28), 18 states have call successors, (28) [2025-03-17 15:44:32,418 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-17 15:44:32,418 INFO L93 Difference]: Finished difference Result 242 states and 315 transitions. [2025-03-17 15:44:32,420 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2025-03-17 15:44:32,420 INFO L78 Accepts]: Start accepts. Automaton has has 24 states, 24 states have (on average 5.541666666666667) internal successors, (133), 24 states have internal predecessors, (133), 18 states have call successors, (23), 2 states have call predecessors, (23), 10 states have return successors, (28), 10 states have call predecessors, (28), 18 states have call successors, (28) Word has length 299 [2025-03-17 15:44:32,420 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-17 15:44:32,421 INFO L225 Difference]: With dead ends: 242 [2025-03-17 15:44:32,422 INFO L226 Difference]: Without dead ends: 117 [2025-03-17 15:44:32,422 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 628 GetRequests, 585 SyntacticMatches, 9 SemanticMatches, 34 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 325 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=349, Invalid=911, Unknown=0, NotChecked=0, Total=1260 [2025-03-17 15:44:32,423 INFO L435 NwaCegarLoop]: 39 mSDtfsCounter, 106 mSDsluCounter, 107 mSDsCounter, 0 mSdLazyCounter, 359 mSolverCounterSat, 58 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 106 SdHoareTripleChecker+Valid, 146 SdHoareTripleChecker+Invalid, 417 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 58 IncrementalHoareTripleChecker+Valid, 359 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-17 15:44:32,423 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [106 Valid, 146 Invalid, 417 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [58 Valid, 359 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-17 15:44:32,423 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 117 states. [2025-03-17 15:44:32,427 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 117 to 105. [2025-03-17 15:44:32,427 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 105 states, 84 states have (on average 1.0357142857142858) internal successors, (87), 82 states have internal predecessors, (87), 13 states have call successors, (13), 10 states have call predecessors, (13), 7 states have return successors, (26), 12 states have call predecessors, (26), 12 states have call successors, (26) [2025-03-17 15:44:32,428 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 105 states to 105 states and 126 transitions. [2025-03-17 15:44:32,428 INFO L78 Accepts]: Start accepts. Automaton has 105 states and 126 transitions. Word has length 299 [2025-03-17 15:44:32,428 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-17 15:44:32,428 INFO L471 AbstractCegarLoop]: Abstraction has 105 states and 126 transitions. [2025-03-17 15:44:32,428 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 24 states, 24 states have (on average 5.541666666666667) internal successors, (133), 24 states have internal predecessors, (133), 18 states have call successors, (23), 2 states have call predecessors, (23), 10 states have return successors, (28), 10 states have call predecessors, (28), 18 states have call successors, (28) [2025-03-17 15:44:32,429 INFO L276 IsEmpty]: Start isEmpty. Operand 105 states and 126 transitions. [2025-03-17 15:44:32,435 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 660 [2025-03-17 15:44:32,436 INFO L210 NwaCegarLoop]: Found error trace [2025-03-17 15:44:32,436 INFO L218 NwaCegarLoop]: trace histogram [69, 65, 56, 35, 35, 35, 35, 33, 33, 33, 33, 33, 32, 32, 32, 31, 21, 13, 1, 1, 1] [2025-03-17 15:44:32,443 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Ended with exit code 0 [2025-03-17 15:44:32,639 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-17 15:44:32,640 INFO L396 AbstractCegarLoop]: === Iteration 18 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-03-17 15:44:32,640 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 15:44:32,640 INFO L85 PathProgramCache]: Analyzing trace with hash -1518734296, now seen corresponding path program 9 times [2025-03-17 15:44:32,640 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 15:44:32,640 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [833384772] [2025-03-17 15:44:32,641 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-17 15:44:32,641 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 15:44:32,664 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 659 statements into 54 equivalence classes. [2025-03-17 15:44:32,699 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 29 check-sat command(s) and asserted 397 of 659 statements. [2025-03-17 15:44:32,699 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 29 check-sat command(s) [2025-03-17 15:44:32,699 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 15:44:34,203 INFO L134 CoverageAnalysis]: Checked inductivity of 15777 backedges. 4590 proven. 1470 refuted. 0 times theorem prover too weak. 9717 trivial. 0 not checked. [2025-03-17 15:44:34,204 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-17 15:44:34,204 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [833384772] [2025-03-17 15:44:34,204 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [833384772] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-17 15:44:34,204 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2032024356] [2025-03-17 15:44:34,204 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-17 15:44:34,204 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-17 15:44:34,204 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 15:44:34,206 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-17 15:44:34,209 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-17 15:44:34,292 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 659 statements into 54 equivalence classes. [2025-03-17 15:44:34,360 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 29 check-sat command(s) and asserted 397 of 659 statements. [2025-03-17 15:44:34,360 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 29 check-sat command(s) [2025-03-17 15:44:34,360 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 15:44:34,362 INFO L256 TraceCheckSpWp]: Trace formula consists of 756 conjuncts, 81 conjuncts are in the unsatisfiable core [2025-03-17 15:44:34,368 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 15:44:34,652 INFO L134 CoverageAnalysis]: Checked inductivity of 15777 backedges. 4580 proven. 1112 refuted. 0 times theorem prover too weak. 10085 trivial. 0 not checked. [2025-03-17 15:44:34,652 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-17 15:44:39,529 INFO L134 CoverageAnalysis]: Checked inductivity of 15777 backedges. 4909 proven. 1015 refuted. 0 times theorem prover too weak. 9853 trivial. 0 not checked. [2025-03-17 15:44:39,529 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2032024356] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-17 15:44:39,529 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-17 15:44:39,529 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 18, 29] total 45 [2025-03-17 15:44:39,529 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [704197729] [2025-03-17 15:44:39,529 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-17 15:44:39,530 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 46 states [2025-03-17 15:44:39,530 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-17 15:44:39,531 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 46 interpolants. [2025-03-17 15:44:39,531 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=463, Invalid=1607, Unknown=0, NotChecked=0, Total=2070 [2025-03-17 15:44:39,532 INFO L87 Difference]: Start difference. First operand 105 states and 126 transitions. Second operand has 46 states, 45 states have (on average 2.8) internal successors, (126), 46 states have internal predecessors, (126), 12 states have call successors, (14), 1 states have call predecessors, (14), 14 states have return successors, (33), 32 states have call predecessors, (33), 12 states have call successors, (33) [2025-03-17 15:44:39,758 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-17 15:44:39,758 INFO L93 Difference]: Finished difference Result 169 states and 242 transitions. [2025-03-17 15:44:39,759 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 33 states. [2025-03-17 15:44:39,760 INFO L78 Accepts]: Start accepts. Automaton has has 46 states, 45 states have (on average 2.8) internal successors, (126), 46 states have internal predecessors, (126), 12 states have call successors, (14), 1 states have call predecessors, (14), 14 states have return successors, (33), 32 states have call predecessors, (33), 12 states have call successors, (33) Word has length 659 [2025-03-17 15:44:39,760 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-17 15:44:39,764 INFO L225 Difference]: With dead ends: 169 [2025-03-17 15:44:39,764 INFO L226 Difference]: Without dead ends: 168 [2025-03-17 15:44:39,764 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 1406 GetRequests, 1302 SyntacticMatches, 51 SemanticMatches, 53 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2580 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=654, Invalid=2316, Unknown=0, NotChecked=0, Total=2970 [2025-03-17 15:44:39,765 INFO L435 NwaCegarLoop]: 18 mSDtfsCounter, 26 mSDsluCounter, 164 mSDsCounter, 0 mSdLazyCounter, 195 mSolverCounterSat, 12 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 39 SdHoareTripleChecker+Valid, 182 SdHoareTripleChecker+Invalid, 207 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 195 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-17 15:44:39,765 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [39 Valid, 182 Invalid, 207 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 195 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-17 15:44:39,765 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 168 states. [2025-03-17 15:44:39,773 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 168 to 141. [2025-03-17 15:44:39,773 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 141 states, 112 states have (on average 1.0267857142857142) internal successors, (115), 110 states have internal predecessors, (115), 17 states have call successors, (17), 10 states have call predecessors, (17), 11 states have return successors, (70), 20 states have call predecessors, (70), 16 states have call successors, (70) [2025-03-17 15:44:39,774 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 141 states to 141 states and 202 transitions. [2025-03-17 15:44:39,774 INFO L78 Accepts]: Start accepts. Automaton has 141 states and 202 transitions. Word has length 659 [2025-03-17 15:44:39,775 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-17 15:44:39,775 INFO L471 AbstractCegarLoop]: Abstraction has 141 states and 202 transitions. [2025-03-17 15:44:39,775 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 46 states, 45 states have (on average 2.8) internal successors, (126), 46 states have internal predecessors, (126), 12 states have call successors, (14), 1 states have call predecessors, (14), 14 states have return successors, (33), 32 states have call predecessors, (33), 12 states have call successors, (33) [2025-03-17 15:44:39,775 INFO L276 IsEmpty]: Start isEmpty. Operand 141 states and 202 transitions. [2025-03-17 15:44:39,782 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1262 [2025-03-17 15:44:39,782 INFO L210 NwaCegarLoop]: Found error trace [2025-03-17 15:44:39,782 INFO L218 NwaCegarLoop]: trace histogram [130, 127, 105, 65, 65, 65, 65, 64, 64, 64, 64, 64, 63, 63, 63, 62, 40, 25, 1, 1, 1] [2025-03-17 15:44:39,788 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Forceful destruction successful, exit code 0 [2025-03-17 15:44:39,982 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 16 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable17 [2025-03-17 15:44:39,982 INFO L396 AbstractCegarLoop]: === Iteration 19 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-03-17 15:44:39,983 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 15:44:39,983 INFO L85 PathProgramCache]: Analyzing trace with hash 369202723, now seen corresponding path program 10 times [2025-03-17 15:44:39,983 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 15:44:39,983 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1542151421] [2025-03-17 15:44:39,983 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-03-17 15:44:39,983 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 15:44:40,008 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 1261 statements into 2 equivalence classes. [2025-03-17 15:44:40,060 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) and asserted 749 of 1261 statements. [2025-03-17 15:44:40,060 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) [2025-03-17 15:44:40,060 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 15:44:40,633 INFO L134 CoverageAnalysis]: Checked inductivity of 58395 backedges. 1208 proven. 8337 refuted. 0 times theorem prover too weak. 48850 trivial. 0 not checked. [2025-03-17 15:44:40,633 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-17 15:44:40,633 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1542151421] [2025-03-17 15:44:40,633 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1542151421] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-17 15:44:40,633 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1008275350] [2025-03-17 15:44:40,634 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-03-17 15:44:40,634 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-17 15:44:40,634 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 15:44:40,635 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-17 15:44:40,637 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2025-03-17 15:44:40,789 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 1261 statements into 2 equivalence classes. [2025-03-17 15:44:40,882 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) and asserted 749 of 1261 statements. [2025-03-17 15:44:40,883 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) [2025-03-17 15:44:40,883 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 15:44:40,886 INFO L256 TraceCheckSpWp]: Trace formula consists of 1568 conjuncts, 26 conjuncts are in the unsatisfiable core [2025-03-17 15:44:40,895 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 15:44:41,031 INFO L134 CoverageAnalysis]: Checked inductivity of 58395 backedges. 29471 proven. 2740 refuted. 0 times theorem prover too weak. 26184 trivial. 0 not checked. [2025-03-17 15:44:41,032 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-17 15:44:43,116 INFO L134 CoverageAnalysis]: Checked inductivity of 58395 backedges. 1443 proven. 10132 refuted. 0 times theorem prover too weak. 46820 trivial. 0 not checked. [2025-03-17 15:44:43,117 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1008275350] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-17 15:44:43,117 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-17 15:44:43,117 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 17, 25] total 30 [2025-03-17 15:44:43,117 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2060589947] [2025-03-17 15:44:43,117 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-17 15:44:43,119 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 30 states [2025-03-17 15:44:43,119 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-17 15:44:43,119 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 30 interpolants. [2025-03-17 15:44:43,120 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=140, Invalid=730, Unknown=0, NotChecked=0, Total=870 [2025-03-17 15:44:43,120 INFO L87 Difference]: Start difference. First operand 141 states and 202 transitions. Second operand has 30 states, 30 states have (on average 5.933333333333334) internal successors, (178), 30 states have internal predecessors, (178), 25 states have call successors, (32), 4 states have call predecessors, (32), 12 states have return successors, (37), 14 states have call predecessors, (37), 23 states have call successors, (37) [2025-03-17 15:44:43,474 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-17 15:44:43,475 INFO L93 Difference]: Finished difference Result 351 states and 576 transitions. [2025-03-17 15:44:43,475 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 31 states. [2025-03-17 15:44:43,475 INFO L78 Accepts]: Start accepts. Automaton has has 30 states, 30 states have (on average 5.933333333333334) internal successors, (178), 30 states have internal predecessors, (178), 25 states have call successors, (32), 4 states have call predecessors, (32), 12 states have return successors, (37), 14 states have call predecessors, (37), 23 states have call successors, (37) Word has length 1261 [2025-03-17 15:44:43,476 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-17 15:44:43,477 INFO L225 Difference]: With dead ends: 351 [2025-03-17 15:44:43,477 INFO L226 Difference]: Without dead ends: 214 [2025-03-17 15:44:43,480 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 2574 GetRequests, 2505 SyntacticMatches, 15 SemanticMatches, 54 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 739 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=796, Invalid=2284, Unknown=0, NotChecked=0, Total=3080 [2025-03-17 15:44:43,481 INFO L435 NwaCegarLoop]: 28 mSDtfsCounter, 259 mSDsluCounter, 102 mSDsCounter, 0 mSdLazyCounter, 292 mSolverCounterSat, 118 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 259 SdHoareTripleChecker+Valid, 130 SdHoareTripleChecker+Invalid, 410 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 118 IncrementalHoareTripleChecker+Valid, 292 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-17 15:44:43,481 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [259 Valid, 130 Invalid, 410 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [118 Valid, 292 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-17 15:44:43,482 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 214 states. [2025-03-17 15:44:43,493 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 214 to 192. [2025-03-17 15:44:43,494 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 192 states, 154 states have (on average 1.0324675324675325) internal successors, (159), 150 states have internal predecessors, (159), 23 states have call successors, (23), 14 states have call predecessors, (23), 14 states have return successors, (90), 27 states have call predecessors, (90), 22 states have call successors, (90) [2025-03-17 15:44:43,496 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 192 states to 192 states and 272 transitions. [2025-03-17 15:44:43,497 INFO L78 Accepts]: Start accepts. Automaton has 192 states and 272 transitions. Word has length 1261 [2025-03-17 15:44:43,497 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-17 15:44:43,497 INFO L471 AbstractCegarLoop]: Abstraction has 192 states and 272 transitions. [2025-03-17 15:44:43,498 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 30 states, 30 states have (on average 5.933333333333334) internal successors, (178), 30 states have internal predecessors, (178), 25 states have call successors, (32), 4 states have call predecessors, (32), 12 states have return successors, (37), 14 states have call predecessors, (37), 23 states have call successors, (37) [2025-03-17 15:44:43,498 INFO L276 IsEmpty]: Start isEmpty. Operand 192 states and 272 transitions. [2025-03-17 15:44:43,505 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1256 [2025-03-17 15:44:43,505 INFO L210 NwaCegarLoop]: Found error trace [2025-03-17 15:44:43,505 INFO L218 NwaCegarLoop]: trace histogram [129, 127, 104, 64, 64, 64, 64, 64, 64, 64, 64, 64, 63, 63, 63, 62, 40, 25, 1, 1, 1] [2025-03-17 15:44:43,514 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Forceful destruction successful, exit code 0 [2025-03-17 15:44:43,705 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable18,17 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-17 15:44:43,706 INFO L396 AbstractCegarLoop]: === Iteration 20 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-03-17 15:44:43,706 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 15:44:43,706 INFO L85 PathProgramCache]: Analyzing trace with hash 131560666, now seen corresponding path program 11 times [2025-03-17 15:44:43,706 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 15:44:43,707 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [461216973] [2025-03-17 15:44:43,707 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2025-03-17 15:44:43,707 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 15:44:43,725 INFO L108 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 partitioned 1255 statements into 98 equivalence classes. [2025-03-17 15:44:43,799 INFO L111 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 69 check-sat command(s) and asserted 820 of 1255 statements. [2025-03-17 15:44:43,800 INFO L114 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 69 check-sat command(s) [2025-03-17 15:44:43,800 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 15:44:44,906 INFO L134 CoverageAnalysis]: Checked inductivity of 57841 backedges. 7343 proven. 6273 refuted. 0 times theorem prover too weak. 44225 trivial. 0 not checked. [2025-03-17 15:44:44,906 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-17 15:44:44,906 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [461216973] [2025-03-17 15:44:44,906 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [461216973] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-17 15:44:44,906 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1529178459] [2025-03-17 15:44:44,906 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2025-03-17 15:44:44,906 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-17 15:44:44,907 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 15:44:44,908 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-17 15:44:44,910 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Waiting until timeout for monitored process [2025-03-17 15:44:45,108 INFO L108 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 partitioned 1255 statements into 98 equivalence classes. [2025-03-17 15:44:45,271 INFO L111 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 69 check-sat command(s) and asserted 820 of 1255 statements. [2025-03-17 15:44:45,271 INFO L114 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 69 check-sat command(s) [2025-03-17 15:44:45,271 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 15:44:45,276 INFO L256 TraceCheckSpWp]: Trace formula consists of 1516 conjuncts, 29 conjuncts are in the unsatisfiable core [2025-03-17 15:44:45,285 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 15:44:45,441 INFO L134 CoverageAnalysis]: Checked inductivity of 57841 backedges. 7402 proven. 5641 refuted. 0 times theorem prover too weak. 44798 trivial. 0 not checked. [2025-03-17 15:44:45,441 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-17 15:44:48,220 INFO L134 CoverageAnalysis]: Checked inductivity of 57841 backedges. 7397 proven. 5788 refuted. 0 times theorem prover too weak. 44656 trivial. 0 not checked. [2025-03-17 15:44:48,220 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1529178459] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-17 15:44:48,220 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-17 15:44:48,220 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 19, 30] total 36 [2025-03-17 15:44:48,221 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2103994267] [2025-03-17 15:44:48,221 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-17 15:44:48,222 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 36 states [2025-03-17 15:44:48,222 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-17 15:44:48,222 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 36 interpolants. [2025-03-17 15:44:48,222 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=193, Invalid=1067, Unknown=0, NotChecked=0, Total=1260 [2025-03-17 15:44:48,223 INFO L87 Difference]: Start difference. First operand 192 states and 272 transitions. Second operand has 36 states, 36 states have (on average 5.333333333333333) internal successors, (192), 36 states have internal predecessors, (192), 28 states have call successors, (31), 1 states have call predecessors, (31), 15 states have return successors, (41), 16 states have call predecessors, (41), 28 states have call successors, (41) [2025-03-17 15:44:48,830 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-17 15:44:48,831 INFO L93 Difference]: Finished difference Result 399 states and 660 transitions. [2025-03-17 15:44:48,831 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 40 states. [2025-03-17 15:44:48,831 INFO L78 Accepts]: Start accepts. Automaton has has 36 states, 36 states have (on average 5.333333333333333) internal successors, (192), 36 states have internal predecessors, (192), 28 states have call successors, (31), 1 states have call predecessors, (31), 15 states have return successors, (41), 16 states have call predecessors, (41), 28 states have call successors, (41) Word has length 1255 [2025-03-17 15:44:48,832 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-17 15:44:48,834 INFO L225 Difference]: With dead ends: 399 [2025-03-17 15:44:48,834 INFO L226 Difference]: Without dead ends: 211 [2025-03-17 15:44:48,837 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 2577 GetRequests, 2497 SyntacticMatches, 14 SemanticMatches, 66 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1042 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=1055, Invalid=3501, Unknown=0, NotChecked=0, Total=4556 [2025-03-17 15:44:48,837 INFO L435 NwaCegarLoop]: 45 mSDtfsCounter, 642 mSDsluCounter, 166 mSDsCounter, 0 mSdLazyCounter, 638 mSolverCounterSat, 304 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 642 SdHoareTripleChecker+Valid, 211 SdHoareTripleChecker+Invalid, 942 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 304 IncrementalHoareTripleChecker+Valid, 638 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2025-03-17 15:44:48,837 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [642 Valid, 211 Invalid, 942 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [304 Valid, 638 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2025-03-17 15:44:48,841 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 211 states. [2025-03-17 15:44:48,856 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 211 to 183. [2025-03-17 15:44:48,856 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 183 states, 148 states have (on average 1.0337837837837838) internal successors, (153), 144 states have internal predecessors, (153), 23 states have call successors, (23), 17 states have call predecessors, (23), 11 states have return successors, (64), 21 states have call predecessors, (64), 22 states have call successors, (64) [2025-03-17 15:44:48,857 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 183 states to 183 states and 240 transitions. [2025-03-17 15:44:48,858 INFO L78 Accepts]: Start accepts. Automaton has 183 states and 240 transitions. Word has length 1255 [2025-03-17 15:44:48,858 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-17 15:44:48,858 INFO L471 AbstractCegarLoop]: Abstraction has 183 states and 240 transitions. [2025-03-17 15:44:48,858 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 36 states, 36 states have (on average 5.333333333333333) internal successors, (192), 36 states have internal predecessors, (192), 28 states have call successors, (31), 1 states have call predecessors, (31), 15 states have return successors, (41), 16 states have call predecessors, (41), 28 states have call successors, (41) [2025-03-17 15:44:48,858 INFO L276 IsEmpty]: Start isEmpty. Operand 183 states and 240 transitions. [2025-03-17 15:44:48,865 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 810 [2025-03-17 15:44:48,865 INFO L210 NwaCegarLoop]: Found error trace [2025-03-17 15:44:48,866 INFO L218 NwaCegarLoop]: trace histogram [83, 82, 67, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 40, 26, 16, 1, 1, 1] [2025-03-17 15:44:48,873 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Ended with exit code 0 [2025-03-17 15:44:49,066 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable19,18 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-17 15:44:49,066 INFO L396 AbstractCegarLoop]: === Iteration 21 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-03-17 15:44:49,067 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 15:44:49,067 INFO L85 PathProgramCache]: Analyzing trace with hash 506070930, now seen corresponding path program 12 times [2025-03-17 15:44:49,067 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 15:44:49,067 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [305826875] [2025-03-17 15:44:49,067 INFO L95 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2025-03-17 15:44:49,067 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 15:44:49,089 INFO L108 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE partitioned 809 statements into 60 equivalence classes. [2025-03-17 15:44:49,139 INFO L111 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 45 check-sat command(s) and asserted 566 of 809 statements. [2025-03-17 15:44:49,140 INFO L114 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 45 check-sat command(s) [2025-03-17 15:44:49,140 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 15:44:49,596 INFO L134 CoverageAnalysis]: Checked inductivity of 23859 backedges. 3084 proven. 2837 refuted. 0 times theorem prover too weak. 17938 trivial. 0 not checked. [2025-03-17 15:44:49,596 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-17 15:44:49,597 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [305826875] [2025-03-17 15:44:49,597 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [305826875] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-17 15:44:49,597 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1249241644] [2025-03-17 15:44:49,597 INFO L95 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2025-03-17 15:44:49,597 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-17 15:44:49,597 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 15:44:49,599 INFO L229 MonitoredProcess]: Starting monitored process 19 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-17 15:44:49,600 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Waiting until timeout for monitored process [2025-03-17 15:44:49,765 INFO L108 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE partitioned 809 statements into 60 equivalence classes. [2025-03-17 15:44:49,879 INFO L111 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 45 check-sat command(s) and asserted 566 of 809 statements. [2025-03-17 15:44:49,880 INFO L114 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 45 check-sat command(s) [2025-03-17 15:44:49,880 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 15:44:49,883 INFO L256 TraceCheckSpWp]: Trace formula consists of 1066 conjuncts, 22 conjuncts are in the unsatisfiable core [2025-03-17 15:44:49,888 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 15:44:49,996 INFO L134 CoverageAnalysis]: Checked inductivity of 23859 backedges. 3129 proven. 2851 refuted. 0 times theorem prover too weak. 17879 trivial. 0 not checked. [2025-03-17 15:44:49,996 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-17 15:44:51,558 INFO L134 CoverageAnalysis]: Checked inductivity of 23859 backedges. 3157 proven. 2907 refuted. 0 times theorem prover too weak. 17795 trivial. 0 not checked. [2025-03-17 15:44:51,559 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1249241644] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-17 15:44:51,559 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-17 15:44:51,559 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 15, 23] total 27 [2025-03-17 15:44:51,559 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1416420469] [2025-03-17 15:44:51,559 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-17 15:44:51,560 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 27 states [2025-03-17 15:44:51,560 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-17 15:44:51,560 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 27 interpolants. [2025-03-17 15:44:51,560 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=137, Invalid=565, Unknown=0, NotChecked=0, Total=702 [2025-03-17 15:44:51,561 INFO L87 Difference]: Start difference. First operand 183 states and 240 transitions. Second operand has 27 states, 27 states have (on average 5.407407407407407) internal successors, (146), 27 states have internal predecessors, (146), 16 states have call successors, (24), 1 states have call predecessors, (24), 12 states have return successors, (31), 17 states have call predecessors, (31), 16 states have call successors, (31) [2025-03-17 15:44:51,883 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-17 15:44:51,883 INFO L93 Difference]: Finished difference Result 400 states and 538 transitions. [2025-03-17 15:44:51,884 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 30 states. [2025-03-17 15:44:51,884 INFO L78 Accepts]: Start accepts. Automaton has has 27 states, 27 states have (on average 5.407407407407407) internal successors, (146), 27 states have internal predecessors, (146), 16 states have call successors, (24), 1 states have call predecessors, (24), 12 states have return successors, (31), 17 states have call predecessors, (31), 16 states have call successors, (31) Word has length 809 [2025-03-17 15:44:51,885 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-17 15:44:51,886 INFO L225 Difference]: With dead ends: 400 [2025-03-17 15:44:51,886 INFO L226 Difference]: Without dead ends: 221 [2025-03-17 15:44:51,888 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 1659 GetRequests, 1604 SyntacticMatches, 11 SemanticMatches, 44 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 517 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=527, Invalid=1543, Unknown=0, NotChecked=0, Total=2070 [2025-03-17 15:44:51,889 INFO L435 NwaCegarLoop]: 51 mSDtfsCounter, 170 mSDsluCounter, 194 mSDsCounter, 0 mSdLazyCounter, 624 mSolverCounterSat, 76 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 170 SdHoareTripleChecker+Valid, 245 SdHoareTripleChecker+Invalid, 700 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 76 IncrementalHoareTripleChecker+Valid, 624 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-03-17 15:44:51,889 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [170 Valid, 245 Invalid, 700 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [76 Valid, 624 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-03-17 15:44:51,889 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 221 states. [2025-03-17 15:44:51,899 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 221 to 165. [2025-03-17 15:44:51,899 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 165 states, 133 states have (on average 1.0300751879699248) internal successors, (137), 131 states have internal predecessors, (137), 22 states have call successors, (22), 17 states have call predecessors, (22), 9 states have return successors, (43), 16 states have call predecessors, (43), 21 states have call successors, (43) [2025-03-17 15:44:51,900 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 165 states to 165 states and 202 transitions. [2025-03-17 15:44:51,901 INFO L78 Accepts]: Start accepts. Automaton has 165 states and 202 transitions. Word has length 809 [2025-03-17 15:44:51,901 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-17 15:44:51,901 INFO L471 AbstractCegarLoop]: Abstraction has 165 states and 202 transitions. [2025-03-17 15:44:51,901 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 27 states, 27 states have (on average 5.407407407407407) internal successors, (146), 27 states have internal predecessors, (146), 16 states have call successors, (24), 1 states have call predecessors, (24), 12 states have return successors, (31), 17 states have call predecessors, (31), 16 states have call successors, (31) [2025-03-17 15:44:51,901 INFO L276 IsEmpty]: Start isEmpty. Operand 165 states and 202 transitions. [2025-03-17 15:44:51,909 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1320 [2025-03-17 15:44:51,910 INFO L210 NwaCegarLoop]: Found error trace [2025-03-17 15:44:51,910 INFO L218 NwaCegarLoop]: trace histogram [135, 134, 109, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 66, 42, 26, 1, 1, 1] [2025-03-17 15:44:51,918 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Forceful destruction successful, exit code 0 [2025-03-17 15:44:52,110 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable20,19 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-17 15:44:52,111 INFO L396 AbstractCegarLoop]: === Iteration 22 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-03-17 15:44:52,111 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 15:44:52,112 INFO L85 PathProgramCache]: Analyzing trace with hash -1828514124, now seen corresponding path program 13 times [2025-03-17 15:44:52,112 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 15:44:52,112 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1408642296] [2025-03-17 15:44:52,112 INFO L95 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2025-03-17 15:44:52,112 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 15:44:52,131 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 1319 statements into 1 equivalence classes. [2025-03-17 15:44:52,188 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 1319 of 1319 statements. [2025-03-17 15:44:52,188 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 15:44:52,188 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 15:44:53,939 INFO L134 CoverageAnalysis]: Checked inductivity of 63908 backedges. 4507 proven. 10243 refuted. 0 times theorem prover too weak. 49158 trivial. 0 not checked. [2025-03-17 15:44:53,940 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-17 15:44:53,940 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1408642296] [2025-03-17 15:44:53,940 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1408642296] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-17 15:44:53,940 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [607833167] [2025-03-17 15:44:53,940 INFO L95 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2025-03-17 15:44:53,940 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-17 15:44:53,940 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 15:44:53,942 INFO L229 MonitoredProcess]: Starting monitored process 20 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-17 15:44:53,942 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Waiting until timeout for monitored process [2025-03-17 15:44:54,126 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 1319 statements into 1 equivalence classes. [2025-03-17 15:44:54,270 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 1319 of 1319 statements. [2025-03-17 15:44:54,270 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 15:44:54,270 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 15:44:54,275 INFO L256 TraceCheckSpWp]: Trace formula consists of 2459 conjuncts, 34 conjuncts are in the unsatisfiable core [2025-03-17 15:44:54,285 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 15:44:54,454 INFO L134 CoverageAnalysis]: Checked inductivity of 63908 backedges. 5209 proven. 10902 refuted. 0 times theorem prover too weak. 47797 trivial. 0 not checked. [2025-03-17 15:44:54,454 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-17 15:44:58,445 INFO L134 CoverageAnalysis]: Checked inductivity of 63908 backedges. 5209 proven. 11133 refuted. 0 times theorem prover too weak. 47566 trivial. 0 not checked. [2025-03-17 15:44:58,445 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [607833167] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-17 15:44:58,445 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-17 15:44:58,446 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 21, 35] total 40 [2025-03-17 15:44:58,446 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [482915700] [2025-03-17 15:44:58,446 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-17 15:44:58,447 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 40 states [2025-03-17 15:44:58,447 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-17 15:44:58,448 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 40 interpolants. [2025-03-17 15:44:58,448 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=251, Invalid=1309, Unknown=0, NotChecked=0, Total=1560 [2025-03-17 15:44:58,448 INFO L87 Difference]: Start difference. First operand 165 states and 202 transitions. Second operand has 40 states, 40 states have (on average 5.5) internal successors, (220), 40 states have internal predecessors, (220), 33 states have call successors, (37), 1 states have call predecessors, (37), 17 states have return successors, (50), 19 states have call predecessors, (50), 33 states have call successors, (50) [2025-03-17 15:44:59,083 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-17 15:44:59,083 INFO L93 Difference]: Finished difference Result 380 states and 509 transitions. [2025-03-17 15:44:59,086 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 45 states. [2025-03-17 15:44:59,086 INFO L78 Accepts]: Start accepts. Automaton has has 40 states, 40 states have (on average 5.5) internal successors, (220), 40 states have internal predecessors, (220), 33 states have call successors, (37), 1 states have call predecessors, (37), 17 states have return successors, (50), 19 states have call predecessors, (50), 33 states have call successors, (50) Word has length 1319 [2025-03-17 15:44:59,087 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-17 15:44:59,089 INFO L225 Difference]: With dead ends: 380 [2025-03-17 15:44:59,089 INFO L226 Difference]: Without dead ends: 219 [2025-03-17 15:44:59,092 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 2707 GetRequests, 2616 SyntacticMatches, 17 SemanticMatches, 74 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1492 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=1360, Invalid=4340, Unknown=0, NotChecked=0, Total=5700 [2025-03-17 15:44:59,093 INFO L435 NwaCegarLoop]: 54 mSDtfsCounter, 648 mSDsluCounter, 170 mSDsCounter, 0 mSdLazyCounter, 605 mSolverCounterSat, 243 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 648 SdHoareTripleChecker+Valid, 224 SdHoareTripleChecker+Invalid, 848 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 243 IncrementalHoareTripleChecker+Valid, 605 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2025-03-17 15:44:59,094 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [648 Valid, 224 Invalid, 848 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [243 Valid, 605 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2025-03-17 15:44:59,094 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 219 states. [2025-03-17 15:44:59,105 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 219 to 186. [2025-03-17 15:44:59,106 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 186 states, 150 states have (on average 1.0266666666666666) internal successors, (154), 148 states have internal predecessors, (154), 25 states have call successors, (25), 20 states have call predecessors, (25), 10 states have return successors, (52), 17 states have call predecessors, (52), 24 states have call successors, (52) [2025-03-17 15:44:59,107 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 186 states to 186 states and 231 transitions. [2025-03-17 15:44:59,107 INFO L78 Accepts]: Start accepts. Automaton has 186 states and 231 transitions. Word has length 1319 [2025-03-17 15:44:59,109 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-17 15:44:59,109 INFO L471 AbstractCegarLoop]: Abstraction has 186 states and 231 transitions. [2025-03-17 15:44:59,110 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 40 states, 40 states have (on average 5.5) internal successors, (220), 40 states have internal predecessors, (220), 33 states have call successors, (37), 1 states have call predecessors, (37), 17 states have return successors, (50), 19 states have call predecessors, (50), 33 states have call successors, (50) [2025-03-17 15:44:59,110 INFO L276 IsEmpty]: Start isEmpty. Operand 186 states and 231 transitions. [2025-03-17 15:44:59,115 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1065 [2025-03-17 15:44:59,115 INFO L210 NwaCegarLoop]: Found error trace [2025-03-17 15:44:59,115 INFO L218 NwaCegarLoop]: trace histogram [109, 108, 88, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 53, 34, 21, 1, 1, 1] [2025-03-17 15:44:59,125 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Ended with exit code 0 [2025-03-17 15:44:59,316 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable21,20 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-17 15:44:59,316 INFO L396 AbstractCegarLoop]: === Iteration 23 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-03-17 15:44:59,316 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 15:44:59,317 INFO L85 PathProgramCache]: Analyzing trace with hash -1124053899, now seen corresponding path program 14 times [2025-03-17 15:44:59,317 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 15:44:59,317 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [886661476] [2025-03-17 15:44:59,317 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-17 15:44:59,317 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 15:44:59,333 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 1064 statements into 2 equivalence classes. [2025-03-17 15:44:59,387 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 1064 of 1064 statements. [2025-03-17 15:44:59,388 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-17 15:44:59,388 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 15:45:11,486 INFO L134 CoverageAnalysis]: Checked inductivity of 41466 backedges. 6794 proven. 10267 refuted. 0 times theorem prover too weak. 24405 trivial. 0 not checked. [2025-03-17 15:45:11,487 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-17 15:45:11,487 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [886661476] [2025-03-17 15:45:11,487 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [886661476] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-17 15:45:11,487 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2009449555] [2025-03-17 15:45:11,487 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-17 15:45:11,487 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-17 15:45:11,487 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 15:45:11,488 INFO L229 MonitoredProcess]: Starting monitored process 21 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-17 15:45:11,489 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Waiting until timeout for monitored process [2025-03-17 15:45:11,705 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 1064 statements into 2 equivalence classes. [2025-03-17 15:45:11,845 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 1064 of 1064 statements. [2025-03-17 15:45:11,846 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-17 15:45:11,846 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 15:45:11,854 INFO L256 TraceCheckSpWp]: Trace formula consists of 1988 conjuncts, 217 conjuncts are in the unsatisfiable core [2025-03-17 15:45:11,863 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 15:45:12,554 INFO L134 CoverageAnalysis]: Checked inductivity of 41466 backedges. 6686 proven. 7855 refuted. 0 times theorem prover too weak. 26925 trivial. 0 not checked. [2025-03-17 15:45:12,555 INFO L312 TraceCheckSpWp]: Computing backward predicates...