./Ultimate.py --spec ../sv-benchmarks/c/properties/no-overflow.prp --file ../sv-benchmarks/c/recursive/Fibonacci01-1.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/Fibonacci01-1.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 6b0570f2e0d80d68bc280040cce27f654b3fe7a2c0bad30f9bb811af9ca3d994 --- Real Ultimate output --- This is Ultimate 0.3.0-?-48c9605-m [2025-02-08 09:58:15,931 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-02-08 09:58:15,986 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:58:15,989 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-02-08 09:58:15,989 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-02-08 09:58:16,007 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-02-08 09:58:16,008 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-02-08 09:58:16,008 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-02-08 09:58:16,008 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-02-08 09:58:16,008 INFO L153 SettingsManager]: * Use memory slicer=true [2025-02-08 09:58:16,009 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2025-02-08 09:58:16,009 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2025-02-08 09:58:16,009 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-02-08 09:58:16,009 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-02-08 09:58:16,010 INFO L153 SettingsManager]: * Use SBE=true [2025-02-08 09:58:16,010 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-02-08 09:58:16,010 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2025-02-08 09:58:16,010 INFO L153 SettingsManager]: * sizeof long=4 [2025-02-08 09:58:16,010 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2025-02-08 09:58:16,010 INFO L153 SettingsManager]: * sizeof POINTER=4 [2025-02-08 09:58:16,010 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-02-08 09:58:16,010 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2025-02-08 09:58:16,010 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2025-02-08 09:58:16,010 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2025-02-08 09:58:16,011 INFO L153 SettingsManager]: * Check absence of signed integer overflows=ASSERTandASSUME [2025-02-08 09:58:16,011 INFO L153 SettingsManager]: * Check unreachability of reach_error function=false [2025-02-08 09:58:16,011 INFO L153 SettingsManager]: * sizeof long double=12 [2025-02-08 09:58:16,011 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-02-08 09:58:16,011 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-02-08 09:58:16,011 INFO L153 SettingsManager]: * Use constant arrays=true [2025-02-08 09:58:16,011 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-02-08 09:58:16,011 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-02-08 09:58:16,011 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-02-08 09:58:16,011 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-02-08 09:58:16,012 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-02-08 09:58:16,012 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-02-08 09:58:16,012 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2025-02-08 09:58:16,012 INFO L153 SettingsManager]: * Compute procedure contracts=false [2025-02-08 09:58:16,012 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2025-02-08 09:58:16,012 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2025-02-08 09:58:16,012 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2025-02-08 09:58:16,012 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2025-02-08 09:58:16,012 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2025-02-08 09:58:16,012 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2025-02-08 09:58:16,013 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2025-02-08 09:58:16,013 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 -> 6b0570f2e0d80d68bc280040cce27f654b3fe7a2c0bad30f9bb811af9ca3d994 [2025-02-08 09:58:16,217 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-02-08 09:58:16,225 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-02-08 09:58:16,227 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-02-08 09:58:16,228 INFO L270 PluginConnector]: Initializing CDTParser... [2025-02-08 09:58:16,228 INFO L274 PluginConnector]: CDTParser initialized [2025-02-08 09:58:16,228 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/recursive/Fibonacci01-1.c [2025-02-08 09:58:17,371 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/5997cdbbe/fe1a7216c26d482280bd9a06a839a78d/FLAGae077c265 [2025-02-08 09:58:17,585 INFO L384 CDTParser]: Found 1 translation units. [2025-02-08 09:58:17,586 INFO L180 CDTParser]: Scanning /storage/repos/ultimate-jdk21/releaseScripts/default/sv-benchmarks/c/recursive/Fibonacci01-1.c [2025-02-08 09:58:17,591 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/5997cdbbe/fe1a7216c26d482280bd9a06a839a78d/FLAGae077c265 [2025-02-08 09:58:17,937 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/5997cdbbe/fe1a7216c26d482280bd9a06a839a78d [2025-02-08 09:58:17,939 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-02-08 09:58:17,940 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-02-08 09:58:17,941 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-02-08 09:58:17,942 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-02-08 09:58:17,946 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-02-08 09:58:17,946 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 08.02 09:58:17" (1/1) ... [2025-02-08 09:58:17,947 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@2d433643 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.02 09:58:17, skipping insertion in model container [2025-02-08 09:58:17,947 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 08.02 09:58:17" (1/1) ... [2025-02-08 09:58:17,958 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-02-08 09:58:18,047 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-02-08 09:58:18,053 INFO L200 MainTranslator]: Completed pre-run [2025-02-08 09:58:18,061 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-02-08 09:58:18,072 INFO L204 MainTranslator]: Completed translation [2025-02-08 09:58:18,073 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.02 09:58:18 WrapperNode [2025-02-08 09:58:18,073 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-02-08 09:58:18,073 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-02-08 09:58:18,073 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-02-08 09:58:18,074 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-02-08 09:58:18,077 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:58:18" (1/1) ... [2025-02-08 09:58:18,082 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:58:18" (1/1) ... [2025-02-08 09:58:18,093 INFO L138 Inliner]: procedures = 13, calls = 11, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 29 [2025-02-08 09:58:18,093 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-02-08 09:58:18,093 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-02-08 09:58:18,093 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-02-08 09:58:18,093 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-02-08 09:58:18,101 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.02 09:58:18" (1/1) ... [2025-02-08 09:58:18,101 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.02 09:58:18" (1/1) ... [2025-02-08 09:58:18,106 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.02 09:58:18" (1/1) ... [2025-02-08 09:58:18,114 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:58:18,115 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.02 09:58:18" (1/1) ... [2025-02-08 09:58:18,115 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.02 09:58:18" (1/1) ... [2025-02-08 09:58:18,120 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.02 09:58:18" (1/1) ... [2025-02-08 09:58:18,120 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.02 09:58:18" (1/1) ... [2025-02-08 09:58:18,121 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.02 09:58:18" (1/1) ... [2025-02-08 09:58:18,122 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.02 09:58:18" (1/1) ... [2025-02-08 09:58:18,123 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-02-08 09:58:18,123 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2025-02-08 09:58:18,127 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2025-02-08 09:58:18,127 INFO L274 PluginConnector]: IcfgBuilder initialized [2025-02-08 09:58:18,128 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.02 09:58:18" (1/1) ... [2025-02-08 09:58:18,132 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-02-08 09:58:18,139 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-08 09:58:18,153 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:58:18,155 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:58:18,175 INFO L130 BoogieDeclarations]: Found specification of procedure fibonacci [2025-02-08 09:58:18,175 INFO L138 BoogieDeclarations]: Found implementation of procedure fibonacci [2025-02-08 09:58:18,176 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2025-02-08 09:58:18,176 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-02-08 09:58:18,176 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-02-08 09:58:18,176 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2025-02-08 09:58:18,211 INFO L257 CfgBuilder]: Building ICFG [2025-02-08 09:58:18,213 INFO L287 CfgBuilder]: Building CFG for each procedure with an implementation [2025-02-08 09:58:18,304 INFO L1324 $ProcedureCfgBuilder]: dead code at ProgramPoint L22: havoc #t~ret4;havoc #t~ret5; [2025-02-08 09:58:18,351 INFO L? ?]: Removed 17 outVars from TransFormulas that were not future-live. [2025-02-08 09:58:18,352 INFO L308 CfgBuilder]: Performing block encoding [2025-02-08 09:58:18,360 INFO L332 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-02-08 09:58:18,360 INFO L337 CfgBuilder]: Removed 0 assume(true) statements. [2025-02-08 09:58:18,360 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 08.02 09:58:18 BoogieIcfgContainer [2025-02-08 09:58:18,360 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2025-02-08 09:58:18,365 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2025-02-08 09:58:18,365 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2025-02-08 09:58:18,368 INFO L274 PluginConnector]: TraceAbstraction initialized [2025-02-08 09:58:18,368 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 08.02 09:58:17" (1/3) ... [2025-02-08 09:58:18,369 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@30f5acbe and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 08.02 09:58:18, skipping insertion in model container [2025-02-08 09:58:18,369 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.02 09:58:18" (2/3) ... [2025-02-08 09:58:18,369 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@30f5acbe and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 08.02 09:58:18, skipping insertion in model container [2025-02-08 09:58:18,369 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 08.02 09:58:18" (3/3) ... [2025-02-08 09:58:18,370 INFO L128 eAbstractionObserver]: Analyzing ICFG Fibonacci01-1.c [2025-02-08 09:58:18,379 INFO L216 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2025-02-08 09:58:18,380 INFO L151 ceAbstractionStarter]: Applying trace abstraction to ICFG Fibonacci01-1.c that has 2 procedures, 33 locations, 1 initial locations, 0 loop locations, and 8 error locations. [2025-02-08 09:58:18,410 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2025-02-08 09:58:18,422 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;@7ac5c123, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2025-02-08 09:58:18,424 INFO L334 AbstractCegarLoop]: Starting to check reachability of 8 error locations. [2025-02-08 09:58:18,428 INFO L276 IsEmpty]: Start isEmpty. Operand has 33 states, 19 states have (on average 1.631578947368421) internal successors, (31), 28 states have internal predecessors, (31), 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:58:18,432 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 8 [2025-02-08 09:58:18,433 INFO L210 NwaCegarLoop]: Found error trace [2025-02-08 09:58:18,434 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2025-02-08 09:58:18,434 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting fibonacciErr5ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 5 more)] === [2025-02-08 09:58:18,437 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-08 09:58:18,438 INFO L85 PathProgramCache]: Analyzing trace with hash 1291714441, now seen corresponding path program 1 times [2025-02-08 09:58:18,442 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-08 09:58:18,442 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1667853105] [2025-02-08 09:58:18,443 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-08 09:58:18,443 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-08 09:58:18,482 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 7 statements into 1 equivalence classes. [2025-02-08 09:58:18,496 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 7 of 7 statements. [2025-02-08 09:58:18,496 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 09:58:18,496 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 09:58:18,555 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:58:18,555 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-08 09:58:18,555 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1667853105] [2025-02-08 09:58:18,556 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1667853105] provided 1 perfect and 0 imperfect interpolant sequences [2025-02-08 09:58:18,556 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-02-08 09:58:18,556 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2025-02-08 09:58:18,557 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1504977542] [2025-02-08 09:58:18,557 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-02-08 09:58:18,559 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2025-02-08 09:58:18,560 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-08 09:58:18,572 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2025-02-08 09:58:18,572 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2025-02-08 09:58:18,574 INFO L87 Difference]: Start difference. First operand has 33 states, 19 states have (on average 1.631578947368421) internal successors, (31), 28 states have internal predecessors, (31), 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:58:18,611 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-08 09:58:18,611 INFO L93 Difference]: Finished difference Result 35 states and 41 transitions. [2025-02-08 09:58:18,612 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2025-02-08 09:58:18,613 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:58:18,613 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-08 09:58:18,617 INFO L225 Difference]: With dead ends: 35 [2025-02-08 09:58:18,617 INFO L226 Difference]: Without dead ends: 29 [2025-02-08 09:58:18,618 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:58:18,620 INFO L435 NwaCegarLoop]: 29 mSDtfsCounter, 11 mSDsluCounter, 15 mSDsCounter, 0 mSdLazyCounter, 13 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 44 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:58:18,620 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [13 Valid, 44 Invalid, 14 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 13 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-02-08 09:58:18,628 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 29 states. [2025-02-08 09:58:18,642 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 29 to 27. [2025-02-08 09:58:18,642 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 27 states, 17 states have (on average 1.411764705882353) internal successors, (24), 22 states have internal predecessors, (24), 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:58:18,646 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 27 states to 27 states and 30 transitions. [2025-02-08 09:58:18,647 INFO L78 Accepts]: Start accepts. Automaton has 27 states and 30 transitions. Word has length 7 [2025-02-08 09:58:18,647 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-08 09:58:18,648 INFO L471 AbstractCegarLoop]: Abstraction has 27 states and 30 transitions. [2025-02-08 09:58:18,649 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:58:18,649 INFO L276 IsEmpty]: Start isEmpty. Operand 27 states and 30 transitions. [2025-02-08 09:58:18,649 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 9 [2025-02-08 09:58:18,649 INFO L210 NwaCegarLoop]: Found error trace [2025-02-08 09:58:18,649 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2025-02-08 09:58:18,650 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2025-02-08 09:58:18,650 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting fibonacciErr4ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 5 more)] === [2025-02-08 09:58:18,650 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-08 09:58:18,650 INFO L85 PathProgramCache]: Analyzing trace with hash 1388441992, now seen corresponding path program 1 times [2025-02-08 09:58:18,651 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-08 09:58:18,651 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1982882925] [2025-02-08 09:58:18,651 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-08 09:58:18,651 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-08 09:58:18,657 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 8 statements into 1 equivalence classes. [2025-02-08 09:58:18,664 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 8 of 8 statements. [2025-02-08 09:58:18,667 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 09:58:18,667 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 09:58:18,728 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:58:18,728 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-08 09:58:18,728 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1982882925] [2025-02-08 09:58:18,728 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1982882925] provided 1 perfect and 0 imperfect interpolant sequences [2025-02-08 09:58:18,728 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-02-08 09:58:18,728 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2025-02-08 09:58:18,729 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1678120637] [2025-02-08 09:58:18,729 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-02-08 09:58:18,729 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-02-08 09:58:18,729 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-08 09:58:18,730 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-02-08 09:58:18,730 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-02-08 09:58:18,730 INFO L87 Difference]: Start difference. First operand 27 states and 30 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:58:18,794 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-08 09:58:18,795 INFO L93 Difference]: Finished difference Result 29 states and 34 transitions. [2025-02-08 09:58:18,795 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-02-08 09:58:18,795 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:58:18,795 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-08 09:58:18,796 INFO L225 Difference]: With dead ends: 29 [2025-02-08 09:58:18,796 INFO L226 Difference]: Without dead ends: 25 [2025-02-08 09:58:18,796 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:58:18,798 INFO L435 NwaCegarLoop]: 14 mSDtfsCounter, 28 mSDsluCounter, 17 mSDsCounter, 0 mSdLazyCounter, 46 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 29 SdHoareTripleChecker+Valid, 31 SdHoareTripleChecker+Invalid, 54 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 46 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-02-08 09:58:18,798 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [29 Valid, 31 Invalid, 54 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 46 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-02-08 09:58:18,799 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 25 states. [2025-02-08 09:58:18,803 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 25 to 23. [2025-02-08 09:58:18,803 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 23 states, 16 states have (on average 1.25) 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, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2025-02-08 09:58:18,805 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 23 states to 23 states and 26 transitions. [2025-02-08 09:58:18,805 INFO L78 Accepts]: Start accepts. Automaton has 23 states and 26 transitions. Word has length 8 [2025-02-08 09:58:18,805 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-08 09:58:18,805 INFO L471 AbstractCegarLoop]: Abstraction has 23 states and 26 transitions. [2025-02-08 09:58:18,806 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:58:18,806 INFO L276 IsEmpty]: Start isEmpty. Operand 23 states and 26 transitions. [2025-02-08 09:58:18,806 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 10 [2025-02-08 09:58:18,806 INFO L210 NwaCegarLoop]: Found error trace [2025-02-08 09:58:18,806 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-02-08 09:58:18,806 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2025-02-08 09:58:18,806 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting ULTIMATE.startErr1ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 5 more)] === [2025-02-08 09:58:18,806 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-08 09:58:18,807 INFO L85 PathProgramCache]: Analyzing trace with hash 73674219, now seen corresponding path program 1 times [2025-02-08 09:58:18,807 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-08 09:58:18,807 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1211826317] [2025-02-08 09:58:18,807 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-08 09:58:18,807 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-08 09:58:18,812 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 9 statements into 1 equivalence classes. [2025-02-08 09:58:18,818 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 9 of 9 statements. [2025-02-08 09:58:18,821 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 09:58:18,821 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 09:58:18,862 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:58:18,862 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-08 09:58:18,862 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1211826317] [2025-02-08 09:58:18,862 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1211826317] provided 1 perfect and 0 imperfect interpolant sequences [2025-02-08 09:58:18,862 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-02-08 09:58:18,863 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2025-02-08 09:58:18,863 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [463144710] [2025-02-08 09:58:18,863 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-02-08 09:58:18,863 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2025-02-08 09:58:18,863 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-08 09:58:18,864 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2025-02-08 09:58:18,864 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2025-02-08 09:58:18,864 INFO L87 Difference]: Start difference. First operand 23 states and 26 transitions. Second operand has 4 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), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2025-02-08 09:58:18,869 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-08 09:58:18,870 INFO L93 Difference]: Finished difference Result 23 states and 26 transitions. [2025-02-08 09:58:18,870 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2025-02-08 09:58:18,870 INFO L78 Accepts]: Start accepts. Automaton has has 4 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), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 9 [2025-02-08 09:58:18,870 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-08 09:58:18,870 INFO L225 Difference]: With dead ends: 23 [2025-02-08 09:58:18,871 INFO L226 Difference]: Without dead ends: 20 [2025-02-08 09:58:18,871 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2025-02-08 09:58:18,871 INFO L435 NwaCegarLoop]: 24 mSDtfsCounter, 0 mSDsluCounter, 21 mSDsCounter, 0 mSdLazyCounter, 2 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 45 SdHoareTripleChecker+Invalid, 2 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 2 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-02-08 09:58:18,872 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 45 Invalid, 2 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 2 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-02-08 09:58:18,872 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 20 states. [2025-02-08 09:58:18,874 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 20 to 20. [2025-02-08 09:58:18,874 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:58:18,874 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 20 states to 20 states and 23 transitions. [2025-02-08 09:58:18,875 INFO L78 Accepts]: Start accepts. Automaton has 20 states and 23 transitions. Word has length 9 [2025-02-08 09:58:18,875 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-08 09:58:18,875 INFO L471 AbstractCegarLoop]: Abstraction has 20 states and 23 transitions. [2025-02-08 09:58:18,875 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 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), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2025-02-08 09:58:18,875 INFO L276 IsEmpty]: Start isEmpty. Operand 20 states and 23 transitions. [2025-02-08 09:58:18,875 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2025-02-08 09:58:18,875 INFO L210 NwaCegarLoop]: Found error trace [2025-02-08 09:58:18,876 INFO L218 NwaCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-02-08 09:58:18,876 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2025-02-08 09:58:18,876 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 5 more)] === [2025-02-08 09:58:18,876 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-08 09:58:18,876 INFO L85 PathProgramCache]: Analyzing trace with hash -1684897159, now seen corresponding path program 1 times [2025-02-08 09:58:18,876 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-08 09:58:18,876 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [803335762] [2025-02-08 09:58:18,876 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-08 09:58:18,877 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-08 09:58:18,880 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 23 statements into 1 equivalence classes. [2025-02-08 09:58:18,885 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 23 of 23 statements. [2025-02-08 09:58:18,887 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 09:58:18,887 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 09:58:18,975 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2025-02-08 09:58:18,975 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-08 09:58:18,975 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [803335762] [2025-02-08 09:58:18,975 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [803335762] provided 1 perfect and 0 imperfect interpolant sequences [2025-02-08 09:58:18,975 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-02-08 09:58:18,976 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2025-02-08 09:58:18,976 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2064953271] [2025-02-08 09:58:18,976 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-02-08 09:58:18,976 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-02-08 09:58:18,976 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-08 09:58:18,977 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-02-08 09:58:18,977 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2025-02-08 09:58:18,978 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:58:19,012 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-08 09:58:19,012 INFO L93 Difference]: Finished difference Result 34 states and 42 transitions. [2025-02-08 09:58:19,012 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-02-08 09:58:19,013 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 23 [2025-02-08 09:58:19,013 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-08 09:58:19,013 INFO L225 Difference]: With dead ends: 34 [2025-02-08 09:58:19,013 INFO L226 Difference]: Without dead ends: 32 [2025-02-08 09:58:19,013 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:58:19,014 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:58:19,014 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:58:19,014 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 32 states. [2025-02-08 09:58:19,019 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 32 to 29. [2025-02-08 09:58:19,019 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:58:19,019 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 29 states to 29 states and 35 transitions. [2025-02-08 09:58:19,020 INFO L78 Accepts]: Start accepts. Automaton has 29 states and 35 transitions. Word has length 23 [2025-02-08 09:58:19,020 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-08 09:58:19,020 INFO L471 AbstractCegarLoop]: Abstraction has 29 states and 35 transitions. [2025-02-08 09:58:19,020 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:58:19,020 INFO L276 IsEmpty]: Start isEmpty. Operand 29 states and 35 transitions. [2025-02-08 09:58:19,021 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2025-02-08 09:58:19,021 INFO L210 NwaCegarLoop]: Found error trace [2025-02-08 09:58:19,021 INFO L218 NwaCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-02-08 09:58:19,021 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2025-02-08 09:58:19,021 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 5 more)] === [2025-02-08 09:58:19,021 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-08 09:58:19,021 INFO L85 PathProgramCache]: Analyzing trace with hash -139519786, now seen corresponding path program 1 times [2025-02-08 09:58:19,022 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-08 09:58:19,022 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [939701194] [2025-02-08 09:58:19,022 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-08 09:58:19,022 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-08 09:58:19,026 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 24 statements into 1 equivalence classes. [2025-02-08 09:58:19,030 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 24 of 24 statements. [2025-02-08 09:58:19,030 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 09:58:19,030 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 09:58:19,112 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2025-02-08 09:58:19,112 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-08 09:58:19,112 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [939701194] [2025-02-08 09:58:19,112 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [939701194] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-08 09:58:19,112 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [189316043] [2025-02-08 09:58:19,112 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-08 09:58:19,112 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-08 09:58:19,112 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-08 09:58:19,115 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:58:19,116 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:58:19,142 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 24 statements into 1 equivalence classes. [2025-02-08 09:58:19,153 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 24 of 24 statements. [2025-02-08 09:58:19,153 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 09:58:19,153 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 09:58:19,154 INFO L256 TraceCheckSpWp]: Trace formula consists of 68 conjuncts, 6 conjuncts are in the unsatisfiable core [2025-02-08 09:58:19,157 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-08 09:58:19,221 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 3 proven. 3 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2025-02-08 09:58:19,221 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-08 09:58:19,359 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 3 proven. 3 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2025-02-08 09:58:19,359 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [189316043] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-08 09:58:19,359 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-08 09:58:19,359 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 7, 7] total 15 [2025-02-08 09:58:19,359 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [195711273] [2025-02-08 09:58:19,359 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-08 09:58:19,359 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2025-02-08 09:58:19,360 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-08 09:58:19,360 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2025-02-08 09:58:19,360 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=35, Invalid=175, Unknown=0, NotChecked=0, Total=210 [2025-02-08 09:58:19,360 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:58:19,583 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-08 09:58:19,583 INFO L93 Difference]: Finished difference Result 90 states and 128 transitions. [2025-02-08 09:58:19,584 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2025-02-08 09:58:19,584 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 24 [2025-02-08 09:58:19,584 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-08 09:58:19,585 INFO L225 Difference]: With dead ends: 90 [2025-02-08 09:58:19,585 INFO L226 Difference]: Without dead ends: 64 [2025-02-08 09:58:19,586 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 60 GetRequests, 38 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:58:19,586 INFO L435 NwaCegarLoop]: 12 mSDtfsCounter, 155 mSDsluCounter, 70 mSDsCounter, 0 mSdLazyCounter, 171 mSolverCounterSat, 69 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 155 SdHoareTripleChecker+Valid, 82 SdHoareTripleChecker+Invalid, 240 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 69 IncrementalHoareTripleChecker+Valid, 171 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-02-08 09:58:19,587 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [155 Valid, 82 Invalid, 240 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [69 Valid, 171 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-02-08 09:58:19,587 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 64 states. [2025-02-08 09:58:19,594 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 64 to 52. [2025-02-08 09:58:19,594 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:58:19,595 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 52 states to 52 states and 67 transitions. [2025-02-08 09:58:19,596 INFO L78 Accepts]: Start accepts. Automaton has 52 states and 67 transitions. Word has length 24 [2025-02-08 09:58:19,596 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-08 09:58:19,596 INFO L471 AbstractCegarLoop]: Abstraction has 52 states and 67 transitions. [2025-02-08 09:58:19,596 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:58:19,596 INFO L276 IsEmpty]: Start isEmpty. Operand 52 states and 67 transitions. [2025-02-08 09:58:19,597 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2025-02-08 09:58:19,597 INFO L210 NwaCegarLoop]: Found error trace [2025-02-08 09:58:19,597 INFO L218 NwaCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-02-08 09:58:19,603 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2025-02-08 09:58:19,798 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,2 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-08 09:58:19,798 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 5 more)] === [2025-02-08 09:58:19,799 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-08 09:58:19,799 INFO L85 PathProgramCache]: Analyzing trace with hash -287699220, now seen corresponding path program 2 times [2025-02-08 09:58:19,799 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-08 09:58:19,799 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [583120205] [2025-02-08 09:58:19,799 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-02-08 09:58:19,800 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-08 09:58:19,805 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 24 statements into 2 equivalence classes. [2025-02-08 09:58:19,809 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 24 of 24 statements. [2025-02-08 09:58:19,809 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-02-08 09:58:19,809 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 09:58:19,866 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2025-02-08 09:58:19,866 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-08 09:58:19,866 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [583120205] [2025-02-08 09:58:19,866 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [583120205] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-08 09:58:19,866 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1272105367] [2025-02-08 09:58:19,866 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-02-08 09:58:19,866 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-08 09:58:19,866 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-08 09:58:19,869 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:58:19,870 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:58:19,891 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 24 statements into 2 equivalence classes. [2025-02-08 09:58:19,900 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 24 of 24 statements. [2025-02-08 09:58:19,900 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-02-08 09:58:19,900 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 09:58:19,901 INFO L256 TraceCheckSpWp]: Trace formula consists of 68 conjuncts, 4 conjuncts are in the unsatisfiable core [2025-02-08 09:58:19,902 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-08 09:58:19,946 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2025-02-08 09:58:19,946 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-02-08 09:58:19,946 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1272105367] provided 1 perfect and 0 imperfect interpolant sequences [2025-02-08 09:58:19,946 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-02-08 09:58:19,946 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [5] total 7 [2025-02-08 09:58:19,946 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [565666189] [2025-02-08 09:58:19,946 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-02-08 09:58:19,946 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-02-08 09:58:19,946 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-08 09:58:19,947 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-02-08 09:58:19,947 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=38, Unknown=0, NotChecked=0, Total=56 [2025-02-08 09:58:19,947 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:58:19,971 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-08 09:58:19,972 INFO L93 Difference]: Finished difference Result 59 states and 75 transitions. [2025-02-08 09:58:19,972 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-02-08 09:58:19,972 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 24 [2025-02-08 09:58:19,972 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-08 09:58:19,973 INFO L225 Difference]: With dead ends: 59 [2025-02-08 09:58:19,973 INFO L226 Difference]: Without dead ends: 58 [2025-02-08 09:58:19,973 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 28 GetRequests, 21 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:58:19,975 INFO L435 NwaCegarLoop]: 17 mSDtfsCounter, 3 mSDsluCounter, 44 mSDsCounter, 0 mSdLazyCounter, 23 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 61 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:58:19,975 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 61 Invalid, 25 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 23 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-02-08 09:58:19,976 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 58 states. [2025-02-08 09:58:19,984 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 58 to 54. [2025-02-08 09:58:19,984 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:58:19,988 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 69 transitions. [2025-02-08 09:58:19,988 INFO L78 Accepts]: Start accepts. Automaton has 54 states and 69 transitions. Word has length 24 [2025-02-08 09:58:19,988 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-08 09:58:19,988 INFO L471 AbstractCegarLoop]: Abstraction has 54 states and 69 transitions. [2025-02-08 09:58:19,988 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:58:19,988 INFO L276 IsEmpty]: Start isEmpty. Operand 54 states and 69 transitions. [2025-02-08 09:58:19,989 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2025-02-08 09:58:19,989 INFO L210 NwaCegarLoop]: Found error trace [2025-02-08 09:58:19,989 INFO L218 NwaCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-02-08 09:58:19,996 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2025-02-08 09:58:20,189 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,3 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-08 09:58:20,190 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 5 more)] === [2025-02-08 09:58:20,190 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-08 09:58:20,190 INFO L85 PathProgramCache]: Analyzing trace with hash -328741255, now seen corresponding path program 1 times [2025-02-08 09:58:20,190 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-08 09:58:20,190 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [374068140] [2025-02-08 09:58:20,190 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-08 09:58:20,190 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-08 09:58:20,193 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 25 statements into 1 equivalence classes. [2025-02-08 09:58:20,196 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 25 of 25 statements. [2025-02-08 09:58:20,196 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 09:58:20,196 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 09:58:20,255 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2025-02-08 09:58:20,256 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-08 09:58:20,256 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [374068140] [2025-02-08 09:58:20,256 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [374068140] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-08 09:58:20,256 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [169758003] [2025-02-08 09:58:20,256 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-08 09:58:20,256 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-08 09:58:20,256 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-08 09:58:20,258 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:58:20,259 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:58:20,276 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 25 statements into 1 equivalence classes. [2025-02-08 09:58:20,283 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 25 of 25 statements. [2025-02-08 09:58:20,283 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 09:58:20,283 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 09:58:20,284 INFO L256 TraceCheckSpWp]: Trace formula consists of 69 conjuncts, 5 conjuncts are in the unsatisfiable core [2025-02-08 09:58:20,284 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-08 09:58:20,323 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2025-02-08 09:58:20,324 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-02-08 09:58:20,324 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [169758003] provided 1 perfect and 0 imperfect interpolant sequences [2025-02-08 09:58:20,324 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-02-08 09:58:20,324 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [5] total 9 [2025-02-08 09:58:20,324 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [644430466] [2025-02-08 09:58:20,324 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-02-08 09:58:20,324 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2025-02-08 09:58:20,325 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-08 09:58:20,325 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2025-02-08 09:58:20,325 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=64, Unknown=0, NotChecked=0, Total=90 [2025-02-08 09:58:20,325 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:58:20,349 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-08 09:58:20,349 INFO L93 Difference]: Finished difference Result 81 states and 116 transitions. [2025-02-08 09:58:20,350 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2025-02-08 09:58:20,350 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 25 [2025-02-08 09:58:20,350 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-08 09:58:20,351 INFO L225 Difference]: With dead ends: 81 [2025-02-08 09:58:20,351 INFO L226 Difference]: Without dead ends: 80 [2025-02-08 09:58:20,351 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 29 GetRequests, 21 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:58:20,352 INFO L435 NwaCegarLoop]: 17 mSDtfsCounter, 2 mSDsluCounter, 36 mSDsCounter, 0 mSdLazyCounter, 24 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 53 SdHoareTripleChecker+Invalid, 25 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 24 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-02-08 09:58:20,352 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 53 Invalid, 25 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 24 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-02-08 09:58:20,353 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 80 states. [2025-02-08 09:58:20,365 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 80 to 63. [2025-02-08 09:58:20,366 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:58:20,367 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 63 states to 63 states and 86 transitions. [2025-02-08 09:58:20,367 INFO L78 Accepts]: Start accepts. Automaton has 63 states and 86 transitions. Word has length 25 [2025-02-08 09:58:20,367 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-08 09:58:20,367 INFO L471 AbstractCegarLoop]: Abstraction has 63 states and 86 transitions. [2025-02-08 09:58:20,369 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:58:20,370 INFO L276 IsEmpty]: Start isEmpty. Operand 63 states and 86 transitions. [2025-02-08 09:58:20,370 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 46 [2025-02-08 09:58:20,370 INFO L210 NwaCegarLoop]: Found error trace [2025-02-08 09:58:20,370 INFO L218 NwaCegarLoop]: trace histogram [5, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1] [2025-02-08 09:58:20,377 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:58:20,571 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,4 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-08 09:58:20,571 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 5 more)] === [2025-02-08 09:58:20,571 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-08 09:58:20,572 INFO L85 PathProgramCache]: Analyzing trace with hash 1695472561, now seen corresponding path program 1 times [2025-02-08 09:58:20,572 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-08 09:58:20,572 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [533484123] [2025-02-08 09:58:20,572 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-08 09:58:20,572 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-08 09:58:20,576 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 45 statements into 1 equivalence classes. [2025-02-08 09:58:20,580 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 45 of 45 statements. [2025-02-08 09:58:20,580 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 09:58:20,580 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 09:58:20,705 INFO L134 CoverageAnalysis]: Checked inductivity of 48 backedges. 2 proven. 15 refuted. 0 times theorem prover too weak. 31 trivial. 0 not checked. [2025-02-08 09:58:20,705 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-08 09:58:20,705 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [533484123] [2025-02-08 09:58:20,705 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [533484123] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-08 09:58:20,705 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [55486804] [2025-02-08 09:58:20,705 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-08 09:58:20,705 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-08 09:58:20,705 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-08 09:58:20,708 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:58:20,709 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:58:20,730 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 45 statements into 1 equivalence classes. [2025-02-08 09:58:20,741 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 45 of 45 statements. [2025-02-08 09:58:20,741 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 09:58:20,741 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 09:58:20,742 INFO L256 TraceCheckSpWp]: Trace formula consists of 106 conjuncts, 9 conjuncts are in the unsatisfiable core [2025-02-08 09:58:20,743 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-08 09:58:20,817 INFO L134 CoverageAnalysis]: Checked inductivity of 48 backedges. 2 proven. 7 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2025-02-08 09:58:20,817 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-08 09:58:20,972 INFO L134 CoverageAnalysis]: Checked inductivity of 48 backedges. 6 proven. 7 refuted. 0 times theorem prover too weak. 35 trivial. 0 not checked. [2025-02-08 09:58:20,972 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [55486804] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-08 09:58:20,972 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-08 09:58:20,972 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 6, 7] total 15 [2025-02-08 09:58:20,972 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1901196637] [2025-02-08 09:58:20,972 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-08 09:58:20,972 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2025-02-08 09:58:20,972 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-08 09:58:20,973 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2025-02-08 09:58:20,973 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=62, Invalid=178, Unknown=0, NotChecked=0, Total=240 [2025-02-08 09:58:20,973 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:58:21,140 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-08 09:58:21,141 INFO L93 Difference]: Finished difference Result 140 states and 216 transitions. [2025-02-08 09:58:21,141 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2025-02-08 09:58:21,141 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 45 [2025-02-08 09:58:21,141 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-08 09:58:21,143 INFO L225 Difference]: With dead ends: 140 [2025-02-08 09:58:21,143 INFO L226 Difference]: Without dead ends: 138 [2025-02-08 09:58:21,146 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 103 GetRequests, 81 SyntacticMatches, 2 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 111 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=126, Invalid=336, Unknown=0, NotChecked=0, Total=462 [2025-02-08 09:58:21,146 INFO L435 NwaCegarLoop]: 24 mSDtfsCounter, 16 mSDsluCounter, 147 mSDsCounter, 0 mSdLazyCounter, 156 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 23 SdHoareTripleChecker+Valid, 171 SdHoareTripleChecker+Invalid, 162 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 156 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-02-08 09:58:21,147 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [23 Valid, 171 Invalid, 162 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 156 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-02-08 09:58:21,148 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 138 states. [2025-02-08 09:58:21,164 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 138 to 97. [2025-02-08 09:58:21,164 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:58:21,165 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 97 states to 97 states and 158 transitions. [2025-02-08 09:58:21,167 INFO L78 Accepts]: Start accepts. Automaton has 97 states and 158 transitions. Word has length 45 [2025-02-08 09:58:21,167 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-08 09:58:21,167 INFO L471 AbstractCegarLoop]: Abstraction has 97 states and 158 transitions. [2025-02-08 09:58:21,167 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:58:21,167 INFO L276 IsEmpty]: Start isEmpty. Operand 97 states and 158 transitions. [2025-02-08 09:58:21,169 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 63 [2025-02-08 09:58:21,169 INFO L210 NwaCegarLoop]: Found error trace [2025-02-08 09:58:21,169 INFO L218 NwaCegarLoop]: trace histogram [7, 6, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1] [2025-02-08 09:58:21,175 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:58:21,370 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,SelfDestructingSolverStorable7 [2025-02-08 09:58:21,371 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 5 more)] === [2025-02-08 09:58:21,371 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-08 09:58:21,371 INFO L85 PathProgramCache]: Analyzing trace with hash -1534593880, now seen corresponding path program 1 times [2025-02-08 09:58:21,371 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-08 09:58:21,371 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2146447632] [2025-02-08 09:58:21,371 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-08 09:58:21,371 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-08 09:58:21,375 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 62 statements into 1 equivalence classes. [2025-02-08 09:58:21,381 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 62 of 62 statements. [2025-02-08 09:58:21,382 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 09:58:21,382 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 09:58:21,516 INFO L134 CoverageAnalysis]: Checked inductivity of 106 backedges. 25 proven. 46 refuted. 0 times theorem prover too weak. 35 trivial. 0 not checked. [2025-02-08 09:58:21,517 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-08 09:58:21,517 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2146447632] [2025-02-08 09:58:21,517 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2146447632] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-08 09:58:21,517 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1042854640] [2025-02-08 09:58:21,517 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-08 09:58:21,517 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-08 09:58:21,517 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-08 09:58:21,519 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:58:21,521 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:58:21,543 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 62 statements into 1 equivalence classes. [2025-02-08 09:58:21,557 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 62 of 62 statements. [2025-02-08 09:58:21,557 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 09:58:21,557 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 09:58:21,558 INFO L256 TraceCheckSpWp]: Trace formula consists of 138 conjuncts, 8 conjuncts are in the unsatisfiable core [2025-02-08 09:58:21,559 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-08 09:58:21,628 INFO L134 CoverageAnalysis]: Checked inductivity of 106 backedges. 4 proven. 33 refuted. 0 times theorem prover too weak. 69 trivial. 0 not checked. [2025-02-08 09:58:21,628 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-08 09:58:21,779 INFO L134 CoverageAnalysis]: Checked inductivity of 106 backedges. 2 proven. 31 refuted. 0 times theorem prover too weak. 73 trivial. 0 not checked. [2025-02-08 09:58:21,779 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1042854640] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-08 09:58:21,780 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-08 09:58:21,780 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 6, 5] total 18 [2025-02-08 09:58:21,780 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1059206909] [2025-02-08 09:58:21,780 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-08 09:58:21,780 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2025-02-08 09:58:21,780 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-08 09:58:21,781 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2025-02-08 09:58:21,781 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=49, Invalid=257, Unknown=0, NotChecked=0, Total=306 [2025-02-08 09:58:21,781 INFO L87 Difference]: Start difference. First operand 97 states and 158 transitions. Second operand has 18 states, 18 states have (on average 3.7222222222222223) internal successors, (67), 18 states have internal predecessors, (67), 7 states have call successors, (10), 1 states have call predecessors, (10), 6 states have return successors, (14), 10 states have call predecessors, (14), 7 states have call successors, (14) [2025-02-08 09:58:22,268 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-08 09:58:22,268 INFO L93 Difference]: Finished difference Result 256 states and 503 transitions. [2025-02-08 09:58:22,270 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 29 states. [2025-02-08 09:58:22,270 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 18 states have (on average 3.7222222222222223) internal successors, (67), 18 states have internal predecessors, (67), 7 states have call successors, (10), 1 states have call predecessors, (10), 6 states have return successors, (14), 10 states have call predecessors, (14), 7 states have call successors, (14) Word has length 62 [2025-02-08 09:58:22,271 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-08 09:58:22,273 INFO L225 Difference]: With dead ends: 256 [2025-02-08 09:58:22,273 INFO L226 Difference]: Without dead ends: 162 [2025-02-08 09:58:22,281 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 161 GetRequests, 116 SyntacticMatches, 3 SemanticMatches, 42 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 412 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=419, Invalid=1473, Unknown=0, NotChecked=0, Total=1892 [2025-02-08 09:58:22,285 INFO L435 NwaCegarLoop]: 11 mSDtfsCounter, 81 mSDsluCounter, 67 mSDsCounter, 0 mSdLazyCounter, 309 mSolverCounterSat, 38 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 81 SdHoareTripleChecker+Valid, 78 SdHoareTripleChecker+Invalid, 347 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 38 IncrementalHoareTripleChecker+Valid, 309 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-02-08 09:58:22,285 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [81 Valid, 78 Invalid, 347 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [38 Valid, 309 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-02-08 09:58:22,286 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 162 states. [2025-02-08 09:58:22,311 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 162 to 102. [2025-02-08 09:58:22,312 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 102 states, 79 states have (on average 1.0506329113924051) internal successors, (83), 79 states have internal predecessors, (83), 12 states have call successors, (12), 3 states have call predecessors, (12), 10 states have return successors, (75), 19 states have call predecessors, (75), 11 states have call successors, (75) [2025-02-08 09:58:22,314 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 102 states to 102 states and 170 transitions. [2025-02-08 09:58:22,315 INFO L78 Accepts]: Start accepts. Automaton has 102 states and 170 transitions. Word has length 62 [2025-02-08 09:58:22,315 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-08 09:58:22,316 INFO L471 AbstractCegarLoop]: Abstraction has 102 states and 170 transitions. [2025-02-08 09:58:22,316 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 18 states, 18 states have (on average 3.7222222222222223) internal successors, (67), 18 states have internal predecessors, (67), 7 states have call successors, (10), 1 states have call predecessors, (10), 6 states have return successors, (14), 10 states have call predecessors, (14), 7 states have call successors, (14) [2025-02-08 09:58:22,318 INFO L276 IsEmpty]: Start isEmpty. Operand 102 states and 170 transitions. [2025-02-08 09:58:22,323 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 176 [2025-02-08 09:58:22,323 INFO L210 NwaCegarLoop]: Found error trace [2025-02-08 09:58:22,324 INFO L218 NwaCegarLoop]: trace histogram [19, 17, 13, 9, 9, 9, 9, 9, 9, 9, 9, 9, 8, 8, 8, 7, 6, 4, 1, 1, 1, 1] [2025-02-08 09:58:22,330 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2025-02-08 09:58:22,528 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,6 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-08 09:58:22,528 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 5 more)] === [2025-02-08 09:58:22,528 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-08 09:58:22,529 INFO L85 PathProgramCache]: Analyzing trace with hash 1698568181, now seen corresponding path program 2 times [2025-02-08 09:58:22,529 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-08 09:58:22,529 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2115905364] [2025-02-08 09:58:22,529 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-02-08 09:58:22,529 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-08 09:58:22,537 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 175 statements into 2 equivalence classes. [2025-02-08 09:58:22,562 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 175 of 175 statements. [2025-02-08 09:58:22,562 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-02-08 09:58:22,563 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 09:58:22,697 INFO L134 CoverageAnalysis]: Checked inductivity of 1028 backedges. 100 proven. 278 refuted. 0 times theorem prover too weak. 650 trivial. 0 not checked. [2025-02-08 09:58:22,697 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-08 09:58:22,697 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2115905364] [2025-02-08 09:58:22,697 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2115905364] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-08 09:58:22,697 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1137978593] [2025-02-08 09:58:22,697 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-02-08 09:58:22,697 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-08 09:58:22,697 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-08 09:58:22,700 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:58:22,702 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:58:22,730 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 175 statements into 2 equivalence classes. [2025-02-08 09:58:22,761 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 175 of 175 statements. [2025-02-08 09:58:22,761 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-02-08 09:58:22,761 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 09:58:22,762 INFO L256 TraceCheckSpWp]: Trace formula consists of 346 conjuncts, 8 conjuncts are in the unsatisfiable core [2025-02-08 09:58:22,765 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-08 09:58:22,813 INFO L134 CoverageAnalysis]: Checked inductivity of 1028 backedges. 450 proven. 15 refuted. 0 times theorem prover too weak. 563 trivial. 0 not checked. [2025-02-08 09:58:22,813 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-08 09:58:23,099 INFO L134 CoverageAnalysis]: Checked inductivity of 1028 backedges. 101 proven. 328 refuted. 0 times theorem prover too weak. 599 trivial. 0 not checked. [2025-02-08 09:58:23,099 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1137978593] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-08 09:58:23,099 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-08 09:58:23,099 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 8, 9] total 14 [2025-02-08 09:58:23,099 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1837143797] [2025-02-08 09:58:23,099 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-08 09:58:23,100 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2025-02-08 09:58:23,100 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-08 09:58:23,100 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2025-02-08 09:58:23,101 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=47, Invalid=135, Unknown=0, NotChecked=0, Total=182 [2025-02-08 09:58:23,101 INFO L87 Difference]: Start difference. First operand 102 states and 170 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:58:23,170 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-08 09:58:23,171 INFO L93 Difference]: Finished difference Result 154 states and 260 transitions. [2025-02-08 09:58:23,171 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2025-02-08 09:58:23,171 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 175 [2025-02-08 09:58:23,171 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-08 09:58:23,172 INFO L225 Difference]: With dead ends: 154 [2025-02-08 09:58:23,172 INFO L226 Difference]: Without dead ends: 55 [2025-02-08 09:58:23,173 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 362 GetRequests, 342 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:58:23,173 INFO L435 NwaCegarLoop]: 20 mSDtfsCounter, 35 mSDsluCounter, 34 mSDsCounter, 0 mSdLazyCounter, 82 mSolverCounterSat, 16 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 35 SdHoareTripleChecker+Valid, 54 SdHoareTripleChecker+Invalid, 98 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 16 IncrementalHoareTripleChecker+Valid, 82 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-02-08 09:58:23,173 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [35 Valid, 54 Invalid, 98 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [16 Valid, 82 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-02-08 09:58:23,174 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 55 states. [2025-02-08 09:58:23,177 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 55 to 55. [2025-02-08 09:58:23,177 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:58:23,177 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 55 states to 55 states and 66 transitions. [2025-02-08 09:58:23,177 INFO L78 Accepts]: Start accepts. Automaton has 55 states and 66 transitions. Word has length 175 [2025-02-08 09:58:23,178 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-08 09:58:23,178 INFO L471 AbstractCegarLoop]: Abstraction has 55 states and 66 transitions. [2025-02-08 09:58:23,178 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:58:23,178 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 66 transitions. [2025-02-08 09:58:23,179 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 131 [2025-02-08 09:58:23,179 INFO L210 NwaCegarLoop]: Found error trace [2025-02-08 09:58:23,179 INFO L218 NwaCegarLoop]: trace histogram [14, 12, 12, 7, 7, 7, 7, 6, 6, 6, 6, 6, 6, 6, 6, 5, 5, 2, 1, 1, 1, 1] [2025-02-08 09:58:23,185 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2025-02-08 09:58:23,383 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,SelfDestructingSolverStorable9 [2025-02-08 09:58:23,383 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 5 more)] === [2025-02-08 09:58:23,383 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-08 09:58:23,383 INFO L85 PathProgramCache]: Analyzing trace with hash -1422165687, now seen corresponding path program 3 times [2025-02-08 09:58:23,383 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-08 09:58:23,383 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1802137951] [2025-02-08 09:58:23,383 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-02-08 09:58:23,383 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-08 09:58:23,388 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 130 statements into 12 equivalence classes. [2025-02-08 09:58:23,395 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) and asserted 70 of 130 statements. [2025-02-08 09:58:23,395 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2025-02-08 09:58:23,395 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 09:58:23,454 INFO L134 CoverageAnalysis]: Checked inductivity of 548 backedges. 210 proven. 18 refuted. 0 times theorem prover too weak. 320 trivial. 0 not checked. [2025-02-08 09:58:23,454 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-08 09:58:23,454 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1802137951] [2025-02-08 09:58:23,454 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1802137951] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-08 09:58:23,454 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1232759038] [2025-02-08 09:58:23,454 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-02-08 09:58:23,455 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-08 09:58:23,455 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-08 09:58:23,456 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:58:23,458 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:58:23,482 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 130 statements into 12 equivalence classes. [2025-02-08 09:58:23,496 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) and asserted 70 of 130 statements. [2025-02-08 09:58:23,496 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2025-02-08 09:58:23,496 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 09:58:23,497 INFO L256 TraceCheckSpWp]: Trace formula consists of 152 conjuncts, 8 conjuncts are in the unsatisfiable core [2025-02-08 09:58:23,499 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-08 09:58:23,538 INFO L134 CoverageAnalysis]: Checked inductivity of 548 backedges. 207 proven. 21 refuted. 0 times theorem prover too weak. 320 trivial. 0 not checked. [2025-02-08 09:58:23,538 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-08 09:58:23,771 INFO L134 CoverageAnalysis]: Checked inductivity of 548 backedges. 207 proven. 22 refuted. 0 times theorem prover too weak. 319 trivial. 0 not checked. [2025-02-08 09:58:23,771 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1232759038] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-08 09:58:23,771 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-08 09:58:23,772 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 9] total 12 [2025-02-08 09:58:23,772 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1209634319] [2025-02-08 09:58:23,772 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-08 09:58:23,772 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2025-02-08 09:58:23,772 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-08 09:58:23,773 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2025-02-08 09:58:23,773 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=35, Invalid=97, Unknown=0, NotChecked=0, Total=132 [2025-02-08 09:58:23,773 INFO L87 Difference]: Start difference. First operand 55 states and 66 transitions. Second operand has 12 states, 12 states have (on average 4.916666666666667) internal successors, (59), 12 states have internal predecessors, (59), 4 states have call successors, (8), 1 states have call predecessors, (8), 5 states have return successors, (9), 6 states have call predecessors, (9), 4 states have call successors, (9) [2025-02-08 09:58:23,866 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-08 09:58:23,866 INFO L93 Difference]: Finished difference Result 107 states and 131 transitions. [2025-02-08 09:58:23,866 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2025-02-08 09:58:23,867 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 4.916666666666667) internal successors, (59), 12 states have internal predecessors, (59), 4 states have call successors, (8), 1 states have call predecessors, (8), 5 states have return successors, (9), 6 states have call predecessors, (9), 4 states have call successors, (9) Word has length 130 [2025-02-08 09:58:23,867 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-08 09:58:23,867 INFO L225 Difference]: With dead ends: 107 [2025-02-08 09:58:23,867 INFO L226 Difference]: Without dead ends: 57 [2025-02-08 09:58:23,868 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 272 GetRequests, 254 SyntacticMatches, 4 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 30 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=74, Invalid=166, Unknown=0, NotChecked=0, Total=240 [2025-02-08 09:58:23,868 INFO L435 NwaCegarLoop]: 24 mSDtfsCounter, 36 mSDsluCounter, 56 mSDsCounter, 0 mSdLazyCounter, 103 mSolverCounterSat, 16 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 36 SdHoareTripleChecker+Valid, 80 SdHoareTripleChecker+Invalid, 119 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 16 IncrementalHoareTripleChecker+Valid, 103 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-02-08 09:58:23,868 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [36 Valid, 80 Invalid, 119 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [16 Valid, 103 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-02-08 09:58:23,869 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 57 states. [2025-02-08 09:58:23,873 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 57 to 55. [2025-02-08 09:58:23,873 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, (12), 8 states have call predecessors, (12), 5 states have call successors, (12) [2025-02-08 09:58:23,873 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 55 states to 55 states and 64 transitions. [2025-02-08 09:58:23,873 INFO L78 Accepts]: Start accepts. Automaton has 55 states and 64 transitions. Word has length 130 [2025-02-08 09:58:23,874 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-08 09:58:23,874 INFO L471 AbstractCegarLoop]: Abstraction has 55 states and 64 transitions. [2025-02-08 09:58:23,874 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 4.916666666666667) internal successors, (59), 12 states have internal predecessors, (59), 4 states have call successors, (8), 1 states have call predecessors, (8), 5 states have return successors, (9), 6 states have call predecessors, (9), 4 states have call successors, (9) [2025-02-08 09:58:23,874 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 64 transitions. [2025-02-08 09:58:23,874 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 105 [2025-02-08 09:58:23,874 INFO L210 NwaCegarLoop]: Found error trace [2025-02-08 09:58:23,874 INFO L218 NwaCegarLoop]: trace histogram [11, 10, 9, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 4, 2, 1, 1, 1, 1] [2025-02-08 09:58:23,885 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:58:24,080 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,8 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-08 09:58:24,080 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 5 more)] === [2025-02-08 09:58:24,081 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-08 09:58:24,081 INFO L85 PathProgramCache]: Analyzing trace with hash -860426792, now seen corresponding path program 4 times [2025-02-08 09:58:24,081 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-08 09:58:24,081 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1903794547] [2025-02-08 09:58:24,081 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-02-08 09:58:24,081 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-08 09:58:24,087 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 104 statements into 2 equivalence classes. [2025-02-08 09:58:24,092 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) and asserted 62 of 104 statements. [2025-02-08 09:58:24,092 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) [2025-02-08 09:58:24,092 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 09:58:24,196 INFO L134 CoverageAnalysis]: Checked inductivity of 336 backedges. 72 proven. 159 refuted. 0 times theorem prover too weak. 105 trivial. 0 not checked. [2025-02-08 09:58:24,196 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-08 09:58:24,197 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1903794547] [2025-02-08 09:58:24,197 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1903794547] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-08 09:58:24,197 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [197284345] [2025-02-08 09:58:24,197 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-02-08 09:58:24,197 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-08 09:58:24,197 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-08 09:58:24,199 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:58:24,200 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:58:24,226 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 104 statements into 2 equivalence classes. [2025-02-08 09:58:24,235 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) and asserted 62 of 104 statements. [2025-02-08 09:58:24,236 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) [2025-02-08 09:58:24,236 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 09:58:24,236 INFO L256 TraceCheckSpWp]: Trace formula consists of 134 conjuncts, 14 conjuncts are in the unsatisfiable core [2025-02-08 09:58:24,238 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-08 09:58:24,316 INFO L134 CoverageAnalysis]: Checked inductivity of 336 backedges. 82 proven. 158 refuted. 0 times theorem prover too weak. 96 trivial. 0 not checked. [2025-02-08 09:58:24,316 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-08 09:58:24,755 INFO L134 CoverageAnalysis]: Checked inductivity of 336 backedges. 82 proven. 174 refuted. 0 times theorem prover too weak. 80 trivial. 0 not checked. [2025-02-08 09:58:24,756 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [197284345] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-08 09:58:24,756 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-08 09:58:24,756 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 11, 15] total 20 [2025-02-08 09:58:24,756 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1429402922] [2025-02-08 09:58:24,756 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-08 09:58:24,756 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2025-02-08 09:58:24,757 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-08 09:58:24,757 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2025-02-08 09:58:24,757 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=76, Invalid=304, Unknown=0, NotChecked=0, Total=380 [2025-02-08 09:58:24,757 INFO L87 Difference]: Start difference. First operand 55 states and 64 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:58:24,934 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-08 09:58:24,934 INFO L93 Difference]: Finished difference Result 120 states and 146 transitions. [2025-02-08 09:58:24,934 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2025-02-08 09:58:24,934 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 104 [2025-02-08 09:58:24,935 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-08 09:58:24,935 INFO L225 Difference]: With dead ends: 120 [2025-02-08 09:58:24,935 INFO L226 Difference]: Without dead ends: 70 [2025-02-08 09:58:24,936 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 237 GetRequests, 200 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:58:24,936 INFO L435 NwaCegarLoop]: 22 mSDtfsCounter, 112 mSDsluCounter, 63 mSDsCounter, 0 mSdLazyCounter, 169 mSolverCounterSat, 54 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 112 SdHoareTripleChecker+Valid, 85 SdHoareTripleChecker+Invalid, 223 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 54 IncrementalHoareTripleChecker+Valid, 169 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-02-08 09:58:24,936 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [112 Valid, 85 Invalid, 223 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [54 Valid, 169 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-02-08 09:58:24,937 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 70 states. [2025-02-08 09:58:24,939 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 70 to 61. [2025-02-08 09:58:24,940 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 61 states, 48 states have (on average 1.0833333333333333) internal successors, (52), 47 states have internal predecessors, (52), 7 states have call successors, (7), 5 states have call predecessors, (7), 5 states have return successors, (11), 8 states have call predecessors, (11), 6 states have call successors, (11) [2025-02-08 09:58:24,940 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 61 states to 61 states and 70 transitions. [2025-02-08 09:58:24,940 INFO L78 Accepts]: Start accepts. Automaton has 61 states and 70 transitions. Word has length 104 [2025-02-08 09:58:24,940 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-08 09:58:24,940 INFO L471 AbstractCegarLoop]: Abstraction has 61 states and 70 transitions. [2025-02-08 09:58:24,941 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:58:24,941 INFO L276 IsEmpty]: Start isEmpty. Operand 61 states and 70 transitions. [2025-02-08 09:58:24,941 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 183 [2025-02-08 09:58:24,941 INFO L210 NwaCegarLoop]: Found error trace [2025-02-08 09:58:24,942 INFO L218 NwaCegarLoop]: trace histogram [19, 18, 15, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 8, 6, 4, 1, 1, 1, 1] [2025-02-08 09:58:24,948 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2025-02-08 09:58:25,146 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11,9 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-08 09:58:25,146 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 5 more)] === [2025-02-08 09:58:25,146 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-08 09:58:25,146 INFO L85 PathProgramCache]: Analyzing trace with hash 1832342530, now seen corresponding path program 5 times [2025-02-08 09:58:25,146 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-08 09:58:25,146 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1713518031] [2025-02-08 09:58:25,146 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2025-02-08 09:58:25,146 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-08 09:58:25,152 INFO L108 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 partitioned 182 statements into 15 equivalence classes. [2025-02-08 09:58:25,164 INFO L111 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 11 check-sat command(s) and asserted 141 of 182 statements. [2025-02-08 09:58:25,164 INFO L114 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 11 check-sat command(s) [2025-02-08 09:58:25,164 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 09:58:25,396 INFO L134 CoverageAnalysis]: Checked inductivity of 1113 backedges. 281 proven. 362 refuted. 0 times theorem prover too weak. 470 trivial. 0 not checked. [2025-02-08 09:58:25,397 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-08 09:58:25,397 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1713518031] [2025-02-08 09:58:25,397 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1713518031] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-08 09:58:25,397 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2044850696] [2025-02-08 09:58:25,397 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2025-02-08 09:58:25,397 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-08 09:58:25,397 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-08 09:58:25,399 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:58:25,401 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:58:25,432 INFO L108 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 partitioned 182 statements into 15 equivalence classes. [2025-02-08 09:58:25,457 INFO L111 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 11 check-sat command(s) and asserted 141 of 182 statements. [2025-02-08 09:58:25,458 INFO L114 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 11 check-sat command(s) [2025-02-08 09:58:25,458 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 09:58:25,459 INFO L256 TraceCheckSpWp]: Trace formula consists of 264 conjuncts, 14 conjuncts are in the unsatisfiable core [2025-02-08 09:58:25,461 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-08 09:58:25,535 INFO L134 CoverageAnalysis]: Checked inductivity of 1113 backedges. 263 proven. 345 refuted. 0 times theorem prover too weak. 505 trivial. 0 not checked. [2025-02-08 09:58:25,535 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-08 09:58:26,039 INFO L134 CoverageAnalysis]: Checked inductivity of 1113 backedges. 267 proven. 357 refuted. 0 times theorem prover too weak. 489 trivial. 0 not checked. [2025-02-08 09:58:26,039 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2044850696] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-08 09:58:26,039 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-08 09:58:26,040 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 11, 15] total 21 [2025-02-08 09:58:26,040 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [899614983] [2025-02-08 09:58:26,040 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-08 09:58:26,040 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2025-02-08 09:58:26,040 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-08 09:58:26,041 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2025-02-08 09:58:26,041 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=82, Invalid=338, Unknown=0, NotChecked=0, Total=420 [2025-02-08 09:58:26,041 INFO L87 Difference]: Start difference. First operand 61 states and 70 transitions. Second operand has 21 states, 21 states have (on average 5.285714285714286) internal successors, (111), 21 states have internal predecessors, (111), 12 states have call successors, (19), 1 states have call predecessors, (19), 8 states have return successors, (22), 13 states have call predecessors, (22), 12 states have call successors, (22) [2025-02-08 09:58:26,272 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-08 09:58:26,273 INFO L93 Difference]: Finished difference Result 148 states and 180 transitions. [2025-02-08 09:58:26,273 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2025-02-08 09:58:26,273 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 21 states have (on average 5.285714285714286) internal successors, (111), 21 states have internal predecessors, (111), 12 states have call successors, (19), 1 states have call predecessors, (19), 8 states have return successors, (22), 13 states have call predecessors, (22), 12 states have call successors, (22) Word has length 182 [2025-02-08 09:58:26,274 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-08 09:58:26,274 INFO L225 Difference]: With dead ends: 148 [2025-02-08 09:58:26,274 INFO L226 Difference]: Without dead ends: 92 [2025-02-08 09:58:26,275 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 396 GetRequests, 355 SyntacticMatches, 7 SemanticMatches, 34 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 239 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=350, Invalid=910, Unknown=0, NotChecked=0, Total=1260 [2025-02-08 09:58:26,275 INFO L435 NwaCegarLoop]: 29 mSDtfsCounter, 109 mSDsluCounter, 84 mSDsCounter, 0 mSdLazyCounter, 255 mSolverCounterSat, 53 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 109 SdHoareTripleChecker+Valid, 113 SdHoareTripleChecker+Invalid, 308 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 53 IncrementalHoareTripleChecker+Valid, 255 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-02-08 09:58:26,275 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [109 Valid, 113 Invalid, 308 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [53 Valid, 255 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-02-08 09:58:26,276 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 92 states. [2025-02-08 09:58:26,279 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 92 to 79. [2025-02-08 09:58:26,279 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 79 states, 63 states have (on average 1.0634920634920635) internal successors, (67), 61 states have internal predecessors, (67), 9 states have call successors, (9), 8 states have call predecessors, (9), 6 states have return successors, (17), 9 states have call predecessors, (17), 8 states have call successors, (17) [2025-02-08 09:58:26,280 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 79 states to 79 states and 93 transitions. [2025-02-08 09:58:26,280 INFO L78 Accepts]: Start accepts. Automaton has 79 states and 93 transitions. Word has length 182 [2025-02-08 09:58:26,280 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-08 09:58:26,280 INFO L471 AbstractCegarLoop]: Abstraction has 79 states and 93 transitions. [2025-02-08 09:58:26,281 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 21 states have (on average 5.285714285714286) internal successors, (111), 21 states have internal predecessors, (111), 12 states have call successors, (19), 1 states have call predecessors, (19), 8 states have return successors, (22), 13 states have call predecessors, (22), 12 states have call successors, (22) [2025-02-08 09:58:26,281 INFO L276 IsEmpty]: Start isEmpty. Operand 79 states and 93 transitions. [2025-02-08 09:58:26,281 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 130 [2025-02-08 09:58:26,281 INFO L210 NwaCegarLoop]: Found error trace [2025-02-08 09:58:26,281 INFO L218 NwaCegarLoop]: trace histogram [14, 12, 11, 7, 7, 7, 7, 6, 6, 6, 6, 6, 6, 6, 6, 5, 4, 3, 1, 1, 1, 1] [2025-02-08 09:58:26,287 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2025-02-08 09:58:26,485 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable12,10 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-08 09:58:26,486 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 5 more)] === [2025-02-08 09:58:26,486 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-08 09:58:26,486 INFO L85 PathProgramCache]: Analyzing trace with hash 799148630, now seen corresponding path program 6 times [2025-02-08 09:58:26,486 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-08 09:58:26,487 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [17854028] [2025-02-08 09:58:26,487 INFO L95 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2025-02-08 09:58:26,487 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-08 09:58:26,491 INFO L108 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE partitioned 129 statements into 9 equivalence classes. [2025-02-08 09:58:26,501 INFO L111 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 9 check-sat command(s) and asserted 129 of 129 statements. [2025-02-08 09:58:26,501 INFO L114 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 9 check-sat command(s) [2025-02-08 09:58:26,501 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 09:58:26,607 INFO L134 CoverageAnalysis]: Checked inductivity of 537 backedges. 183 proven. 132 refuted. 0 times theorem prover too weak. 222 trivial. 0 not checked. [2025-02-08 09:58:26,607 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-08 09:58:26,607 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [17854028] [2025-02-08 09:58:26,607 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [17854028] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-08 09:58:26,607 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [905757731] [2025-02-08 09:58:26,607 INFO L95 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2025-02-08 09:58:26,608 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-08 09:58:26,608 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-08 09:58:26,610 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:58:26,613 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:58:26,643 INFO L108 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE partitioned 129 statements into 9 equivalence classes. [2025-02-08 09:58:26,665 INFO L111 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 9 check-sat command(s) and asserted 129 of 129 statements. [2025-02-08 09:58:26,665 INFO L114 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 9 check-sat command(s) [2025-02-08 09:58:26,665 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 09:58:26,666 INFO L256 TraceCheckSpWp]: Trace formula consists of 260 conjuncts, 25 conjuncts are in the unsatisfiable core [2025-02-08 09:58:26,668 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-08 09:58:26,839 INFO L134 CoverageAnalysis]: Checked inductivity of 537 backedges. 61 proven. 95 refuted. 0 times theorem prover too weak. 381 trivial. 0 not checked. [2025-02-08 09:58:26,839 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-08 09:58:27,578 INFO L134 CoverageAnalysis]: Checked inductivity of 537 backedges. 103 proven. 95 refuted. 0 times theorem prover too weak. 339 trivial. 0 not checked. [2025-02-08 09:58:27,579 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [905757731] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-08 09:58:27,579 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-08 09:58:27,579 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 12, 15] total 33 [2025-02-08 09:58:27,579 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1352729649] [2025-02-08 09:58:27,579 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-08 09:58:27,579 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 33 states [2025-02-08 09:58:27,579 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-08 09:58:27,580 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 33 interpolants. [2025-02-08 09:58:27,580 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=159, Invalid=897, Unknown=0, NotChecked=0, Total=1056 [2025-02-08 09:58:27,581 INFO L87 Difference]: Start difference. First operand 79 states and 93 transitions. Second operand has 33 states, 33 states have (on average 3.4545454545454546) internal successors, (114), 33 states have internal predecessors, (114), 11 states have call successors, (15), 1 states have call predecessors, (15), 13 states have return successors, (25), 23 states have call predecessors, (25), 11 states have call successors, (25) [2025-02-08 09:58:28,072 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-08 09:58:28,072 INFO L93 Difference]: Finished difference Result 202 states and 264 transitions. [2025-02-08 09:58:28,073 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2025-02-08 09:58:28,073 INFO L78 Accepts]: Start accepts. Automaton has has 33 states, 33 states have (on average 3.4545454545454546) internal successors, (114), 33 states have internal predecessors, (114), 11 states have call successors, (15), 1 states have call predecessors, (15), 13 states have return successors, (25), 23 states have call predecessors, (25), 11 states have call successors, (25) Word has length 129 [2025-02-08 09:58:28,073 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-08 09:58:28,074 INFO L225 Difference]: With dead ends: 202 [2025-02-08 09:58:28,074 INFO L226 Difference]: Without dead ends: 122 [2025-02-08 09:58:28,075 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 292 GetRequests, 229 SyntacticMatches, 10 SemanticMatches, 53 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 840 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=501, Invalid=2469, Unknown=0, NotChecked=0, Total=2970 [2025-02-08 09:58:28,075 INFO L435 NwaCegarLoop]: 16 mSDtfsCounter, 127 mSDsluCounter, 103 mSDsCounter, 0 mSdLazyCounter, 654 mSolverCounterSat, 62 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 127 SdHoareTripleChecker+Valid, 119 SdHoareTripleChecker+Invalid, 716 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 62 IncrementalHoareTripleChecker+Valid, 654 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2025-02-08 09:58:28,075 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [127 Valid, 119 Invalid, 716 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [62 Valid, 654 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2025-02-08 09:58:28,076 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 122 states. [2025-02-08 09:58:28,081 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 122 to 97. [2025-02-08 09:58:28,082 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 97 states, 77 states have (on average 1.051948051948052) internal successors, (81), 76 states have internal predecessors, (81), 12 states have call successors, (12), 8 states have call predecessors, (12), 7 states have return successors, (26), 12 states have call predecessors, (26), 11 states have call successors, (26) [2025-02-08 09:58:28,083 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 97 states to 97 states and 119 transitions. [2025-02-08 09:58:28,083 INFO L78 Accepts]: Start accepts. Automaton has 97 states and 119 transitions. Word has length 129 [2025-02-08 09:58:28,083 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-08 09:58:28,083 INFO L471 AbstractCegarLoop]: Abstraction has 97 states and 119 transitions. [2025-02-08 09:58:28,083 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 33 states, 33 states have (on average 3.4545454545454546) internal successors, (114), 33 states have internal predecessors, (114), 11 states have call successors, (15), 1 states have call predecessors, (15), 13 states have return successors, (25), 23 states have call predecessors, (25), 11 states have call successors, (25) [2025-02-08 09:58:28,084 INFO L276 IsEmpty]: Start isEmpty. Operand 97 states and 119 transitions. [2025-02-08 09:58:28,088 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 465 [2025-02-08 09:58:28,088 INFO L210 NwaCegarLoop]: Found error trace [2025-02-08 09:58:28,088 INFO L218 NwaCegarLoop]: trace histogram [49, 45, 40, 25, 25, 25, 25, 23, 23, 23, 23, 23, 22, 22, 22, 21, 15, 9, 1, 1, 1, 1] [2025-02-08 09:58:28,094 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:58:28,289 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,SelfDestructingSolverStorable13 [2025-02-08 09:58:28,289 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 5 more)] === [2025-02-08 09:58:28,289 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-08 09:58:28,289 INFO L85 PathProgramCache]: Analyzing trace with hash -1512723524, now seen corresponding path program 7 times [2025-02-08 09:58:28,289 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-08 09:58:28,289 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1406672683] [2025-02-08 09:58:28,290 INFO L95 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2025-02-08 09:58:28,290 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-08 09:58:28,304 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 464 statements into 1 equivalence classes. [2025-02-08 09:58:28,330 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 464 of 464 statements. [2025-02-08 09:58:28,330 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 09:58:28,330 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 09:58:28,756 INFO L134 CoverageAnalysis]: Checked inductivity of 7717 backedges. 593 proven. 1908 refuted. 0 times theorem prover too weak. 5216 trivial. 0 not checked. [2025-02-08 09:58:28,757 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-08 09:58:28,757 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1406672683] [2025-02-08 09:58:28,757 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1406672683] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-08 09:58:28,757 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1982245916] [2025-02-08 09:58:28,757 INFO L95 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2025-02-08 09:58:28,757 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-08 09:58:28,757 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-08 09:58:28,759 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:58:28,760 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:58:28,813 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 464 statements into 1 equivalence classes. [2025-02-08 09:58:28,875 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 464 of 464 statements. [2025-02-08 09:58:28,875 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 09:58:28,876 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 09:58:28,878 INFO L256 TraceCheckSpWp]: Trace formula consists of 878 conjuncts, 22 conjuncts are in the unsatisfiable core [2025-02-08 09:58:28,883 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-08 09:58:29,011 INFO L134 CoverageAnalysis]: Checked inductivity of 7717 backedges. 4011 proven. 1274 refuted. 0 times theorem prover too weak. 2432 trivial. 0 not checked. [2025-02-08 09:58:29,012 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-08 09:58:29,982 INFO L134 CoverageAnalysis]: Checked inductivity of 7717 backedges. 684 proven. 2447 refuted. 0 times theorem prover too weak. 4586 trivial. 0 not checked. [2025-02-08 09:58:29,983 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1982245916] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-08 09:58:29,983 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-08 09:58:29,983 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 15, 21] total 26 [2025-02-08 09:58:29,983 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [998948361] [2025-02-08 09:58:29,983 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-08 09:58:29,984 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 26 states [2025-02-08 09:58:29,984 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-08 09:58:29,984 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2025-02-08 09:58:29,985 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=109, Invalid=541, Unknown=0, NotChecked=0, Total=650 [2025-02-08 09:58:29,985 INFO L87 Difference]: Start difference. First operand 97 states and 119 transitions. Second operand has 26 states, 26 states have (on average 5.961538461538462) internal successors, (155), 26 states have internal predecessors, (155), 21 states have call successors, (28), 4 states have call predecessors, (28), 10 states have return successors, (31), 12 states have call predecessors, (31), 19 states have call successors, (31) [2025-02-08 09:58:30,287 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-08 09:58:30,288 INFO L93 Difference]: Finished difference Result 232 states and 307 transitions. [2025-02-08 09:58:30,288 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2025-02-08 09:58:30,288 INFO L78 Accepts]: Start accepts. Automaton has has 26 states, 26 states have (on average 5.961538461538462) internal successors, (155), 26 states have internal predecessors, (155), 21 states have call successors, (28), 4 states have call predecessors, (28), 10 states have return successors, (31), 12 states have call predecessors, (31), 19 states have call successors, (31) Word has length 464 [2025-02-08 09:58:30,289 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-08 09:58:30,290 INFO L225 Difference]: With dead ends: 232 [2025-02-08 09:58:30,290 INFO L226 Difference]: Without dead ends: 140 [2025-02-08 09:58:30,291 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 970 GetRequests, 913 SyntacticMatches, 13 SemanticMatches, 44 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 464 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=568, Invalid=1502, Unknown=0, NotChecked=0, Total=2070 [2025-02-08 09:58:30,291 INFO L435 NwaCegarLoop]: 22 mSDtfsCounter, 168 mSDsluCounter, 96 mSDsCounter, 0 mSdLazyCounter, 224 mSolverCounterSat, 69 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 168 SdHoareTripleChecker+Valid, 118 SdHoareTripleChecker+Invalid, 293 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 69 IncrementalHoareTripleChecker+Valid, 224 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-02-08 09:58:30,292 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [168 Valid, 118 Invalid, 293 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [69 Valid, 224 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-02-08 09:58:30,293 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 140 states. [2025-02-08 09:58:30,302 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 140 to 118. [2025-02-08 09:58:30,302 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 118 states, 95 states have (on average 1.063157894736842) internal successors, (101), 92 states have internal predecessors, (101), 14 states have call successors, (14), 10 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:58:30,304 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 118 states to 118 states and 147 transitions. [2025-02-08 09:58:30,304 INFO L78 Accepts]: Start accepts. Automaton has 118 states and 147 transitions. Word has length 464 [2025-02-08 09:58:30,304 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-08 09:58:30,305 INFO L471 AbstractCegarLoop]: Abstraction has 118 states and 147 transitions. [2025-02-08 09:58:30,305 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 26 states, 26 states have (on average 5.961538461538462) internal successors, (155), 26 states have internal predecessors, (155), 21 states have call successors, (28), 4 states have call predecessors, (28), 10 states have return successors, (31), 12 states have call predecessors, (31), 19 states have call successors, (31) [2025-02-08 09:58:30,305 INFO L276 IsEmpty]: Start isEmpty. Operand 118 states and 147 transitions. [2025-02-08 09:58:30,309 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 268 [2025-02-08 09:58:30,309 INFO L210 NwaCegarLoop]: Found error trace [2025-02-08 09:58:30,309 INFO L218 NwaCegarLoop]: trace histogram [28, 26, 23, 14, 14, 14, 14, 13, 13, 13, 13, 13, 13, 13, 13, 12, 9, 5, 1, 1, 1, 1] [2025-02-08 09:58:30,316 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:58:30,514 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,SelfDestructingSolverStorable14 [2025-02-08 09:58:30,514 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 5 more)] === [2025-02-08 09:58:30,514 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-08 09:58:30,515 INFO L85 PathProgramCache]: Analyzing trace with hash 2089571020, now seen corresponding path program 8 times [2025-02-08 09:58:30,515 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-08 09:58:30,515 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [750773754] [2025-02-08 09:58:30,515 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-02-08 09:58:30,515 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-08 09:58:30,523 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 267 statements into 2 equivalence classes. [2025-02-08 09:58:30,537 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 267 of 267 statements. [2025-02-08 09:58:30,537 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-02-08 09:58:30,537 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 09:58:30,753 INFO L134 CoverageAnalysis]: Checked inductivity of 2478 backedges. 480 proven. 678 refuted. 0 times theorem prover too weak. 1320 trivial. 0 not checked. [2025-02-08 09:58:30,753 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-08 09:58:30,753 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [750773754] [2025-02-08 09:58:30,753 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [750773754] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-08 09:58:30,753 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [836614364] [2025-02-08 09:58:30,753 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-02-08 09:58:30,754 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-08 09:58:30,754 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-08 09:58:30,755 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:58:30,762 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:58:30,815 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 267 statements into 2 equivalence classes. [2025-02-08 09:58:30,852 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 267 of 267 statements. [2025-02-08 09:58:30,852 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-02-08 09:58:30,852 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 09:58:30,854 INFO L256 TraceCheckSpWp]: Trace formula consists of 515 conjuncts, 18 conjuncts are in the unsatisfiable core [2025-02-08 09:58:30,857 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-08 09:58:30,962 INFO L134 CoverageAnalysis]: Checked inductivity of 2478 backedges. 1251 proven. 484 refuted. 0 times theorem prover too weak. 743 trivial. 0 not checked. [2025-02-08 09:58:30,962 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-08 09:58:31,955 INFO L134 CoverageAnalysis]: Checked inductivity of 2478 backedges. 545 proven. 831 refuted. 0 times theorem prover too weak. 1102 trivial. 0 not checked. [2025-02-08 09:58:31,955 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [836614364] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-08 09:58:31,955 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-08 09:58:31,955 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 13, 19] total 24 [2025-02-08 09:58:31,955 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1725474777] [2025-02-08 09:58:31,955 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-08 09:58:31,956 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 24 states [2025-02-08 09:58:31,956 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-08 09:58:31,956 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2025-02-08 09:58:31,956 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=111, Invalid=441, Unknown=0, NotChecked=0, Total=552 [2025-02-08 09:58:31,956 INFO L87 Difference]: Start difference. First operand 118 states and 147 transitions. Second operand has 24 states, 24 states have (on average 5.708333333333333) internal successors, (137), 24 states have internal predecessors, (137), 18 states have call successors, (24), 2 states have call predecessors, (24), 10 states have return successors, (30), 11 states have call predecessors, (30), 18 states have call successors, (30) [2025-02-08 09:58:32,153 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-08 09:58:32,153 INFO L93 Difference]: Finished difference Result 231 states and 299 transitions. [2025-02-08 09:58:32,154 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2025-02-08 09:58:32,154 INFO L78 Accepts]: Start accepts. Automaton has has 24 states, 24 states have (on average 5.708333333333333) internal successors, (137), 24 states have internal predecessors, (137), 18 states have call successors, (24), 2 states have call predecessors, (24), 10 states have return successors, (30), 11 states have call predecessors, (30), 18 states have call successors, (30) Word has length 267 [2025-02-08 09:58:32,155 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-08 09:58:32,155 INFO L225 Difference]: With dead ends: 231 [2025-02-08 09:58:32,156 INFO L226 Difference]: Without dead ends: 118 [2025-02-08 09:58:32,156 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 562 GetRequests, 519 SyntacticMatches, 9 SemanticMatches, 34 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 341 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=349, Invalid=911, Unknown=0, NotChecked=0, Total=1260 [2025-02-08 09:58:32,157 INFO L435 NwaCegarLoop]: 40 mSDtfsCounter, 50 mSDsluCounter, 108 mSDsCounter, 0 mSdLazyCounter, 331 mSolverCounterSat, 33 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 50 SdHoareTripleChecker+Valid, 148 SdHoareTripleChecker+Invalid, 364 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 33 IncrementalHoareTripleChecker+Valid, 331 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-02-08 09:58:32,157 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [50 Valid, 148 Invalid, 364 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [33 Valid, 331 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-02-08 09:58:32,157 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 118 states. [2025-02-08 09:58:32,164 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 118 to 106. [2025-02-08 09:58:32,164 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 106 states, 85 states have (on average 1.035294117647059) internal successors, (88), 83 states have internal predecessors, (88), 13 states have call successors, (13), 10 states have call predecessors, (13), 7 states have return successors, (26), 12 states have call predecessors, (26), 12 states have call successors, (26) [2025-02-08 09:58:32,165 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 106 states to 106 states and 127 transitions. [2025-02-08 09:58:32,165 INFO L78 Accepts]: Start accepts. Automaton has 106 states and 127 transitions. Word has length 267 [2025-02-08 09:58:32,165 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-08 09:58:32,165 INFO L471 AbstractCegarLoop]: Abstraction has 106 states and 127 transitions. [2025-02-08 09:58:32,165 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 24 states, 24 states have (on average 5.708333333333333) internal successors, (137), 24 states have internal predecessors, (137), 18 states have call successors, (24), 2 states have call predecessors, (24), 10 states have return successors, (30), 11 states have call predecessors, (30), 18 states have call successors, (30) [2025-02-08 09:58:32,165 INFO L276 IsEmpty]: Start isEmpty. Operand 106 states and 127 transitions. [2025-02-08 09:58:32,170 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 765 [2025-02-08 09:58:32,170 INFO L210 NwaCegarLoop]: Found error trace [2025-02-08 09:58:32,170 INFO L218 NwaCegarLoop]: trace histogram [80, 75, 65, 41, 41, 41, 41, 38, 38, 38, 38, 38, 37, 37, 37, 36, 24, 15, 1, 1, 1, 1] [2025-02-08 09:58:32,176 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Forceful destruction successful, exit code 0 [2025-02-08 09:58:32,370 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable15,13 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-08 09:58:32,371 INFO L396 AbstractCegarLoop]: === Iteration 17 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 5 more)] === [2025-02-08 09:58:32,371 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-08 09:58:32,371 INFO L85 PathProgramCache]: Analyzing trace with hash 7922085, now seen corresponding path program 9 times [2025-02-08 09:58:32,371 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-08 09:58:32,371 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2103048667] [2025-02-08 09:58:32,371 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-02-08 09:58:32,371 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-08 09:58:32,384 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 764 statements into 60 equivalence classes. [2025-02-08 09:58:32,439 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 35 check-sat command(s) and asserted 502 of 764 statements. [2025-02-08 09:58:32,440 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 35 check-sat command(s) [2025-02-08 09:58:32,440 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 09:58:35,337 INFO L134 CoverageAnalysis]: Checked inductivity of 21220 backedges. 6070 proven. 2318 refuted. 0 times theorem prover too weak. 12832 trivial. 0 not checked. [2025-02-08 09:58:35,337 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-08 09:58:35,337 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2103048667] [2025-02-08 09:58:35,337 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2103048667] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-08 09:58:35,337 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [694615452] [2025-02-08 09:58:35,337 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-02-08 09:58:35,337 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-08 09:58:35,338 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-08 09:58:35,339 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:58:35,343 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:58:35,420 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 764 statements into 60 equivalence classes. [2025-02-08 09:58:35,527 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 35 check-sat command(s) and asserted 502 of 764 statements. [2025-02-08 09:58:35,527 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 35 check-sat command(s) [2025-02-08 09:58:35,527 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 09:58:35,533 INFO L256 TraceCheckSpWp]: Trace formula consists of 949 conjuncts, 101 conjuncts are in the unsatisfiable core [2025-02-08 09:58:35,544 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-08 09:58:35,953 INFO L134 CoverageAnalysis]: Checked inductivity of 21220 backedges. 6012 proven. 1736 refuted. 0 times theorem prover too weak. 13472 trivial. 0 not checked. [2025-02-08 09:58:35,953 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-08 09:58:42,935 INFO L134 CoverageAnalysis]: Checked inductivity of 21220 backedges. 6479 proven. 1574 refuted. 0 times theorem prover too weak. 13167 trivial. 0 not checked. [2025-02-08 09:58:42,936 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [694615452] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-08 09:58:42,936 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-08 09:58:42,936 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 18, 32] total 46 [2025-02-08 09:58:42,936 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [51797560] [2025-02-08 09:58:42,936 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-08 09:58:42,937 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 47 states [2025-02-08 09:58:42,937 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-08 09:58:42,937 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 47 interpolants. [2025-02-08 09:58:42,938 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=495, Invalid=1667, Unknown=0, NotChecked=0, Total=2162 [2025-02-08 09:58:42,938 INFO L87 Difference]: Start difference. First operand 106 states and 127 transitions. Second operand has 47 states, 46 states have (on average 2.8260869565217392) internal successors, (130), 47 states have internal predecessors, (130), 12 states have call successors, (14), 1 states have call predecessors, (14), 14 states have return successors, (34), 33 states have call predecessors, (34), 12 states have call successors, (34) [2025-02-08 09:58:43,164 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-08 09:58:43,164 INFO L93 Difference]: Finished difference Result 167 states and 239 transitions. [2025-02-08 09:58:43,164 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 32 states. [2025-02-08 09:58:43,165 INFO L78 Accepts]: Start accepts. Automaton has has 47 states, 46 states have (on average 2.8260869565217392) internal successors, (130), 47 states have internal predecessors, (130), 12 states have call successors, (14), 1 states have call predecessors, (14), 14 states have return successors, (34), 33 states have call predecessors, (34), 12 states have call successors, (34) Word has length 764 [2025-02-08 09:58:43,166 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-08 09:58:43,167 INFO L225 Difference]: With dead ends: 167 [2025-02-08 09:58:43,167 INFO L226 Difference]: Without dead ends: 166 [2025-02-08 09:58:43,168 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 1635 GetRequests, 1514 SyntacticMatches, 68 SemanticMatches, 53 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2945 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=663, Invalid=2307, Unknown=0, NotChecked=0, Total=2970 [2025-02-08 09:58:43,168 INFO L435 NwaCegarLoop]: 19 mSDtfsCounter, 22 mSDsluCounter, 274 mSDsCounter, 0 mSdLazyCounter, 224 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 32 SdHoareTripleChecker+Valid, 293 SdHoareTripleChecker+Invalid, 231 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 224 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-02-08 09:58:43,168 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [32 Valid, 293 Invalid, 231 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 224 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-02-08 09:58:43,168 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 166 states. [2025-02-08 09:58:43,176 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 166 to 142. [2025-02-08 09:58:43,176 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 142 states, 113 states have (on average 1.0265486725663717) internal successors, (116), 111 states have internal predecessors, (116), 17 states have call successors, (17), 10 states have call predecessors, (17), 11 states have return successors, (70), 20 states have call predecessors, (70), 16 states have call successors, (70) [2025-02-08 09:58:43,177 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 142 states to 142 states and 203 transitions. [2025-02-08 09:58:43,177 INFO L78 Accepts]: Start accepts. Automaton has 142 states and 203 transitions. Word has length 764 [2025-02-08 09:58:43,178 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-08 09:58:43,178 INFO L471 AbstractCegarLoop]: Abstraction has 142 states and 203 transitions. [2025-02-08 09:58:43,178 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 47 states, 46 states have (on average 2.8260869565217392) internal successors, (130), 47 states have internal predecessors, (130), 12 states have call successors, (14), 1 states have call predecessors, (14), 14 states have return successors, (34), 33 states have call predecessors, (34), 12 states have call successors, (34) [2025-02-08 09:58:43,178 INFO L276 IsEmpty]: Start isEmpty. Operand 142 states and 203 transitions. [2025-02-08 09:58:43,184 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1171 [2025-02-08 09:58:43,184 INFO L210 NwaCegarLoop]: Found error trace [2025-02-08 09:58:43,184 INFO L218 NwaCegarLoop]: trace histogram [121, 117, 98, 61, 61, 61, 61, 59, 59, 59, 59, 59, 58, 58, 58, 57, 37, 23, 1, 1, 1, 1] [2025-02-08 09:58:43,191 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:58:43,385 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable16 [2025-02-08 09:58:43,385 INFO L396 AbstractCegarLoop]: === Iteration 18 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 5 more)] === [2025-02-08 09:58:43,385 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-08 09:58:43,386 INFO L85 PathProgramCache]: Analyzing trace with hash -388125480, now seen corresponding path program 10 times [2025-02-08 09:58:43,386 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-08 09:58:43,386 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1082138358] [2025-02-08 09:58:43,386 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-02-08 09:58:43,386 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-08 09:58:43,405 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 1170 statements into 2 equivalence classes. [2025-02-08 09:58:43,449 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) and asserted 695 of 1170 statements. [2025-02-08 09:58:43,450 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) [2025-02-08 09:58:43,450 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 09:58:44,090 INFO L134 CoverageAnalysis]: Checked inductivity of 50138 backedges. 1339 proven. 7010 refuted. 0 times theorem prover too weak. 41789 trivial. 0 not checked. [2025-02-08 09:58:44,091 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-08 09:58:44,091 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1082138358] [2025-02-08 09:58:44,091 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1082138358] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-08 09:58:44,091 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1420761168] [2025-02-08 09:58:44,091 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-02-08 09:58:44,091 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-08 09:58:44,091 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-08 09:58:44,093 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:58:44,095 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:58:44,309 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 1170 statements into 2 equivalence classes. [2025-02-08 09:58:44,411 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) and asserted 695 of 1170 statements. [2025-02-08 09:58:44,411 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) [2025-02-08 09:58:44,412 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 09:58:44,415 INFO L256 TraceCheckSpWp]: Trace formula consists of 1455 conjuncts, 26 conjuncts are in the unsatisfiable core [2025-02-08 09:58:44,426 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-08 09:58:44,556 INFO L134 CoverageAnalysis]: Checked inductivity of 50138 backedges. 26025 proven. 2740 refuted. 0 times theorem prover too weak. 21373 trivial. 0 not checked. [2025-02-08 09:58:44,556 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-08 09:58:46,400 INFO L134 CoverageAnalysis]: Checked inductivity of 50138 backedges. 1364 proven. 8867 refuted. 0 times theorem prover too weak. 39907 trivial. 0 not checked. [2025-02-08 09:58:46,400 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1420761168] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-08 09:58:46,400 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-08 09:58:46,400 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 17, 24] total 29 [2025-02-08 09:58:46,400 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1754807382] [2025-02-08 09:58:46,400 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-08 09:58:46,402 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 29 states [2025-02-08 09:58:46,402 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-08 09:58:46,403 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 29 interpolants. [2025-02-08 09:58:46,403 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=130, Invalid=682, Unknown=0, NotChecked=0, Total=812 [2025-02-08 09:58:46,403 INFO L87 Difference]: Start difference. First operand 142 states and 203 transitions. Second operand has 29 states, 29 states have (on average 5.931034482758621) internal successors, (172), 29 states have internal predecessors, (172), 24 states have call successors, (31), 5 states have call predecessors, (31), 11 states have return successors, (34), 13 states have call predecessors, (34), 21 states have call successors, (34) [2025-02-08 09:58:46,748 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-08 09:58:46,748 INFO L93 Difference]: Finished difference Result 346 states and 571 transitions. [2025-02-08 09:58:46,749 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 28 states. [2025-02-08 09:58:46,749 INFO L78 Accepts]: Start accepts. Automaton has has 29 states, 29 states have (on average 5.931034482758621) internal successors, (172), 29 states have internal predecessors, (172), 24 states have call successors, (31), 5 states have call predecessors, (31), 11 states have return successors, (34), 13 states have call predecessors, (34), 21 states have call successors, (34) Word has length 1170 [2025-02-08 09:58:46,750 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-08 09:58:46,751 INFO L225 Difference]: With dead ends: 346 [2025-02-08 09:58:46,751 INFO L226 Difference]: Without dead ends: 209 [2025-02-08 09:58:46,753 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 2390 GetRequests, 2323 SyntacticMatches, 16 SemanticMatches, 51 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 658 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=752, Invalid=2004, Unknown=0, NotChecked=0, Total=2756 [2025-02-08 09:58:46,754 INFO L435 NwaCegarLoop]: 23 mSDtfsCounter, 332 mSDsluCounter, 125 mSDsCounter, 0 mSdLazyCounter, 284 mSolverCounterSat, 141 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 332 SdHoareTripleChecker+Valid, 148 SdHoareTripleChecker+Invalid, 425 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 141 IncrementalHoareTripleChecker+Valid, 284 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-02-08 09:58:46,754 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [332 Valid, 148 Invalid, 425 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [141 Valid, 284 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-02-08 09:58:46,754 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 209 states. [2025-02-08 09:58:46,764 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 209 to 193. [2025-02-08 09:58:46,765 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 193 states, 155 states have (on average 1.032258064516129) internal successors, (160), 151 states have internal predecessors, (160), 23 states have call successors, (23), 14 states have call predecessors, (23), 14 states have return successors, (90), 27 states have call predecessors, (90), 22 states have call successors, (90) [2025-02-08 09:58:46,767 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 193 states to 193 states and 273 transitions. [2025-02-08 09:58:46,767 INFO L78 Accepts]: Start accepts. Automaton has 193 states and 273 transitions. Word has length 1170 [2025-02-08 09:58:46,767 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-08 09:58:46,767 INFO L471 AbstractCegarLoop]: Abstraction has 193 states and 273 transitions. [2025-02-08 09:58:46,768 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 29 states, 29 states have (on average 5.931034482758621) internal successors, (172), 29 states have internal predecessors, (172), 24 states have call successors, (31), 5 states have call predecessors, (31), 11 states have return successors, (34), 13 states have call predecessors, (34), 21 states have call successors, (34) [2025-02-08 09:58:46,768 INFO L276 IsEmpty]: Start isEmpty. Operand 193 states and 273 transitions. [2025-02-08 09:58:46,776 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1355 [2025-02-08 09:58:46,776 INFO L210 NwaCegarLoop]: Found error trace [2025-02-08 09:58:46,776 INFO L218 NwaCegarLoop]: trace histogram [139, 137, 112, 69, 69, 69, 69, 69, 69, 69, 69, 69, 68, 68, 68, 67, 43, 27, 1, 1, 1, 1] [2025-02-08 09:58:46,783 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:58:46,977 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,SelfDestructingSolverStorable17 [2025-02-08 09:58:46,977 INFO L396 AbstractCegarLoop]: === Iteration 19 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 5 more)] === [2025-02-08 09:58:46,977 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-08 09:58:46,977 INFO L85 PathProgramCache]: Analyzing trace with hash 52382542, now seen corresponding path program 11 times [2025-02-08 09:58:46,977 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-08 09:58:46,978 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1971362705] [2025-02-08 09:58:46,978 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2025-02-08 09:58:46,978 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-08 09:58:46,998 INFO L108 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 partitioned 1354 statements into 97 equivalence classes. [2025-02-08 09:58:47,060 INFO L111 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 56 check-sat command(s) and asserted 803 of 1354 statements. [2025-02-08 09:58:47,060 INFO L114 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 56 check-sat command(s) [2025-02-08 09:58:47,060 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 09:58:47,725 INFO L134 CoverageAnalysis]: Checked inductivity of 67286 backedges. 5641 proven. 5132 refuted. 0 times theorem prover too weak. 56513 trivial. 0 not checked. [2025-02-08 09:58:47,725 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-08 09:58:47,725 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1971362705] [2025-02-08 09:58:47,725 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1971362705] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-08 09:58:47,725 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1534452673] [2025-02-08 09:58:47,726 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2025-02-08 09:58:47,726 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-08 09:58:47,726 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-08 09:58:47,727 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 09:58:47,729 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 09:58:47,908 INFO L108 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 partitioned 1354 statements into 97 equivalence classes. [2025-02-08 09:58:48,054 INFO L111 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 56 check-sat command(s) and asserted 803 of 1354 statements. [2025-02-08 09:58:48,055 INFO L114 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 56 check-sat command(s) [2025-02-08 09:58:48,055 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 09:58:48,059 INFO L256 TraceCheckSpWp]: Trace formula consists of 1492 conjuncts, 20 conjuncts are in the unsatisfiable core [2025-02-08 09:58:48,072 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-08 09:58:48,175 INFO L134 CoverageAnalysis]: Checked inductivity of 67286 backedges. 36087 proven. 1171 refuted. 0 times theorem prover too weak. 30028 trivial. 0 not checked. [2025-02-08 09:58:48,175 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-08 09:58:50,737 INFO L134 CoverageAnalysis]: Checked inductivity of 67286 backedges. 5638 proven. 5178 refuted. 0 times theorem prover too weak. 56470 trivial. 0 not checked. [2025-02-08 09:58:50,737 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1534452673] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-08 09:58:50,737 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-08 09:58:50,738 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 14, 21] total 25 [2025-02-08 09:58:50,738 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [754277457] [2025-02-08 09:58:50,738 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-08 09:58:50,739 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 25 states [2025-02-08 09:58:50,739 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-08 09:58:50,740 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2025-02-08 09:58:50,740 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=130, Invalid=470, Unknown=0, NotChecked=0, Total=600 [2025-02-08 09:58:50,740 INFO L87 Difference]: Start difference. First operand 193 states and 273 transitions. Second operand has 25 states, 25 states have (on average 5.96) internal successors, (149), 25 states have internal predecessors, (149), 20 states have call successors, (26), 2 states have call predecessors, (26), 11 states have return successors, (32), 13 states have call predecessors, (32), 20 states have call successors, (32) [2025-02-08 09:58:51,000 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-08 09:58:51,000 INFO L93 Difference]: Finished difference Result 357 states and 540 transitions. [2025-02-08 09:58:51,000 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 25 states. [2025-02-08 09:58:51,001 INFO L78 Accepts]: Start accepts. Automaton has has 25 states, 25 states have (on average 5.96) internal successors, (149), 25 states have internal predecessors, (149), 20 states have call successors, (26), 2 states have call predecessors, (26), 11 states have return successors, (32), 13 states have call predecessors, (32), 20 states have call successors, (32) Word has length 1354 [2025-02-08 09:58:51,001 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-08 09:58:51,002 INFO L225 Difference]: With dead ends: 357 [2025-02-08 09:58:51,002 INFO L226 Difference]: Without dead ends: 169 [2025-02-08 09:58:51,004 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 2744 GetRequests, 2696 SyntacticMatches, 10 SemanticMatches, 38 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 425 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=421, Invalid=1139, Unknown=0, NotChecked=0, Total=1560 [2025-02-08 09:58:51,004 INFO L435 NwaCegarLoop]: 48 mSDtfsCounter, 107 mSDsluCounter, 147 mSDsCounter, 0 mSdLazyCounter, 469 mSolverCounterSat, 57 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 107 SdHoareTripleChecker+Valid, 195 SdHoareTripleChecker+Invalid, 526 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 57 IncrementalHoareTripleChecker+Valid, 469 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-02-08 09:58:51,004 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [107 Valid, 195 Invalid, 526 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [57 Valid, 469 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-02-08 09:58:51,004 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 169 states. [2025-02-08 09:58:51,011 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 169 to 145. [2025-02-08 09:58:51,012 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:58:51,012 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 145 states to 145 states and 192 transitions. [2025-02-08 09:58:51,013 INFO L78 Accepts]: Start accepts. Automaton has 145 states and 192 transitions. Word has length 1354 [2025-02-08 09:58:51,013 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-08 09:58:51,014 INFO L471 AbstractCegarLoop]: Abstraction has 145 states and 192 transitions. [2025-02-08 09:58:51,014 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 25 states, 25 states have (on average 5.96) internal successors, (149), 25 states have internal predecessors, (149), 20 states have call successors, (26), 2 states have call predecessors, (26), 11 states have return successors, (32), 13 states have call predecessors, (32), 20 states have call successors, (32) [2025-02-08 09:58:51,014 INFO L276 IsEmpty]: Start isEmpty. Operand 145 states and 192 transitions. [2025-02-08 09:58:51,020 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1230 [2025-02-08 09:58:51,020 INFO L210 NwaCegarLoop]: Found error trace [2025-02-08 09:58:51,020 INFO L218 NwaCegarLoop]: trace histogram [127, 123, 103, 64, 64, 64, 64, 62, 62, 62, 62, 62, 61, 61, 61, 60, 39, 24, 1, 1, 1, 1] [2025-02-08 09:58:51,028 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 09:58:51,221 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable18,16 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-08 09:58:51,221 INFO L396 AbstractCegarLoop]: === Iteration 20 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 5 more)] === [2025-02-08 09:58:51,221 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-08 09:58:51,221 INFO L85 PathProgramCache]: Analyzing trace with hash -865339205, now seen corresponding path program 12 times [2025-02-08 09:58:51,222 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-08 09:58:51,222 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1955263058] [2025-02-08 09:58:51,222 INFO L95 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2025-02-08 09:58:51,222 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-08 09:58:51,239 INFO L108 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE partitioned 1229 statements into 98 equivalence classes. [2025-02-08 09:58:51,318 INFO L111 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 62 check-sat command(s) and asserted 800 of 1229 statements. [2025-02-08 09:58:51,319 INFO L114 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 62 check-sat command(s) [2025-02-08 09:58:51,319 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 09:58:52,348 INFO L134 CoverageAnalysis]: Checked inductivity of 55363 backedges. 2958 proven. 8146 refuted. 0 times theorem prover too weak. 44259 trivial. 0 not checked. [2025-02-08 09:58:52,348 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-08 09:58:52,348 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1955263058] [2025-02-08 09:58:52,348 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1955263058] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-08 09:58:52,348 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1226279437] [2025-02-08 09:58:52,348 INFO L95 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2025-02-08 09:58:52,349 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-08 09:58:52,349 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-08 09:58:52,351 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 09:58:52,352 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 09:58:52,571 INFO L108 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE partitioned 1229 statements into 98 equivalence classes. [2025-02-08 09:58:52,732 INFO L111 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 62 check-sat command(s) and asserted 800 of 1229 statements. [2025-02-08 09:58:52,732 INFO L114 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 62 check-sat command(s) [2025-02-08 09:58:52,732 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 09:58:52,741 INFO L256 TraceCheckSpWp]: Trace formula consists of 1496 conjuncts, 28 conjuncts are in the unsatisfiable core [2025-02-08 09:58:52,753 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-08 09:58:52,901 INFO L134 CoverageAnalysis]: Checked inductivity of 55363 backedges. 27490 proven. 4465 refuted. 0 times theorem prover too weak. 23408 trivial. 0 not checked. [2025-02-08 09:58:52,901 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-08 09:58:54,790 INFO L134 CoverageAnalysis]: Checked inductivity of 55363 backedges. 3156 proven. 8576 refuted. 0 times theorem prover too weak. 43631 trivial. 0 not checked. [2025-02-08 09:58:54,791 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1226279437] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-08 09:58:54,791 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-08 09:58:54,791 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [23, 19, 27] total 34 [2025-02-08 09:58:54,791 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [361745938] [2025-02-08 09:58:54,791 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-08 09:58:54,792 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 34 states [2025-02-08 09:58:54,792 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-08 09:58:54,793 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 34 interpolants. [2025-02-08 09:58:54,793 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=197, Invalid=925, Unknown=0, NotChecked=0, Total=1122 [2025-02-08 09:58:54,793 INFO L87 Difference]: Start difference. First operand 145 states and 192 transitions. Second operand has 34 states, 34 states have (on average 5.676470588235294) internal successors, (193), 33 states have internal predecessors, (193), 28 states have call successors, (35), 5 states have call predecessors, (35), 12 states have return successors, (38), 15 states have call predecessors, (38), 25 states have call successors, (38) [2025-02-08 09:58:55,224 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-08 09:58:55,224 INFO L93 Difference]: Finished difference Result 346 states and 498 transitions. [2025-02-08 09:58:55,225 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 36 states. [2025-02-08 09:58:55,225 INFO L78 Accepts]: Start accepts. Automaton has has 34 states, 34 states have (on average 5.676470588235294) internal successors, (193), 33 states have internal predecessors, (193), 28 states have call successors, (35), 5 states have call predecessors, (35), 12 states have return successors, (38), 15 states have call predecessors, (38), 25 states have call successors, (38) Word has length 1229 [2025-02-08 09:58:55,226 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-08 09:58:55,227 INFO L225 Difference]: With dead ends: 346 [2025-02-08 09:58:55,227 INFO L226 Difference]: Without dead ends: 206 [2025-02-08 09:58:55,229 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 2521 GetRequests, 2442 SyntacticMatches, 17 SemanticMatches, 62 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1265 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=1035, Invalid=2997, Unknown=0, NotChecked=0, Total=4032 [2025-02-08 09:58:55,229 INFO L435 NwaCegarLoop]: 27 mSDtfsCounter, 458 mSDsluCounter, 152 mSDsCounter, 0 mSdLazyCounter, 363 mSolverCounterSat, 191 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 458 SdHoareTripleChecker+Valid, 179 SdHoareTripleChecker+Invalid, 554 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 191 IncrementalHoareTripleChecker+Valid, 363 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-02-08 09:58:55,230 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [458 Valid, 179 Invalid, 554 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [191 Valid, 363 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-02-08 09:58:55,230 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 206 states. [2025-02-08 09:58:55,238 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 206 to 184. [2025-02-08 09:58:55,239 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 184 states, 149 states have (on average 1.0335570469798658) internal successors, (154), 145 states have internal predecessors, (154), 23 states have call successors, (23), 17 states have call predecessors, (23), 11 states have return successors, (64), 21 states have call predecessors, (64), 22 states have call successors, (64) [2025-02-08 09:58:55,241 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 184 states to 184 states and 241 transitions. [2025-02-08 09:58:55,241 INFO L78 Accepts]: Start accepts. Automaton has 184 states and 241 transitions. Word has length 1229 [2025-02-08 09:58:55,242 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-08 09:58:55,242 INFO L471 AbstractCegarLoop]: Abstraction has 184 states and 241 transitions. [2025-02-08 09:58:55,243 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 34 states, 34 states have (on average 5.676470588235294) internal successors, (193), 33 states have internal predecessors, (193), 28 states have call successors, (35), 5 states have call predecessors, (35), 12 states have return successors, (38), 15 states have call predecessors, (38), 25 states have call successors, (38) [2025-02-08 09:58:55,243 INFO L276 IsEmpty]: Start isEmpty. Operand 184 states and 241 transitions. [2025-02-08 09:58:55,247 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 968 [2025-02-08 09:58:55,247 INFO L210 NwaCegarLoop]: Found error trace [2025-02-08 09:58:55,247 INFO L218 NwaCegarLoop]: trace histogram [99, 98, 80, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 48, 31, 19, 1, 1, 1, 1] [2025-02-08 09:58:55,255 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 09:58:55,448 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable19,17 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-08 09:58:55,448 INFO L396 AbstractCegarLoop]: === Iteration 21 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 5 more)] === [2025-02-08 09:58:55,448 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-08 09:58:55,448 INFO L85 PathProgramCache]: Analyzing trace with hash 2052943363, now seen corresponding path program 13 times [2025-02-08 09:58:55,449 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-08 09:58:55,449 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [165491107] [2025-02-08 09:58:55,449 INFO L95 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2025-02-08 09:58:55,449 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-08 09:58:55,463 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 967 statements into 1 equivalence classes. [2025-02-08 09:58:55,507 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 967 of 967 statements. [2025-02-08 09:58:55,507 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 09:58:55,507 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 09:58:56,504 INFO L134 CoverageAnalysis]: Checked inductivity of 34128 backedges. 3250 proven. 6227 refuted. 0 times theorem prover too weak. 24651 trivial. 0 not checked. [2025-02-08 09:58:56,504 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-08 09:58:56,505 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [165491107] [2025-02-08 09:58:56,505 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [165491107] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-08 09:58:56,505 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [809305670] [2025-02-08 09:58:56,505 INFO L95 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2025-02-08 09:58:56,505 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-08 09:58:56,505 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-08 09:58:56,506 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 09:58:56,507 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 09:58:56,686 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 967 statements into 1 equivalence classes. [2025-02-08 09:58:56,796 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 967 of 967 statements. [2025-02-08 09:58:56,796 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 09:58:56,796 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 09:58:56,800 INFO L256 TraceCheckSpWp]: Trace formula consists of 1809 conjuncts, 26 conjuncts are in the unsatisfiable core [2025-02-08 09:58:56,806 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-08 09:58:56,937 INFO L134 CoverageAnalysis]: Checked inductivity of 34128 backedges. 18682 proven. 2667 refuted. 0 times theorem prover too weak. 12779 trivial. 0 not checked. [2025-02-08 09:58:56,937 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-08 09:59:00,050 INFO L134 CoverageAnalysis]: Checked inductivity of 34128 backedges. 2705 proven. 6933 refuted. 0 times theorem prover too weak. 24490 trivial. 0 not checked. [2025-02-08 09:59:00,050 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [809305670] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-08 09:59:00,050 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-08 09:59:00,050 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 17, 27] total 29 [2025-02-08 09:59:00,051 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [96450593] [2025-02-08 09:59:00,051 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-08 09:59:00,051 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 29 states [2025-02-08 09:59:00,051 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-08 09:59:00,052 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 29 interpolants. [2025-02-08 09:59:00,052 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=146, Invalid=666, Unknown=0, NotChecked=0, Total=812 [2025-02-08 09:59:00,053 INFO L87 Difference]: Start difference. First operand 184 states and 241 transitions. Second operand has 29 states, 29 states have (on average 6.310344827586207) internal successors, (183), 29 states have internal predecessors, (183), 26 states have call successors, (31), 2 states have call predecessors, (31), 14 states have return successors, (40), 14 states have call predecessors, (40), 26 states have call successors, (40) [2025-02-08 09:59:00,442 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-08 09:59:00,443 INFO L93 Difference]: Finished difference Result 363 states and 492 transitions. [2025-02-08 09:59:00,443 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2025-02-08 09:59:00,443 INFO L78 Accepts]: Start accepts. Automaton has has 29 states, 29 states have (on average 6.310344827586207) internal successors, (183), 29 states have internal predecessors, (183), 26 states have call successors, (31), 2 states have call predecessors, (31), 14 states have return successors, (40), 14 states have call predecessors, (40), 26 states have call successors, (40) Word has length 967 [2025-02-08 09:59:00,444 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-08 09:59:00,446 INFO L225 Difference]: With dead ends: 363 [2025-02-08 09:59:00,446 INFO L226 Difference]: Without dead ends: 184 [2025-02-08 09:59:00,448 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 1978 GetRequests, 1920 SyntacticMatches, 13 SemanticMatches, 45 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 488 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=560, Invalid=1602, Unknown=0, NotChecked=0, Total=2162 [2025-02-08 09:59:00,448 INFO L435 NwaCegarLoop]: 55 mSDtfsCounter, 260 mSDsluCounter, 241 mSDsCounter, 0 mSdLazyCounter, 692 mSolverCounterSat, 118 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 260 SdHoareTripleChecker+Valid, 296 SdHoareTripleChecker+Invalid, 810 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 118 IncrementalHoareTripleChecker+Valid, 692 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2025-02-08 09:59:00,448 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [260 Valid, 296 Invalid, 810 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [118 Valid, 692 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2025-02-08 09:59:00,449 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 184 states. [2025-02-08 09:59:00,457 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 184 to 148. [2025-02-08 09:59:00,459 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 148 states, 119 states have (on average 1.0252100840336134) internal successors, (122), 117 states have internal predecessors, (122), 19 states have call successors, (19), 14 states have call predecessors, (19), 9 states have return successors, (45), 16 states have call predecessors, (45), 18 states have call successors, (45) [2025-02-08 09:59:00,460 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 148 states to 148 states and 186 transitions. [2025-02-08 09:59:00,461 INFO L78 Accepts]: Start accepts. Automaton has 148 states and 186 transitions. Word has length 967 [2025-02-08 09:59:00,462 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-08 09:59:00,462 INFO L471 AbstractCegarLoop]: Abstraction has 148 states and 186 transitions. [2025-02-08 09:59:00,462 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 29 states, 29 states have (on average 6.310344827586207) internal successors, (183), 29 states have internal predecessors, (183), 26 states have call successors, (31), 2 states have call predecessors, (31), 14 states have return successors, (40), 14 states have call predecessors, (40), 26 states have call successors, (40) [2025-02-08 09:59:00,462 INFO L276 IsEmpty]: Start isEmpty. Operand 148 states and 186 transitions. [2025-02-08 09:59:00,474 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1577 [2025-02-08 09:59:00,475 INFO L210 NwaCegarLoop]: Found error trace [2025-02-08 09:59:00,475 INFO L218 NwaCegarLoop]: trace histogram [162, 159, 131, 81, 81, 81, 81, 80, 80, 80, 80, 80, 79, 79, 79, 78, 50, 31, 1, 1, 1, 1] [2025-02-08 09:59:00,488 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 09:59:00,675 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable20,18 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-08 09:59:00,676 INFO L396 AbstractCegarLoop]: === Iteration 22 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 5 more)] === [2025-02-08 09:59:00,676 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-08 09:59:00,676 INFO L85 PathProgramCache]: Analyzing trace with hash -989774729, now seen corresponding path program 14 times [2025-02-08 09:59:00,676 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-08 09:59:00,676 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1332144701] [2025-02-08 09:59:00,677 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-02-08 09:59:00,677 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-08 09:59:00,703 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 1576 statements into 2 equivalence classes. [2025-02-08 09:59:00,797 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 1576 of 1576 statements. [2025-02-08 09:59:00,798 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-02-08 09:59:00,798 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 09:59:03,565 INFO L134 CoverageAnalysis]: Checked inductivity of 91322 backedges. 4385 proven. 12646 refuted. 0 times theorem prover too weak. 74291 trivial. 0 not checked. [2025-02-08 09:59:03,565 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-08 09:59:03,565 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1332144701] [2025-02-08 09:59:03,565 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1332144701] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-08 09:59:03,565 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [505923961] [2025-02-08 09:59:03,565 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-02-08 09:59:03,565 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-08 09:59:03,565 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-08 09:59:03,567 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 09:59:03,568 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 09:59:03,830 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 1576 statements into 2 equivalence classes. [2025-02-08 09:59:04,066 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 1576 of 1576 statements. [2025-02-08 09:59:04,067 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-02-08 09:59:04,067 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 09:59:04,073 INFO L256 TraceCheckSpWp]: Trace formula consists of 2933 conjuncts, 34 conjuncts are in the unsatisfiable core [2025-02-08 09:59:04,088 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-08 09:59:04,313 INFO L134 CoverageAnalysis]: Checked inductivity of 91322 backedges. 29124 proven. 10901 refuted. 0 times theorem prover too weak. 51297 trivial. 0 not checked. [2025-02-08 09:59:04,313 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-08 09:59:07,705 INFO L134 CoverageAnalysis]: Checked inductivity of 91322 backedges. 5314 proven. 14273 refuted. 0 times theorem prover too weak. 71735 trivial. 0 not checked. [2025-02-08 09:59:07,705 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [505923961] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-08 09:59:07,705 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-08 09:59:07,706 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 21, 33] total 38 [2025-02-08 09:59:07,706 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1935557947] [2025-02-08 09:59:07,706 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-08 09:59:07,707 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 38 states [2025-02-08 09:59:07,707 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-08 09:59:07,708 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 38 interpolants. [2025-02-08 09:59:07,708 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=214, Invalid=1192, Unknown=0, NotChecked=0, Total=1406 [2025-02-08 09:59:07,708 INFO L87 Difference]: Start difference. First operand 148 states and 186 transitions. Second operand has 38 states, 38 states have (on average 5.973684210526316) internal successors, (227), 38 states have internal predecessors, (227), 33 states have call successors, (40), 4 states have call predecessors, (40), 16 states have return successors, (49), 18 states have call predecessors, (49), 31 states have call successors, (49) [2025-02-08 09:59:08,407 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-08 09:59:08,407 INFO L93 Difference]: Finished difference Result 376 states and 514 transitions. [2025-02-08 09:59:08,408 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 51 states. [2025-02-08 09:59:08,408 INFO L78 Accepts]: Start accepts. Automaton has has 38 states, 38 states have (on average 5.973684210526316) internal successors, (227), 38 states have internal predecessors, (227), 33 states have call successors, (40), 4 states have call predecessors, (40), 16 states have return successors, (49), 18 states have call predecessors, (49), 31 states have call successors, (49) Word has length 1576 [2025-02-08 09:59:08,409 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-08 09:59:08,410 INFO L225 Difference]: With dead ends: 376 [2025-02-08 09:59:08,410 INFO L226 Difference]: Without dead ends: 233 [2025-02-08 09:59:08,413 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 3230 GetRequests, 3131 SyntacticMatches, 19 SemanticMatches, 80 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1755 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=1599, Invalid=5043, Unknown=0, NotChecked=0, Total=6642 [2025-02-08 09:59:08,417 INFO L435 NwaCegarLoop]: 41 mSDtfsCounter, 748 mSDsluCounter, 170 mSDsCounter, 0 mSdLazyCounter, 502 mSolverCounterSat, 271 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 748 SdHoareTripleChecker+Valid, 211 SdHoareTripleChecker+Invalid, 773 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 271 IncrementalHoareTripleChecker+Valid, 502 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2025-02-08 09:59:08,417 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [748 Valid, 211 Invalid, 773 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [271 Valid, 502 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2025-02-08 09:59:08,419 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 233 states. [2025-02-08 09:59:08,429 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 233 to 190. [2025-02-08 09:59:08,429 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 190 states, 154 states have (on average 1.0324675324675325) internal successors, (159), 151 states have internal predecessors, (159), 25 states have call successors, (25), 20 states have call predecessors, (25), 10 states have return successors, (63), 18 states have call predecessors, (63), 24 states have call successors, (63) [2025-02-08 09:59:08,430 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 190 states to 190 states and 247 transitions. [2025-02-08 09:59:08,431 INFO L78 Accepts]: Start accepts. Automaton has 190 states and 247 transitions. Word has length 1576 [2025-02-08 09:59:08,431 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-08 09:59:08,431 INFO L471 AbstractCegarLoop]: Abstraction has 190 states and 247 transitions. [2025-02-08 09:59:08,431 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 38 states, 38 states have (on average 5.973684210526316) internal successors, (227), 38 states have internal predecessors, (227), 33 states have call successors, (40), 4 states have call predecessors, (40), 16 states have return successors, (49), 18 states have call predecessors, (49), 31 states have call successors, (49) [2025-02-08 09:59:08,432 INFO L276 IsEmpty]: Start isEmpty. Operand 190 states and 247 transitions. [2025-02-08 09:59:08,435 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 915 [2025-02-08 09:59:08,436 INFO L210 NwaCegarLoop]: Found error trace [2025-02-08 09:59:08,436 INFO L218 NwaCegarLoop]: trace histogram [94, 92, 76, 47, 47, 47, 47, 46, 46, 46, 46, 46, 46, 46, 46, 45, 29, 18, 1, 1, 1, 1] [2025-02-08 09:59:08,445 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 09:59:08,636 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable21,19 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-08 09:59:08,636 INFO L396 AbstractCegarLoop]: === Iteration 23 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 5 more)] === [2025-02-08 09:59:08,637 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-08 09:59:08,637 INFO L85 PathProgramCache]: Analyzing trace with hash 1035728743, now seen corresponding path program 15 times [2025-02-08 09:59:08,637 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-08 09:59:08,637 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [774783622] [2025-02-08 09:59:08,637 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-02-08 09:59:08,637 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-08 09:59:08,651 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 914 statements into 66 equivalence classes. [2025-02-08 09:59:08,676 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 41 check-sat command(s) and asserted 552 of 914 statements. [2025-02-08 09:59:08,676 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 41 check-sat command(s) [2025-02-08 09:59:08,676 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 09:59:09,063 INFO L134 CoverageAnalysis]: Checked inductivity of 30452 backedges. 4481 proven. 1382 refuted. 0 times theorem prover too weak. 24589 trivial. 0 not checked. [2025-02-08 09:59:09,063 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-08 09:59:09,063 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [774783622] [2025-02-08 09:59:09,063 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [774783622] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-08 09:59:09,063 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1064413181] [2025-02-08 09:59:09,063 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-02-08 09:59:09,063 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-08 09:59:09,063 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-08 09:59:09,065 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 09:59:09,065 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 09:59:09,291 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 914 statements into 66 equivalence classes. [2025-02-08 09:59:09,380 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 41 check-sat command(s) and asserted 552 of 914 statements. [2025-02-08 09:59:09,380 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 41 check-sat command(s) [2025-02-08 09:59:09,380 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 09:59:09,383 INFO L256 TraceCheckSpWp]: Trace formula consists of 1036 conjuncts, 20 conjuncts are in the unsatisfiable core [2025-02-08 09:59:09,388 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-08 09:59:09,518 INFO L134 CoverageAnalysis]: Checked inductivity of 30452 backedges. 4680 proven. 1482 refuted. 0 times theorem prover too weak. 24290 trivial. 0 not checked. [2025-02-08 09:59:09,518 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-08 09:59:10,885 INFO L134 CoverageAnalysis]: Checked inductivity of 30452 backedges. 4688 proven. 1545 refuted. 0 times theorem prover too weak. 24219 trivial. 0 not checked. [2025-02-08 09:59:10,885 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1064413181] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-08 09:59:10,885 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-08 09:59:10,886 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 14, 21] total 26 [2025-02-08 09:59:10,886 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1445448535] [2025-02-08 09:59:10,886 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-08 09:59:10,887 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 26 states [2025-02-08 09:59:10,887 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-08 09:59:10,887 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2025-02-08 09:59:10,887 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=124, Invalid=526, Unknown=0, NotChecked=0, Total=650 [2025-02-08 09:59:10,887 INFO L87 Difference]: Start difference. First operand 190 states and 247 transitions. Second operand has 26 states, 26 states have (on average 5.384615384615385) internal successors, (140), 26 states have internal predecessors, (140), 14 states have call successors, (24), 1 states have call predecessors, (24), 10 states have return successors, (29), 18 states have call predecessors, (29), 14 states have call successors, (29) [2025-02-08 09:59:11,162 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-08 09:59:11,162 INFO L93 Difference]: Finished difference Result 421 states and 551 transitions. [2025-02-08 09:59:11,163 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 30 states. [2025-02-08 09:59:11,163 INFO L78 Accepts]: Start accepts. Automaton has has 26 states, 26 states have (on average 5.384615384615385) internal successors, (140), 26 states have internal predecessors, (140), 14 states have call successors, (24), 1 states have call predecessors, (24), 10 states have return successors, (29), 18 states have call predecessors, (29), 14 states have call successors, (29) Word has length 914 [2025-02-08 09:59:11,163 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-08 09:59:11,165 INFO L225 Difference]: With dead ends: 421 [2025-02-08 09:59:11,165 INFO L226 Difference]: Without dead ends: 216 [2025-02-08 09:59:11,166 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 1869 GetRequests, 1814 SyntacticMatches, 10 SemanticMatches, 45 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 521 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=578, Invalid=1584, Unknown=0, NotChecked=0, Total=2162 [2025-02-08 09:59:11,166 INFO L435 NwaCegarLoop]: 39 mSDtfsCounter, 91 mSDsluCounter, 145 mSDsCounter, 0 mSdLazyCounter, 459 mSolverCounterSat, 55 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 91 SdHoareTripleChecker+Valid, 184 SdHoareTripleChecker+Invalid, 514 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 55 IncrementalHoareTripleChecker+Valid, 459 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-02-08 09:59:11,166 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [91 Valid, 184 Invalid, 514 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [55 Valid, 459 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-02-08 09:59:11,167 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 216 states. [2025-02-08 09:59:11,175 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 216 to 187. [2025-02-08 09:59:11,175 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 187 states, 151 states have (on average 1.0264900662251655) internal successors, (155), 149 states have internal predecessors, (155), 25 states have call successors, (25), 20 states have call predecessors, (25), 10 states have return successors, (52), 17 states have call predecessors, (52), 24 states have call successors, (52) [2025-02-08 09:59:11,176 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 187 states to 187 states and 232 transitions. [2025-02-08 09:59:11,176 INFO L78 Accepts]: Start accepts. Automaton has 187 states and 232 transitions. Word has length 914 [2025-02-08 09:59:11,177 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-08 09:59:11,177 INFO L471 AbstractCegarLoop]: Abstraction has 187 states and 232 transitions. [2025-02-08 09:59:11,177 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 26 states, 26 states have (on average 5.384615384615385) internal successors, (140), 26 states have internal predecessors, (140), 14 states have call successors, (24), 1 states have call predecessors, (24), 10 states have return successors, (29), 18 states have call predecessors, (29), 14 states have call successors, (29) [2025-02-08 09:59:11,177 INFO L276 IsEmpty]: Start isEmpty. Operand 187 states and 232 transitions. [2025-02-08 09:59:11,182 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1066 [2025-02-08 09:59:11,182 INFO L210 NwaCegarLoop]: Found error trace [2025-02-08 09:59:11,182 INFO L218 NwaCegarLoop]: trace histogram [109, 108, 88, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 53, 34, 21, 1, 1, 1, 1] [2025-02-08 09:59:11,190 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 09:59:11,382 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable22,20 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-08 09:59:11,383 INFO L396 AbstractCegarLoop]: === Iteration 24 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 5 more)] === [2025-02-08 09:59:11,383 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-08 09:59:11,383 INFO L85 PathProgramCache]: Analyzing trace with hash 560042553, now seen corresponding path program 16 times [2025-02-08 09:59:11,383 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-08 09:59:11,383 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [880358679] [2025-02-08 09:59:11,383 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-02-08 09:59:11,383 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-08 09:59:11,399 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 1065 statements into 2 equivalence classes. [2025-02-08 09:59:11,436 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) and asserted 1065 of 1065 statements. [2025-02-08 09:59:11,436 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) [2025-02-08 09:59:11,436 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 09:59:26,157 INFO L134 CoverageAnalysis]: Checked inductivity of 41466 backedges. 6976 proven. 7865 refuted. 0 times theorem prover too weak. 26625 trivial. 0 not checked. [2025-02-08 09:59:26,157 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-08 09:59:26,157 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [880358679] [2025-02-08 09:59:26,157 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [880358679] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-08 09:59:26,157 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1369960478] [2025-02-08 09:59:26,157 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-02-08 09:59:26,157 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-08 09:59:26,157 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-08 09:59:26,159 INFO L229 MonitoredProcess]: Starting monitored process 21 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,160 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Waiting until timeout for monitored process [2025-02-08 09:59:26,403 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 1065 statements into 2 equivalence classes. [2025-02-08 09:59:26,530 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) and asserted 1065 of 1065 statements. [2025-02-08 09:59:26,530 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) [2025-02-08 09:59:26,530 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 09:59:26,536 INFO L256 TraceCheckSpWp]: Trace formula consists of 1990 conjuncts, 217 conjuncts are in the unsatisfiable core [2025-02-08 09:59:26,543 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-08 09:59:27,164 INFO L134 CoverageAnalysis]: Checked inductivity of 41466 backedges. 6686 proven. 7855 refuted. 0 times theorem prover too weak. 26925 trivial. 0 not checked. [2025-02-08 09:59:27,165 INFO L312 TraceCheckSpWp]: Computing backward predicates...