./Ultimate.py --spec ../sv-benchmarks/c/properties/no-overflow.prp --file ../sv-benchmarks/c/recursive/Fibonacci04.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for overflows Using default analysis Version 48c9605d Calling Ultimate with: /root/.sdkman/candidates/java/21.0.5-tem/bin/java -Dosgi.configuration.area=/storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.6.800.v20240513-1750.jar -data @noDefault -ultimatedata /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/recursive/Fibonacci04.c -s /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/config/svcomp-Overflow-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate-jdk21/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 8d1a4b1841ad6fa39491d7c82c38d46725a7eceb7c19c007d9e026b8eedadeb5 --- Real Ultimate output --- This is Ultimate 0.3.0-?-48c9605-m [2025-02-08 09:59:23,351 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-02-08 09:59:23,410 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/config/svcomp-Overflow-32bit-Automizer_Default.epf [2025-02-08 09:59:23,413 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-02-08 09:59:23,413 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-02-08 09:59:23,425 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-02-08 09:59:23,425 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-02-08 09:59:23,425 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-02-08 09:59:23,425 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-02-08 09:59:23,425 INFO L153 SettingsManager]: * Use memory slicer=true [2025-02-08 09:59:23,425 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2025-02-08 09:59:23,425 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2025-02-08 09:59:23,426 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-02-08 09:59:23,426 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-02-08 09:59:23,426 INFO L153 SettingsManager]: * Use SBE=true [2025-02-08 09:59:23,426 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-02-08 09:59:23,426 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2025-02-08 09:59:23,426 INFO L153 SettingsManager]: * sizeof long=4 [2025-02-08 09:59:23,426 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2025-02-08 09:59:23,426 INFO L153 SettingsManager]: * sizeof POINTER=4 [2025-02-08 09:59:23,426 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-02-08 09:59:23,426 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2025-02-08 09:59:23,427 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2025-02-08 09:59:23,427 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2025-02-08 09:59:23,427 INFO L153 SettingsManager]: * Check absence of signed integer overflows=ASSERTandASSUME [2025-02-08 09:59:23,427 INFO L153 SettingsManager]: * Check unreachability of reach_error function=false [2025-02-08 09:59:23,427 INFO L153 SettingsManager]: * sizeof long double=12 [2025-02-08 09:59:23,427 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-02-08 09:59:23,427 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-02-08 09:59:23,427 INFO L153 SettingsManager]: * Use constant arrays=true [2025-02-08 09:59:23,427 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-02-08 09:59:23,427 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-02-08 09:59:23,427 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-02-08 09:59:23,427 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-02-08 09:59:23,427 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-02-08 09:59:23,427 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-02-08 09:59:23,427 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2025-02-08 09:59:23,427 INFO L153 SettingsManager]: * Compute procedure contracts=false [2025-02-08 09:59:23,427 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2025-02-08 09:59:23,427 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2025-02-08 09:59:23,427 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2025-02-08 09:59:23,428 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2025-02-08 09:59:23,428 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2025-02-08 09:59:23,428 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2025-02-08 09:59:23,428 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2025-02-08 09:59:23,428 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-jdk21/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 -> 8d1a4b1841ad6fa39491d7c82c38d46725a7eceb7c19c007d9e026b8eedadeb5 [2025-02-08 09:59:23,579 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-02-08 09:59:23,584 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-02-08 09:59:23,585 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-02-08 09:59:23,585 INFO L270 PluginConnector]: Initializing CDTParser... [2025-02-08 09:59:23,586 INFO L274 PluginConnector]: CDTParser initialized [2025-02-08 09:59:23,586 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/recursive/Fibonacci04.c [2025-02-08 09:59:24,653 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/d857f8490/d3cb4a0f5d644c8e982289e00a1fdfdf/FLAGe1782a955 [2025-02-08 09:59:24,837 INFO L384 CDTParser]: Found 1 translation units. [2025-02-08 09:59:24,838 INFO L180 CDTParser]: Scanning /storage/repos/ultimate-jdk21/releaseScripts/default/sv-benchmarks/c/recursive/Fibonacci04.c [2025-02-08 09:59:24,852 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/d857f8490/d3cb4a0f5d644c8e982289e00a1fdfdf/FLAGe1782a955 [2025-02-08 09:59:25,214 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/d857f8490/d3cb4a0f5d644c8e982289e00a1fdfdf [2025-02-08 09:59:25,216 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-02-08 09:59:25,217 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-02-08 09:59:25,218 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-02-08 09:59:25,218 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-02-08 09:59:25,221 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-02-08 09:59:25,221 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 08.02 09:59:25" (1/1) ... [2025-02-08 09:59:25,222 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@2334be49 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.02 09:59:25, skipping insertion in model container [2025-02-08 09:59:25,222 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 08.02 09:59:25" (1/1) ... [2025-02-08 09:59:25,230 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-02-08 09:59:25,326 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-02-08 09:59:25,334 INFO L200 MainTranslator]: Completed pre-run [2025-02-08 09:59:25,342 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-02-08 09:59:25,353 INFO L204 MainTranslator]: Completed translation [2025-02-08 09:59:25,354 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.02 09:59:25 WrapperNode [2025-02-08 09:59:25,354 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-02-08 09:59:25,355 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-02-08 09:59:25,355 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-02-08 09:59:25,355 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-02-08 09:59:25,359 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.02 09:59:25" (1/1) ... [2025-02-08 09:59:25,363 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.02 09:59:25" (1/1) ... [2025-02-08 09:59:25,373 INFO L138 Inliner]: procedures = 13, calls = 11, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 27 [2025-02-08 09:59:25,373 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-02-08 09:59:25,374 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-02-08 09:59:25,374 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-02-08 09:59:25,374 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-02-08 09:59:25,379 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.02 09:59:25" (1/1) ... [2025-02-08 09:59:25,379 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.02 09:59:25" (1/1) ... [2025-02-08 09:59:25,383 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.02 09:59:25" (1/1) ... [2025-02-08 09:59:25,390 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-02-08 09:59:25,393 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.02 09:59:25" (1/1) ... [2025-02-08 09:59:25,394 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.02 09:59:25" (1/1) ... [2025-02-08 09:59:25,395 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.02 09:59:25" (1/1) ... [2025-02-08 09:59:25,396 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.02 09:59:25" (1/1) ... [2025-02-08 09:59:25,397 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.02 09:59:25" (1/1) ... [2025-02-08 09:59:25,397 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.02 09:59:25" (1/1) ... [2025-02-08 09:59:25,398 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-02-08 09:59:25,401 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2025-02-08 09:59:25,401 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2025-02-08 09:59:25,401 INFO L274 PluginConnector]: IcfgBuilder initialized [2025-02-08 09:59:25,402 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.02 09:59:25" (1/1) ... [2025-02-08 09:59:25,405 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-02-08 09:59:25,414 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-08 09:59:25,427 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2025-02-08 09:59:25,437 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2025-02-08 09:59:25,450 INFO L130 BoogieDeclarations]: Found specification of procedure fibonacci [2025-02-08 09:59:25,450 INFO L138 BoogieDeclarations]: Found implementation of procedure fibonacci [2025-02-08 09:59:25,450 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2025-02-08 09:59:25,451 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-02-08 09:59:25,451 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-02-08 09:59:25,451 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2025-02-08 09:59:25,488 INFO L257 CfgBuilder]: Building ICFG [2025-02-08 09:59:25,489 INFO L287 CfgBuilder]: Building CFG for each procedure with an implementation [2025-02-08 09:59:25,566 INFO L1324 $ProcedureCfgBuilder]: dead code at ProgramPoint L24: havoc #t~ret4;havoc #t~ret5; [2025-02-08 09:59:25,585 INFO L? ?]: Removed 15 outVars from TransFormulas that were not future-live. [2025-02-08 09:59:25,585 INFO L308 CfgBuilder]: Performing block encoding [2025-02-08 09:59:25,591 INFO L332 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-02-08 09:59:25,591 INFO L337 CfgBuilder]: Removed 0 assume(true) statements. [2025-02-08 09:59:25,591 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 08.02 09:59:25 BoogieIcfgContainer [2025-02-08 09:59:25,592 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2025-02-08 09:59:25,593 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2025-02-08 09:59:25,593 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2025-02-08 09:59:25,596 INFO L274 PluginConnector]: TraceAbstraction initialized [2025-02-08 09:59:25,596 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 08.02 09:59:25" (1/3) ... [2025-02-08 09:59:25,597 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@46bb474 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 08.02 09:59:25, skipping insertion in model container [2025-02-08 09:59:25,597 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.02 09:59:25" (2/3) ... [2025-02-08 09:59:25,597 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@46bb474 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 08.02 09:59:25, skipping insertion in model container [2025-02-08 09:59:25,597 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 08.02 09:59:25" (3/3) ... [2025-02-08 09:59:25,598 INFO L128 eAbstractionObserver]: Analyzing ICFG Fibonacci04.c [2025-02-08 09:59:25,607 INFO L216 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2025-02-08 09:59:25,608 INFO L151 ceAbstractionStarter]: Applying trace abstraction to ICFG Fibonacci04.c that has 2 procedures, 29 locations, 1 initial locations, 0 loop locations, and 6 error locations. [2025-02-08 09:59:25,637 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2025-02-08 09:59:25,644 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;@447a7cde, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2025-02-08 09:59:25,645 INFO L334 AbstractCegarLoop]: Starting to check reachability of 6 error locations. [2025-02-08 09:59:25,647 INFO L276 IsEmpty]: Start isEmpty. Operand has 29 states, 17 states have (on average 1.588235294117647) internal successors, (27), 24 states have internal predecessors, (27), 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-02-08 09:59:25,650 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 8 [2025-02-08 09:59:25,650 INFO L210 NwaCegarLoop]: Found error trace [2025-02-08 09:59:25,651 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2025-02-08 09:59:25,651 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting fibonacciErr5ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-02-08 09:59:25,654 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-08 09:59:25,654 INFO L85 PathProgramCache]: Analyzing trace with hash 1918456325, now seen corresponding path program 1 times [2025-02-08 09:59:25,659 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-08 09:59:25,659 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [632955866] [2025-02-08 09:59:25,659 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-08 09:59:25,659 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-08 09:59:25,697 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 7 statements into 1 equivalence classes. [2025-02-08 09:59:25,707 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 7 of 7 statements. [2025-02-08 09:59:25,707 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 09:59:25,707 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 09:59:25,747 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-02-08 09:59:25,748 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-08 09:59:25,748 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [632955866] [2025-02-08 09:59:25,748 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [632955866] provided 1 perfect and 0 imperfect interpolant sequences [2025-02-08 09:59:25,748 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-02-08 09:59:25,749 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2025-02-08 09:59:25,749 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1127010460] [2025-02-08 09:59:25,750 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-02-08 09:59:25,752 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2025-02-08 09:59:25,752 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-08 09:59:25,762 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2025-02-08 09:59:25,763 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2025-02-08 09:59:25,764 INFO L87 Difference]: Start difference. First operand has 29 states, 17 states have (on average 1.588235294117647) internal successors, (27), 24 states have internal predecessors, (27), 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 3.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-02-08 09:59:25,789 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-08 09:59:25,789 INFO L93 Difference]: Finished difference Result 31 states and 37 transitions. [2025-02-08 09:59:25,790 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2025-02-08 09:59:25,791 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 2 states have (on average 3.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-02-08 09:59:25,791 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-08 09:59:25,795 INFO L225 Difference]: With dead ends: 31 [2025-02-08 09:59:25,795 INFO L226 Difference]: Without dead ends: 24 [2025-02-08 09:59:25,796 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-02-08 09:59:25,798 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-02-08 09:59:25,798 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-02-08 09:59:25,806 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 24 states. [2025-02-08 09:59:25,816 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 24 to 22. [2025-02-08 09:59:25,817 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 22 states, 14 states have (on average 1.4285714285714286) internal successors, (20), 18 states have internal predecessors, (20), 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-02-08 09:59:25,819 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 22 states to 22 states and 25 transitions. [2025-02-08 09:59:25,820 INFO L78 Accepts]: Start accepts. Automaton has 22 states and 25 transitions. Word has length 7 [2025-02-08 09:59:25,820 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-08 09:59:25,820 INFO L471 AbstractCegarLoop]: Abstraction has 22 states and 25 transitions. [2025-02-08 09:59:25,820 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 2 states have (on average 3.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-02-08 09:59:25,820 INFO L276 IsEmpty]: Start isEmpty. Operand 22 states and 25 transitions. [2025-02-08 09:59:25,821 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 9 [2025-02-08 09:59:25,821 INFO L210 NwaCegarLoop]: Found error trace [2025-02-08 09:59:25,821 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2025-02-08 09:59:25,821 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2025-02-08 09:59:25,821 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting fibonacciErr4ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-02-08 09:59:25,822 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-08 09:59:25,822 INFO L85 PathProgramCache]: Analyzing trace with hash -657396084, now seen corresponding path program 1 times [2025-02-08 09:59:25,822 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-08 09:59:25,822 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1114930899] [2025-02-08 09:59:25,822 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-08 09:59:25,822 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-08 09:59:25,826 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 8 statements into 1 equivalence classes. [2025-02-08 09:59:25,830 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 8 of 8 statements. [2025-02-08 09:59:25,830 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 09:59:25,830 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 09:59:25,902 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-02-08 09:59:25,904 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-08 09:59:25,904 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1114930899] [2025-02-08 09:59:25,904 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1114930899] provided 1 perfect and 0 imperfect interpolant sequences [2025-02-08 09:59:25,905 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-02-08 09:59:25,905 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2025-02-08 09:59:25,905 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1490945561] [2025-02-08 09:59:25,905 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-02-08 09:59:25,906 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-02-08 09:59:25,906 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-08 09:59:25,906 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-02-08 09:59:25,906 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-02-08 09:59:25,906 INFO L87 Difference]: Start difference. First operand 22 states and 25 transitions. Second operand has 5 states, 3 states have (on average 2.3333333333333335) internal successors, (7), 4 states have internal predecessors, (7), 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-02-08 09:59:25,958 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-08 09:59:25,958 INFO L93 Difference]: Finished difference Result 24 states and 28 transitions. [2025-02-08 09:59:25,958 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-02-08 09:59:25,959 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 3 states have (on average 2.3333333333333335) internal successors, (7), 4 states have internal predecessors, (7), 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 8 [2025-02-08 09:59:25,959 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-08 09:59:25,959 INFO L225 Difference]: With dead ends: 24 [2025-02-08 09:59:25,959 INFO L226 Difference]: Without dead ends: 22 [2025-02-08 09:59:25,959 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 1 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-02-08 09:59:25,960 INFO L435 NwaCegarLoop]: 13 mSDtfsCounter, 26 mSDsluCounter, 15 mSDsCounter, 0 mSdLazyCounter, 33 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 26 SdHoareTripleChecker+Valid, 28 SdHoareTripleChecker+Invalid, 40 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 33 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-02-08 09:59:25,960 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [26 Valid, 28 Invalid, 40 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 33 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-02-08 09:59:25,961 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 22 states. [2025-02-08 09:59:25,963 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 22 to 20. [2025-02-08 09:59:25,963 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 20 states, 14 states have (on average 1.2857142857142858) internal successors, (18), 16 states have internal predecessors, (18), 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-02-08 09:59:25,964 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 20 states to 20 states and 23 transitions. [2025-02-08 09:59:25,964 INFO L78 Accepts]: Start accepts. Automaton has 20 states and 23 transitions. Word has length 8 [2025-02-08 09:59:25,964 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-08 09:59:25,964 INFO L471 AbstractCegarLoop]: Abstraction has 20 states and 23 transitions. [2025-02-08 09:59:25,964 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 3 states have (on average 2.3333333333333335) internal successors, (7), 4 states have internal predecessors, (7), 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-02-08 09:59:25,964 INFO L276 IsEmpty]: Start isEmpty. Operand 20 states and 23 transitions. [2025-02-08 09:59:25,965 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2025-02-08 09:59:25,965 INFO L210 NwaCegarLoop]: Found error trace [2025-02-08 09:59:25,965 INFO L218 NwaCegarLoop]: trace histogram [4, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-02-08 09:59:25,965 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2025-02-08 09:59:25,965 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-02-08 09:59:25,966 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-08 09:59:25,966 INFO L85 PathProgramCache]: Analyzing trace with hash 1219789848, now seen corresponding path program 1 times [2025-02-08 09:59:25,966 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-08 09:59:25,966 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1480838416] [2025-02-08 09:59:25,966 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-08 09:59:25,966 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-08 09:59:25,972 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 29 statements into 1 equivalence classes. [2025-02-08 09:59:25,980 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 29 of 29 statements. [2025-02-08 09:59:25,980 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 09:59:25,980 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 09:59:26,076 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2025-02-08 09:59:26,076 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-08 09:59:26,076 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1480838416] [2025-02-08 09:59:26,076 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1480838416] provided 1 perfect and 0 imperfect interpolant sequences [2025-02-08 09:59:26,076 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-02-08 09:59:26,076 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2025-02-08 09:59:26,076 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1174808434] [2025-02-08 09:59:26,077 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-02-08 09:59:26,077 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-02-08 09:59:26,077 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-08 09:59:26,078 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-02-08 09:59:26,078 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2025-02-08 09:59:26,078 INFO L87 Difference]: Start difference. First operand 20 states and 23 transitions. Second operand has 5 states, 4 states have (on average 3.5) internal successors, (14), 5 states have internal predecessors, (14), 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-02-08 09:59:26,104 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-08 09:59:26,107 INFO L93 Difference]: Finished difference Result 34 states and 42 transitions. [2025-02-08 09:59:26,107 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-02-08 09:59:26,107 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 3.5) internal successors, (14), 5 states have internal predecessors, (14), 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 29 [2025-02-08 09:59:26,108 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-08 09:59:26,108 INFO L225 Difference]: With dead ends: 34 [2025-02-08 09:59:26,108 INFO L226 Difference]: Without dead ends: 32 [2025-02-08 09:59:26,108 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-02-08 09:59:26,109 INFO L435 NwaCegarLoop]: 17 mSDtfsCounter, 4 mSDsluCounter, 35 mSDsCounter, 0 mSdLazyCounter, 23 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 52 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-02-08 09:59:26,109 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [5 Valid, 52 Invalid, 25 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 23 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-02-08 09:59:26,109 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 32 states. [2025-02-08 09:59:26,117 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 32 to 29. [2025-02-08 09:59:26,118 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 29 states, 21 states have (on average 1.1904761904761905) internal successors, (25), 23 states have internal predecessors, (25), 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-02-08 09:59:26,119 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 29 states to 29 states and 35 transitions. [2025-02-08 09:59:26,119 INFO L78 Accepts]: Start accepts. Automaton has 29 states and 35 transitions. Word has length 29 [2025-02-08 09:59:26,119 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-08 09:59:26,119 INFO L471 AbstractCegarLoop]: Abstraction has 29 states and 35 transitions. [2025-02-08 09:59:26,119 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 3.5) internal successors, (14), 5 states have internal predecessors, (14), 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-02-08 09:59:26,119 INFO L276 IsEmpty]: Start isEmpty. Operand 29 states and 35 transitions. [2025-02-08 09:59:26,120 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2025-02-08 09:59:26,120 INFO L210 NwaCegarLoop]: Found error trace [2025-02-08 09:59:26,120 INFO L218 NwaCegarLoop]: trace histogram [4, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-02-08 09:59:26,120 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2025-02-08 09:59:26,120 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-02-08 09:59:26,121 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-08 09:59:26,121 INFO L85 PathProgramCache]: Analyzing trace with hash -288420465, now seen corresponding path program 1 times [2025-02-08 09:59:26,121 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-08 09:59:26,121 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [854738309] [2025-02-08 09:59:26,121 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-08 09:59:26,121 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-08 09:59:26,126 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 30 statements into 1 equivalence classes. [2025-02-08 09:59:26,131 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 30 of 30 statements. [2025-02-08 09:59:26,131 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 09:59:26,131 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 09:59:26,236 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2025-02-08 09:59:26,236 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-08 09:59:26,236 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [854738309] [2025-02-08 09:59:26,236 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [854738309] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-08 09:59:26,236 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1736121471] [2025-02-08 09:59:26,236 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-08 09:59:26,236 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-08 09:59:26,236 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-08 09:59:26,239 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-02-08 09:59:26,240 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2025-02-08 09:59:26,265 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 30 statements into 1 equivalence classes. [2025-02-08 09:59:26,275 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 30 of 30 statements. [2025-02-08 09:59:26,275 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 09:59:26,276 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 09:59:26,276 INFO L256 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 6 conjuncts are in the unsatisfiable core [2025-02-08 09:59:26,279 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-08 09:59:26,359 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 6 proven. 3 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2025-02-08 09:59:26,362 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-08 09:59:26,490 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 6 proven. 3 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2025-02-08 09:59:26,490 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1736121471] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-08 09:59:26,490 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-08 09:59:26,491 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 7, 7] total 15 [2025-02-08 09:59:26,491 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [507723631] [2025-02-08 09:59:26,491 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-08 09:59:26,491 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2025-02-08 09:59:26,491 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-08 09:59:26,492 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2025-02-08 09:59:26,492 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=35, Invalid=175, Unknown=0, NotChecked=0, Total=210 [2025-02-08 09:59:26,492 INFO L87 Difference]: Start difference. First operand 29 states and 35 transitions. Second operand has 15 states, 15 states have (on average 2.4) internal successors, (36), 15 states have internal predecessors, (36), 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-02-08 09:59:26,688 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-08 09:59:26,688 INFO L93 Difference]: Finished difference Result 90 states and 128 transitions. [2025-02-08 09:59:26,688 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2025-02-08 09:59:26,688 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 15 states have (on average 2.4) internal successors, (36), 15 states have internal predecessors, (36), 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 30 [2025-02-08 09:59:26,689 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-08 09:59:26,689 INFO L225 Difference]: With dead ends: 90 [2025-02-08 09:59:26,689 INFO L226 Difference]: Without dead ends: 64 [2025-02-08 09:59:26,690 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 72 GetRequests, 50 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-02-08 09:59:26,691 INFO L435 NwaCegarLoop]: 12 mSDtfsCounter, 106 mSDsluCounter, 72 mSDsCounter, 0 mSdLazyCounter, 168 mSolverCounterSat, 47 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 106 SdHoareTripleChecker+Valid, 84 SdHoareTripleChecker+Invalid, 215 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 47 IncrementalHoareTripleChecker+Valid, 168 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-02-08 09:59:26,691 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [106 Valid, 84 Invalid, 215 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [47 Valid, 168 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-02-08 09:59:26,691 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 64 states. [2025-02-08 09:59:26,698 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 64 to 52. [2025-02-08 09:59:26,698 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 52 states, 38 states have (on average 1.105263157894737) internal successors, (42), 41 states have internal predecessors, (42), 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-02-08 09:59:26,699 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 52 states to 52 states and 67 transitions. [2025-02-08 09:59:26,699 INFO L78 Accepts]: Start accepts. Automaton has 52 states and 67 transitions. Word has length 30 [2025-02-08 09:59:26,699 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-08 09:59:26,699 INFO L471 AbstractCegarLoop]: Abstraction has 52 states and 67 transitions. [2025-02-08 09:59:26,700 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 2.4) internal successors, (36), 15 states have internal predecessors, (36), 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-02-08 09:59:26,700 INFO L276 IsEmpty]: Start isEmpty. Operand 52 states and 67 transitions. [2025-02-08 09:59:26,700 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2025-02-08 09:59:26,700 INFO L210 NwaCegarLoop]: Found error trace [2025-02-08 09:59:26,700 INFO L218 NwaCegarLoop]: trace histogram [4, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-02-08 09:59:26,707 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2025-02-08 09:59:26,901 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,2 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-08 09:59:26,901 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-02-08 09:59:26,901 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-08 09:59:26,901 INFO L85 PathProgramCache]: Analyzing trace with hash 2098828437, now seen corresponding path program 2 times [2025-02-08 09:59:26,902 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-08 09:59:26,902 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1216005362] [2025-02-08 09:59:26,902 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-02-08 09:59:26,902 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-08 09:59:26,909 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 30 statements into 2 equivalence classes. [2025-02-08 09:59:26,916 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 30 of 30 statements. [2025-02-08 09:59:26,919 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-02-08 09:59:26,919 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 09:59:27,006 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2025-02-08 09:59:27,006 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-08 09:59:27,006 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1216005362] [2025-02-08 09:59:27,006 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1216005362] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-08 09:59:27,006 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [526078834] [2025-02-08 09:59:27,006 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-02-08 09:59:27,006 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-08 09:59:27,006 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-08 09:59:27,008 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-02-08 09:59:27,009 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2025-02-08 09:59:27,027 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 30 statements into 2 equivalence classes. [2025-02-08 09:59:27,035 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 30 of 30 statements. [2025-02-08 09:59:27,035 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-02-08 09:59:27,035 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 09:59:27,035 INFO L256 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 4 conjuncts are in the unsatisfiable core [2025-02-08 09:59:27,036 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-08 09:59:27,064 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2025-02-08 09:59:27,064 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-02-08 09:59:27,064 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [526078834] provided 1 perfect and 0 imperfect interpolant sequences [2025-02-08 09:59:27,064 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-02-08 09:59:27,064 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [5] total 7 [2025-02-08 09:59:27,064 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [501214201] [2025-02-08 09:59:27,064 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-02-08 09:59:27,064 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-02-08 09:59:27,064 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-08 09:59:27,065 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-02-08 09:59:27,065 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=38, Unknown=0, NotChecked=0, Total=56 [2025-02-08 09:59:27,065 INFO L87 Difference]: Start difference. First operand 52 states and 67 transitions. Second operand has 5 states, 4 states have (on average 4.0) internal successors, (16), 5 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-02-08 09:59:27,083 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-08 09:59:27,083 INFO L93 Difference]: Finished difference Result 59 states and 75 transitions. [2025-02-08 09:59:27,084 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-02-08 09:59:27,084 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 4.0) internal successors, (16), 5 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 30 [2025-02-08 09:59:27,084 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-08 09:59:27,084 INFO L225 Difference]: With dead ends: 59 [2025-02-08 09:59:27,084 INFO L226 Difference]: Without dead ends: 58 [2025-02-08 09:59:27,085 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 34 GetRequests, 27 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-02-08 09:59:27,085 INFO L435 NwaCegarLoop]: 17 mSDtfsCounter, 4 mSDsluCounter, 31 mSDsCounter, 0 mSdLazyCounter, 20 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 48 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-02-08 09:59:27,085 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [5 Valid, 48 Invalid, 22 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 20 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-02-08 09:59:27,086 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 58 states. [2025-02-08 09:59:27,094 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 58 to 54. [2025-02-08 09:59:27,094 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 54 states, 40 states have (on average 1.1) internal successors, (44), 42 states have internal predecessors, (44), 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-02-08 09:59:27,095 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 69 transitions. [2025-02-08 09:59:27,095 INFO L78 Accepts]: Start accepts. Automaton has 54 states and 69 transitions. Word has length 30 [2025-02-08 09:59:27,095 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-08 09:59:27,095 INFO L471 AbstractCegarLoop]: Abstraction has 54 states and 69 transitions. [2025-02-08 09:59:27,095 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 4.0) internal successors, (16), 5 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-02-08 09:59:27,095 INFO L276 IsEmpty]: Start isEmpty. Operand 54 states and 69 transitions. [2025-02-08 09:59:27,095 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2025-02-08 09:59:27,095 INFO L210 NwaCegarLoop]: Found error trace [2025-02-08 09:59:27,096 INFO L218 NwaCegarLoop]: trace histogram [4, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-02-08 09:59:27,101 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2025-02-08 09:59:27,296 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,3 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-08 09:59:27,296 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-02-08 09:59:27,297 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-08 09:59:27,297 INFO L85 PathProgramCache]: Analyzing trace with hash 639172080, now seen corresponding path program 1 times [2025-02-08 09:59:27,297 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-08 09:59:27,297 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [586034590] [2025-02-08 09:59:27,297 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-08 09:59:27,297 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-08 09:59:27,300 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 31 statements into 1 equivalence classes. [2025-02-08 09:59:27,302 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 31 of 31 statements. [2025-02-08 09:59:27,302 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 09:59:27,302 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 09:59:27,352 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2025-02-08 09:59:27,352 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-08 09:59:27,352 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [586034590] [2025-02-08 09:59:27,352 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [586034590] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-08 09:59:27,352 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [391735809] [2025-02-08 09:59:27,352 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-08 09:59:27,352 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-08 09:59:27,352 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-08 09:59:27,354 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-02-08 09:59:27,356 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2025-02-08 09:59:27,373 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 31 statements into 1 equivalence classes. [2025-02-08 09:59:27,382 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 31 of 31 statements. [2025-02-08 09:59:27,382 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 09:59:27,382 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 09:59:27,382 INFO L256 TraceCheckSpWp]: Trace formula consists of 78 conjuncts, 5 conjuncts are in the unsatisfiable core [2025-02-08 09:59:27,383 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-08 09:59:27,423 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2025-02-08 09:59:27,423 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-02-08 09:59:27,423 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [391735809] provided 1 perfect and 0 imperfect interpolant sequences [2025-02-08 09:59:27,423 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-02-08 09:59:27,423 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [5] total 9 [2025-02-08 09:59:27,423 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [549351415] [2025-02-08 09:59:27,423 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-02-08 09:59:27,423 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2025-02-08 09:59:27,423 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-08 09:59:27,424 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2025-02-08 09:59:27,424 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=64, Unknown=0, NotChecked=0, Total=90 [2025-02-08 09:59:27,424 INFO L87 Difference]: Start difference. First operand 54 states and 69 transitions. Second operand has 6 states, 5 states have (on average 3.4) internal successors, (17), 6 states have internal predecessors, (17), 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-02-08 09:59:27,449 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-08 09:59:27,449 INFO L93 Difference]: Finished difference Result 81 states and 116 transitions. [2025-02-08 09:59:27,449 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2025-02-08 09:59:27,449 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 3.4) internal successors, (17), 6 states have internal predecessors, (17), 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 31 [2025-02-08 09:59:27,449 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-08 09:59:27,450 INFO L225 Difference]: With dead ends: 81 [2025-02-08 09:59:27,450 INFO L226 Difference]: Without dead ends: 80 [2025-02-08 09:59:27,450 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 35 GetRequests, 27 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-02-08 09:59:27,451 INFO L435 NwaCegarLoop]: 17 mSDtfsCounter, 2 mSDsluCounter, 50 mSDsCounter, 0 mSdLazyCounter, 29 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 67 SdHoareTripleChecker+Invalid, 30 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 29 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-02-08 09:59:27,451 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 67 Invalid, 30 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 29 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-02-08 09:59:27,451 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 80 states. [2025-02-08 09:59:27,459 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 80 to 63. [2025-02-08 09:59:27,459 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 63 states, 47 states have (on average 1.0851063829787233) internal successors, (51), 49 states have internal predecessors, (51), 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-02-08 09:59:27,460 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 63 states to 63 states and 86 transitions. [2025-02-08 09:59:27,460 INFO L78 Accepts]: Start accepts. Automaton has 63 states and 86 transitions. Word has length 31 [2025-02-08 09:59:27,460 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-08 09:59:27,460 INFO L471 AbstractCegarLoop]: Abstraction has 63 states and 86 transitions. [2025-02-08 09:59:27,460 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 3.4) internal successors, (17), 6 states have internal predecessors, (17), 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-02-08 09:59:27,460 INFO L276 IsEmpty]: Start isEmpty. Operand 63 states and 86 transitions. [2025-02-08 09:59:27,461 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 52 [2025-02-08 09:59:27,461 INFO L210 NwaCegarLoop]: Found error trace [2025-02-08 09:59:27,461 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, 1] [2025-02-08 09:59:27,467 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2025-02-08 09:59:27,661 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,4 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-08 09:59:27,662 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-02-08 09:59:27,662 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-08 09:59:27,662 INFO L85 PathProgramCache]: Analyzing trace with hash 233929248, now seen corresponding path program 1 times [2025-02-08 09:59:27,662 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-08 09:59:27,662 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [188271250] [2025-02-08 09:59:27,663 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-08 09:59:27,663 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-08 09:59:27,667 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 51 statements into 1 equivalence classes. [2025-02-08 09:59:27,671 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 51 of 51 statements. [2025-02-08 09:59:27,671 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 09:59:27,671 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 09:59:27,797 INFO L134 CoverageAnalysis]: Checked inductivity of 68 backedges. 2 proven. 15 refuted. 0 times theorem prover too weak. 51 trivial. 0 not checked. [2025-02-08 09:59:27,798 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-08 09:59:27,798 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [188271250] [2025-02-08 09:59:27,798 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [188271250] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-08 09:59:27,798 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [555787954] [2025-02-08 09:59:27,798 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-08 09:59:27,798 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-08 09:59:27,798 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-08 09:59:27,800 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-02-08 09:59:27,801 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2025-02-08 09:59:27,825 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 51 statements into 1 equivalence classes. [2025-02-08 09:59:27,837 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 51 of 51 statements. [2025-02-08 09:59:27,837 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 09:59:27,837 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 09:59:27,837 INFO L256 TraceCheckSpWp]: Trace formula consists of 115 conjuncts, 9 conjuncts are in the unsatisfiable core [2025-02-08 09:59:27,838 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-08 09:59:27,904 INFO L134 CoverageAnalysis]: Checked inductivity of 68 backedges. 2 proven. 7 refuted. 0 times theorem prover too weak. 59 trivial. 0 not checked. [2025-02-08 09:59:27,905 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-08 09:59:28,056 INFO L134 CoverageAnalysis]: Checked inductivity of 68 backedges. 6 proven. 7 refuted. 0 times theorem prover too weak. 55 trivial. 0 not checked. [2025-02-08 09:59:28,057 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [555787954] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-08 09:59:28,057 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-08 09:59:28,057 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 6, 7] total 15 [2025-02-08 09:59:28,057 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2125349804] [2025-02-08 09:59:28,059 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-08 09:59:28,059 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2025-02-08 09:59:28,059 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-08 09:59:28,060 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2025-02-08 09:59:28,060 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=62, Invalid=178, Unknown=0, NotChecked=0, Total=240 [2025-02-08 09:59:28,060 INFO L87 Difference]: Start difference. First operand 63 states and 86 transitions. Second operand has 16 states, 15 states have (on average 2.933333333333333) internal successors, (44), 16 states have internal predecessors, (44), 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-02-08 09:59:28,220 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-08 09:59:28,220 INFO L93 Difference]: Finished difference Result 140 states and 216 transitions. [2025-02-08 09:59:28,220 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2025-02-08 09:59:28,220 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 15 states have (on average 2.933333333333333) internal successors, (44), 16 states have internal predecessors, (44), 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 51 [2025-02-08 09:59:28,221 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-08 09:59:28,226 INFO L225 Difference]: With dead ends: 140 [2025-02-08 09:59:28,226 INFO L226 Difference]: Without dead ends: 138 [2025-02-08 09:59:28,226 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 115 GetRequests, 93 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-02-08 09:59:28,227 INFO L435 NwaCegarLoop]: 24 mSDtfsCounter, 14 mSDsluCounter, 160 mSDsCounter, 0 mSdLazyCounter, 164 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 20 SdHoareTripleChecker+Valid, 184 SdHoareTripleChecker+Invalid, 169 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 164 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-02-08 09:59:28,227 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [20 Valid, 184 Invalid, 169 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 164 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-02-08 09:59:28,227 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 138 states. [2025-02-08 09:59:28,248 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 138 to 97. [2025-02-08 09:59:28,252 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 97 states, 75 states have (on average 1.08) internal successors, (81), 74 states have internal predecessors, (81), 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-02-08 09:59:28,253 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 97 states to 97 states and 158 transitions. [2025-02-08 09:59:28,253 INFO L78 Accepts]: Start accepts. Automaton has 97 states and 158 transitions. Word has length 51 [2025-02-08 09:59:28,253 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-08 09:59:28,254 INFO L471 AbstractCegarLoop]: Abstraction has 97 states and 158 transitions. [2025-02-08 09:59:28,254 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 15 states have (on average 2.933333333333333) internal successors, (44), 16 states have internal predecessors, (44), 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-02-08 09:59:28,254 INFO L276 IsEmpty]: Start isEmpty. Operand 97 states and 158 transitions. [2025-02-08 09:59:28,256 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 82 [2025-02-08 09:59:28,259 INFO L210 NwaCegarLoop]: Found error trace [2025-02-08 09:59:28,259 INFO L218 NwaCegarLoop]: trace histogram [9, 8, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 1, 1, 1, 1, 1] [2025-02-08 09:59:28,269 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2025-02-08 09:59:28,460 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 5 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable6 [2025-02-08 09:59:28,460 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-02-08 09:59:28,460 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-08 09:59:28,461 INFO L85 PathProgramCache]: Analyzing trace with hash 124336117, now seen corresponding path program 1 times [2025-02-08 09:59:28,461 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-08 09:59:28,461 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1331739790] [2025-02-08 09:59:28,461 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-08 09:59:28,461 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-08 09:59:28,472 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 81 statements into 1 equivalence classes. [2025-02-08 09:59:28,480 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 81 of 81 statements. [2025-02-08 09:59:28,481 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 09:59:28,481 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 09:59:28,630 INFO L134 CoverageAnalysis]: Checked inductivity of 195 backedges. 38 proven. 80 refuted. 0 times theorem prover too weak. 77 trivial. 0 not checked. [2025-02-08 09:59:28,630 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-08 09:59:28,630 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1331739790] [2025-02-08 09:59:28,630 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1331739790] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-08 09:59:28,630 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [785043313] [2025-02-08 09:59:28,630 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-08 09:59:28,630 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-08 09:59:28,630 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-08 09:59:28,633 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-02-08 09:59:28,638 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2025-02-08 09:59:28,660 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 81 statements into 1 equivalence classes. [2025-02-08 09:59:28,674 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 81 of 81 statements. [2025-02-08 09:59:28,675 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 09:59:28,675 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 09:59:28,675 INFO L256 TraceCheckSpWp]: Trace formula consists of 172 conjuncts, 10 conjuncts are in the unsatisfiable core [2025-02-08 09:59:28,676 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-08 09:59:28,748 INFO L134 CoverageAnalysis]: Checked inductivity of 195 backedges. 50 proven. 84 refuted. 0 times theorem prover too weak. 61 trivial. 0 not checked. [2025-02-08 09:59:28,748 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-08 09:59:29,004 INFO L134 CoverageAnalysis]: Checked inductivity of 195 backedges. 50 proven. 87 refuted. 0 times theorem prover too weak. 58 trivial. 0 not checked. [2025-02-08 09:59:29,004 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [785043313] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-08 09:59:29,004 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-08 09:59:29,004 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 9, 11] total 16 [2025-02-08 09:59:29,004 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2077127490] [2025-02-08 09:59:29,004 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-08 09:59:29,005 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2025-02-08 09:59:29,005 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-08 09:59:29,005 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2025-02-08 09:59:29,005 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=53, Invalid=187, Unknown=0, NotChecked=0, Total=240 [2025-02-08 09:59:29,006 INFO L87 Difference]: Start difference. First operand 97 states and 158 transitions. Second operand has 16 states, 16 states have (on average 5.0) internal successors, (80), 16 states have internal predecessors, (80), 10 states have call successors, (14), 1 states have call predecessors, (14), 5 states have return successors, (14), 7 states have call predecessors, (14), 10 states have call successors, (14) [2025-02-08 09:59:29,138 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-08 09:59:29,138 INFO L93 Difference]: Finished difference Result 173 states and 298 transitions. [2025-02-08 09:59:29,138 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2025-02-08 09:59:29,138 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 16 states have (on average 5.0) internal successors, (80), 16 states have internal predecessors, (80), 10 states have call successors, (14), 1 states have call predecessors, (14), 5 states have return successors, (14), 7 states have call predecessors, (14), 10 states have call successors, (14) Word has length 81 [2025-02-08 09:59:29,139 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-08 09:59:29,139 INFO L225 Difference]: With dead ends: 173 [2025-02-08 09:59:29,140 INFO L226 Difference]: Without dead ends: 79 [2025-02-08 09:59:29,141 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 182 GetRequests, 155 SyntacticMatches, 5 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 73 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=164, Invalid=388, Unknown=0, NotChecked=0, Total=552 [2025-02-08 09:59:29,141 INFO L435 NwaCegarLoop]: 15 mSDtfsCounter, 86 mSDsluCounter, 60 mSDsCounter, 0 mSdLazyCounter, 132 mSolverCounterSat, 35 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 86 SdHoareTripleChecker+Valid, 75 SdHoareTripleChecker+Invalid, 167 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 35 IncrementalHoareTripleChecker+Valid, 132 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-02-08 09:59:29,142 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [86 Valid, 75 Invalid, 167 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [35 Valid, 132 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-02-08 09:59:29,142 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 79 states. [2025-02-08 09:59:29,146 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 79 to 69. [2025-02-08 09:59:29,147 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 69 states, 54 states have (on average 1.1111111111111112) internal successors, (60), 52 states have internal predecessors, (60), 7 states have call successors, (7), 4 states have call predecessors, (7), 6 states have return successors, (26), 12 states have call predecessors, (26), 6 states have call successors, (26) [2025-02-08 09:59:29,147 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 69 states to 69 states and 93 transitions. [2025-02-08 09:59:29,147 INFO L78 Accepts]: Start accepts. Automaton has 69 states and 93 transitions. Word has length 81 [2025-02-08 09:59:29,147 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-08 09:59:29,147 INFO L471 AbstractCegarLoop]: Abstraction has 69 states and 93 transitions. [2025-02-08 09:59:29,148 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 16 states have (on average 5.0) internal successors, (80), 16 states have internal predecessors, (80), 10 states have call successors, (14), 1 states have call predecessors, (14), 5 states have return successors, (14), 7 states have call predecessors, (14), 10 states have call successors, (14) [2025-02-08 09:59:29,148 INFO L276 IsEmpty]: Start isEmpty. Operand 69 states and 93 transitions. [2025-02-08 09:59:29,149 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 162 [2025-02-08 09:59:29,149 INFO L210 NwaCegarLoop]: Found error trace [2025-02-08 09:59:29,149 INFO L218 NwaCegarLoop]: trace histogram [18, 15, 13, 9, 9, 9, 9, 8, 8, 8, 8, 8, 7, 7, 6, 6, 5, 4, 1, 1, 1, 1] [2025-02-08 09:59:29,155 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2025-02-08 09:59:29,349 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,6 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-08 09:59:29,350 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-02-08 09:59:29,350 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-08 09:59:29,350 INFO L85 PathProgramCache]: Analyzing trace with hash 2103146220, now seen corresponding path program 2 times [2025-02-08 09:59:29,350 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-08 09:59:29,350 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [66411289] [2025-02-08 09:59:29,350 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-02-08 09:59:29,350 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-08 09:59:29,356 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 161 statements into 2 equivalence classes. [2025-02-08 09:59:29,366 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 161 of 161 statements. [2025-02-08 09:59:29,367 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-02-08 09:59:29,367 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 09:59:29,489 INFO L134 CoverageAnalysis]: Checked inductivity of 871 backedges. 104 proven. 228 refuted. 0 times theorem prover too weak. 539 trivial. 0 not checked. [2025-02-08 09:59:29,489 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-08 09:59:29,489 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [66411289] [2025-02-08 09:59:29,489 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [66411289] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-08 09:59:29,489 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [682319437] [2025-02-08 09:59:29,489 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-02-08 09:59:29,490 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-08 09:59:29,490 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-08 09:59:29,492 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-02-08 09:59:29,494 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2025-02-08 09:59:29,519 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 161 statements into 2 equivalence classes. [2025-02-08 09:59:29,545 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 161 of 161 statements. [2025-02-08 09:59:29,545 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-02-08 09:59:29,545 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 09:59:29,546 INFO L256 TraceCheckSpWp]: Trace formula consists of 319 conjuncts, 8 conjuncts are in the unsatisfiable core [2025-02-08 09:59:29,548 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-08 09:59:29,595 INFO L134 CoverageAnalysis]: Checked inductivity of 871 backedges. 438 proven. 15 refuted. 0 times theorem prover too weak. 418 trivial. 0 not checked. [2025-02-08 09:59:29,595 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-08 09:59:29,823 INFO L134 CoverageAnalysis]: Checked inductivity of 871 backedges. 107 proven. 271 refuted. 0 times theorem prover too weak. 493 trivial. 0 not checked. [2025-02-08 09:59:29,823 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [682319437] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-08 09:59:29,823 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-08 09:59:29,823 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 8, 9] total 14 [2025-02-08 09:59:29,823 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1650785140] [2025-02-08 09:59:29,823 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-08 09:59:29,824 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2025-02-08 09:59:29,824 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-08 09:59:29,824 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2025-02-08 09:59:29,824 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=47, Invalid=135, Unknown=0, NotChecked=0, Total=182 [2025-02-08 09:59:29,825 INFO L87 Difference]: Start difference. First operand 69 states and 93 transitions. Second operand has 14 states, 14 states have (on average 4.928571428571429) internal successors, (69), 14 states have internal predecessors, (69), 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-02-08 09:59:29,896 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-08 09:59:29,897 INFO L93 Difference]: Finished difference Result 128 states and 178 transitions. [2025-02-08 09:59:29,897 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2025-02-08 09:59:29,897 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 4.928571428571429) internal successors, (69), 14 states have internal predecessors, (69), 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 161 [2025-02-08 09:59:29,897 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-08 09:59:29,898 INFO L225 Difference]: With dead ends: 128 [2025-02-08 09:59:29,898 INFO L226 Difference]: Without dead ends: 62 [2025-02-08 09:59:29,898 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 334 GetRequests, 314 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-02-08 09:59:29,899 INFO L435 NwaCegarLoop]: 21 mSDtfsCounter, 42 mSDsluCounter, 45 mSDsCounter, 0 mSdLazyCounter, 94 mSolverCounterSat, 16 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 42 SdHoareTripleChecker+Valid, 66 SdHoareTripleChecker+Invalid, 110 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 16 IncrementalHoareTripleChecker+Valid, 94 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-02-08 09:59:29,899 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [42 Valid, 66 Invalid, 110 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [16 Valid, 94 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-02-08 09:59:29,899 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 62 states. [2025-02-08 09:59:29,902 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 62 to 60. [2025-02-08 09:59:29,902 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 60 states, 47 states have (on average 1.1063829787234043) internal successors, (52), 45 states have internal predecessors, (52), 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-02-08 09:59:29,903 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 60 states to 60 states and 72 transitions. [2025-02-08 09:59:29,903 INFO L78 Accepts]: Start accepts. Automaton has 60 states and 72 transitions. Word has length 161 [2025-02-08 09:59:29,903 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-08 09:59:29,903 INFO L471 AbstractCegarLoop]: Abstraction has 60 states and 72 transitions. [2025-02-08 09:59:29,903 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 4.928571428571429) internal successors, (69), 14 states have internal predecessors, (69), 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-02-08 09:59:29,903 INFO L276 IsEmpty]: Start isEmpty. Operand 60 states and 72 transitions. [2025-02-08 09:59:29,904 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 84 [2025-02-08 09:59:29,904 INFO L210 NwaCegarLoop]: Found error trace [2025-02-08 09:59:29,904 INFO L218 NwaCegarLoop]: trace histogram [9, 8, 7, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 2, 1, 1, 1, 1] [2025-02-08 09:59:29,910 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2025-02-08 09:59:30,104 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 7 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable8 [2025-02-08 09:59:30,105 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-02-08 09:59:30,106 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-08 09:59:30,106 INFO L85 PathProgramCache]: Analyzing trace with hash -767376791, now seen corresponding path program 3 times [2025-02-08 09:59:30,106 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-08 09:59:30,106 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1767533510] [2025-02-08 09:59:30,106 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-02-08 09:59:30,106 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-08 09:59:30,110 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 83 statements into 8 equivalence classes. [2025-02-08 09:59:30,116 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) and asserted 50 of 83 statements. [2025-02-08 09:59:30,116 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2025-02-08 09:59:30,116 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 09:59:30,213 INFO L134 CoverageAnalysis]: Checked inductivity of 206 backedges. 58 proven. 8 refuted. 0 times theorem prover too weak. 140 trivial. 0 not checked. [2025-02-08 09:59:30,213 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-08 09:59:30,214 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1767533510] [2025-02-08 09:59:30,214 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1767533510] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-08 09:59:30,214 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [186105897] [2025-02-08 09:59:30,214 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-02-08 09:59:30,214 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-08 09:59:30,214 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-08 09:59:30,218 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-02-08 09:59:30,221 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2025-02-08 09:59:30,244 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 83 statements into 8 equivalence classes. [2025-02-08 09:59:30,254 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) and asserted 50 of 83 statements. [2025-02-08 09:59:30,254 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2025-02-08 09:59:30,254 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 09:59:30,255 INFO L256 TraceCheckSpWp]: Trace formula consists of 114 conjuncts, 8 conjuncts are in the unsatisfiable core [2025-02-08 09:59:30,256 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-08 09:59:30,306 INFO L134 CoverageAnalysis]: Checked inductivity of 206 backedges. 60 proven. 4 refuted. 0 times theorem prover too weak. 142 trivial. 0 not checked. [2025-02-08 09:59:30,306 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-08 09:59:30,439 INFO L134 CoverageAnalysis]: Checked inductivity of 206 backedges. 60 proven. 4 refuted. 0 times theorem prover too weak. 142 trivial. 0 not checked. [2025-02-08 09:59:30,439 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [186105897] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-08 09:59:30,439 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-08 09:59:30,440 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 7, 7] total 15 [2025-02-08 09:59:30,440 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [715655667] [2025-02-08 09:59:30,440 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-08 09:59:30,440 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2025-02-08 09:59:30,440 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-08 09:59:30,440 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2025-02-08 09:59:30,440 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=60, Invalid=180, Unknown=0, NotChecked=0, Total=240 [2025-02-08 09:59:30,441 INFO L87 Difference]: Start difference. First operand 60 states and 72 transitions. Second operand has 16 states, 15 states have (on average 3.4) internal successors, (51), 16 states have internal predecessors, (51), 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-02-08 09:59:30,489 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-08 09:59:30,489 INFO L93 Difference]: Finished difference Result 60 states and 72 transitions. [2025-02-08 09:59:30,489 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2025-02-08 09:59:30,489 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 15 states have (on average 3.4) internal successors, (51), 16 states have internal predecessors, (51), 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 83 [2025-02-08 09:59:30,489 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-08 09:59:30,490 INFO L225 Difference]: With dead ends: 60 [2025-02-08 09:59:30,490 INFO L226 Difference]: Without dead ends: 59 [2025-02-08 09:59:30,490 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 174 GetRequests, 154 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-02-08 09:59:30,491 INFO L435 NwaCegarLoop]: 19 mSDtfsCounter, 4 mSDsluCounter, 128 mSDsCounter, 0 mSdLazyCounter, 67 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 147 SdHoareTripleChecker+Invalid, 68 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 67 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-02-08 09:59:30,491 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [5 Valid, 147 Invalid, 68 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 67 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-02-08 09:59:30,491 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 59 states. [2025-02-08 09:59:30,494 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 59 to 55. [2025-02-08 09:59:30,494 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 55 states, 43 states have (on average 1.069767441860465) internal successors, (46), 42 states have internal predecessors, (46), 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-02-08 09:59:30,495 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 55 states to 55 states and 66 transitions. [2025-02-08 09:59:30,495 INFO L78 Accepts]: Start accepts. Automaton has 55 states and 66 transitions. Word has length 83 [2025-02-08 09:59:30,495 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-08 09:59:30,495 INFO L471 AbstractCegarLoop]: Abstraction has 55 states and 66 transitions. [2025-02-08 09:59:30,495 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 15 states have (on average 3.4) internal successors, (51), 16 states have internal predecessors, (51), 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-02-08 09:59:30,495 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 66 transitions. [2025-02-08 09:59:30,496 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 111 [2025-02-08 09:59:30,496 INFO L210 NwaCegarLoop]: Found error trace [2025-02-08 09:59:30,496 INFO L218 NwaCegarLoop]: trace histogram [12, 10, 10, 6, 6, 6, 6, 5, 5, 5, 5, 5, 5, 5, 5, 4, 4, 2, 1, 1, 1, 1] [2025-02-08 09:59:30,502 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2025-02-08 09:59:30,700 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,8 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-08 09:59:30,700 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-02-08 09:59:30,700 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-08 09:59:30,701 INFO L85 PathProgramCache]: Analyzing trace with hash 1308717593, now seen corresponding path program 2 times [2025-02-08 09:59:30,701 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-08 09:59:30,701 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1845286895] [2025-02-08 09:59:30,701 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-02-08 09:59:30,701 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-08 09:59:30,705 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 110 statements into 2 equivalence classes. [2025-02-08 09:59:30,713 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 110 of 110 statements. [2025-02-08 09:59:30,713 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-02-08 09:59:30,713 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 09:59:30,865 INFO L134 CoverageAnalysis]: Checked inductivity of 382 backedges. 94 proven. 159 refuted. 0 times theorem prover too weak. 129 trivial. 0 not checked. [2025-02-08 09:59:30,866 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-08 09:59:30,866 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1845286895] [2025-02-08 09:59:30,866 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1845286895] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-08 09:59:30,866 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1474063584] [2025-02-08 09:59:30,866 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-02-08 09:59:30,866 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-08 09:59:30,866 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-08 09:59:30,869 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-02-08 09:59:30,872 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2025-02-08 09:59:30,894 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 110 statements into 2 equivalence classes. [2025-02-08 09:59:30,911 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 110 of 110 statements. [2025-02-08 09:59:30,911 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-02-08 09:59:30,911 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 09:59:30,912 INFO L256 TraceCheckSpWp]: Trace formula consists of 224 conjuncts, 14 conjuncts are in the unsatisfiable core [2025-02-08 09:59:30,913 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-08 09:59:30,985 INFO L134 CoverageAnalysis]: Checked inductivity of 382 backedges. 106 proven. 158 refuted. 0 times theorem prover too weak. 118 trivial. 0 not checked. [2025-02-08 09:59:30,986 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-08 09:59:31,424 INFO L134 CoverageAnalysis]: Checked inductivity of 382 backedges. 106 proven. 174 refuted. 0 times theorem prover too weak. 102 trivial. 0 not checked. [2025-02-08 09:59:31,424 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1474063584] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-08 09:59:31,424 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-08 09:59:31,424 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 11, 15] total 20 [2025-02-08 09:59:31,424 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [607713060] [2025-02-08 09:59:31,424 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-08 09:59:31,425 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2025-02-08 09:59:31,425 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-08 09:59:31,425 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2025-02-08 09:59:31,425 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=76, Invalid=304, Unknown=0, NotChecked=0, Total=380 [2025-02-08 09:59:31,426 INFO L87 Difference]: Start difference. First operand 55 states and 66 transitions. Second operand has 20 states, 20 states have (on average 4.6) internal successors, (92), 20 states have internal predecessors, (92), 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-02-08 09:59:31,611 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-08 09:59:31,611 INFO L93 Difference]: Finished difference Result 133 states and 168 transitions. [2025-02-08 09:59:31,611 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2025-02-08 09:59:31,611 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 20 states have (on average 4.6) internal successors, (92), 20 states have internal predecessors, (92), 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 110 [2025-02-08 09:59:31,612 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-08 09:59:31,612 INFO L225 Difference]: With dead ends: 133 [2025-02-08 09:59:31,612 INFO L226 Difference]: Without dead ends: 83 [2025-02-08 09:59:31,613 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 249 GetRequests, 212 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-02-08 09:59:31,613 INFO L435 NwaCegarLoop]: 21 mSDtfsCounter, 105 mSDsluCounter, 75 mSDsCounter, 0 mSdLazyCounter, 182 mSolverCounterSat, 52 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 105 SdHoareTripleChecker+Valid, 96 SdHoareTripleChecker+Invalid, 234 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 52 IncrementalHoareTripleChecker+Valid, 182 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-02-08 09:59:31,614 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [105 Valid, 96 Invalid, 234 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [52 Valid, 182 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-02-08 09:59:31,614 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 83 states. [2025-02-08 09:59:31,618 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 83 to 73. [2025-02-08 09:59:31,619 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 73 states, 58 states have (on average 1.0862068965517242) internal successors, (63), 56 states have internal predecessors, (63), 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-02-08 09:59:31,619 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 73 states to 73 states and 88 transitions. [2025-02-08 09:59:31,620 INFO L78 Accepts]: Start accepts. Automaton has 73 states and 88 transitions. Word has length 110 [2025-02-08 09:59:31,620 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-08 09:59:31,620 INFO L471 AbstractCegarLoop]: Abstraction has 73 states and 88 transitions. [2025-02-08 09:59:31,620 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 20 states have (on average 4.6) internal successors, (92), 20 states have internal predecessors, (92), 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-02-08 09:59:31,620 INFO L276 IsEmpty]: Start isEmpty. Operand 73 states and 88 transitions. [2025-02-08 09:59:31,620 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 92 [2025-02-08 09:59:31,621 INFO L210 NwaCegarLoop]: Found error trace [2025-02-08 09:59:31,621 INFO L218 NwaCegarLoop]: trace histogram [10, 9, 8, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 1, 1, 1, 1, 1] [2025-02-08 09:59:31,627 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2025-02-08 09:59:31,821 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,9 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-08 09:59:31,821 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-02-08 09:59:31,822 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-08 09:59:31,822 INFO L85 PathProgramCache]: Analyzing trace with hash 685125632, now seen corresponding path program 3 times [2025-02-08 09:59:31,822 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-08 09:59:31,822 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [22291778] [2025-02-08 09:59:31,822 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-02-08 09:59:31,822 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-08 09:59:31,826 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 91 statements into 8 equivalence classes. [2025-02-08 09:59:31,832 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) and asserted 79 of 91 statements. [2025-02-08 09:59:31,832 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2025-02-08 09:59:31,832 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 09:59:31,917 INFO L134 CoverageAnalysis]: Checked inductivity of 254 backedges. 102 proven. 38 refuted. 0 times theorem prover too weak. 114 trivial. 0 not checked. [2025-02-08 09:59:31,920 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-08 09:59:31,920 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [22291778] [2025-02-08 09:59:31,920 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [22291778] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-08 09:59:31,920 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1659988839] [2025-02-08 09:59:31,920 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-02-08 09:59:31,921 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-08 09:59:31,921 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-08 09:59:31,922 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-02-08 09:59:31,924 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2025-02-08 09:59:31,948 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 91 statements into 8 equivalence classes. [2025-02-08 09:59:31,963 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) and asserted 79 of 91 statements. [2025-02-08 09:59:31,963 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2025-02-08 09:59:31,963 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 09:59:31,964 INFO L256 TraceCheckSpWp]: Trace formula consists of 169 conjuncts, 17 conjuncts are in the unsatisfiable core [2025-02-08 09:59:31,965 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-08 09:59:32,227 INFO L134 CoverageAnalysis]: Checked inductivity of 254 backedges. 8 proven. 66 refuted. 0 times theorem prover too weak. 180 trivial. 0 not checked. [2025-02-08 09:59:32,228 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-08 09:59:32,957 INFO L134 CoverageAnalysis]: Checked inductivity of 254 backedges. 20 proven. 66 refuted. 0 times theorem prover too weak. 168 trivial. 0 not checked. [2025-02-08 09:59:32,957 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1659988839] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-08 09:59:32,957 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-08 09:59:32,957 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 12, 13] total 30 [2025-02-08 09:59:32,958 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [535620209] [2025-02-08 09:59:32,958 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-08 09:59:32,958 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 30 states [2025-02-08 09:59:32,958 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-08 09:59:32,959 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 30 interpolants. [2025-02-08 09:59:32,959 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=144, Invalid=726, Unknown=0, NotChecked=0, Total=870 [2025-02-08 09:59:32,959 INFO L87 Difference]: Start difference. First operand 73 states and 88 transitions. Second operand has 30 states, 30 states have (on average 3.3) internal successors, (99), 30 states have internal predecessors, (99), 10 states have call successors, (13), 1 states have call predecessors, (13), 12 states have return successors, (22), 19 states have call predecessors, (22), 10 states have call successors, (22) [2025-02-08 09:59:33,617 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-08 09:59:33,618 INFO L93 Difference]: Finished difference Result 192 states and 278 transitions. [2025-02-08 09:59:33,618 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 30 states. [2025-02-08 09:59:33,618 INFO L78 Accepts]: Start accepts. Automaton has has 30 states, 30 states have (on average 3.3) internal successors, (99), 30 states have internal predecessors, (99), 10 states have call successors, (13), 1 states have call predecessors, (13), 12 states have return successors, (22), 19 states have call predecessors, (22), 10 states have call successors, (22) Word has length 91 [2025-02-08 09:59:33,618 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-08 09:59:33,619 INFO L225 Difference]: With dead ends: 192 [2025-02-08 09:59:33,619 INFO L226 Difference]: Without dead ends: 124 [2025-02-08 09:59:33,621 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 218 GetRequests, 158 SyntacticMatches, 4 SemanticMatches, 56 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 863 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=597, Invalid=2709, Unknown=0, NotChecked=0, Total=3306 [2025-02-08 09:59:33,621 INFO L435 NwaCegarLoop]: 12 mSDtfsCounter, 178 mSDsluCounter, 108 mSDsCounter, 0 mSdLazyCounter, 505 mSolverCounterSat, 101 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 178 SdHoareTripleChecker+Valid, 120 SdHoareTripleChecker+Invalid, 606 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 101 IncrementalHoareTripleChecker+Valid, 505 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2025-02-08 09:59:33,621 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [178 Valid, 120 Invalid, 606 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [101 Valid, 505 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2025-02-08 09:59:33,622 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 124 states. [2025-02-08 09:59:33,636 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 124 to 97. [2025-02-08 09:59:33,636 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 97 states, 76 states have (on average 1.0526315789473684) internal successors, (80), 75 states have internal predecessors, (80), 11 states have call successors, (11), 5 states have call predecessors, (11), 9 states have return successors, (47), 16 states have call predecessors, (47), 10 states have call successors, (47) [2025-02-08 09:59:33,637 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 97 states to 97 states and 138 transitions. [2025-02-08 09:59:33,638 INFO L78 Accepts]: Start accepts. Automaton has 97 states and 138 transitions. Word has length 91 [2025-02-08 09:59:33,638 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-08 09:59:33,638 INFO L471 AbstractCegarLoop]: Abstraction has 97 states and 138 transitions. [2025-02-08 09:59:33,638 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 30 states, 30 states have (on average 3.3) internal successors, (99), 30 states have internal predecessors, (99), 10 states have call successors, (13), 1 states have call predecessors, (13), 12 states have return successors, (22), 19 states have call predecessors, (22), 10 states have call successors, (22) [2025-02-08 09:59:33,638 INFO L276 IsEmpty]: Start isEmpty. Operand 97 states and 138 transitions. [2025-02-08 09:59:33,642 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 439 [2025-02-08 09:59:33,642 INFO L210 NwaCegarLoop]: Found error trace [2025-02-08 09:59:33,642 INFO L218 NwaCegarLoop]: trace histogram [46, 43, 37, 23, 23, 23, 23, 22, 22, 22, 22, 22, 21, 21, 21, 20, 14, 9, 1, 1, 1, 1] [2025-02-08 09:59:33,650 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2025-02-08 09:59:33,842 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11,10 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-08 09:59:33,843 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-02-08 09:59:33,843 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-08 09:59:33,844 INFO L85 PathProgramCache]: Analyzing trace with hash -1784762055, now seen corresponding path program 4 times [2025-02-08 09:59:33,844 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-08 09:59:33,844 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [93922937] [2025-02-08 09:59:33,844 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-02-08 09:59:33,844 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-08 09:59:33,861 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 438 statements into 2 equivalence classes. [2025-02-08 09:59:33,886 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) and asserted 261 of 438 statements. [2025-02-08 09:59:33,886 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) [2025-02-08 09:59:33,886 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 09:59:34,186 INFO L134 CoverageAnalysis]: Checked inductivity of 6855 backedges. 382 proven. 1512 refuted. 0 times theorem prover too weak. 4961 trivial. 0 not checked. [2025-02-08 09:59:34,187 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-08 09:59:34,187 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [93922937] [2025-02-08 09:59:34,187 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [93922937] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-08 09:59:34,187 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1750896363] [2025-02-08 09:59:34,187 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-02-08 09:59:34,187 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-08 09:59:34,188 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-08 09:59:34,193 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-02-08 09:59:34,195 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2025-02-08 09:59:34,241 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 438 statements into 2 equivalence classes. [2025-02-08 09:59:34,280 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) and asserted 261 of 438 statements. [2025-02-08 09:59:34,280 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) [2025-02-08 09:59:34,281 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 09:59:34,282 INFO L256 TraceCheckSpWp]: Trace formula consists of 550 conjuncts, 18 conjuncts are in the unsatisfiable core [2025-02-08 09:59:34,288 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-08 09:59:34,422 INFO L134 CoverageAnalysis]: Checked inductivity of 6855 backedges. 3721 proven. 533 refuted. 0 times theorem prover too weak. 2601 trivial. 0 not checked. [2025-02-08 09:59:34,422 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-08 09:59:35,295 INFO L134 CoverageAnalysis]: Checked inductivity of 6855 backedges. 351 proven. 2148 refuted. 0 times theorem prover too weak. 4356 trivial. 0 not checked. [2025-02-08 09:59:35,295 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1750896363] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-08 09:59:35,295 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-08 09:59:35,295 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13, 18] total 23 [2025-02-08 09:59:35,295 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [989968973] [2025-02-08 09:59:35,295 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-08 09:59:35,296 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2025-02-08 09:59:35,296 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-08 09:59:35,296 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2025-02-08 09:59:35,298 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=91, Invalid=415, Unknown=0, NotChecked=0, Total=506 [2025-02-08 09:59:35,298 INFO L87 Difference]: Start difference. First operand 97 states and 138 transitions. Second operand has 23 states, 23 states have (on average 6.0) internal successors, (138), 23 states have internal predecessors, (138), 18 states have call successors, (25), 3 states have call predecessors, (25), 9 states have return successors, (28), 11 states have call predecessors, (28), 17 states have call successors, (28) [2025-02-08 09:59:35,532 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-08 09:59:35,533 INFO L93 Difference]: Finished difference Result 244 states and 393 transitions. [2025-02-08 09:59:35,533 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2025-02-08 09:59:35,533 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 23 states have (on average 6.0) internal successors, (138), 23 states have internal predecessors, (138), 18 states have call successors, (25), 3 states have call predecessors, (25), 9 states have return successors, (28), 11 states have call predecessors, (28), 17 states have call successors, (28) Word has length 438 [2025-02-08 09:59:35,534 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-08 09:59:35,534 INFO L225 Difference]: With dead ends: 244 [2025-02-08 09:59:35,535 INFO L226 Difference]: Without dead ends: 152 [2025-02-08 09:59:35,536 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 910 GetRequests, 863 SyntacticMatches, 10 SemanticMatches, 37 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 307 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=411, Invalid=1071, Unknown=0, NotChecked=0, Total=1482 [2025-02-08 09:59:35,536 INFO L435 NwaCegarLoop]: 23 mSDtfsCounter, 119 mSDsluCounter, 94 mSDsCounter, 0 mSdLazyCounter, 212 mSolverCounterSat, 57 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 119 SdHoareTripleChecker+Valid, 117 SdHoareTripleChecker+Invalid, 269 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 57 IncrementalHoareTripleChecker+Valid, 212 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-02-08 09:59:35,536 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [119 Valid, 117 Invalid, 269 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [57 Valid, 212 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-02-08 09:59:35,537 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 152 states. [2025-02-08 09:59:35,543 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 152 to 133. [2025-02-08 09:59:35,544 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 133 states, 105 states have (on average 1.0571428571428572) internal successors, (111), 103 states have internal predecessors, (111), 15 states have call successors, (15), 6 states have call predecessors, (15), 12 states have return successors, (57), 23 states have call predecessors, (57), 14 states have call successors, (57) [2025-02-08 09:59:35,544 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 133 states to 133 states and 183 transitions. [2025-02-08 09:59:35,545 INFO L78 Accepts]: Start accepts. Automaton has 133 states and 183 transitions. Word has length 438 [2025-02-08 09:59:35,545 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-08 09:59:35,545 INFO L471 AbstractCegarLoop]: Abstraction has 133 states and 183 transitions. [2025-02-08 09:59:35,545 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 23 states have (on average 6.0) internal successors, (138), 23 states have internal predecessors, (138), 18 states have call successors, (25), 3 states have call predecessors, (25), 9 states have return successors, (28), 11 states have call predecessors, (28), 17 states have call successors, (28) [2025-02-08 09:59:35,545 INFO L276 IsEmpty]: Start isEmpty. Operand 133 states and 183 transitions. [2025-02-08 09:59:35,547 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 346 [2025-02-08 09:59:35,547 INFO L210 NwaCegarLoop]: Found error trace [2025-02-08 09:59:35,547 INFO L218 NwaCegarLoop]: trace histogram [36, 34, 29, 18, 18, 18, 18, 17, 17, 17, 17, 17, 17, 17, 17, 16, 11, 7, 1, 1, 1, 1] [2025-02-08 09:59:35,554 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2025-02-08 09:59:35,751 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2025-02-08 09:59:35,752 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-02-08 09:59:35,752 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-08 09:59:35,752 INFO L85 PathProgramCache]: Analyzing trace with hash 1934682716, now seen corresponding path program 5 times [2025-02-08 09:59:35,752 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-08 09:59:35,752 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1544279543] [2025-02-08 09:59:35,752 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2025-02-08 09:59:35,752 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-08 09:59:35,760 INFO L108 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 partitioned 345 statements into 27 equivalence classes. [2025-02-08 09:59:35,771 INFO L111 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 15 check-sat command(s) and asserted 197 of 345 statements. [2025-02-08 09:59:35,771 INFO L114 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 15 check-sat command(s) [2025-02-08 09:59:35,771 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 09:59:35,998 INFO L134 CoverageAnalysis]: Checked inductivity of 4199 backedges. 734 proven. 1144 refuted. 0 times theorem prover too weak. 2321 trivial. 0 not checked. [2025-02-08 09:59:35,998 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-08 09:59:35,998 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1544279543] [2025-02-08 09:59:35,998 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1544279543] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-08 09:59:35,998 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [74439819] [2025-02-08 09:59:35,998 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2025-02-08 09:59:35,998 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-08 09:59:35,998 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-08 09:59:36,005 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-02-08 09:59:36,006 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2025-02-08 09:59:36,052 INFO L108 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 partitioned 345 statements into 27 equivalence classes. [2025-02-08 09:59:36,084 INFO L111 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 15 check-sat command(s) and asserted 197 of 345 statements. [2025-02-08 09:59:36,084 INFO L114 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 15 check-sat command(s) [2025-02-08 09:59:36,084 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 09:59:36,085 INFO L256 TraceCheckSpWp]: Trace formula consists of 365 conjuncts, 19 conjuncts are in the unsatisfiable core [2025-02-08 09:59:36,088 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-08 09:59:36,267 INFO L134 CoverageAnalysis]: Checked inductivity of 4199 backedges. 740 proven. 1135 refuted. 0 times theorem prover too weak. 2324 trivial. 0 not checked. [2025-02-08 09:59:36,268 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-08 09:59:37,236 INFO L134 CoverageAnalysis]: Checked inductivity of 4199 backedges. 737 proven. 1177 refuted. 0 times theorem prover too weak. 2285 trivial. 0 not checked. [2025-02-08 09:59:37,236 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [74439819] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-08 09:59:37,236 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-08 09:59:37,236 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 14, 20] total 26 [2025-02-08 09:59:37,236 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [897045960] [2025-02-08 09:59:37,236 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-08 09:59:37,237 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 26 states [2025-02-08 09:59:37,237 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-08 09:59:37,237 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2025-02-08 09:59:37,238 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=124, Invalid=526, Unknown=0, NotChecked=0, Total=650 [2025-02-08 09:59:37,238 INFO L87 Difference]: Start difference. First operand 133 states and 183 transitions. Second operand has 26 states, 26 states have (on average 5.153846153846154) internal successors, (134), 26 states have internal predecessors, (134), 17 states have call successors, (23), 1 states have call predecessors, (23), 9 states have return successors, (27), 13 states have call predecessors, (27), 17 states have call successors, (27) [2025-02-08 09:59:37,560 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-08 09:59:37,561 INFO L93 Difference]: Finished difference Result 269 states and 422 transitions. [2025-02-08 09:59:37,561 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2025-02-08 09:59:37,561 INFO L78 Accepts]: Start accepts. Automaton has has 26 states, 26 states have (on average 5.153846153846154) internal successors, (134), 26 states have internal predecessors, (134), 17 states have call successors, (23), 1 states have call predecessors, (23), 9 states have return successors, (27), 13 states have call predecessors, (27), 17 states have call successors, (27) Word has length 345 [2025-02-08 09:59:37,562 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-08 09:59:37,563 INFO L225 Difference]: With dead ends: 269 [2025-02-08 09:59:37,563 INFO L226 Difference]: Without dead ends: 141 [2025-02-08 09:59:37,565 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 730 GetRequests, 679 SyntacticMatches, 9 SemanticMatches, 42 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 417 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=519, Invalid=1373, Unknown=0, NotChecked=0, Total=1892 [2025-02-08 09:59:37,565 INFO L435 NwaCegarLoop]: 35 mSDtfsCounter, 251 mSDsluCounter, 106 mSDsCounter, 0 mSdLazyCounter, 350 mSolverCounterSat, 155 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 251 SdHoareTripleChecker+Valid, 141 SdHoareTripleChecker+Invalid, 505 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 155 IncrementalHoareTripleChecker+Valid, 350 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-02-08 09:59:37,565 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [251 Valid, 141 Invalid, 505 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [155 Valid, 350 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-02-08 09:59:37,565 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 141 states. [2025-02-08 09:59:37,595 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 141 to 121. [2025-02-08 09:59:37,596 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 121 states, 98 states have (on average 1.0510204081632653) internal successors, (103), 94 states have internal predecessors, (103), 14 states have call successors, (14), 11 states have call predecessors, (14), 8 states have return successors, (32), 15 states have call predecessors, (32), 13 states have call successors, (32) [2025-02-08 09:59:37,596 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 121 states to 121 states and 149 transitions. [2025-02-08 09:59:37,597 INFO L78 Accepts]: Start accepts. Automaton has 121 states and 149 transitions. Word has length 345 [2025-02-08 09:59:37,597 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-08 09:59:37,597 INFO L471 AbstractCegarLoop]: Abstraction has 121 states and 149 transitions. [2025-02-08 09:59:37,597 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 26 states, 26 states have (on average 5.153846153846154) internal successors, (134), 26 states have internal predecessors, (134), 17 states have call successors, (23), 1 states have call predecessors, (23), 9 states have return successors, (27), 13 states have call predecessors, (27), 17 states have call successors, (27) [2025-02-08 09:59:37,597 INFO L276 IsEmpty]: Start isEmpty. Operand 121 states and 149 transitions. [2025-02-08 09:59:37,599 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 262 [2025-02-08 09:59:37,599 INFO L210 NwaCegarLoop]: Found error trace [2025-02-08 09:59:37,599 INFO L218 NwaCegarLoop]: trace histogram [27, 26, 22, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 12, 9, 5, 1, 1, 1, 1] [2025-02-08 09:59:37,607 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Ended with exit code 0 [2025-02-08 09:59:37,803 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2025-02-08 09:59:37,804 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-02-08 09:59:37,804 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-08 09:59:37,804 INFO L85 PathProgramCache]: Analyzing trace with hash -1142938423, now seen corresponding path program 6 times [2025-02-08 09:59:37,804 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-08 09:59:37,804 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1805141995] [2025-02-08 09:59:37,804 INFO L95 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2025-02-08 09:59:37,805 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-08 09:59:37,813 INFO L108 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE partitioned 261 statements into 19 equivalence classes. [2025-02-08 09:59:37,843 INFO L111 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 15 check-sat command(s) and asserted 184 of 261 statements. [2025-02-08 09:59:37,843 INFO L114 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 15 check-sat command(s) [2025-02-08 09:59:37,843 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 09:59:38,048 INFO L134 CoverageAnalysis]: Checked inductivity of 2363 backedges. 502 proven. 671 refuted. 0 times theorem prover too weak. 1190 trivial. 0 not checked. [2025-02-08 09:59:38,049 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-08 09:59:38,049 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1805141995] [2025-02-08 09:59:38,049 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1805141995] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-08 09:59:38,049 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1467387831] [2025-02-08 09:59:38,049 INFO L95 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2025-02-08 09:59:38,049 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-08 09:59:38,049 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-08 09:59:38,051 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-02-08 09:59:38,052 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2025-02-08 09:59:38,099 INFO L108 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE partitioned 261 statements into 19 equivalence classes. [2025-02-08 09:59:38,128 INFO L111 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 15 check-sat command(s) and asserted 184 of 261 statements. [2025-02-08 09:59:38,129 INFO L114 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 15 check-sat command(s) [2025-02-08 09:59:38,129 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 09:59:38,130 INFO L256 TraceCheckSpWp]: Trace formula consists of 361 conjuncts, 18 conjuncts are in the unsatisfiable core [2025-02-08 09:59:38,132 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-08 09:59:38,228 INFO L134 CoverageAnalysis]: Checked inductivity of 2363 backedges. 485 proven. 734 refuted. 0 times theorem prover too weak. 1144 trivial. 0 not checked. [2025-02-08 09:59:38,228 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-08 09:59:39,272 INFO L134 CoverageAnalysis]: Checked inductivity of 2363 backedges. 481 proven. 786 refuted. 0 times theorem prover too weak. 1096 trivial. 0 not checked. [2025-02-08 09:59:39,272 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1467387831] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-08 09:59:39,272 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-08 09:59:39,272 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13, 18] total 23 [2025-02-08 09:59:39,273 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [887513940] [2025-02-08 09:59:39,273 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-08 09:59:39,273 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2025-02-08 09:59:39,273 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-08 09:59:39,273 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2025-02-08 09:59:39,273 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=108, Invalid=398, Unknown=0, NotChecked=0, Total=506 [2025-02-08 09:59:39,274 INFO L87 Difference]: Start difference. First operand 121 states and 149 transitions. Second operand has 23 states, 23 states have (on average 5.739130434782608) internal successors, (132), 23 states have internal predecessors, (132), 17 states have call successors, (22), 1 states have call predecessors, (22), 9 states have return successors, (27), 13 states have call predecessors, (27), 17 states have call successors, (27) [2025-02-08 09:59:39,495 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-08 09:59:39,495 INFO L93 Difference]: Finished difference Result 245 states and 326 transitions. [2025-02-08 09:59:39,496 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2025-02-08 09:59:39,496 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 23 states have (on average 5.739130434782608) internal successors, (132), 23 states have internal predecessors, (132), 17 states have call successors, (22), 1 states have call predecessors, (22), 9 states have return successors, (27), 13 states have call predecessors, (27), 17 states have call successors, (27) Word has length 261 [2025-02-08 09:59:39,496 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-08 09:59:39,497 INFO L225 Difference]: With dead ends: 245 [2025-02-08 09:59:39,497 INFO L226 Difference]: Without dead ends: 129 [2025-02-08 09:59:39,498 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 549 GetRequests, 508 SyntacticMatches, 9 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 261 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=312, Invalid=810, Unknown=0, NotChecked=0, Total=1122 [2025-02-08 09:59:39,498 INFO L435 NwaCegarLoop]: 47 mSDtfsCounter, 117 mSDsluCounter, 142 mSDsCounter, 0 mSdLazyCounter, 391 mSolverCounterSat, 61 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 117 SdHoareTripleChecker+Valid, 189 SdHoareTripleChecker+Invalid, 452 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 61 IncrementalHoareTripleChecker+Valid, 391 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-02-08 09:59:39,499 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [117 Valid, 189 Invalid, 452 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [61 Valid, 391 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-02-08 09:59:39,499 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 129 states. [2025-02-08 09:59:39,503 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 129 to 127. [2025-02-08 09:59:39,504 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 127 states, 103 states have (on average 1.0388349514563107) internal successors, (107), 100 states have internal predecessors, (107), 16 states have call successors, (16), 14 states have call predecessors, (16), 7 states have return successors, (30), 12 states have call predecessors, (30), 15 states have call successors, (30) [2025-02-08 09:59:39,504 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 127 states to 127 states and 153 transitions. [2025-02-08 09:59:39,504 INFO L78 Accepts]: Start accepts. Automaton has 127 states and 153 transitions. Word has length 261 [2025-02-08 09:59:39,505 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-08 09:59:39,505 INFO L471 AbstractCegarLoop]: Abstraction has 127 states and 153 transitions. [2025-02-08 09:59:39,505 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 23 states have (on average 5.739130434782608) internal successors, (132), 23 states have internal predecessors, (132), 17 states have call successors, (22), 1 states have call predecessors, (22), 9 states have return successors, (27), 13 states have call predecessors, (27), 17 states have call successors, (27) [2025-02-08 09:59:39,505 INFO L276 IsEmpty]: Start isEmpty. Operand 127 states and 153 transitions. [2025-02-08 09:59:39,507 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 655 [2025-02-08 09:59:39,507 INFO L210 NwaCegarLoop]: Found error trace [2025-02-08 09:59:39,508 INFO L218 NwaCegarLoop]: trace histogram [68, 65, 55, 34, 34, 34, 34, 33, 33, 33, 33, 33, 32, 32, 32, 31, 21, 13, 1, 1, 1, 1] [2025-02-08 09:59:39,517 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Ended with exit code 0 [2025-02-08 09:59:39,712 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable14,13 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-08 09:59:39,712 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-02-08 09:59:39,712 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-08 09:59:39,712 INFO L85 PathProgramCache]: Analyzing trace with hash 1226165847, now seen corresponding path program 7 times [2025-02-08 09:59:39,712 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-08 09:59:39,712 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [784885891] [2025-02-08 09:59:39,712 INFO L95 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2025-02-08 09:59:39,712 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-08 09:59:39,725 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 654 statements into 1 equivalence classes. [2025-02-08 09:59:39,757 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 654 of 654 statements. [2025-02-08 09:59:39,757 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 09:59:39,757 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 09:59:40,557 INFO L134 CoverageAnalysis]: Checked inductivity of 15484 backedges. 1115 proven. 3497 refuted. 0 times theorem prover too weak. 10872 trivial. 0 not checked. [2025-02-08 09:59:40,558 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-08 09:59:40,558 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [784885891] [2025-02-08 09:59:40,558 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [784885891] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-08 09:59:40,558 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1953709460] [2025-02-08 09:59:40,558 INFO L95 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2025-02-08 09:59:40,558 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-08 09:59:40,558 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-08 09:59:40,560 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-02-08 09:59:40,561 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2025-02-08 09:59:40,632 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 654 statements into 1 equivalence classes. [2025-02-08 09:59:40,715 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 654 of 654 statements. [2025-02-08 09:59:40,715 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 09:59:40,715 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 09:59:40,718 INFO L256 TraceCheckSpWp]: Trace formula consists of 1229 conjuncts, 26 conjuncts are in the unsatisfiable core [2025-02-08 09:59:40,723 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-08 09:59:40,861 INFO L134 CoverageAnalysis]: Checked inductivity of 15484 backedges. 6706 proven. 2740 refuted. 0 times theorem prover too weak. 6038 trivial. 0 not checked. [2025-02-08 09:59:40,862 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-08 09:59:42,446 INFO L134 CoverageAnalysis]: Checked inductivity of 15484 backedges. 1350 proven. 4200 refuted. 0 times theorem prover too weak. 9934 trivial. 0 not checked. [2025-02-08 09:59:42,446 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1953709460] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-08 09:59:42,446 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-08 09:59:42,446 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 17, 25] total 30 [2025-02-08 09:59:42,446 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1073784153] [2025-02-08 09:59:42,446 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-08 09:59:42,447 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 30 states [2025-02-08 09:59:42,447 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-08 09:59:42,447 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 30 interpolants. [2025-02-08 09:59:42,448 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=140, Invalid=730, Unknown=0, NotChecked=0, Total=870 [2025-02-08 09:59:42,448 INFO L87 Difference]: Start difference. First operand 127 states and 153 transitions. Second operand has 30 states, 30 states have (on average 5.966666666666667) internal successors, (179), 30 states have internal predecessors, (179), 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-02-08 09:59:42,821 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-08 09:59:42,822 INFO L93 Difference]: Finished difference Result 291 states and 376 transitions. [2025-02-08 09:59:42,822 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 31 states. [2025-02-08 09:59:42,822 INFO L78 Accepts]: Start accepts. Automaton has has 30 states, 30 states have (on average 5.966666666666667) internal successors, (179), 30 states have internal predecessors, (179), 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 654 [2025-02-08 09:59:42,822 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-08 09:59:42,823 INFO L225 Difference]: With dead ends: 291 [2025-02-08 09:59:42,823 INFO L226 Difference]: Without dead ends: 169 [2025-02-08 09:59:42,824 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 1359 GetRequests, 1290 SyntacticMatches, 15 SemanticMatches, 54 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 739 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=796, Invalid=2284, Unknown=0, NotChecked=0, Total=3080 [2025-02-08 09:59:42,825 INFO L435 NwaCegarLoop]: 27 mSDtfsCounter, 310 mSDsluCounter, 112 mSDsCounter, 0 mSdLazyCounter, 275 mSolverCounterSat, 127 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 310 SdHoareTripleChecker+Valid, 139 SdHoareTripleChecker+Invalid, 402 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 127 IncrementalHoareTripleChecker+Valid, 275 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-02-08 09:59:42,825 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [310 Valid, 139 Invalid, 402 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [127 Valid, 275 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-02-08 09:59:42,826 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 169 states. [2025-02-08 09:59:42,832 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 169 to 124. [2025-02-08 09:59:42,833 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 124 states, 99 states have (on average 1.0303030303030303) internal successors, (102), 98 states have internal predecessors, (102), 16 states have call successors, (16), 12 states have call predecessors, (16), 8 states have return successors, (35), 13 states have call predecessors, (35), 15 states have call successors, (35) [2025-02-08 09:59:42,833 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 124 states to 124 states and 153 transitions. [2025-02-08 09:59:42,833 INFO L78 Accepts]: Start accepts. Automaton has 124 states and 153 transitions. Word has length 654 [2025-02-08 09:59:42,834 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-08 09:59:42,834 INFO L471 AbstractCegarLoop]: Abstraction has 124 states and 153 transitions. [2025-02-08 09:59:42,834 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 30 states, 30 states have (on average 5.966666666666667) internal successors, (179), 30 states have internal predecessors, (179), 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-02-08 09:59:42,834 INFO L276 IsEmpty]: Start isEmpty. Operand 124 states and 153 transitions. [2025-02-08 09:59:42,835 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 405 [2025-02-08 09:59:42,835 INFO L210 NwaCegarLoop]: Found error trace [2025-02-08 09:59:42,835 INFO L218 NwaCegarLoop]: trace histogram [42, 40, 34, 21, 21, 21, 21, 20, 20, 20, 20, 20, 20, 20, 20, 19, 13, 8, 1, 1, 1, 1] [2025-02-08 09:59:42,842 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Forceful destruction successful, exit code 0 [2025-02-08 09:59:43,040 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable15,14 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-08 09:59:43,040 INFO L396 AbstractCegarLoop]: === Iteration 17 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-02-08 09:59:43,040 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-08 09:59:43,040 INFO L85 PathProgramCache]: Analyzing trace with hash 1664869117, now seen corresponding path program 8 times [2025-02-08 09:59:43,040 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-08 09:59:43,040 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [942047605] [2025-02-08 09:59:43,040 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-02-08 09:59:43,040 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-08 09:59:43,048 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 404 statements into 2 equivalence classes. [2025-02-08 09:59:43,072 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 404 of 404 statements. [2025-02-08 09:59:43,072 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-02-08 09:59:43,072 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 09:59:44,536 INFO L134 CoverageAnalysis]: Checked inductivity of 5803 backedges. 830 proven. 1470 refuted. 0 times theorem prover too weak. 3503 trivial. 0 not checked. [2025-02-08 09:59:44,536 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-08 09:59:44,536 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [942047605] [2025-02-08 09:59:44,536 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [942047605] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-08 09:59:44,536 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1423571634] [2025-02-08 09:59:44,536 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-02-08 09:59:44,536 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-08 09:59:44,536 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-08 09:59:44,538 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-02-08 09:59:44,540 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2025-02-08 09:59:44,611 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 404 statements into 2 equivalence classes. [2025-02-08 09:59:44,669 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 404 of 404 statements. [2025-02-08 09:59:44,669 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-02-08 09:59:44,669 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 09:59:44,675 INFO L256 TraceCheckSpWp]: Trace formula consists of 767 conjuncts, 81 conjuncts are in the unsatisfiable core [2025-02-08 09:59:44,679 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-08 09:59:44,978 INFO L134 CoverageAnalysis]: Checked inductivity of 5803 backedges. 820 proven. 1112 refuted. 0 times theorem prover too weak. 3871 trivial. 0 not checked. [2025-02-08 09:59:44,978 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-08 09:59:50,663 INFO L134 CoverageAnalysis]: Checked inductivity of 5803 backedges. 1149 proven. 1015 refuted. 0 times theorem prover too weak. 3639 trivial. 0 not checked. [2025-02-08 09:59:50,664 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1423571634] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-08 09:59:50,664 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-08 09:59:50,664 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 18, 29] total 45 [2025-02-08 09:59:50,664 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [474583985] [2025-02-08 09:59:50,664 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-08 09:59:50,664 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 46 states [2025-02-08 09:59:50,665 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-08 09:59:50,665 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 46 interpolants. [2025-02-08 09:59:50,665 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=463, Invalid=1607, Unknown=0, NotChecked=0, Total=2070 [2025-02-08 09:59:50,666 INFO L87 Difference]: Start difference. First operand 124 states and 153 transitions. Second operand has 46 states, 45 states have (on average 2.6222222222222222) internal successors, (118), 46 states have internal predecessors, (118), 12 states have call successors, (13), 1 states have call predecessors, (13), 13 states have return successors, (31), 31 states have call predecessors, (31), 12 states have call successors, (31) [2025-02-08 09:59:50,833 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-08 09:59:50,833 INFO L93 Difference]: Finished difference Result 155 states and 207 transitions. [2025-02-08 09:59:50,834 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 26 states. [2025-02-08 09:59:50,834 INFO L78 Accepts]: Start accepts. Automaton has has 46 states, 45 states have (on average 2.6222222222222222) internal successors, (118), 46 states have internal predecessors, (118), 12 states have call successors, (13), 1 states have call predecessors, (13), 13 states have return successors, (31), 31 states have call predecessors, (31), 12 states have call successors, (31) Word has length 404 [2025-02-08 09:59:50,835 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-08 09:59:50,837 INFO L225 Difference]: With dead ends: 155 [2025-02-08 09:59:50,837 INFO L226 Difference]: Without dead ends: 154 [2025-02-08 09:59:50,838 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 891 GetRequests, 792 SyntacticMatches, 51 SemanticMatches, 48 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2454 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=544, Invalid=1906, Unknown=0, NotChecked=0, Total=2450 [2025-02-08 09:59:50,838 INFO L435 NwaCegarLoop]: 19 mSDtfsCounter, 8 mSDsluCounter, 180 mSDsCounter, 0 mSdLazyCounter, 157 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 199 SdHoareTripleChecker+Invalid, 160 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 157 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-02-08 09:59:50,838 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [13 Valid, 199 Invalid, 160 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 157 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-02-08 09:59:50,838 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 154 states. [2025-02-08 09:59:50,846 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 154 to 145. [2025-02-08 09:59:50,846 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 145 states, 116 states have (on average 1.0258620689655173) internal successors, (119), 114 states have internal predecessors, (119), 18 states have call successors, (18), 12 states have call predecessors, (18), 10 states have return successors, (55), 18 states have call predecessors, (55), 17 states have call successors, (55) [2025-02-08 09:59:50,847 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 145 states to 145 states and 192 transitions. [2025-02-08 09:59:50,847 INFO L78 Accepts]: Start accepts. Automaton has 145 states and 192 transitions. Word has length 404 [2025-02-08 09:59:50,849 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-08 09:59:50,849 INFO L471 AbstractCegarLoop]: Abstraction has 145 states and 192 transitions. [2025-02-08 09:59:50,849 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 46 states, 45 states have (on average 2.6222222222222222) internal successors, (118), 46 states have internal predecessors, (118), 12 states have call successors, (13), 1 states have call predecessors, (13), 13 states have return successors, (31), 31 states have call predecessors, (31), 12 states have call successors, (31) [2025-02-08 09:59:50,849 INFO L276 IsEmpty]: Start isEmpty. Operand 145 states and 192 transitions. [2025-02-08 09:59:50,858 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1236 [2025-02-08 09:59:50,858 INFO L210 NwaCegarLoop]: Found error trace [2025-02-08 09:59:50,858 INFO L218 NwaCegarLoop]: trace histogram [128, 123, 104, 65, 65, 65, 65, 62, 62, 62, 62, 62, 61, 61, 61, 60, 39, 24, 1, 1, 1, 1] [2025-02-08 09:59:50,865 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Forceful destruction successful, exit code 0 [2025-02-08 09:59:51,058 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 15 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable16 [2025-02-08 09:59:51,059 INFO L396 AbstractCegarLoop]: === Iteration 18 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-02-08 09:59:51,059 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-08 09:59:51,059 INFO L85 PathProgramCache]: Analyzing trace with hash 1010103062, now seen corresponding path program 9 times [2025-02-08 09:59:51,059 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-08 09:59:51,059 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [7854561] [2025-02-08 09:59:51,059 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-02-08 09:59:51,059 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-08 09:59:51,079 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 1235 statements into 91 equivalence classes. [2025-02-08 09:59:51,187 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 61 check-sat command(s) and asserted 833 of 1235 statements. [2025-02-08 09:59:51,187 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 61 check-sat command(s) [2025-02-08 09:59:51,187 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 10:00:01,003 INFO L134 CoverageAnalysis]: Checked inductivity of 55912 backedges. 16624 proven. 5959 refuted. 0 times theorem prover too weak. 33329 trivial. 0 not checked. [2025-02-08 10:00:01,003 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-08 10:00:01,003 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [7854561] [2025-02-08 10:00:01,003 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [7854561] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-08 10:00:01,003 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [223233477] [2025-02-08 10:00:01,004 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-02-08 10:00:01,004 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-08 10:00:01,004 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-08 10:00:01,005 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-02-08 10:00:01,007 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2025-02-08 10:00:01,170 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 1235 statements into 91 equivalence classes. [2025-02-08 10:00:01,369 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 61 check-sat command(s) and asserted 833 of 1235 statements. [2025-02-08 10:00:01,369 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 61 check-sat command(s) [2025-02-08 10:00:01,370 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 10:00:01,375 INFO L256 TraceCheckSpWp]: Trace formula consists of 1562 conjuncts, 165 conjuncts are in the unsatisfiable core [2025-02-08 10:00:01,385 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-08 10:00:01,958 INFO L134 CoverageAnalysis]: Checked inductivity of 55912 backedges. 16360 proven. 4596 refuted. 0 times theorem prover too weak. 34956 trivial. 0 not checked. [2025-02-08 10:00:01,958 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-08 10:00:21,548 INFO L134 CoverageAnalysis]: Checked inductivity of 55912 backedges. 17227 proven. 4261 refuted. 0 times theorem prover too weak. 34424 trivial. 0 not checked. [2025-02-08 10:00:21,549 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [223233477] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-08 10:00:21,549 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-08 10:00:21,549 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [26, 21, 38] total 54 [2025-02-08 10:00:21,549 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1465915116] [2025-02-08 10:00:21,549 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-08 10:00:21,550 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 55 states [2025-02-08 10:00:21,550 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-08 10:00:21,551 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 55 interpolants. [2025-02-08 10:00:21,551 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=680, Invalid=2290, Unknown=0, NotChecked=0, Total=2970 [2025-02-08 10:00:21,552 INFO L87 Difference]: Start difference. First operand 145 states and 192 transitions. Second operand has 55 states, 54 states have (on average 2.7777777777777777) internal successors, (150), 55 states have internal predecessors, (150), 14 states have call successors, (16), 1 states have call predecessors, (16), 16 states have return successors, (40), 39 states have call predecessors, (40), 14 states have call successors, (40) [2025-02-08 10:00:21,800 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-08 10:00:21,800 INFO L93 Difference]: Finished difference Result 203 states and 303 transitions. [2025-02-08 10:00:21,801 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 35 states. [2025-02-08 10:00:21,801 INFO L78 Accepts]: Start accepts. Automaton has has 55 states, 54 states have (on average 2.7777777777777777) internal successors, (150), 55 states have internal predecessors, (150), 14 states have call successors, (16), 1 states have call predecessors, (16), 16 states have return successors, (40), 39 states have call predecessors, (40), 14 states have call successors, (40) Word has length 1235 [2025-02-08 10:00:21,802 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-08 10:00:21,804 INFO L225 Difference]: With dead ends: 203 [2025-02-08 10:00:21,804 INFO L226 Difference]: Without dead ends: 202 [2025-02-08 10:00:21,805 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 2641 GetRequests, 2461 SyntacticMatches, 119 SemanticMatches, 61 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4966 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=871, Invalid=3035, Unknown=0, NotChecked=0, Total=3906 [2025-02-08 10:00:21,805 INFO L435 NwaCegarLoop]: 19 mSDtfsCounter, 18 mSDsluCounter, 272 mSDsCounter, 0 mSdLazyCounter, 267 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 26 SdHoareTripleChecker+Valid, 291 SdHoareTripleChecker+Invalid, 274 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 267 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-02-08 10:00:21,805 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [26 Valid, 291 Invalid, 274 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 267 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-02-08 10:00:21,806 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 202 states. [2025-02-08 10:00:21,813 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 202 to 163. [2025-02-08 10:00:21,814 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 163 states, 130 states have (on average 1.023076923076923) internal successors, (133), 128 states have internal predecessors, (133), 20 states have call successors, (20), 12 states have call predecessors, (20), 12 states have return successors, (83), 22 states have call predecessors, (83), 19 states have call successors, (83) [2025-02-08 10:00:21,814 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 163 states to 163 states and 236 transitions. [2025-02-08 10:00:21,815 INFO L78 Accepts]: Start accepts. Automaton has 163 states and 236 transitions. Word has length 1235 [2025-02-08 10:00:21,816 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-08 10:00:21,816 INFO L471 AbstractCegarLoop]: Abstraction has 163 states and 236 transitions. [2025-02-08 10:00:21,816 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 55 states, 54 states have (on average 2.7777777777777777) internal successors, (150), 55 states have internal predecessors, (150), 14 states have call successors, (16), 1 states have call predecessors, (16), 16 states have return successors, (40), 39 states have call predecessors, (40), 14 states have call successors, (40) [2025-02-08 10:00:21,816 INFO L276 IsEmpty]: Start isEmpty. Operand 163 states and 236 transitions. [2025-02-08 10:00:21,828 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1805 [2025-02-08 10:00:21,829 INFO L210 NwaCegarLoop]: Found error trace [2025-02-08 10:00:21,829 INFO L218 NwaCegarLoop]: trace histogram [186, 181, 151, 94, 94, 94, 94, 91, 91, 91, 91, 91, 90, 90, 90, 89, 57, 35, 1, 1, 1, 1] [2025-02-08 10:00:21,838 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Ended with exit code 0 [2025-02-08 10:00:22,034 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 16 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable17 [2025-02-08 10:00:22,034 INFO L396 AbstractCegarLoop]: === Iteration 19 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-02-08 10:00:22,035 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-08 10:00:22,035 INFO L85 PathProgramCache]: Analyzing trace with hash -1889270359, now seen corresponding path program 10 times [2025-02-08 10:00:22,035 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-08 10:00:22,035 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1896793741] [2025-02-08 10:00:22,035 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-02-08 10:00:22,035 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-08 10:00:22,062 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 1804 statements into 2 equivalence classes. [2025-02-08 10:00:22,118 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) and asserted 1071 of 1804 statements. [2025-02-08 10:00:22,118 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) [2025-02-08 10:00:22,119 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 10:00:23,383 INFO L134 CoverageAnalysis]: Checked inductivity of 119823 backedges. 2320 proven. 13820 refuted. 0 times theorem prover too weak. 103683 trivial. 0 not checked. [2025-02-08 10:00:23,384 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-08 10:00:23,384 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1896793741] [2025-02-08 10:00:23,384 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1896793741] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-08 10:00:23,384 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1292838808] [2025-02-08 10:00:23,384 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-02-08 10:00:23,384 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-08 10:00:23,384 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-08 10:00:23,388 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-02-08 10:00:23,392 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2025-02-08 10:00:23,743 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 1804 statements into 2 equivalence classes. [2025-02-08 10:00:23,890 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) and asserted 1071 of 1804 statements. [2025-02-08 10:00:23,890 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) [2025-02-08 10:00:23,890 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 10:00:23,895 INFO L256 TraceCheckSpWp]: Trace formula consists of 2239 conjuncts, 30 conjuncts are in the unsatisfiable core [2025-02-08 10:00:23,908 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-08 10:00:24,116 INFO L134 CoverageAnalysis]: Checked inductivity of 119823 backedges. 62322 proven. 5516 refuted. 0 times theorem prover too weak. 51985 trivial. 0 not checked. [2025-02-08 10:00:24,117 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-08 10:00:27,378 INFO L134 CoverageAnalysis]: Checked inductivity of 119823 backedges. 2796 proven. 16335 refuted. 0 times theorem prover too weak. 100692 trivial. 0 not checked. [2025-02-08 10:00:27,378 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1292838808] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-08 10:00:27,378 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-08 10:00:27,379 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 19, 28] total 33 [2025-02-08 10:00:27,379 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [711586028] [2025-02-08 10:00:27,379 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-08 10:00:27,380 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 33 states [2025-02-08 10:00:27,380 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-08 10:00:27,381 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 33 interpolants. [2025-02-08 10:00:27,381 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=163, Invalid=893, Unknown=0, NotChecked=0, Total=1056 [2025-02-08 10:00:27,381 INFO L87 Difference]: Start difference. First operand 163 states and 236 transitions. Second operand has 33 states, 33 states have (on average 5.9393939393939394) internal successors, (196), 33 states have internal predecessors, (196), 28 states have call successors, (35), 5 states have call predecessors, (35), 13 states have return successors, (40), 15 states have call predecessors, (40), 25 states have call successors, (40) [2025-02-08 10:00:27,900 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-08 10:00:27,900 INFO L93 Difference]: Finished difference Result 403 states and 672 transitions. [2025-02-08 10:00:27,901 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 36 states. [2025-02-08 10:00:27,901 INFO L78 Accepts]: Start accepts. Automaton has has 33 states, 33 states have (on average 5.9393939393939394) internal successors, (196), 33 states have internal predecessors, (196), 28 states have call successors, (35), 5 states have call predecessors, (35), 13 states have return successors, (40), 15 states have call predecessors, (40), 25 states have call successors, (40) Word has length 1804 [2025-02-08 10:00:27,902 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-08 10:00:27,903 INFO L225 Difference]: With dead ends: 403 [2025-02-08 10:00:27,904 INFO L226 Difference]: Without dead ends: 245 [2025-02-08 10:00:27,906 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 3669 GetRequests, 3589 SyntacticMatches, 18 SemanticMatches, 62 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1015 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=1036, Invalid=2996, Unknown=0, NotChecked=0, Total=4032 [2025-02-08 10:00:27,906 INFO L435 NwaCegarLoop]: 28 mSDtfsCounter, 397 mSDsluCounter, 140 mSDsCounter, 0 mSdLazyCounter, 332 mSolverCounterSat, 161 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 397 SdHoareTripleChecker+Valid, 168 SdHoareTripleChecker+Invalid, 493 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 161 IncrementalHoareTripleChecker+Valid, 332 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-02-08 10:00:27,907 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [397 Valid, 168 Invalid, 493 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [161 Valid, 332 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-02-08 10:00:27,907 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 245 states. [2025-02-08 10:00:27,919 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 245 to 220. [2025-02-08 10:00:27,919 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 220 states, 177 states have (on average 1.0282485875706215) internal successors, (182), 173 states have internal predecessors, (182), 27 states have call successors, (27), 17 states have call predecessors, (27), 15 states have return successors, (108), 29 states have call predecessors, (108), 26 states have call successors, (108) [2025-02-08 10:00:27,922 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 220 states to 220 states and 317 transitions. [2025-02-08 10:00:27,923 INFO L78 Accepts]: Start accepts. Automaton has 220 states and 317 transitions. Word has length 1804 [2025-02-08 10:00:27,924 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-08 10:00:27,924 INFO L471 AbstractCegarLoop]: Abstraction has 220 states and 317 transitions. [2025-02-08 10:00:27,925 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 33 states, 33 states have (on average 5.9393939393939394) internal successors, (196), 33 states have internal predecessors, (196), 28 states have call successors, (35), 5 states have call predecessors, (35), 13 states have return successors, (40), 15 states have call predecessors, (40), 25 states have call successors, (40) [2025-02-08 10:00:27,925 INFO L276 IsEmpty]: Start isEmpty. Operand 220 states and 317 transitions. [2025-02-08 10:00:27,948 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 2460 [2025-02-08 10:00:27,948 INFO L210 NwaCegarLoop]: Found error trace [2025-02-08 10:00:27,949 INFO L218 NwaCegarLoop]: trace histogram [252, 249, 204, 126, 126, 126, 126, 125, 125, 125, 125, 125, 124, 124, 124, 123, 78, 48, 1, 1, 1, 1] [2025-02-08 10:00:27,958 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Forceful destruction successful, exit code 0 [2025-02-08 10:00:28,152 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable18,17 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-08 10:00:28,153 INFO L396 AbstractCegarLoop]: === Iteration 20 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-02-08 10:00:28,153 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-08 10:00:28,154 INFO L85 PathProgramCache]: Analyzing trace with hash 264278418, now seen corresponding path program 11 times [2025-02-08 10:00:28,154 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-08 10:00:28,154 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [775987633] [2025-02-08 10:00:28,154 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2025-02-08 10:00:28,154 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-08 10:00:28,188 INFO L108 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 partitioned 2459 statements into 190 equivalence classes. [2025-02-08 10:00:28,299 INFO L111 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 93 check-sat command(s) and asserted 1186 of 2459 statements. [2025-02-08 10:00:28,299 INFO L114 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 93 check-sat command(s) [2025-02-08 10:00:28,299 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 10:00:29,711 INFO L134 CoverageAnalysis]: Checked inductivity of 223213 backedges. 12107 proven. 14177 refuted. 0 times theorem prover too weak. 196929 trivial. 0 not checked. [2025-02-08 10:00:29,711 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-08 10:00:29,711 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [775987633] [2025-02-08 10:00:29,711 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [775987633] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-08 10:00:29,711 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1570453196] [2025-02-08 10:00:29,711 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2025-02-08 10:00:29,711 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-08 10:00:29,712 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-08 10:00:29,714 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-02-08 10:00:29,714 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Waiting until timeout for monitored process [2025-02-08 10:00:30,105 INFO L108 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 partitioned 2459 statements into 190 equivalence classes. [2025-02-08 10:00:30,438 INFO L111 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 93 check-sat command(s) and asserted 1186 of 2459 statements. [2025-02-08 10:00:30,438 INFO L114 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 93 check-sat command(s) [2025-02-08 10:00:30,438 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 10:00:30,444 INFO L256 TraceCheckSpWp]: Trace formula consists of 2194 conjuncts, 26 conjuncts are in the unsatisfiable core [2025-02-08 10:00:30,468 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-08 10:00:30,755 INFO L134 CoverageAnalysis]: Checked inductivity of 223213 backedges. 120380 proven. 2667 refuted. 0 times theorem prover too weak. 100166 trivial. 0 not checked. [2025-02-08 10:00:30,755 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-08 10:00:36,111 INFO L134 CoverageAnalysis]: Checked inductivity of 223213 backedges. 12107 proven. 14270 refuted. 0 times theorem prover too weak. 196836 trivial. 0 not checked. [2025-02-08 10:00:36,112 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1570453196] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-08 10:00:36,112 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-08 10:00:36,112 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 17, 27] total 31 [2025-02-08 10:00:36,112 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1624893964] [2025-02-08 10:00:36,112 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-08 10:00:36,114 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 31 states [2025-02-08 10:00:36,114 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-08 10:00:36,115 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 31 interpolants. [2025-02-08 10:00:36,115 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=186, Invalid=744, Unknown=0, NotChecked=0, Total=930 [2025-02-08 10:00:36,116 INFO L87 Difference]: Start difference. First operand 220 states and 317 transitions. Second operand has 31 states, 31 states have (on average 5.870967741935484) internal successors, (182), 31 states have internal predecessors, (182), 27 states have call successors, (31), 2 states have call predecessors, (31), 14 states have return successors, (40), 14 states have call predecessors, (40), 27 states have call successors, (40) [2025-02-08 10:00:36,419 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-08 10:00:36,419 INFO L93 Difference]: Finished difference Result 417 states and 638 transitions. [2025-02-08 10:00:36,420 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2025-02-08 10:00:36,420 INFO L78 Accepts]: Start accepts. Automaton has has 31 states, 31 states have (on average 5.870967741935484) internal successors, (182), 31 states have internal predecessors, (182), 27 states have call successors, (31), 2 states have call predecessors, (31), 14 states have return successors, (40), 14 states have call predecessors, (40), 27 states have call successors, (40) Word has length 2459 [2025-02-08 10:00:36,420 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-08 10:00:36,422 INFO L225 Difference]: With dead ends: 417 [2025-02-08 10:00:36,422 INFO L226 Difference]: Without dead ends: 202 [2025-02-08 10:00:36,423 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 4961 GetRequests, 4903 SyntacticMatches, 13 SemanticMatches, 45 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 622 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=560, Invalid=1602, Unknown=0, NotChecked=0, Total=2162 [2025-02-08 10:00:36,424 INFO L435 NwaCegarLoop]: 55 mSDtfsCounter, 102 mSDsluCounter, 221 mSDsCounter, 0 mSdLazyCounter, 658 mSolverCounterSat, 48 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 103 SdHoareTripleChecker+Valid, 276 SdHoareTripleChecker+Invalid, 706 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 48 IncrementalHoareTripleChecker+Valid, 658 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-02-08 10:00:36,424 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [103 Valid, 276 Invalid, 706 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [48 Valid, 658 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-02-08 10:00:36,424 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 202 states. [2025-02-08 10:00:36,431 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 202 to 166. [2025-02-08 10:00:36,431 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 166 states, 133 states have (on average 1.0225563909774436) internal successors, (136), 131 states have internal predecessors, (136), 21 states have call successors, (21), 14 states have call predecessors, (21), 11 states have return successors, (67), 20 states have call predecessors, (67), 20 states have call successors, (67) [2025-02-08 10:00:36,432 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 166 states to 166 states and 224 transitions. [2025-02-08 10:00:36,432 INFO L78 Accepts]: Start accepts. Automaton has 166 states and 224 transitions. Word has length 2459 [2025-02-08 10:00:36,433 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-08 10:00:36,433 INFO L471 AbstractCegarLoop]: Abstraction has 166 states and 224 transitions. [2025-02-08 10:00:36,433 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 31 states, 31 states have (on average 5.870967741935484) internal successors, (182), 31 states have internal predecessors, (182), 27 states have call successors, (31), 2 states have call predecessors, (31), 14 states have return successors, (40), 14 states have call predecessors, (40), 27 states have call successors, (40) [2025-02-08 10:00:36,433 INFO L276 IsEmpty]: Start isEmpty. Operand 166 states and 224 transitions. [2025-02-08 10:00:36,447 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1983 [2025-02-08 10:00:36,448 INFO L210 NwaCegarLoop]: Found error trace [2025-02-08 10:00:36,448 INFO L218 NwaCegarLoop]: trace histogram [203, 201, 164, 101, 101, 101, 101, 101, 101, 101, 101, 101, 100, 100, 100, 99, 63, 39, 1, 1, 1, 1] [2025-02-08 10:00:36,458 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Ended with exit code 0 [2025-02-08 10:00:36,652 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable19,18 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-08 10:00:36,652 INFO L396 AbstractCegarLoop]: === Iteration 21 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-02-08 10:00:36,653 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-08 10:00:36,653 INFO L85 PathProgramCache]: Analyzing trace with hash 225193944, now seen corresponding path program 12 times [2025-02-08 10:00:36,653 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-08 10:00:36,653 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1496626084] [2025-02-08 10:00:36,653 INFO L95 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2025-02-08 10:00:36,653 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-08 10:00:36,681 INFO L108 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE partitioned 1982 statements into 157 equivalence classes. [2025-02-08 10:00:36,841 INFO L111 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 96 check-sat command(s) and asserted 1278 of 1982 statements. [2025-02-08 10:00:36,842 INFO L114 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 96 check-sat command(s) [2025-02-08 10:00:36,842 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 10:00:39,142 INFO L134 CoverageAnalysis]: Checked inductivity of 144772 backedges. 6334 proven. 16825 refuted. 0 times theorem prover too weak. 121613 trivial. 0 not checked. [2025-02-08 10:00:39,142 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-08 10:00:39,142 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1496626084] [2025-02-08 10:00:39,142 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1496626084] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-08 10:00:39,142 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [998621660] [2025-02-08 10:00:39,142 INFO L95 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2025-02-08 10:00:39,142 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-08 10:00:39,142 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-08 10:00:39,144 INFO L229 MonitoredProcess]: Starting monitored process 19 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-02-08 10:00:39,145 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Waiting until timeout for monitored process [2025-02-08 10:00:39,556 INFO L108 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE partitioned 1982 statements into 157 equivalence classes. [2025-02-08 10:00:39,945 INFO L111 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 96 check-sat command(s) and asserted 1278 of 1982 statements. [2025-02-08 10:00:39,946 INFO L114 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 96 check-sat command(s) [2025-02-08 10:00:39,946 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 10:00:39,952 INFO L256 TraceCheckSpWp]: Trace formula consists of 2376 conjuncts, 32 conjuncts are in the unsatisfiable core [2025-02-08 10:00:39,963 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-08 10:00:40,181 INFO L134 CoverageAnalysis]: Checked inductivity of 144772 backedges. 70758 proven. 9071 refuted. 0 times theorem prover too weak. 64943 trivial. 0 not checked. [2025-02-08 10:00:40,181 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-08 10:00:44,218 INFO L134 CoverageAnalysis]: Checked inductivity of 144772 backedges. 6643 proven. 17634 refuted. 0 times theorem prover too weak. 120495 trivial. 0 not checked. [2025-02-08 10:00:44,218 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [998621660] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-08 10:00:44,218 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-08 10:00:44,218 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 20, 32] total 37 [2025-02-08 10:00:44,218 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1898281684] [2025-02-08 10:00:44,219 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-08 10:00:44,220 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 37 states [2025-02-08 10:00:44,220 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-08 10:00:44,221 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 37 interpolants. [2025-02-08 10:00:44,221 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=214, Invalid=1118, Unknown=0, NotChecked=0, Total=1332 [2025-02-08 10:00:44,221 INFO L87 Difference]: Start difference. First operand 166 states and 224 transitions. Second operand has 37 states, 37 states have (on average 6.027027027027027) internal successors, (223), 37 states have internal predecessors, (223), 32 states have call successors, (39), 3 states have call predecessors, (39), 16 states have return successors, (48), 18 states have call predecessors, (48), 31 states have call successors, (48) [2025-02-08 10:00:45,067 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-08 10:00:45,067 INFO L93 Difference]: Finished difference Result 439 states and 619 transitions. [2025-02-08 10:00:45,067 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 48 states. [2025-02-08 10:00:45,067 INFO L78 Accepts]: Start accepts. Automaton has has 37 states, 37 states have (on average 6.027027027027027) internal successors, (223), 37 states have internal predecessors, (223), 32 states have call successors, (39), 3 states have call predecessors, (39), 16 states have return successors, (48), 18 states have call predecessors, (48), 31 states have call successors, (48) Word has length 1982 [2025-02-08 10:00:45,068 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-08 10:00:45,070 INFO L225 Difference]: With dead ends: 439 [2025-02-08 10:00:45,070 INFO L226 Difference]: Without dead ends: 278 [2025-02-08 10:00:45,076 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 4039 GetRequests, 3947 SyntacticMatches, 17 SemanticMatches, 75 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1523 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=1427, Invalid=4425, Unknown=0, NotChecked=0, Total=5852 [2025-02-08 10:00:45,077 INFO L435 NwaCegarLoop]: 53 mSDtfsCounter, 406 mSDsluCounter, 182 mSDsCounter, 0 mSdLazyCounter, 665 mSolverCounterSat, 181 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 406 SdHoareTripleChecker+Valid, 235 SdHoareTripleChecker+Invalid, 846 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 181 IncrementalHoareTripleChecker+Valid, 665 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2025-02-08 10:00:45,077 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [406 Valid, 235 Invalid, 846 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [181 Valid, 665 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2025-02-08 10:00:45,077 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 278 states. [2025-02-08 10:00:45,145 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 278 to 199. [2025-02-08 10:00:45,145 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 199 states, 161 states have (on average 1.0248447204968945) internal successors, (165), 158 states have internal predecessors, (165), 26 states have call successors, (26), 20 states have call predecessors, (26), 11 states have return successors, (74), 20 states have call predecessors, (74), 25 states have call successors, (74) [2025-02-08 10:00:45,148 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 199 states to 199 states and 265 transitions. [2025-02-08 10:00:45,148 INFO L78 Accepts]: Start accepts. Automaton has 199 states and 265 transitions. Word has length 1982 [2025-02-08 10:00:45,148 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-08 10:00:45,148 INFO L471 AbstractCegarLoop]: Abstraction has 199 states and 265 transitions. [2025-02-08 10:00:45,149 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 37 states, 37 states have (on average 6.027027027027027) internal successors, (223), 37 states have internal predecessors, (223), 32 states have call successors, (39), 3 states have call predecessors, (39), 16 states have return successors, (48), 18 states have call predecessors, (48), 31 states have call successors, (48) [2025-02-08 10:00:45,149 INFO L276 IsEmpty]: Start isEmpty. Operand 199 states and 265 transitions. [2025-02-08 10:00:45,167 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 2238 [2025-02-08 10:00:45,167 INFO L210 NwaCegarLoop]: Found error trace [2025-02-08 10:00:45,168 INFO L218 NwaCegarLoop]: trace histogram [229, 227, 185, 114, 114, 114, 114, 114, 114, 114, 114, 114, 113, 113, 113, 112, 71, 44, 1, 1, 1, 1] [2025-02-08 10:00:45,178 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Ended with exit code 0 [2025-02-08 10:00:45,371 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable20,19 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-08 10:00:45,372 INFO L396 AbstractCegarLoop]: === Iteration 22 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-02-08 10:00:45,372 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-08 10:00:45,372 INFO L85 PathProgramCache]: Analyzing trace with hash -116038505, now seen corresponding path program 13 times [2025-02-08 10:00:45,372 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-08 10:00:45,372 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1388778368] [2025-02-08 10:00:45,372 INFO L95 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2025-02-08 10:00:45,373 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-08 10:00:45,403 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 2237 statements into 1 equivalence classes. [2025-02-08 10:00:45,512 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 2237 of 2237 statements. [2025-02-08 10:00:45,513 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 10:00:45,513 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 10:00:49,717 INFO L134 CoverageAnalysis]: Checked inductivity of 184605 backedges. 4912 proven. 20084 refuted. 0 times theorem prover too weak. 159609 trivial. 0 not checked. [2025-02-08 10:00:49,717 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-08 10:00:49,717 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1388778368] [2025-02-08 10:00:49,717 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1388778368] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-08 10:00:49,718 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1869651235] [2025-02-08 10:00:49,718 INFO L95 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2025-02-08 10:00:49,718 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-08 10:00:49,718 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-08 10:00:49,720 INFO L229 MonitoredProcess]: Starting monitored process 20 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-02-08 10:00:49,721 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Waiting until timeout for monitored process [2025-02-08 10:00:50,161 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 2237 statements into 1 equivalence classes. [2025-02-08 10:00:50,434 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 2237 of 2237 statements. [2025-02-08 10:00:50,435 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 10:00:50,435 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 10:00:50,445 INFO L256 TraceCheckSpWp]: Trace formula consists of 4154 conjuncts, 30 conjuncts are in the unsatisfiable core [2025-02-08 10:00:50,457 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-08 10:00:50,645 INFO L134 CoverageAnalysis]: Checked inductivity of 184605 backedges. 93352 proven. 5527 refuted. 0 times theorem prover too weak. 85726 trivial. 0 not checked. [2025-02-08 10:00:50,645 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-08 10:00:55,971 INFO L134 CoverageAnalysis]: Checked inductivity of 184605 backedges. 5350 proven. 22375 refuted. 0 times theorem prover too weak. 156880 trivial. 0 not checked. [2025-02-08 10:00:55,971 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1869651235] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-08 10:00:55,971 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-08 10:00:55,972 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 19, 31] total 36 [2025-02-08 10:00:55,972 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [696005411] [2025-02-08 10:00:55,972 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-08 10:00:55,973 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 36 states [2025-02-08 10:00:55,974 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-08 10:00:55,974 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 36 interpolants. [2025-02-08 10:00:55,974 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=219, Invalid=1041, Unknown=0, NotChecked=0, Total=1260 [2025-02-08 10:00:55,975 INFO L87 Difference]: Start difference. First operand 199 states and 265 transitions. Second operand has 36 states, 36 states have (on average 5.805555555555555) internal successors, (209), 36 states have internal predecessors, (209), 30 states have call successors, (37), 2 states have call predecessors, (37), 16 states have return successors, (49), 17 states have call predecessors, (49), 30 states have call successors, (49) [2025-02-08 10:00:56,447 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-08 10:00:56,448 INFO L93 Difference]: Finished difference Result 417 states and 568 transitions. [2025-02-08 10:00:56,448 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 31 states. [2025-02-08 10:00:56,448 INFO L78 Accepts]: Start accepts. Automaton has has 36 states, 36 states have (on average 5.805555555555555) internal successors, (209), 36 states have internal predecessors, (209), 30 states have call successors, (37), 2 states have call predecessors, (37), 16 states have return successors, (49), 17 states have call predecessors, (49), 30 states have call successors, (49) Word has length 2237 [2025-02-08 10:00:56,449 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-08 10:00:56,450 INFO L225 Difference]: With dead ends: 417 [2025-02-08 10:00:56,451 INFO L226 Difference]: Without dead ends: 223 [2025-02-08 10:00:56,452 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 4523 GetRequests, 4453 SyntacticMatches, 15 SemanticMatches, 55 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 962 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=805, Invalid=2387, Unknown=0, NotChecked=0, Total=3192 [2025-02-08 10:00:56,453 INFO L435 NwaCegarLoop]: 62 mSDtfsCounter, 242 mSDsluCounter, 203 mSDsCounter, 0 mSdLazyCounter, 657 mSolverCounterSat, 134 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 242 SdHoareTripleChecker+Valid, 265 SdHoareTripleChecker+Invalid, 791 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 134 IncrementalHoareTripleChecker+Valid, 657 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2025-02-08 10:00:56,453 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [242 Valid, 265 Invalid, 791 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [134 Valid, 657 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2025-02-08 10:00:56,453 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 223 states. [2025-02-08 10:00:56,462 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 223 to 202. [2025-02-08 10:00:56,462 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 202 states, 164 states have (on average 1.024390243902439) internal successors, (168), 161 states have internal predecessors, (168), 27 states have call successors, (27), 22 states have call predecessors, (27), 10 states have return successors, (61), 18 states have call predecessors, (61), 26 states have call successors, (61) [2025-02-08 10:00:56,463 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 202 states to 202 states and 256 transitions. [2025-02-08 10:00:56,463 INFO L78 Accepts]: Start accepts. Automaton has 202 states and 256 transitions. Word has length 2237 [2025-02-08 10:00:56,464 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-08 10:00:56,464 INFO L471 AbstractCegarLoop]: Abstraction has 202 states and 256 transitions. [2025-02-08 10:00:56,464 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 36 states, 36 states have (on average 5.805555555555555) internal successors, (209), 36 states have internal predecessors, (209), 30 states have call successors, (37), 2 states have call predecessors, (37), 16 states have return successors, (49), 17 states have call predecessors, (49), 30 states have call successors, (49) [2025-02-08 10:00:56,464 INFO L276 IsEmpty]: Start isEmpty. Operand 202 states and 256 transitions. [2025-02-08 10:00:56,476 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1733 [2025-02-08 10:00:56,476 INFO L210 NwaCegarLoop]: Found error trace [2025-02-08 10:00:56,477 INFO L218 NwaCegarLoop]: trace histogram [177, 176, 143, 88, 88, 88, 88, 88, 88, 88, 88, 88, 88, 88, 88, 87, 55, 34, 1, 1, 1, 1] [2025-02-08 10:00:56,489 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Ended with exit code 0 [2025-02-08 10:00:56,681 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable21,20 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-08 10:00:56,681 INFO L396 AbstractCegarLoop]: === Iteration 23 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-02-08 10:00:56,682 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-08 10:00:56,682 INFO L85 PathProgramCache]: Analyzing trace with hash 1195642616, now seen corresponding path program 14 times [2025-02-08 10:00:56,682 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-08 10:00:56,682 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1104863687] [2025-02-08 10:00:56,682 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-02-08 10:00:56,682 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-08 10:00:56,713 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 1732 statements into 2 equivalence classes. [2025-02-08 10:00:56,829 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 1732 of 1732 statements. [2025-02-08 10:00:56,829 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-02-08 10:00:56,829 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat