./Ultimate.py --spec ../sv-benchmarks/c/properties/no-overflow.prp --file ../sv-benchmarks/c/recursive/Fibonacci04.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for overflows Using default analysis Version 551b0097 Calling Ultimate with: /root/.sdkman/candidates/java/21.0.5-tem/bin/java -Dosgi.configuration.area=/storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.6.800.v20240513-1750.jar -data @noDefault -ultimatedata /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/recursive/Fibonacci04.c -s /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/config/svcomp-Overflow-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(G ! overflow) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash 8d1a4b1841ad6fa39491d7c82c38d46725a7eceb7c19c007d9e026b8eedadeb5 --- Real Ultimate output --- This is Ultimate 0.3.0-?-551b009-m [2025-01-10 02:30:24,178 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-01-10 02:30:24,235 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/config/svcomp-Overflow-32bit-Automizer_Default.epf [2025-01-10 02:30:24,242 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-01-10 02:30:24,242 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-01-10 02:30:24,257 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-01-10 02:30:24,258 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-01-10 02:30:24,258 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-01-10 02:30:24,258 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-01-10 02:30:24,258 INFO L153 SettingsManager]: * Use memory slicer=true [2025-01-10 02:30:24,258 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2025-01-10 02:30:24,258 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2025-01-10 02:30:24,259 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-01-10 02:30:24,259 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-01-10 02:30:24,259 INFO L153 SettingsManager]: * Use SBE=true [2025-01-10 02:30:24,259 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-01-10 02:30:24,259 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2025-01-10 02:30:24,259 INFO L153 SettingsManager]: * sizeof long=4 [2025-01-10 02:30:24,259 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2025-01-10 02:30:24,259 INFO L153 SettingsManager]: * sizeof POINTER=4 [2025-01-10 02:30:24,259 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-01-10 02:30:24,260 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2025-01-10 02:30:24,260 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2025-01-10 02:30:24,260 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2025-01-10 02:30:24,260 INFO L153 SettingsManager]: * Check absence of signed integer overflows=ASSERTandASSUME [2025-01-10 02:30:24,260 INFO L153 SettingsManager]: * Check unreachability of reach_error function=false [2025-01-10 02:30:24,260 INFO L153 SettingsManager]: * sizeof long double=12 [2025-01-10 02:30:24,260 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-01-10 02:30:24,260 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-01-10 02:30:24,260 INFO L153 SettingsManager]: * Use constant arrays=true [2025-01-10 02:30:24,260 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-01-10 02:30:24,260 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-01-10 02:30:24,261 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-01-10 02:30:24,261 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-01-10 02:30:24,261 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-01-10 02:30:24,261 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2025-01-10 02:30:24,261 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-01-10 02:30:24,261 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-01-10 02:30:24,261 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-01-10 02:30:24,261 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-01-10 02:30:24,261 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-01-10 02:30:24,261 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2025-01-10 02:30:24,262 INFO L153 SettingsManager]: * Compute procedure contracts=false [2025-01-10 02:30:24,262 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2025-01-10 02:30:24,262 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2025-01-10 02:30:24,262 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2025-01-10 02:30:24,262 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2025-01-10 02:30:24,262 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2025-01-10 02:30:24,262 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2025-01-10 02:30:24,262 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2025-01-10 02:30:24,262 INFO L153 SettingsManager]: * Looper check in Petri net analysis=SEMANTIC Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Entry function -> main Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness directory -> /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Write witness besides input file -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data specification -> CHECK( init(main()), LTL(G ! overflow) ) Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data producer -> Automizer Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data architecture -> 32bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> 8d1a4b1841ad6fa39491d7c82c38d46725a7eceb7c19c007d9e026b8eedadeb5 [2025-01-10 02:30:24,434 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-01-10 02:30:24,439 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-01-10 02:30:24,441 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-01-10 02:30:24,442 INFO L270 PluginConnector]: Initializing CDTParser... [2025-01-10 02:30:24,442 INFO L274 PluginConnector]: CDTParser initialized [2025-01-10 02:30:24,443 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/recursive/Fibonacci04.c [2025-01-10 02:30:25,547 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/a51fa8368/1c488e73aac6461a977fa1e6a87dd1bf/FLAGced41841f [2025-01-10 02:30:25,826 INFO L384 CDTParser]: Found 1 translation units. [2025-01-10 02:30:25,826 INFO L180 CDTParser]: Scanning /storage/repos/ultimate-jdk21/releaseScripts/default/sv-benchmarks/c/recursive/Fibonacci04.c [2025-01-10 02:30:25,833 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/a51fa8368/1c488e73aac6461a977fa1e6a87dd1bf/FLAGced41841f [2025-01-10 02:30:25,849 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/a51fa8368/1c488e73aac6461a977fa1e6a87dd1bf [2025-01-10 02:30:25,850 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-01-10 02:30:25,853 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-01-10 02:30:25,854 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-01-10 02:30:25,855 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-01-10 02:30:25,859 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-01-10 02:30:25,859 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 10.01 02:30:25" (1/1) ... [2025-01-10 02:30:25,860 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@359c797e and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.01 02:30:25, skipping insertion in model container [2025-01-10 02:30:25,860 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 10.01 02:30:25" (1/1) ... [2025-01-10 02:30:25,870 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-01-10 02:30:25,984 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-01-10 02:30:25,993 INFO L200 MainTranslator]: Completed pre-run [2025-01-10 02:30:26,002 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-01-10 02:30:26,012 INFO L204 MainTranslator]: Completed translation [2025-01-10 02:30:26,014 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.01 02:30:26 WrapperNode [2025-01-10 02:30:26,015 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-01-10 02:30:26,015 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-01-10 02:30:26,016 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-01-10 02:30:26,016 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-01-10 02:30:26,022 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.01 02:30:26" (1/1) ... [2025-01-10 02:30:26,027 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.01 02:30:26" (1/1) ... [2025-01-10 02:30:26,038 INFO L138 Inliner]: procedures = 13, calls = 11, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 27 [2025-01-10 02:30:26,038 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-01-10 02:30:26,039 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-01-10 02:30:26,039 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-01-10 02:30:26,039 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-01-10 02:30:26,045 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.01 02:30:26" (1/1) ... [2025-01-10 02:30:26,046 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.01 02:30:26" (1/1) ... [2025-01-10 02:30:26,051 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.01 02:30:26" (1/1) ... [2025-01-10 02:30:26,060 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-01-10 02:30:26,060 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.01 02:30:26" (1/1) ... [2025-01-10 02:30:26,060 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.01 02:30:26" (1/1) ... [2025-01-10 02:30:26,066 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.01 02:30:26" (1/1) ... [2025-01-10 02:30:26,066 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.01 02:30:26" (1/1) ... [2025-01-10 02:30:26,067 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.01 02:30:26" (1/1) ... [2025-01-10 02:30:26,068 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.01 02:30:26" (1/1) ... [2025-01-10 02:30:26,068 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.01 02:30:26" (1/1) ... [2025-01-10 02:30:26,070 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-01-10 02:30:26,075 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2025-01-10 02:30:26,075 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2025-01-10 02:30:26,075 INFO L274 PluginConnector]: RCFGBuilder initialized [2025-01-10 02:30:26,076 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.01 02:30:26" (1/1) ... [2025-01-10 02:30:26,081 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-01-10 02:30:26,095 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-10 02:30:26,118 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-01-10 02:30:26,121 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-01-10 02:30:26,140 INFO L130 BoogieDeclarations]: Found specification of procedure fibonacci [2025-01-10 02:30:26,140 INFO L138 BoogieDeclarations]: Found implementation of procedure fibonacci [2025-01-10 02:30:26,140 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2025-01-10 02:30:26,140 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-01-10 02:30:26,141 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-01-10 02:30:26,141 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2025-01-10 02:30:26,179 INFO L234 CfgBuilder]: Building ICFG [2025-01-10 02:30:26,181 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2025-01-10 02:30:26,292 INFO L? ?]: Removed 17 outVars from TransFormulas that were not future-live. [2025-01-10 02:30:26,292 INFO L283 CfgBuilder]: Performing block encoding [2025-01-10 02:30:26,301 INFO L307 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-01-10 02:30:26,301 INFO L312 CfgBuilder]: Removed 0 assume(true) statements. [2025-01-10 02:30:26,302 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 10.01 02:30:26 BoogieIcfgContainer [2025-01-10 02:30:26,302 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2025-01-10 02:30:26,303 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2025-01-10 02:30:26,303 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2025-01-10 02:30:26,306 INFO L274 PluginConnector]: TraceAbstraction initialized [2025-01-10 02:30:26,306 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 10.01 02:30:25" (1/3) ... [2025-01-10 02:30:26,307 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6ee96fb1 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 10.01 02:30:26, skipping insertion in model container [2025-01-10 02:30:26,307 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.01 02:30:26" (2/3) ... [2025-01-10 02:30:26,307 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6ee96fb1 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 10.01 02:30:26, skipping insertion in model container [2025-01-10 02:30:26,307 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 10.01 02:30:26" (3/3) ... [2025-01-10 02:30:26,308 INFO L128 eAbstractionObserver]: Analyzing ICFG Fibonacci04.c [2025-01-10 02:30:26,317 INFO L216 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2025-01-10 02:30:26,318 INFO L151 ceAbstractionStarter]: Applying trace abstraction to ICFG Fibonacci04.c that has 2 procedures, 32 locations, 1 initial locations, 0 loop locations, and 6 error locations. [2025-01-10 02:30:26,349 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2025-01-10 02:30:26,356 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;@7b8980c3, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2025-01-10 02:30:26,357 INFO L334 AbstractCegarLoop]: Starting to check reachability of 6 error locations. [2025-01-10 02:30:26,359 INFO L276 IsEmpty]: Start isEmpty. Operand has 32 states, 21 states have (on average 1.4761904761904763) internal successors, (31), 27 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-01-10 02:30:26,362 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 9 [2025-01-10 02:30:26,363 INFO L210 NwaCegarLoop]: Found error trace [2025-01-10 02:30:26,363 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2025-01-10 02:30:26,363 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-01-10 02:30:26,366 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-10 02:30:26,366 INFO L85 PathProgramCache]: Analyzing trace with hash 629029755, now seen corresponding path program 1 times [2025-01-10 02:30:26,371 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-10 02:30:26,371 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1566704081] [2025-01-10 02:30:26,372 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-10 02:30:26,372 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-10 02:30:26,412 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 8 statements into 1 equivalence classes. [2025-01-10 02:30:26,422 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 8 of 8 statements. [2025-01-10 02:30:26,422 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-10 02:30:26,423 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 02:30:26,464 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-01-10 02:30:26,465 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-10 02:30:26,465 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1566704081] [2025-01-10 02:30:26,465 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1566704081] provided 1 perfect and 0 imperfect interpolant sequences [2025-01-10 02:30:26,466 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-01-10 02:30:26,466 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2025-01-10 02:30:26,467 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [134120366] [2025-01-10 02:30:26,467 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-01-10 02:30:26,469 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2025-01-10 02:30:26,470 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-10 02:30:26,480 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2025-01-10 02:30:26,480 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2025-01-10 02:30:26,482 INFO L87 Difference]: Start difference. First operand has 32 states, 21 states have (on average 1.4761904761904763) internal successors, (31), 27 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.5) internal successors, (7), 3 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-01-10 02:30:26,507 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-10 02:30:26,507 INFO L93 Difference]: Finished difference Result 37 states and 43 transitions. [2025-01-10 02:30:26,508 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2025-01-10 02:30:26,508 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 2 states have (on average 3.5) internal successors, (7), 3 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-01-10 02:30:26,509 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-10 02:30:26,512 INFO L225 Difference]: With dead ends: 37 [2025-01-10 02:30:26,512 INFO L226 Difference]: Without dead ends: 25 [2025-01-10 02:30:26,514 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-01-10 02:30:26,515 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-01-10 02:30:26,516 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-01-10 02:30:26,524 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 25 states. [2025-01-10 02:30:26,534 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 25 to 23. [2025-01-10 02:30:26,535 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 23 states, 15 states have (on average 1.4) internal successors, (21), 19 states have internal predecessors, (21), 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-01-10 02:30:26,537 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 23 states to 23 states and 26 transitions. [2025-01-10 02:30:26,538 INFO L78 Accepts]: Start accepts. Automaton has 23 states and 26 transitions. Word has length 8 [2025-01-10 02:30:26,538 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-10 02:30:26,538 INFO L471 AbstractCegarLoop]: Abstraction has 23 states and 26 transitions. [2025-01-10 02:30:26,538 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 2 states have (on average 3.5) internal successors, (7), 3 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-01-10 02:30:26,538 INFO L276 IsEmpty]: Start isEmpty. Operand 23 states and 26 transitions. [2025-01-10 02:30:26,539 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 10 [2025-01-10 02:30:26,539 INFO L210 NwaCegarLoop]: Found error trace [2025-01-10 02:30:26,539 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-01-10 02:30:26,539 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2025-01-10 02:30:26,539 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-01-10 02:30:26,539 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-10 02:30:26,539 INFO L85 PathProgramCache]: Analyzing trace with hash -1974914033, now seen corresponding path program 1 times [2025-01-10 02:30:26,539 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-10 02:30:26,540 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1216291043] [2025-01-10 02:30:26,540 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-10 02:30:26,540 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-10 02:30:26,543 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 9 statements into 1 equivalence classes. [2025-01-10 02:30:26,547 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 9 of 9 statements. [2025-01-10 02:30:26,547 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-10 02:30:26,547 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 02:30:26,590 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-01-10 02:30:26,590 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-10 02:30:26,590 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1216291043] [2025-01-10 02:30:26,590 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1216291043] provided 1 perfect and 0 imperfect interpolant sequences [2025-01-10 02:30:26,590 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-01-10 02:30:26,590 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2025-01-10 02:30:26,590 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1175112971] [2025-01-10 02:30:26,590 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-01-10 02:30:26,591 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-01-10 02:30:26,591 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-10 02:30:26,591 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-01-10 02:30:26,591 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-01-10 02:30:26,591 INFO L87 Difference]: Start difference. First operand 23 states and 26 transitions. Second operand has 5 states, 3 states have (on average 2.6666666666666665) internal successors, (8), 4 states have internal predecessors, (8), 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-01-10 02:30:26,647 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-10 02:30:26,647 INFO L93 Difference]: Finished difference Result 25 states and 29 transitions. [2025-01-10 02:30:26,647 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-01-10 02:30:26,648 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 3 states have (on average 2.6666666666666665) internal successors, (8), 4 states have internal predecessors, (8), 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 9 [2025-01-10 02:30:26,648 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-10 02:30:26,648 INFO L225 Difference]: With dead ends: 25 [2025-01-10 02:30:26,648 INFO L226 Difference]: Without dead ends: 23 [2025-01-10 02:30:26,648 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-01-10 02:30:26,649 INFO L435 NwaCegarLoop]: 14 mSDtfsCounter, 26 mSDsluCounter, 18 mSDsCounter, 0 mSdLazyCounter, 33 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 26 SdHoareTripleChecker+Valid, 32 SdHoareTripleChecker+Invalid, 40 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 33 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-01-10 02:30:26,649 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [26 Valid, 32 Invalid, 40 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 33 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-01-10 02:30:26,649 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 23 states. [2025-01-10 02:30:26,651 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 23 to 21. [2025-01-10 02:30:26,652 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 21 states, 15 states have (on average 1.2666666666666666) internal successors, (19), 17 states have internal predecessors, (19), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-01-10 02:30:26,652 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 21 states to 21 states and 24 transitions. [2025-01-10 02:30:26,652 INFO L78 Accepts]: Start accepts. Automaton has 21 states and 24 transitions. Word has length 9 [2025-01-10 02:30:26,652 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-10 02:30:26,652 INFO L471 AbstractCegarLoop]: Abstraction has 21 states and 24 transitions. [2025-01-10 02:30:26,652 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 3 states have (on average 2.6666666666666665) internal successors, (8), 4 states have internal predecessors, (8), 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-01-10 02:30:26,652 INFO L276 IsEmpty]: Start isEmpty. Operand 21 states and 24 transitions. [2025-01-10 02:30:26,653 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2025-01-10 02:30:26,653 INFO L210 NwaCegarLoop]: Found error trace [2025-01-10 02:30:26,653 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-01-10 02:30:26,653 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2025-01-10 02:30:26,653 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting fibonacciErr4ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-01-10 02:30:26,653 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-10 02:30:26,654 INFO L85 PathProgramCache]: Analyzing trace with hash 1558234811, now seen corresponding path program 1 times [2025-01-10 02:30:26,654 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-10 02:30:26,654 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [149817055] [2025-01-10 02:30:26,654 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-10 02:30:26,654 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-10 02:30:26,659 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 24 statements into 1 equivalence classes. [2025-01-10 02:30:26,666 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 24 of 24 statements. [2025-01-10 02:30:26,666 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-10 02:30:26,666 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 02:30:26,781 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2025-01-10 02:30:26,782 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-10 02:30:26,782 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [149817055] [2025-01-10 02:30:26,782 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [149817055] provided 1 perfect and 0 imperfect interpolant sequences [2025-01-10 02:30:26,782 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-01-10 02:30:26,782 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2025-01-10 02:30:26,782 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1815087675] [2025-01-10 02:30:26,782 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-01-10 02:30:26,782 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-01-10 02:30:26,782 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-10 02:30:26,783 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-01-10 02:30:26,783 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2025-01-10 02:30:26,783 INFO L87 Difference]: Start difference. First operand 21 states and 24 transitions. Second operand has 5 states, 4 states have (on average 3.75) internal successors, (15), 5 states have internal predecessors, (15), 2 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-01-10 02:30:26,828 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-10 02:30:26,828 INFO L93 Difference]: Finished difference Result 35 states and 43 transitions. [2025-01-10 02:30:26,829 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-01-10 02:30:26,829 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 3.75) internal successors, (15), 5 states have internal predecessors, (15), 2 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 24 [2025-01-10 02:30:26,829 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-10 02:30:26,829 INFO L225 Difference]: With dead ends: 35 [2025-01-10 02:30:26,830 INFO L226 Difference]: Without dead ends: 33 [2025-01-10 02:30:26,830 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-01-10 02:30:26,830 INFO L435 NwaCegarLoop]: 18 mSDtfsCounter, 3 mSDsluCounter, 51 mSDsCounter, 0 mSdLazyCounter, 27 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 69 SdHoareTripleChecker+Invalid, 29 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 27 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-01-10 02:30:26,830 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 69 Invalid, 29 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 27 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-01-10 02:30:26,831 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 33 states. [2025-01-10 02:30:26,838 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 33 to 30. [2025-01-10 02:30:26,839 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 30 states, 22 states have (on average 1.1818181818181819) internal successors, (26), 24 states have internal predecessors, (26), 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-01-10 02:30:26,839 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 30 states to 30 states and 36 transitions. [2025-01-10 02:30:26,841 INFO L78 Accepts]: Start accepts. Automaton has 30 states and 36 transitions. Word has length 24 [2025-01-10 02:30:26,841 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-10 02:30:26,841 INFO L471 AbstractCegarLoop]: Abstraction has 30 states and 36 transitions. [2025-01-10 02:30:26,841 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 3.75) internal successors, (15), 5 states have internal predecessors, (15), 2 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-01-10 02:30:26,841 INFO L276 IsEmpty]: Start isEmpty. Operand 30 states and 36 transitions. [2025-01-10 02:30:26,842 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2025-01-10 02:30:26,842 INFO L210 NwaCegarLoop]: Found error trace [2025-01-10 02:30:26,842 INFO L218 NwaCegarLoop]: trace histogram [4, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-01-10 02:30:26,843 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2025-01-10 02:30:26,843 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting fibonacciErr4ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-01-10 02:30:26,843 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-10 02:30:26,843 INFO L85 PathProgramCache]: Analyzing trace with hash 171916151, now seen corresponding path program 1 times [2025-01-10 02:30:26,843 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-10 02:30:26,843 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [568008543] [2025-01-10 02:30:26,843 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-10 02:30:26,843 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-10 02:30:26,853 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 31 statements into 1 equivalence classes. [2025-01-10 02:30:26,866 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 31 of 31 statements. [2025-01-10 02:30:26,867 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-10 02:30:26,867 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 02:30:27,046 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2025-01-10 02:30:27,047 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-10 02:30:27,047 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [568008543] [2025-01-10 02:30:27,047 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [568008543] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-10 02:30:27,047 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [212975641] [2025-01-10 02:30:27,047 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-10 02:30:27,047 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-10 02:30:27,048 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-10 02:30:27,053 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-01-10 02:30:27,054 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-01-10 02:30:27,084 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 31 statements into 1 equivalence classes. [2025-01-10 02:30:27,093 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 31 of 31 statements. [2025-01-10 02:30:27,093 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-10 02:30:27,093 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 02:30:27,094 INFO L256 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 6 conjuncts are in the unsatisfiable core [2025-01-10 02:30:27,097 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-10 02:30:27,176 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 6 proven. 3 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2025-01-10 02:30:27,176 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-10 02:30:27,286 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 6 proven. 3 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2025-01-10 02:30:27,286 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [212975641] provided 0 perfect and 2 imperfect interpolant sequences [2025-01-10 02:30:27,287 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-01-10 02:30:27,287 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 7, 7] total 15 [2025-01-10 02:30:27,287 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1355474980] [2025-01-10 02:30:27,287 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-01-10 02:30:27,287 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2025-01-10 02:30:27,287 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-10 02:30:27,288 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2025-01-10 02:30:27,288 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=35, Invalid=175, Unknown=0, NotChecked=0, Total=210 [2025-01-10 02:30:27,288 INFO L87 Difference]: Start difference. First operand 30 states and 36 transitions. Second operand has 15 states, 15 states have (on average 2.466666666666667) internal successors, (37), 15 states have internal predecessors, (37), 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-01-10 02:30:27,478 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-10 02:30:27,479 INFO L93 Difference]: Finished difference Result 91 states and 129 transitions. [2025-01-10 02:30:27,479 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2025-01-10 02:30:27,479 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 15 states have (on average 2.466666666666667) internal successors, (37), 15 states have internal predecessors, (37), 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 31 [2025-01-10 02:30:27,479 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-10 02:30:27,480 INFO L225 Difference]: With dead ends: 91 [2025-01-10 02:30:27,480 INFO L226 Difference]: Without dead ends: 65 [2025-01-10 02:30:27,481 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 74 GetRequests, 52 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-01-10 02:30:27,481 INFO L435 NwaCegarLoop]: 13 mSDtfsCounter, 134 mSDsluCounter, 79 mSDsCounter, 0 mSdLazyCounter, 174 mSolverCounterSat, 56 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 134 SdHoareTripleChecker+Valid, 92 SdHoareTripleChecker+Invalid, 230 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 56 IncrementalHoareTripleChecker+Valid, 174 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-01-10 02:30:27,482 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [134 Valid, 92 Invalid, 230 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [56 Valid, 174 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-01-10 02:30:27,482 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 65 states. [2025-01-10 02:30:27,488 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 65 to 53. [2025-01-10 02:30:27,488 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 53 states, 39 states have (on average 1.1025641025641026) internal successors, (43), 42 states have internal predecessors, (43), 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-01-10 02:30:27,489 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 53 states to 53 states and 68 transitions. [2025-01-10 02:30:27,489 INFO L78 Accepts]: Start accepts. Automaton has 53 states and 68 transitions. Word has length 31 [2025-01-10 02:30:27,489 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-10 02:30:27,489 INFO L471 AbstractCegarLoop]: Abstraction has 53 states and 68 transitions. [2025-01-10 02:30:27,489 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 2.466666666666667) internal successors, (37), 15 states have internal predecessors, (37), 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-01-10 02:30:27,490 INFO L276 IsEmpty]: Start isEmpty. Operand 53 states and 68 transitions. [2025-01-10 02:30:27,490 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2025-01-10 02:30:27,490 INFO L210 NwaCegarLoop]: Found error trace [2025-01-10 02:30:27,490 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-01-10 02:30:27,496 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2025-01-10 02:30:27,694 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,2 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-10 02:30:27,694 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting fibonacciErr4ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-01-10 02:30:27,694 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-10 02:30:27,694 INFO L85 PathProgramCache]: Analyzing trace with hash 1070767867, now seen corresponding path program 2 times [2025-01-10 02:30:27,695 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-10 02:30:27,695 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1227338592] [2025-01-10 02:30:27,695 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-01-10 02:30:27,695 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-10 02:30:27,700 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 25 statements into 2 equivalence classes. [2025-01-10 02:30:27,704 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 25 of 25 statements. [2025-01-10 02:30:27,704 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-01-10 02:30:27,704 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 02:30:27,768 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2025-01-10 02:30:27,768 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-10 02:30:27,768 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1227338592] [2025-01-10 02:30:27,768 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1227338592] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-10 02:30:27,768 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1710742325] [2025-01-10 02:30:27,768 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-01-10 02:30:27,768 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-10 02:30:27,768 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-10 02:30:27,770 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-01-10 02:30:27,771 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-01-10 02:30:27,791 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 25 statements into 2 equivalence classes. [2025-01-10 02:30:27,799 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 25 of 25 statements. [2025-01-10 02:30:27,799 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-01-10 02:30:27,799 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 02:30:27,800 INFO L256 TraceCheckSpWp]: Trace formula consists of 67 conjuncts, 4 conjuncts are in the unsatisfiable core [2025-01-10 02:30:27,801 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-10 02:30:27,832 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2025-01-10 02:30:27,832 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-01-10 02:30:27,832 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1710742325] provided 1 perfect and 0 imperfect interpolant sequences [2025-01-10 02:30:27,832 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-01-10 02:30:27,832 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [5] total 7 [2025-01-10 02:30:27,833 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1916409492] [2025-01-10 02:30:27,833 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-01-10 02:30:27,833 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-01-10 02:30:27,833 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-10 02:30:27,833 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-01-10 02:30:27,833 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=38, Unknown=0, NotChecked=0, Total=56 [2025-01-10 02:30:27,833 INFO L87 Difference]: Start difference. First operand 53 states and 68 transitions. Second operand has 5 states, 4 states have (on average 4.25) internal successors, (17), 5 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-01-10 02:30:27,853 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-10 02:30:27,853 INFO L93 Difference]: Finished difference Result 60 states and 76 transitions. [2025-01-10 02:30:27,854 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-01-10 02:30:27,854 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 4.25) internal successors, (17), 5 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-01-10 02:30:27,854 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-10 02:30:27,855 INFO L225 Difference]: With dead ends: 60 [2025-01-10 02:30:27,855 INFO L226 Difference]: Without dead ends: 59 [2025-01-10 02:30:27,855 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 29 GetRequests, 22 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-01-10 02:30:27,855 INFO L435 NwaCegarLoop]: 18 mSDtfsCounter, 4 mSDsluCounter, 33 mSDsCounter, 0 mSdLazyCounter, 20 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 51 SdHoareTripleChecker+Invalid, 22 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 20 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-01-10 02:30:27,855 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [5 Valid, 51 Invalid, 22 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 20 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-01-10 02:30:27,856 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 59 states. [2025-01-10 02:30:27,861 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 59 to 55. [2025-01-10 02:30:27,861 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 55 states, 41 states have (on average 1.0975609756097562) internal successors, (45), 43 states have internal predecessors, (45), 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-01-10 02:30:27,862 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 55 states to 55 states and 70 transitions. [2025-01-10 02:30:27,862 INFO L78 Accepts]: Start accepts. Automaton has 55 states and 70 transitions. Word has length 25 [2025-01-10 02:30:27,863 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-10 02:30:27,863 INFO L471 AbstractCegarLoop]: Abstraction has 55 states and 70 transitions. [2025-01-10 02:30:27,863 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 4.25) internal successors, (17), 5 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-01-10 02:30:27,863 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 70 transitions. [2025-01-10 02:30:27,863 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2025-01-10 02:30:27,863 INFO L210 NwaCegarLoop]: Found error trace [2025-01-10 02:30:27,863 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, 1] [2025-01-10 02:30:27,869 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2025-01-10 02:30:28,068 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,3 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-10 02:30:28,068 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting fibonacciErr5ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-01-10 02:30:28,068 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-10 02:30:28,068 INFO L85 PathProgramCache]: Analyzing trace with hash -1165934437, now seen corresponding path program 1 times [2025-01-10 02:30:28,068 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-10 02:30:28,068 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [760624099] [2025-01-10 02:30:28,068 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-10 02:30:28,069 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-10 02:30:28,072 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 26 statements into 1 equivalence classes. [2025-01-10 02:30:28,075 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 26 of 26 statements. [2025-01-10 02:30:28,075 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-10 02:30:28,075 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 02:30:28,151 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2025-01-10 02:30:28,151 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-10 02:30:28,151 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [760624099] [2025-01-10 02:30:28,151 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [760624099] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-10 02:30:28,151 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [658558908] [2025-01-10 02:30:28,151 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-10 02:30:28,151 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-10 02:30:28,152 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-10 02:30:28,153 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-01-10 02:30:28,155 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-01-10 02:30:28,174 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 26 statements into 1 equivalence classes. [2025-01-10 02:30:28,181 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 26 of 26 statements. [2025-01-10 02:30:28,181 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-10 02:30:28,181 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 02:30:28,182 INFO L256 TraceCheckSpWp]: Trace formula consists of 68 conjuncts, 5 conjuncts are in the unsatisfiable core [2025-01-10 02:30:28,182 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-10 02:30:28,234 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2025-01-10 02:30:28,234 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-01-10 02:30:28,234 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [658558908] provided 1 perfect and 0 imperfect interpolant sequences [2025-01-10 02:30:28,234 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-01-10 02:30:28,234 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [5] total 9 [2025-01-10 02:30:28,234 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1338675845] [2025-01-10 02:30:28,234 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-01-10 02:30:28,234 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2025-01-10 02:30:28,234 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-10 02:30:28,235 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2025-01-10 02:30:28,235 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=64, Unknown=0, NotChecked=0, Total=90 [2025-01-10 02:30:28,235 INFO L87 Difference]: Start difference. First operand 55 states and 70 transitions. Second operand has 6 states, 5 states have (on average 3.6) internal successors, (18), 6 states have internal predecessors, (18), 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-01-10 02:30:28,269 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-10 02:30:28,270 INFO L93 Difference]: Finished difference Result 82 states and 117 transitions. [2025-01-10 02:30:28,271 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2025-01-10 02:30:28,271 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 3.6) internal successors, (18), 6 states have internal predecessors, (18), 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 26 [2025-01-10 02:30:28,271 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-10 02:30:28,272 INFO L225 Difference]: With dead ends: 82 [2025-01-10 02:30:28,272 INFO L226 Difference]: Without dead ends: 81 [2025-01-10 02:30:28,273 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 30 GetRequests, 22 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-01-10 02:30:28,273 INFO L435 NwaCegarLoop]: 18 mSDtfsCounter, 2 mSDsluCounter, 53 mSDsCounter, 0 mSdLazyCounter, 29 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 71 SdHoareTripleChecker+Invalid, 30 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 29 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-01-10 02:30:28,273 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 71 Invalid, 30 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 29 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-01-10 02:30:28,274 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 81 states. [2025-01-10 02:30:28,288 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 81 to 64. [2025-01-10 02:30:28,290 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 64 states, 48 states have (on average 1.0833333333333333) internal successors, (52), 50 states have internal predecessors, (52), 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-01-10 02:30:28,292 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 64 states to 64 states and 87 transitions. [2025-01-10 02:30:28,293 INFO L78 Accepts]: Start accepts. Automaton has 64 states and 87 transitions. Word has length 26 [2025-01-10 02:30:28,293 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-10 02:30:28,293 INFO L471 AbstractCegarLoop]: Abstraction has 64 states and 87 transitions. [2025-01-10 02:30:28,293 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 3.6) internal successors, (18), 6 states have internal predecessors, (18), 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-01-10 02:30:28,293 INFO L276 IsEmpty]: Start isEmpty. Operand 64 states and 87 transitions. [2025-01-10 02:30:28,295 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 47 [2025-01-10 02:30:28,295 INFO L210 NwaCegarLoop]: Found error trace [2025-01-10 02:30:28,295 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, 1] [2025-01-10 02:30:28,301 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2025-01-10 02:30:28,495 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,4 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-10 02:30:28,496 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting fibonacciErr5ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-01-10 02:30:28,496 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-10 02:30:28,496 INFO L85 PathProgramCache]: Analyzing trace with hash -728410920, now seen corresponding path program 1 times [2025-01-10 02:30:28,496 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-10 02:30:28,496 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1913099049] [2025-01-10 02:30:28,496 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-10 02:30:28,496 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-10 02:30:28,500 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 46 statements into 1 equivalence classes. [2025-01-10 02:30:28,504 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 46 of 46 statements. [2025-01-10 02:30:28,504 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-10 02:30:28,504 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 02:30:28,607 INFO L134 CoverageAnalysis]: Checked inductivity of 48 backedges. 2 proven. 15 refuted. 0 times theorem prover too weak. 31 trivial. 0 not checked. [2025-01-10 02:30:28,607 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-10 02:30:28,607 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1913099049] [2025-01-10 02:30:28,607 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1913099049] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-10 02:30:28,607 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1162267799] [2025-01-10 02:30:28,607 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-10 02:30:28,607 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-10 02:30:28,607 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-10 02:30:28,609 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-01-10 02:30:28,610 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-01-10 02:30:28,629 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 46 statements into 1 equivalence classes. [2025-01-10 02:30:28,639 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 46 of 46 statements. [2025-01-10 02:30:28,639 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-10 02:30:28,639 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 02:30:28,640 INFO L256 TraceCheckSpWp]: Trace formula consists of 105 conjuncts, 9 conjuncts are in the unsatisfiable core [2025-01-10 02:30:28,641 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-10 02:30:28,694 INFO L134 CoverageAnalysis]: Checked inductivity of 48 backedges. 2 proven. 7 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2025-01-10 02:30:28,694 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-10 02:30:28,859 INFO L134 CoverageAnalysis]: Checked inductivity of 48 backedges. 6 proven. 7 refuted. 0 times theorem prover too weak. 35 trivial. 0 not checked. [2025-01-10 02:30:28,860 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1162267799] provided 0 perfect and 2 imperfect interpolant sequences [2025-01-10 02:30:28,860 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-01-10 02:30:28,860 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 6, 7] total 15 [2025-01-10 02:30:28,860 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [606106407] [2025-01-10 02:30:28,860 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-01-10 02:30:28,861 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2025-01-10 02:30:28,863 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-10 02:30:28,863 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2025-01-10 02:30:28,863 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=62, Invalid=178, Unknown=0, NotChecked=0, Total=240 [2025-01-10 02:30:28,863 INFO L87 Difference]: Start difference. First operand 64 states and 87 transitions. Second operand has 16 states, 15 states have (on average 3.0) internal successors, (45), 16 states have internal predecessors, (45), 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-01-10 02:30:29,045 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-10 02:30:29,046 INFO L93 Difference]: Finished difference Result 141 states and 217 transitions. [2025-01-10 02:30:29,047 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2025-01-10 02:30:29,047 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 15 states have (on average 3.0) internal successors, (45), 16 states have internal predecessors, (45), 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 46 [2025-01-10 02:30:29,047 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-10 02:30:29,049 INFO L225 Difference]: With dead ends: 141 [2025-01-10 02:30:29,049 INFO L226 Difference]: Without dead ends: 139 [2025-01-10 02:30:29,050 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 105 GetRequests, 83 SyntacticMatches, 2 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 110 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=126, Invalid=336, Unknown=0, NotChecked=0, Total=462 [2025-01-10 02:30:29,050 INFO L435 NwaCegarLoop]: 25 mSDtfsCounter, 18 mSDsluCounter, 135 mSDsCounter, 0 mSdLazyCounter, 153 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 24 SdHoareTripleChecker+Valid, 160 SdHoareTripleChecker+Invalid, 160 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 153 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-01-10 02:30:29,050 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [24 Valid, 160 Invalid, 160 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 153 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-01-10 02:30:29,051 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 139 states. [2025-01-10 02:30:29,061 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 139 to 98. [2025-01-10 02:30:29,062 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 98 states, 76 states have (on average 1.0789473684210527) internal successors, (82), 75 states have internal predecessors, (82), 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-01-10 02:30:29,063 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 98 states to 98 states and 159 transitions. [2025-01-10 02:30:29,063 INFO L78 Accepts]: Start accepts. Automaton has 98 states and 159 transitions. Word has length 46 [2025-01-10 02:30:29,064 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-10 02:30:29,064 INFO L471 AbstractCegarLoop]: Abstraction has 98 states and 159 transitions. [2025-01-10 02:30:29,064 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 15 states have (on average 3.0) internal successors, (45), 16 states have internal predecessors, (45), 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-01-10 02:30:29,064 INFO L276 IsEmpty]: Start isEmpty. Operand 98 states and 159 transitions. [2025-01-10 02:30:29,066 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 85 [2025-01-10 02:30:29,066 INFO L210 NwaCegarLoop]: Found error trace [2025-01-10 02:30:29,066 INFO L218 NwaCegarLoop]: trace histogram [9, 8, 7, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 2, 1, 1, 1, 1, 1] [2025-01-10 02:30:29,072 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2025-01-10 02:30:29,270 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 5 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable6 [2025-01-10 02:30:29,270 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting fibonacciErr4ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-01-10 02:30:29,270 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-10 02:30:29,271 INFO L85 PathProgramCache]: Analyzing trace with hash -1625603394, now seen corresponding path program 1 times [2025-01-10 02:30:29,271 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-10 02:30:29,271 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [536691196] [2025-01-10 02:30:29,271 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-10 02:30:29,271 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-10 02:30:29,279 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 84 statements into 1 equivalence classes. [2025-01-10 02:30:29,289 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 84 of 84 statements. [2025-01-10 02:30:29,290 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-10 02:30:29,290 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 02:30:29,430 INFO L134 CoverageAnalysis]: Checked inductivity of 206 backedges. 38 proven. 86 refuted. 0 times theorem prover too weak. 82 trivial. 0 not checked. [2025-01-10 02:30:29,430 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-10 02:30:29,430 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [536691196] [2025-01-10 02:30:29,430 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [536691196] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-10 02:30:29,430 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1473630894] [2025-01-10 02:30:29,430 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-10 02:30:29,430 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-10 02:30:29,430 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-10 02:30:29,434 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-01-10 02:30:29,435 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-01-10 02:30:29,459 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 84 statements into 1 equivalence classes. [2025-01-10 02:30:29,479 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 84 of 84 statements. [2025-01-10 02:30:29,479 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-10 02:30:29,479 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 02:30:29,480 INFO L256 TraceCheckSpWp]: Trace formula consists of 176 conjuncts, 10 conjuncts are in the unsatisfiable core [2025-01-10 02:30:29,482 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-10 02:30:29,564 INFO L134 CoverageAnalysis]: Checked inductivity of 206 backedges. 50 proven. 92 refuted. 0 times theorem prover too weak. 64 trivial. 0 not checked. [2025-01-10 02:30:29,565 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-10 02:30:29,842 INFO L134 CoverageAnalysis]: Checked inductivity of 206 backedges. 50 proven. 95 refuted. 0 times theorem prover too weak. 61 trivial. 0 not checked. [2025-01-10 02:30:29,843 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1473630894] provided 0 perfect and 2 imperfect interpolant sequences [2025-01-10 02:30:29,843 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-01-10 02:30:29,843 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 9, 11] total 16 [2025-01-10 02:30:29,843 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [86067336] [2025-01-10 02:30:29,843 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-01-10 02:30:29,843 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2025-01-10 02:30:29,843 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-10 02:30:29,844 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2025-01-10 02:30:29,844 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=53, Invalid=187, Unknown=0, NotChecked=0, Total=240 [2025-01-10 02:30:29,844 INFO L87 Difference]: Start difference. First operand 98 states and 159 transitions. Second operand has 16 states, 16 states have (on average 5.125) internal successors, (82), 16 states have internal predecessors, (82), 10 states have call successors, (14), 1 states have call predecessors, (14), 5 states have return successors, (14), 7 states have call predecessors, (14), 10 states have call successors, (14) [2025-01-10 02:30:29,971 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-10 02:30:29,971 INFO L93 Difference]: Finished difference Result 174 states and 299 transitions. [2025-01-10 02:30:29,971 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2025-01-10 02:30:29,971 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 16 states have (on average 5.125) internal successors, (82), 16 states have internal predecessors, (82), 10 states have call successors, (14), 1 states have call predecessors, (14), 5 states have return successors, (14), 7 states have call predecessors, (14), 10 states have call successors, (14) Word has length 84 [2025-01-10 02:30:29,972 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-10 02:30:29,972 INFO L225 Difference]: With dead ends: 174 [2025-01-10 02:30:29,972 INFO L226 Difference]: Without dead ends: 80 [2025-01-10 02:30:29,975 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 187 GetRequests, 160 SyntacticMatches, 5 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 73 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=164, Invalid=388, Unknown=0, NotChecked=0, Total=552 [2025-01-10 02:30:29,975 INFO L435 NwaCegarLoop]: 16 mSDtfsCounter, 61 mSDsluCounter, 50 mSDsCounter, 0 mSdLazyCounter, 95 mSolverCounterSat, 34 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 61 SdHoareTripleChecker+Valid, 66 SdHoareTripleChecker+Invalid, 129 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 34 IncrementalHoareTripleChecker+Valid, 95 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-01-10 02:30:29,975 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [61 Valid, 66 Invalid, 129 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [34 Valid, 95 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-01-10 02:30:29,976 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 80 states. [2025-01-10 02:30:29,981 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 80 to 70. [2025-01-10 02:30:29,981 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 70 states, 55 states have (on average 1.1090909090909091) internal successors, (61), 53 states have internal predecessors, (61), 7 states have call successors, (7), 4 states have call predecessors, (7), 6 states have return successors, (26), 12 states have call predecessors, (26), 6 states have call successors, (26) [2025-01-10 02:30:29,982 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 70 states to 70 states and 94 transitions. [2025-01-10 02:30:29,982 INFO L78 Accepts]: Start accepts. Automaton has 70 states and 94 transitions. Word has length 84 [2025-01-10 02:30:29,982 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-10 02:30:29,982 INFO L471 AbstractCegarLoop]: Abstraction has 70 states and 94 transitions. [2025-01-10 02:30:29,983 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 16 states have (on average 5.125) internal successors, (82), 16 states have internal predecessors, (82), 10 states have call successors, (14), 1 states have call predecessors, (14), 5 states have return successors, (14), 7 states have call predecessors, (14), 10 states have call successors, (14) [2025-01-10 02:30:29,983 INFO L276 IsEmpty]: Start isEmpty. Operand 70 states and 94 transitions. [2025-01-10 02:30:29,983 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 110 [2025-01-10 02:30:29,984 INFO L210 NwaCegarLoop]: Found error trace [2025-01-10 02:30:29,984 INFO L218 NwaCegarLoop]: trace histogram [12, 10, 9, 6, 6, 6, 6, 5, 5, 5, 5, 5, 5, 5, 4, 4, 3, 3, 1, 1, 1, 1, 1] [2025-01-10 02:30:29,990 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2025-01-10 02:30:30,188 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,6 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-10 02:30:30,189 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting fibonacciErr4ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-01-10 02:30:30,189 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-10 02:30:30,189 INFO L85 PathProgramCache]: Analyzing trace with hash -1887443395, now seen corresponding path program 2 times [2025-01-10 02:30:30,189 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-10 02:30:30,189 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1731257535] [2025-01-10 02:30:30,189 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-01-10 02:30:30,190 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-10 02:30:30,194 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 109 statements into 2 equivalence classes. [2025-01-10 02:30:30,202 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 109 of 109 statements. [2025-01-10 02:30:30,202 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-01-10 02:30:30,202 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 02:30:30,329 INFO L134 CoverageAnalysis]: Checked inductivity of 369 backedges. 53 proven. 96 refuted. 0 times theorem prover too weak. 220 trivial. 0 not checked. [2025-01-10 02:30:30,329 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-10 02:30:30,329 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1731257535] [2025-01-10 02:30:30,329 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1731257535] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-10 02:30:30,329 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1223790121] [2025-01-10 02:30:30,329 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-01-10 02:30:30,330 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-10 02:30:30,330 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-10 02:30:30,332 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-01-10 02:30:30,333 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-01-10 02:30:30,358 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 109 statements into 2 equivalence classes. [2025-01-10 02:30:30,377 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 109 of 109 statements. [2025-01-10 02:30:30,377 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-01-10 02:30:30,377 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 02:30:30,377 INFO L256 TraceCheckSpWp]: Trace formula consists of 221 conjuncts, 8 conjuncts are in the unsatisfiable core [2025-01-10 02:30:30,379 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-10 02:30:30,457 INFO L134 CoverageAnalysis]: Checked inductivity of 369 backedges. 228 proven. 15 refuted. 0 times theorem prover too weak. 126 trivial. 0 not checked. [2025-01-10 02:30:30,457 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-10 02:30:30,740 INFO L134 CoverageAnalysis]: Checked inductivity of 369 backedges. 56 proven. 121 refuted. 0 times theorem prover too weak. 192 trivial. 0 not checked. [2025-01-10 02:30:30,740 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1223790121] provided 0 perfect and 2 imperfect interpolant sequences [2025-01-10 02:30:30,740 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-01-10 02:30:30,741 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 8, 9] total 14 [2025-01-10 02:30:30,741 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1945097826] [2025-01-10 02:30:30,741 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-01-10 02:30:30,741 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2025-01-10 02:30:30,741 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-10 02:30:30,741 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2025-01-10 02:30:30,742 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=47, Invalid=135, Unknown=0, NotChecked=0, Total=182 [2025-01-10 02:30:30,742 INFO L87 Difference]: Start difference. First operand 70 states and 94 transitions. Second operand has 14 states, 14 states have (on average 5.0) internal successors, (70), 14 states have internal predecessors, (70), 7 states have call successors, (12), 2 states have call predecessors, (12), 5 states have return successors, (13), 5 states have call predecessors, (13), 7 states have call successors, (13) [2025-01-10 02:30:30,840 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-10 02:30:30,840 INFO L93 Difference]: Finished difference Result 129 states and 179 transitions. [2025-01-10 02:30:30,841 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2025-01-10 02:30:30,841 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 5.0) internal successors, (70), 14 states have internal predecessors, (70), 7 states have call successors, (12), 2 states have call predecessors, (12), 5 states have return successors, (13), 5 states have call predecessors, (13), 7 states have call successors, (13) Word has length 109 [2025-01-10 02:30:30,842 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-10 02:30:30,843 INFO L225 Difference]: With dead ends: 129 [2025-01-10 02:30:30,843 INFO L226 Difference]: Without dead ends: 63 [2025-01-10 02:30:30,843 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 230 GetRequests, 210 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-01-10 02:30:30,844 INFO L435 NwaCegarLoop]: 22 mSDtfsCounter, 26 mSDsluCounter, 59 mSDsCounter, 0 mSdLazyCounter, 101 mSolverCounterSat, 10 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 26 SdHoareTripleChecker+Valid, 81 SdHoareTripleChecker+Invalid, 111 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 101 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-01-10 02:30:30,844 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [26 Valid, 81 Invalid, 111 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 101 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-01-10 02:30:30,844 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 63 states. [2025-01-10 02:30:30,848 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 63 to 61. [2025-01-10 02:30:30,850 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 61 states, 48 states have (on average 1.1041666666666667) internal successors, (53), 46 states have internal predecessors, (53), 6 states have call successors, (6), 4 states have call predecessors, (6), 5 states have return successors, (14), 10 states have call predecessors, (14), 5 states have call successors, (14) [2025-01-10 02:30:30,851 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 61 states to 61 states and 73 transitions. [2025-01-10 02:30:30,851 INFO L78 Accepts]: Start accepts. Automaton has 61 states and 73 transitions. Word has length 109 [2025-01-10 02:30:30,851 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-10 02:30:30,853 INFO L471 AbstractCegarLoop]: Abstraction has 61 states and 73 transitions. [2025-01-10 02:30:30,853 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 5.0) internal successors, (70), 14 states have internal predecessors, (70), 7 states have call successors, (12), 2 states have call predecessors, (12), 5 states have return successors, (13), 5 states have call predecessors, (13), 7 states have call successors, (13) [2025-01-10 02:30:30,853 INFO L276 IsEmpty]: Start isEmpty. Operand 61 states and 73 transitions. [2025-01-10 02:30:30,854 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 131 [2025-01-10 02:30:30,854 INFO L210 NwaCegarLoop]: Found error trace [2025-01-10 02:30:30,854 INFO L218 NwaCegarLoop]: trace histogram [14, 12, 12, 7, 7, 7, 7, 6, 6, 6, 6, 6, 6, 6, 5, 5, 5, 2, 1, 1, 1, 1, 1] [2025-01-10 02:30:30,861 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2025-01-10 02:30:31,055 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 7 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable8 [2025-01-10 02:30:31,056 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting fibonacciErr4ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-01-10 02:30:31,056 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-10 02:30:31,056 INFO L85 PathProgramCache]: Analyzing trace with hash 1731852194, now seen corresponding path program 3 times [2025-01-10 02:30:31,056 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-10 02:30:31,056 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [444819764] [2025-01-10 02:30:31,056 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-01-10 02:30:31,057 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-10 02:30:31,064 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 130 statements into 12 equivalence classes. [2025-01-10 02:30:31,074 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) and asserted 70 of 130 statements. [2025-01-10 02:30:31,074 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2025-01-10 02:30:31,075 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 02:30:31,165 INFO L134 CoverageAnalysis]: Checked inductivity of 543 backedges. 206 proven. 18 refuted. 0 times theorem prover too weak. 319 trivial. 0 not checked. [2025-01-10 02:30:31,165 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-10 02:30:31,165 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [444819764] [2025-01-10 02:30:31,165 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [444819764] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-10 02:30:31,165 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [646934170] [2025-01-10 02:30:31,165 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-01-10 02:30:31,165 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-10 02:30:31,166 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-10 02:30:31,169 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-01-10 02:30:31,172 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-01-10 02:30:31,196 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 130 statements into 12 equivalence classes. [2025-01-10 02:30:31,210 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) and asserted 70 of 130 statements. [2025-01-10 02:30:31,211 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2025-01-10 02:30:31,211 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 02:30:31,211 INFO L256 TraceCheckSpWp]: Trace formula consists of 150 conjuncts, 8 conjuncts are in the unsatisfiable core [2025-01-10 02:30:31,213 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-10 02:30:31,256 INFO L134 CoverageAnalysis]: Checked inductivity of 543 backedges. 203 proven. 21 refuted. 0 times theorem prover too weak. 319 trivial. 0 not checked. [2025-01-10 02:30:31,256 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-10 02:30:31,508 INFO L134 CoverageAnalysis]: Checked inductivity of 543 backedges. 203 proven. 22 refuted. 0 times theorem prover too weak. 318 trivial. 0 not checked. [2025-01-10 02:30:31,508 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [646934170] provided 0 perfect and 2 imperfect interpolant sequences [2025-01-10 02:30:31,508 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-01-10 02:30:31,508 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 9] total 12 [2025-01-10 02:30:31,508 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1127659659] [2025-01-10 02:30:31,508 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-01-10 02:30:31,509 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2025-01-10 02:30:31,509 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-10 02:30:31,509 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2025-01-10 02:30:31,511 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=35, Invalid=97, Unknown=0, NotChecked=0, Total=132 [2025-01-10 02:30:31,511 INFO L87 Difference]: Start difference. First operand 61 states and 73 transitions. Second operand has 12 states, 12 states have (on average 5.0) internal successors, (60), 12 states have internal predecessors, (60), 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-01-10 02:30:31,585 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-10 02:30:31,585 INFO L93 Difference]: Finished difference Result 114 states and 140 transitions. [2025-01-10 02:30:31,585 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2025-01-10 02:30:31,586 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 5.0) internal successors, (60), 12 states have internal predecessors, (60), 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-01-10 02:30:31,586 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-10 02:30:31,587 INFO L225 Difference]: With dead ends: 114 [2025-01-10 02:30:31,587 INFO L226 Difference]: Without dead ends: 59 [2025-01-10 02:30:31,587 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-01-10 02:30:31,588 INFO L435 NwaCegarLoop]: 26 mSDtfsCounter, 41 mSDsluCounter, 57 mSDsCounter, 0 mSdLazyCounter, 93 mSolverCounterSat, 15 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 41 SdHoareTripleChecker+Valid, 83 SdHoareTripleChecker+Invalid, 108 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 15 IncrementalHoareTripleChecker+Valid, 93 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-01-10 02:30:31,588 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [41 Valid, 83 Invalid, 108 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [15 Valid, 93 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-01-10 02:30:31,588 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 59 states. [2025-01-10 02:30:31,591 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 59 to 57. [2025-01-10 02:30:31,592 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 57 states, 44 states have (on average 1.1136363636363635) internal successors, (49), 44 states have internal predecessors, (49), 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-01-10 02:30:31,592 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 57 states to 57 states and 67 transitions. [2025-01-10 02:30:31,592 INFO L78 Accepts]: Start accepts. Automaton has 57 states and 67 transitions. Word has length 130 [2025-01-10 02:30:31,593 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-10 02:30:31,593 INFO L471 AbstractCegarLoop]: Abstraction has 57 states and 67 transitions. [2025-01-10 02:30:31,593 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 5.0) internal successors, (60), 12 states have internal predecessors, (60), 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-01-10 02:30:31,593 INFO L276 IsEmpty]: Start isEmpty. Operand 57 states and 67 transitions. [2025-01-10 02:30:31,594 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 159 [2025-01-10 02:30:31,594 INFO L210 NwaCegarLoop]: Found error trace [2025-01-10 02:30:31,594 INFO L218 NwaCegarLoop]: trace histogram [17, 15, 14, 8, 8, 8, 8, 8, 8, 8, 8, 8, 7, 7, 6, 6, 6, 3, 1, 1, 1, 1, 1] [2025-01-10 02:30:31,600 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2025-01-10 02:30:31,798 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,8 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-10 02:30:31,798 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting fibonacciErr4ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-01-10 02:30:31,799 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-10 02:30:31,799 INFO L85 PathProgramCache]: Analyzing trace with hash 1713086498, now seen corresponding path program 4 times [2025-01-10 02:30:31,799 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-10 02:30:31,799 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1468278469] [2025-01-10 02:30:31,799 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-01-10 02:30:31,799 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-10 02:30:31,804 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 158 statements into 2 equivalence classes. [2025-01-10 02:30:31,810 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) and asserted 95 of 158 statements. [2025-01-10 02:30:31,810 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) [2025-01-10 02:30:31,810 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 02:30:31,946 INFO L134 CoverageAnalysis]: Checked inductivity of 826 backedges. 91 proven. 355 refuted. 0 times theorem prover too weak. 380 trivial. 0 not checked. [2025-01-10 02:30:31,946 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-10 02:30:31,946 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1468278469] [2025-01-10 02:30:31,946 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1468278469] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-10 02:30:31,946 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [885507328] [2025-01-10 02:30:31,946 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-01-10 02:30:31,947 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-10 02:30:31,947 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-10 02:30:31,952 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-01-10 02:30:31,953 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-01-10 02:30:31,982 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 158 statements into 2 equivalence classes. [2025-01-10 02:30:31,998 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) and asserted 95 of 158 statements. [2025-01-10 02:30:31,998 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) [2025-01-10 02:30:31,998 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 02:30:31,999 INFO L256 TraceCheckSpWp]: Trace formula consists of 204 conjuncts, 14 conjuncts are in the unsatisfiable core [2025-01-10 02:30:32,001 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-10 02:30:32,096 INFO L134 CoverageAnalysis]: Checked inductivity of 826 backedges. 463 proven. 189 refuted. 0 times theorem prover too weak. 174 trivial. 0 not checked. [2025-01-10 02:30:32,097 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-10 02:30:32,509 INFO L134 CoverageAnalysis]: Checked inductivity of 826 backedges. 107 proven. 410 refuted. 0 times theorem prover too weak. 309 trivial. 0 not checked. [2025-01-10 02:30:32,510 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [885507328] provided 0 perfect and 2 imperfect interpolant sequences [2025-01-10 02:30:32,510 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-01-10 02:30:32,510 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 11, 14] total 19 [2025-01-10 02:30:32,510 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [989892664] [2025-01-10 02:30:32,510 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-01-10 02:30:32,510 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2025-01-10 02:30:32,510 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-10 02:30:32,511 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2025-01-10 02:30:32,511 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=66, Invalid=276, Unknown=0, NotChecked=0, Total=342 [2025-01-10 02:30:32,511 INFO L87 Difference]: Start difference. First operand 57 states and 67 transitions. Second operand has 19 states, 19 states have (on average 5.894736842105263) internal successors, (112), 19 states have internal predecessors, (112), 14 states have call successors, (20), 3 states have call predecessors, (20), 7 states have return successors, (20), 8 states have call predecessors, (20), 13 states have call successors, (20) [2025-01-10 02:30:32,677 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-10 02:30:32,677 INFO L93 Difference]: Finished difference Result 126 states and 154 transitions. [2025-01-10 02:30:32,677 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2025-01-10 02:30:32,678 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 19 states have (on average 5.894736842105263) internal successors, (112), 19 states have internal predecessors, (112), 14 states have call successors, (20), 3 states have call predecessors, (20), 7 states have return successors, (20), 8 states have call predecessors, (20), 13 states have call successors, (20) Word has length 158 [2025-01-10 02:30:32,678 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-10 02:30:32,678 INFO L225 Difference]: With dead ends: 126 [2025-01-10 02:30:32,678 INFO L226 Difference]: Without dead ends: 75 [2025-01-10 02:30:32,679 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 342 GetRequests, 306 SyntacticMatches, 8 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 147 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=252, Invalid=618, Unknown=0, NotChecked=0, Total=870 [2025-01-10 02:30:32,679 INFO L435 NwaCegarLoop]: 17 mSDtfsCounter, 174 mSDsluCounter, 80 mSDsCounter, 0 mSdLazyCounter, 152 mSolverCounterSat, 60 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 174 SdHoareTripleChecker+Valid, 97 SdHoareTripleChecker+Invalid, 212 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 60 IncrementalHoareTripleChecker+Valid, 152 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-01-10 02:30:32,679 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [174 Valid, 97 Invalid, 212 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [60 Valid, 152 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-01-10 02:30:32,680 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 75 states. [2025-01-10 02:30:32,685 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 75 to 63. [2025-01-10 02:30:32,687 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 63 states, 49 states have (on average 1.1224489795918366) internal successors, (55), 49 states have internal predecessors, (55), 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-01-10 02:30:32,688 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 63 states to 63 states and 73 transitions. [2025-01-10 02:30:32,688 INFO L78 Accepts]: Start accepts. Automaton has 63 states and 73 transitions. Word has length 158 [2025-01-10 02:30:32,688 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-10 02:30:32,688 INFO L471 AbstractCegarLoop]: Abstraction has 63 states and 73 transitions. [2025-01-10 02:30:32,689 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 19 states have (on average 5.894736842105263) internal successors, (112), 19 states have internal predecessors, (112), 14 states have call successors, (20), 3 states have call predecessors, (20), 7 states have return successors, (20), 8 states have call predecessors, (20), 13 states have call successors, (20) [2025-01-10 02:30:32,689 INFO L276 IsEmpty]: Start isEmpty. Operand 63 states and 73 transitions. [2025-01-10 02:30:32,689 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 85 [2025-01-10 02:30:32,692 INFO L210 NwaCegarLoop]: Found error trace [2025-01-10 02:30:32,692 INFO L218 NwaCegarLoop]: trace histogram [9, 8, 7, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 2, 1, 1, 1, 1, 1] [2025-01-10 02:30:32,703 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2025-01-10 02:30:32,893 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,9 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-10 02:30:32,893 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting fibonacciErr4ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-01-10 02:30:32,894 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-10 02:30:32,894 INFO L85 PathProgramCache]: Analyzing trace with hash -1988790978, now seen corresponding path program 5 times [2025-01-10 02:30:32,894 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-10 02:30:32,894 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1839894734] [2025-01-10 02:30:32,894 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2025-01-10 02:30:32,894 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-10 02:30:32,901 INFO L108 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 partitioned 84 statements into 8 equivalence classes. [2025-01-10 02:30:32,908 INFO L111 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 8 check-sat command(s) and asserted 84 of 84 statements. [2025-01-10 02:30:32,908 INFO L114 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 8 check-sat command(s) [2025-01-10 02:30:32,908 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 02:30:33,099 INFO L134 CoverageAnalysis]: Checked inductivity of 206 backedges. 16 proven. 71 refuted. 0 times theorem prover too weak. 119 trivial. 0 not checked. [2025-01-10 02:30:33,099 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-10 02:30:33,099 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1839894734] [2025-01-10 02:30:33,099 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1839894734] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-10 02:30:33,099 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [267565458] [2025-01-10 02:30:33,099 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2025-01-10 02:30:33,100 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-10 02:30:33,100 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-10 02:30:33,103 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-01-10 02:30:33,106 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-01-10 02:30:33,136 INFO L108 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 partitioned 84 statements into 8 equivalence classes. [2025-01-10 02:30:33,152 INFO L111 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 8 check-sat command(s) and asserted 84 of 84 statements. [2025-01-10 02:30:33,152 INFO L114 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 8 check-sat command(s) [2025-01-10 02:30:33,152 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 02:30:33,153 INFO L256 TraceCheckSpWp]: Trace formula consists of 176 conjuncts, 17 conjuncts are in the unsatisfiable core [2025-01-10 02:30:33,155 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-10 02:30:33,247 INFO L134 CoverageAnalysis]: Checked inductivity of 206 backedges. 35 proven. 23 refuted. 0 times theorem prover too weak. 148 trivial. 0 not checked. [2025-01-10 02:30:33,247 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-10 02:30:33,638 INFO L134 CoverageAnalysis]: Checked inductivity of 206 backedges. 69 proven. 12 refuted. 0 times theorem prover too weak. 125 trivial. 0 not checked. [2025-01-10 02:30:33,639 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [267565458] provided 0 perfect and 2 imperfect interpolant sequences [2025-01-10 02:30:33,639 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-01-10 02:30:33,639 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 9, 12] total 22 [2025-01-10 02:30:33,639 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [267994673] [2025-01-10 02:30:33,639 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-01-10 02:30:33,639 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2025-01-10 02:30:33,639 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-10 02:30:33,640 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2025-01-10 02:30:33,640 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=121, Invalid=385, Unknown=0, NotChecked=0, Total=506 [2025-01-10 02:30:33,640 INFO L87 Difference]: Start difference. First operand 63 states and 73 transitions. Second operand has 23 states, 22 states have (on average 3.1363636363636362) internal successors, (69), 23 states have internal predecessors, (69), 6 states have call successors, (8), 1 states have call predecessors, (8), 7 states have return successors, (17), 15 states have call predecessors, (17), 6 states have call successors, (17) [2025-01-10 02:30:33,698 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-10 02:30:33,698 INFO L93 Difference]: Finished difference Result 63 states and 73 transitions. [2025-01-10 02:30:33,698 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2025-01-10 02:30:33,699 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 22 states have (on average 3.1363636363636362) internal successors, (69), 23 states have internal predecessors, (69), 6 states have call successors, (8), 1 states have call predecessors, (8), 7 states have return successors, (17), 15 states have call predecessors, (17), 6 states have call successors, (17) Word has length 84 [2025-01-10 02:30:33,699 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-10 02:30:33,699 INFO L225 Difference]: With dead ends: 63 [2025-01-10 02:30:33,699 INFO L226 Difference]: Without dead ends: 62 [2025-01-10 02:30:33,700 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 178 GetRequests, 151 SyntacticMatches, 6 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 239 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=121, Invalid=385, Unknown=0, NotChecked=0, Total=506 [2025-01-10 02:30:33,700 INFO L435 NwaCegarLoop]: 27 mSDtfsCounter, 1 mSDsluCounter, 153 mSDsCounter, 0 mSdLazyCounter, 95 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1 SdHoareTripleChecker+Valid, 180 SdHoareTripleChecker+Invalid, 95 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 95 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-01-10 02:30:33,700 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [1 Valid, 180 Invalid, 95 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 95 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-01-10 02:30:33,700 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 62 states. [2025-01-10 02:30:33,703 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 62 to 62. [2025-01-10 02:30:33,703 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 62 states, 49 states have (on average 1.0816326530612246) internal successors, (53), 48 states have internal predecessors, (53), 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-01-10 02:30:33,704 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 62 states to 62 states and 71 transitions. [2025-01-10 02:30:33,704 INFO L78 Accepts]: Start accepts. Automaton has 62 states and 71 transitions. Word has length 84 [2025-01-10 02:30:33,704 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-10 02:30:33,704 INFO L471 AbstractCegarLoop]: Abstraction has 62 states and 71 transitions. [2025-01-10 02:30:33,704 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 22 states have (on average 3.1363636363636362) internal successors, (69), 23 states have internal predecessors, (69), 6 states have call successors, (8), 1 states have call predecessors, (8), 7 states have return successors, (17), 15 states have call predecessors, (17), 6 states have call successors, (17) [2025-01-10 02:30:33,704 INFO L276 IsEmpty]: Start isEmpty. Operand 62 states and 71 transitions. [2025-01-10 02:30:33,705 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 131 [2025-01-10 02:30:33,705 INFO L210 NwaCegarLoop]: Found error trace [2025-01-10 02:30:33,705 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, 1] [2025-01-10 02:30:33,711 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2025-01-10 02:30:33,909 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11,10 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-10 02:30:33,909 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting fibonacciErr5ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-01-10 02:30:33,909 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-10 02:30:33,909 INFO L85 PathProgramCache]: Analyzing trace with hash 1463816598, now seen corresponding path program 2 times [2025-01-10 02:30:33,910 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-10 02:30:33,910 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2117192026] [2025-01-10 02:30:33,910 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-01-10 02:30:33,913 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-10 02:30:33,917 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 130 statements into 2 equivalence classes. [2025-01-10 02:30:33,925 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 130 of 130 statements. [2025-01-10 02:30:33,925 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-01-10 02:30:33,925 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 02:30:34,179 INFO L134 CoverageAnalysis]: Checked inductivity of 537 backedges. 55 proven. 137 refuted. 0 times theorem prover too weak. 345 trivial. 0 not checked. [2025-01-10 02:30:34,179 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-10 02:30:34,179 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2117192026] [2025-01-10 02:30:34,179 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2117192026] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-10 02:30:34,179 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1116336208] [2025-01-10 02:30:34,179 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-01-10 02:30:34,180 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-10 02:30:34,180 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-10 02:30:34,182 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-01-10 02:30:34,185 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-01-10 02:30:34,215 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 130 statements into 2 equivalence classes. [2025-01-10 02:30:34,234 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 130 of 130 statements. [2025-01-10 02:30:34,234 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-01-10 02:30:34,234 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 02:30:34,236 INFO L256 TraceCheckSpWp]: Trace formula consists of 259 conjuncts, 14 conjuncts are in the unsatisfiable core [2025-01-10 02:30:34,237 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-10 02:30:34,379 INFO L134 CoverageAnalysis]: Checked inductivity of 537 backedges. 167 proven. 182 refuted. 0 times theorem prover too weak. 188 trivial. 0 not checked. [2025-01-10 02:30:34,379 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-10 02:30:34,906 INFO L134 CoverageAnalysis]: Checked inductivity of 537 backedges. 167 proven. 202 refuted. 0 times theorem prover too weak. 168 trivial. 0 not checked. [2025-01-10 02:30:34,907 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1116336208] provided 0 perfect and 2 imperfect interpolant sequences [2025-01-10 02:30:34,907 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-01-10 02:30:34,907 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 11, 15] total 30 [2025-01-10 02:30:34,907 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1812487425] [2025-01-10 02:30:34,907 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-01-10 02:30:34,907 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 30 states [2025-01-10 02:30:34,907 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-10 02:30:34,908 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 30 interpolants. [2025-01-10 02:30:34,908 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=112, Invalid=758, Unknown=0, NotChecked=0, Total=870 [2025-01-10 02:30:34,909 INFO L87 Difference]: Start difference. First operand 62 states and 71 transitions. Second operand has 30 states, 30 states have (on average 4.066666666666666) internal successors, (122), 30 states have internal predecessors, (122), 16 states have call successors, (18), 1 states have call predecessors, (18), 12 states have return successors, (24), 15 states have call predecessors, (24), 16 states have call successors, (24) [2025-01-10 02:30:35,328 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-10 02:30:35,328 INFO L93 Difference]: Finished difference Result 136 states and 170 transitions. [2025-01-10 02:30:35,328 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2025-01-10 02:30:35,329 INFO L78 Accepts]: Start accepts. Automaton has has 30 states, 30 states have (on average 4.066666666666666) internal successors, (122), 30 states have internal predecessors, (122), 16 states have call successors, (18), 1 states have call predecessors, (18), 12 states have return successors, (24), 15 states have call predecessors, (24), 16 states have call successors, (24) Word has length 130 [2025-01-10 02:30:35,329 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-10 02:30:35,330 INFO L225 Difference]: With dead ends: 136 [2025-01-10 02:30:35,330 INFO L226 Difference]: Without dead ends: 80 [2025-01-10 02:30:35,331 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 302 GetRequests, 249 SyntacticMatches, 7 SemanticMatches, 46 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 491 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=430, Invalid=1826, Unknown=0, NotChecked=0, Total=2256 [2025-01-10 02:30:35,331 INFO L435 NwaCegarLoop]: 18 mSDtfsCounter, 188 mSDsluCounter, 99 mSDsCounter, 0 mSdLazyCounter, 536 mSolverCounterSat, 91 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 188 SdHoareTripleChecker+Valid, 117 SdHoareTripleChecker+Invalid, 627 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 91 IncrementalHoareTripleChecker+Valid, 536 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-01-10 02:30:35,331 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [188 Valid, 117 Invalid, 627 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [91 Valid, 536 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-01-10 02:30:35,332 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 80 states. [2025-01-10 02:30:35,335 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 80 to 71. [2025-01-10 02:30:35,335 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 71 states, 57 states have (on average 1.0526315789473684) internal successors, (60), 55 states have internal predecessors, (60), 8 states have call successors, (8), 7 states have call predecessors, (8), 5 states have return successors, (13), 8 states have call predecessors, (13), 7 states have call successors, (13) [2025-01-10 02:30:35,336 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 71 states to 71 states and 81 transitions. [2025-01-10 02:30:35,336 INFO L78 Accepts]: Start accepts. Automaton has 71 states and 81 transitions. Word has length 130 [2025-01-10 02:30:35,336 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-10 02:30:35,336 INFO L471 AbstractCegarLoop]: Abstraction has 71 states and 81 transitions. [2025-01-10 02:30:35,337 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 30 states, 30 states have (on average 4.066666666666666) internal successors, (122), 30 states have internal predecessors, (122), 16 states have call successors, (18), 1 states have call predecessors, (18), 12 states have return successors, (24), 15 states have call predecessors, (24), 16 states have call successors, (24) [2025-01-10 02:30:35,337 INFO L276 IsEmpty]: Start isEmpty. Operand 71 states and 81 transitions. [2025-01-10 02:30:35,337 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 145 [2025-01-10 02:30:35,337 INFO L210 NwaCegarLoop]: Found error trace [2025-01-10 02:30:35,338 INFO L218 NwaCegarLoop]: trace histogram [15, 14, 12, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 6, 5, 3, 1, 1, 1, 1, 1] [2025-01-10 02:30:35,346 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Ended with exit code 0 [2025-01-10 02:30:35,538 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2025-01-10 02:30:35,538 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting fibonacciErr5ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-01-10 02:30:35,539 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-10 02:30:35,539 INFO L85 PathProgramCache]: Analyzing trace with hash -1841209009, now seen corresponding path program 3 times [2025-01-10 02:30:35,539 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-10 02:30:35,539 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1321867270] [2025-01-10 02:30:35,539 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-01-10 02:30:35,539 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-10 02:30:35,545 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 144 statements into 12 equivalence classes. [2025-01-10 02:30:35,566 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 11 check-sat command(s) and asserted 138 of 144 statements. [2025-01-10 02:30:35,566 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 11 check-sat command(s) [2025-01-10 02:30:35,566 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 02:30:35,980 INFO L134 CoverageAnalysis]: Checked inductivity of 668 backedges. 78 proven. 189 refuted. 0 times theorem prover too weak. 401 trivial. 0 not checked. [2025-01-10 02:30:35,981 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-10 02:30:35,981 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1321867270] [2025-01-10 02:30:35,981 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1321867270] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-10 02:30:35,981 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [17929153] [2025-01-10 02:30:35,981 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-01-10 02:30:35,981 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-10 02:30:35,981 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-10 02:30:35,985 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-01-10 02:30:35,991 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-01-10 02:30:36,024 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 144 statements into 12 equivalence classes. [2025-01-10 02:30:36,048 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 11 check-sat command(s) and asserted 138 of 144 statements. [2025-01-10 02:30:36,049 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 11 check-sat command(s) [2025-01-10 02:30:36,049 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 02:30:36,050 INFO L256 TraceCheckSpWp]: Trace formula consists of 276 conjuncts, 29 conjuncts are in the unsatisfiable core [2025-01-10 02:30:36,052 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-10 02:30:36,190 INFO L134 CoverageAnalysis]: Checked inductivity of 668 backedges. 78 proven. 135 refuted. 0 times theorem prover too weak. 455 trivial. 0 not checked. [2025-01-10 02:30:36,190 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-10 02:30:37,094 INFO L134 CoverageAnalysis]: Checked inductivity of 668 backedges. 144 proven. 128 refuted. 0 times theorem prover too weak. 396 trivial. 0 not checked. [2025-01-10 02:30:37,094 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [17929153] provided 0 perfect and 2 imperfect interpolant sequences [2025-01-10 02:30:37,094 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-01-10 02:30:37,094 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 12, 17] total 31 [2025-01-10 02:30:37,094 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1050628348] [2025-01-10 02:30:37,095 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-01-10 02:30:37,095 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 32 states [2025-01-10 02:30:37,095 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-10 02:30:37,096 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 32 interpolants. [2025-01-10 02:30:37,096 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=232, Invalid=760, Unknown=0, NotChecked=0, Total=992 [2025-01-10 02:30:37,096 INFO L87 Difference]: Start difference. First operand 71 states and 81 transitions. Second operand has 32 states, 31 states have (on average 2.7419354838709675) internal successors, (85), 32 states have internal predecessors, (85), 8 states have call successors, (9), 1 states have call predecessors, (9), 9 states have return successors, (21), 21 states have call predecessors, (21), 8 states have call successors, (21) [2025-01-10 02:30:37,269 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-10 02:30:37,269 INFO L93 Difference]: Finished difference Result 117 states and 156 transitions. [2025-01-10 02:30:37,270 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2025-01-10 02:30:37,270 INFO L78 Accepts]: Start accepts. Automaton has has 32 states, 31 states have (on average 2.7419354838709675) internal successors, (85), 32 states have internal predecessors, (85), 8 states have call successors, (9), 1 states have call predecessors, (9), 9 states have return successors, (21), 21 states have call predecessors, (21), 8 states have call successors, (21) Word has length 144 [2025-01-10 02:30:37,271 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-10 02:30:37,272 INFO L225 Difference]: With dead ends: 117 [2025-01-10 02:30:37,272 INFO L226 Difference]: Without dead ends: 116 [2025-01-10 02:30:37,272 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 321 GetRequests, 272 SyntacticMatches, 13 SemanticMatches, 36 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 758 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=330, Invalid=1076, Unknown=0, NotChecked=0, Total=1406 [2025-01-10 02:30:37,273 INFO L435 NwaCegarLoop]: 20 mSDtfsCounter, 24 mSDsluCounter, 144 mSDsCounter, 0 mSdLazyCounter, 139 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 32 SdHoareTripleChecker+Valid, 164 SdHoareTripleChecker+Invalid, 150 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 139 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-01-10 02:30:37,273 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [32 Valid, 164 Invalid, 150 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 139 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-01-10 02:30:37,274 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 116 states. [2025-01-10 02:30:37,283 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 116 to 98. [2025-01-10 02:30:37,283 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 98 states, 78 states have (on average 1.0384615384615385) internal successors, (81), 76 states have internal predecessors, (81), 11 states have call successors, (11), 7 states have call predecessors, (11), 8 states have return successors, (37), 14 states have call predecessors, (37), 10 states have call successors, (37) [2025-01-10 02:30:37,284 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 98 states to 98 states and 129 transitions. [2025-01-10 02:30:37,285 INFO L78 Accepts]: Start accepts. Automaton has 98 states and 129 transitions. Word has length 144 [2025-01-10 02:30:37,285 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-10 02:30:37,285 INFO L471 AbstractCegarLoop]: Abstraction has 98 states and 129 transitions. [2025-01-10 02:30:37,285 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 32 states, 31 states have (on average 2.7419354838709675) internal successors, (85), 32 states have internal predecessors, (85), 8 states have call successors, (9), 1 states have call predecessors, (9), 9 states have return successors, (21), 21 states have call predecessors, (21), 8 states have call successors, (21) [2025-01-10 02:30:37,286 INFO L276 IsEmpty]: Start isEmpty. Operand 98 states and 129 transitions. [2025-01-10 02:30:37,290 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 479 [2025-01-10 02:30:37,290 INFO L210 NwaCegarLoop]: Found error trace [2025-01-10 02:30:37,291 INFO L218 NwaCegarLoop]: trace histogram [50, 47, 40, 25, 25, 25, 25, 24, 24, 24, 24, 24, 23, 23, 23, 22, 15, 10, 1, 1, 1, 1, 1] [2025-01-10 02:30:37,297 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-01-10 02:30:37,495 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2025-01-10 02:30:37,495 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting fibonacciErr5ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-01-10 02:30:37,496 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-10 02:30:37,496 INFO L85 PathProgramCache]: Analyzing trace with hash -51644392, now seen corresponding path program 4 times [2025-01-10 02:30:37,496 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-10 02:30:37,496 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1150870760] [2025-01-10 02:30:37,496 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-01-10 02:30:37,496 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-10 02:30:37,512 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 478 statements into 2 equivalence classes. [2025-01-10 02:30:37,532 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) and asserted 284 of 478 statements. [2025-01-10 02:30:37,532 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) [2025-01-10 02:30:37,532 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 02:30:37,808 INFO L134 CoverageAnalysis]: Checked inductivity of 8155 backedges. 266 proven. 2003 refuted. 0 times theorem prover too weak. 5886 trivial. 0 not checked. [2025-01-10 02:30:37,808 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-10 02:30:37,808 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1150870760] [2025-01-10 02:30:37,808 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1150870760] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-10 02:30:37,808 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1945874857] [2025-01-10 02:30:37,808 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-01-10 02:30:37,809 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-10 02:30:37,809 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-10 02:30:37,814 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-01-10 02:30:37,815 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-01-10 02:30:37,871 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 478 statements into 2 equivalence classes. [2025-01-10 02:30:37,911 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) and asserted 284 of 478 statements. [2025-01-10 02:30:37,911 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) [2025-01-10 02:30:37,911 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 02:30:37,912 INFO L256 TraceCheckSpWp]: Trace formula consists of 598 conjuncts, 18 conjuncts are in the unsatisfiable core [2025-01-10 02:30:37,916 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-10 02:30:38,036 INFO L134 CoverageAnalysis]: Checked inductivity of 8155 backedges. 4227 proven. 565 refuted. 0 times theorem prover too weak. 3363 trivial. 0 not checked. [2025-01-10 02:30:38,037 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-10 02:30:38,859 INFO L134 CoverageAnalysis]: Checked inductivity of 8155 backedges. 314 proven. 2305 refuted. 0 times theorem prover too weak. 5536 trivial. 0 not checked. [2025-01-10 02:30:38,859 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1945874857] provided 0 perfect and 2 imperfect interpolant sequences [2025-01-10 02:30:38,859 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-01-10 02:30:38,859 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 13, 17] total 22 [2025-01-10 02:30:38,859 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [169581549] [2025-01-10 02:30:38,859 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-01-10 02:30:38,860 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2025-01-10 02:30:38,860 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-10 02:30:38,861 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2025-01-10 02:30:38,861 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=82, Invalid=380, Unknown=0, NotChecked=0, Total=462 [2025-01-10 02:30:38,861 INFO L87 Difference]: Start difference. First operand 98 states and 129 transitions. Second operand has 22 states, 22 states have (on average 5.863636363636363) internal successors, (129), 22 states have internal predecessors, (129), 17 states have call successors, (23), 4 states have call predecessors, (23), 8 states have return successors, (23), 9 states have call predecessors, (23), 15 states have call successors, (23) [2025-01-10 02:30:39,085 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-10 02:30:39,085 INFO L93 Difference]: Finished difference Result 216 states and 310 transitions. [2025-01-10 02:30:39,086 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2025-01-10 02:30:39,086 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 22 states have (on average 5.863636363636363) internal successors, (129), 22 states have internal predecessors, (129), 17 states have call successors, (23), 4 states have call predecessors, (23), 8 states have return successors, (23), 9 states have call predecessors, (23), 15 states have call successors, (23) Word has length 478 [2025-01-10 02:30:39,086 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-10 02:30:39,087 INFO L225 Difference]: With dead ends: 216 [2025-01-10 02:30:39,087 INFO L226 Difference]: Without dead ends: 124 [2025-01-10 02:30:39,088 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 990 GetRequests, 944 SyntacticMatches, 11 SemanticMatches, 35 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 266 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=375, Invalid=957, Unknown=0, NotChecked=0, Total=1332 [2025-01-10 02:30:39,088 INFO L435 NwaCegarLoop]: 17 mSDtfsCounter, 215 mSDsluCounter, 81 mSDsCounter, 0 mSdLazyCounter, 163 mSolverCounterSat, 79 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 215 SdHoareTripleChecker+Valid, 98 SdHoareTripleChecker+Invalid, 242 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 79 IncrementalHoareTripleChecker+Valid, 163 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-01-10 02:30:39,088 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [215 Valid, 98 Invalid, 242 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [79 Valid, 163 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-01-10 02:30:39,089 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 124 states. [2025-01-10 02:30:39,093 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 124 to 104. [2025-01-10 02:30:39,094 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 104 states, 83 states have (on average 1.036144578313253) internal successors, (86), 81 states have internal predecessors, (86), 12 states have call successors, (12), 8 states have call predecessors, (12), 8 states have return successors, (34), 14 states have call predecessors, (34), 11 states have call successors, (34) [2025-01-10 02:30:39,094 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 104 states to 104 states and 132 transitions. [2025-01-10 02:30:39,094 INFO L78 Accepts]: Start accepts. Automaton has 104 states and 132 transitions. Word has length 478 [2025-01-10 02:30:39,095 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-10 02:30:39,095 INFO L471 AbstractCegarLoop]: Abstraction has 104 states and 132 transitions. [2025-01-10 02:30:39,095 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 22 states have (on average 5.863636363636363) internal successors, (129), 22 states have internal predecessors, (129), 17 states have call successors, (23), 4 states have call predecessors, (23), 8 states have return successors, (23), 9 states have call predecessors, (23), 15 states have call successors, (23) [2025-01-10 02:30:39,095 INFO L276 IsEmpty]: Start isEmpty. Operand 104 states and 132 transitions. [2025-01-10 02:30:39,098 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 466 [2025-01-10 02:30:39,098 INFO L210 NwaCegarLoop]: Found error trace [2025-01-10 02:30:39,099 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, 1] [2025-01-10 02:30:39,107 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Ended with exit code 0 [2025-01-10 02:30:39,303 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable14,13 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-10 02:30:39,303 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting fibonacciErr5ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-01-10 02:30:39,303 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-10 02:30:39,303 INFO L85 PathProgramCache]: Analyzing trace with hash -38256645, now seen corresponding path program 5 times [2025-01-10 02:30:39,303 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-10 02:30:39,303 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [741149138] [2025-01-10 02:30:39,303 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2025-01-10 02:30:39,303 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-10 02:30:39,312 INFO L108 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 partitioned 465 statements into 39 equivalence classes. [2025-01-10 02:30:39,329 INFO L111 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 27 check-sat command(s) and asserted 316 of 465 statements. [2025-01-10 02:30:39,330 INFO L114 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 27 check-sat command(s) [2025-01-10 02:30:39,330 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 02:30:39,608 INFO L134 CoverageAnalysis]: Checked inductivity of 7717 backedges. 1043 proven. 1771 refuted. 0 times theorem prover too weak. 4903 trivial. 0 not checked. [2025-01-10 02:30:39,608 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-10 02:30:39,608 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [741149138] [2025-01-10 02:30:39,608 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [741149138] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-10 02:30:39,608 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1081968366] [2025-01-10 02:30:39,609 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2025-01-10 02:30:39,609 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-10 02:30:39,609 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-10 02:30:39,610 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-01-10 02:30:39,612 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-01-10 02:30:39,668 INFO L108 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 partitioned 465 statements into 39 equivalence classes. [2025-01-10 02:30:39,723 INFO L111 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 27 check-sat command(s) and asserted 316 of 465 statements. [2025-01-10 02:30:39,723 INFO L114 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 27 check-sat command(s) [2025-01-10 02:30:39,723 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 02:30:39,725 INFO L256 TraceCheckSpWp]: Trace formula consists of 584 conjuncts, 22 conjuncts are in the unsatisfiable core [2025-01-10 02:30:39,729 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-10 02:30:39,836 INFO L134 CoverageAnalysis]: Checked inductivity of 7717 backedges. 4396 proven. 811 refuted. 0 times theorem prover too weak. 2510 trivial. 0 not checked. [2025-01-10 02:30:39,837 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-10 02:30:40,909 INFO L134 CoverageAnalysis]: Checked inductivity of 7717 backedges. 1069 proven. 1916 refuted. 0 times theorem prover too weak. 4732 trivial. 0 not checked. [2025-01-10 02:30:40,910 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1081968366] provided 0 perfect and 2 imperfect interpolant sequences [2025-01-10 02:30:40,910 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-01-10 02:30:40,910 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 16, 23] total 30 [2025-01-10 02:30:40,910 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [955226078] [2025-01-10 02:30:40,910 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-01-10 02:30:40,910 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 30 states [2025-01-10 02:30:40,911 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-10 02:30:40,911 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 30 interpolants. [2025-01-10 02:30:40,911 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=149, Invalid=721, Unknown=0, NotChecked=0, Total=870 [2025-01-10 02:30:40,911 INFO L87 Difference]: Start difference. First operand 104 states and 132 transitions. Second operand has 30 states, 30 states have (on average 5.6) internal successors, (168), 28 states have internal predecessors, (168), 20 states have call successors, (29), 6 states have call predecessors, (29), 11 states have return successors, (31), 16 states have call predecessors, (31), 17 states have call successors, (31) [2025-01-10 02:30:41,400 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-10 02:30:41,400 INFO L93 Difference]: Finished difference Result 290 states and 414 transitions. [2025-01-10 02:30:41,401 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 37 states. [2025-01-10 02:30:41,401 INFO L78 Accepts]: Start accepts. Automaton has has 30 states, 30 states have (on average 5.6) internal successors, (168), 28 states have internal predecessors, (168), 20 states have call successors, (29), 6 states have call predecessors, (29), 11 states have return successors, (31), 16 states have call predecessors, (31), 17 states have call successors, (31) Word has length 465 [2025-01-10 02:30:41,401 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-10 02:30:41,403 INFO L225 Difference]: With dead ends: 290 [2025-01-10 02:30:41,403 INFO L226 Difference]: Without dead ends: 192 [2025-01-10 02:30:41,405 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 984 GetRequests, 918 SyntacticMatches, 9 SemanticMatches, 57 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 950 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=837, Invalid=2585, Unknown=0, NotChecked=0, Total=3422 [2025-01-10 02:30:41,405 INFO L435 NwaCegarLoop]: 38 mSDtfsCounter, 288 mSDsluCounter, 155 mSDsCounter, 0 mSdLazyCounter, 401 mSolverCounterSat, 150 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 288 SdHoareTripleChecker+Valid, 193 SdHoareTripleChecker+Invalid, 551 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 150 IncrementalHoareTripleChecker+Valid, 401 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-01-10 02:30:41,405 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [288 Valid, 193 Invalid, 551 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [150 Valid, 401 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-01-10 02:30:41,406 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 192 states. [2025-01-10 02:30:41,429 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 192 to 176. [2025-01-10 02:30:41,429 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 176 states, 143 states have (on average 1.055944055944056) internal successors, (151), 138 states have internal predecessors, (151), 21 states have call successors, (21), 16 states have call predecessors, (21), 11 states have return successors, (65), 21 states have call predecessors, (65), 20 states have call successors, (65) [2025-01-10 02:30:41,431 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 176 states to 176 states and 237 transitions. [2025-01-10 02:30:41,431 INFO L78 Accepts]: Start accepts. Automaton has 176 states and 237 transitions. Word has length 465 [2025-01-10 02:30:41,432 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-10 02:30:41,432 INFO L471 AbstractCegarLoop]: Abstraction has 176 states and 237 transitions. [2025-01-10 02:30:41,432 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 30 states, 30 states have (on average 5.6) internal successors, (168), 28 states have internal predecessors, (168), 20 states have call successors, (29), 6 states have call predecessors, (29), 11 states have return successors, (31), 16 states have call predecessors, (31), 17 states have call successors, (31) [2025-01-10 02:30:41,432 INFO L276 IsEmpty]: Start isEmpty. Operand 176 states and 237 transitions. [2025-01-10 02:30:41,435 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 308 [2025-01-10 02:30:41,435 INFO L210 NwaCegarLoop]: Found error trace [2025-01-10 02:30:41,435 INFO L218 NwaCegarLoop]: trace histogram [32, 30, 26, 16, 16, 16, 16, 15, 15, 15, 15, 15, 15, 15, 15, 14, 10, 6, 1, 1, 1, 1, 1] [2025-01-10 02:30:41,442 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Ended with exit code 0 [2025-01-10 02:30:41,640 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable15,14 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-10 02:30:41,640 INFO L396 AbstractCegarLoop]: === Iteration 17 === Targeting fibonacciErr5ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-01-10 02:30:41,640 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-10 02:30:41,640 INFO L85 PathProgramCache]: Analyzing trace with hash -198377129, now seen corresponding path program 6 times [2025-01-10 02:30:41,641 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-10 02:30:41,641 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [682214919] [2025-01-10 02:30:41,641 INFO L95 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2025-01-10 02:30:41,641 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-10 02:30:41,648 INFO L108 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE partitioned 307 statements into 21 equivalence classes. [2025-01-10 02:30:41,677 INFO L111 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 18 check-sat command(s) and asserted 271 of 307 statements. [2025-01-10 02:30:41,678 INFO L114 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 18 check-sat command(s) [2025-01-10 02:30:41,678 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 02:30:41,917 INFO L134 CoverageAnalysis]: Checked inductivity of 3282 backedges. 716 proven. 787 refuted. 0 times theorem prover too weak. 1779 trivial. 0 not checked. [2025-01-10 02:30:41,917 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-10 02:30:41,917 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [682214919] [2025-01-10 02:30:41,917 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [682214919] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-10 02:30:41,917 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [6642235] [2025-01-10 02:30:41,917 INFO L95 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2025-01-10 02:30:41,917 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-10 02:30:41,917 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-10 02:30:41,920 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-01-10 02:30:41,920 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-01-10 02:30:41,976 INFO L108 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE partitioned 307 statements into 21 equivalence classes. [2025-01-10 02:30:42,026 INFO L111 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 18 check-sat command(s) and asserted 271 of 307 statements. [2025-01-10 02:30:42,026 INFO L114 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 18 check-sat command(s) [2025-01-10 02:30:42,026 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 02:30:42,028 INFO L256 TraceCheckSpWp]: Trace formula consists of 522 conjuncts, 18 conjuncts are in the unsatisfiable core [2025-01-10 02:30:42,031 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-10 02:30:42,126 INFO L134 CoverageAnalysis]: Checked inductivity of 3282 backedges. 724 proven. 797 refuted. 0 times theorem prover too weak. 1761 trivial. 0 not checked. [2025-01-10 02:30:42,126 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-10 02:30:43,036 INFO L134 CoverageAnalysis]: Checked inductivity of 3282 backedges. 740 proven. 824 refuted. 0 times theorem prover too weak. 1718 trivial. 0 not checked. [2025-01-10 02:30:43,036 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [6642235] provided 0 perfect and 2 imperfect interpolant sequences [2025-01-10 02:30:43,036 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-01-10 02:30:43,036 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 13, 19] total 23 [2025-01-10 02:30:43,036 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [736824652] [2025-01-10 02:30:43,036 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-01-10 02:30:43,037 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2025-01-10 02:30:43,037 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-10 02:30:43,039 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2025-01-10 02:30:43,039 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=104, Invalid=402, Unknown=0, NotChecked=0, Total=506 [2025-01-10 02:30:43,040 INFO L87 Difference]: Start difference. First operand 176 states and 237 transitions. Second operand has 23 states, 23 states have (on average 5.391304347826087) internal successors, (124), 23 states have internal predecessors, (124), 14 states have call successors, (20), 1 states have call predecessors, (20), 10 states have return successors, (25), 13 states have call predecessors, (25), 14 states have call successors, (25) [2025-01-10 02:30:43,369 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-10 02:30:43,369 INFO L93 Difference]: Finished difference Result 353 states and 513 transitions. [2025-01-10 02:30:43,369 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2025-01-10 02:30:43,370 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 23 states have (on average 5.391304347826087) internal successors, (124), 23 states have internal predecessors, (124), 14 states have call successors, (20), 1 states have call predecessors, (20), 10 states have return successors, (25), 13 states have call predecessors, (25), 14 states have call successors, (25) Word has length 307 [2025-01-10 02:30:43,370 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-10 02:30:43,372 INFO L225 Difference]: With dead ends: 353 [2025-01-10 02:30:43,372 INFO L226 Difference]: Without dead ends: 183 [2025-01-10 02:30:43,373 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 646 GetRequests, 602 SyntacticMatches, 9 SemanticMatches, 35 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 307 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=347, Invalid=985, Unknown=0, NotChecked=0, Total=1332 [2025-01-10 02:30:43,373 INFO L435 NwaCegarLoop]: 48 mSDtfsCounter, 70 mSDsluCounter, 207 mSDsCounter, 0 mSdLazyCounter, 559 mSolverCounterSat, 28 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 70 SdHoareTripleChecker+Valid, 255 SdHoareTripleChecker+Invalid, 587 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 28 IncrementalHoareTripleChecker+Valid, 559 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-01-10 02:30:43,374 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [70 Valid, 255 Invalid, 587 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [28 Valid, 559 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-01-10 02:30:43,375 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 183 states. [2025-01-10 02:30:43,383 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 183 to 161. [2025-01-10 02:30:43,383 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 161 states, 129 states have (on average 1.0387596899224807) internal successors, (134), 129 states have internal predecessors, (134), 22 states have call successors, (22), 16 states have call predecessors, (22), 9 states have return successors, (51), 15 states have call predecessors, (51), 21 states have call successors, (51) [2025-01-10 02:30:43,384 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 161 states to 161 states and 207 transitions. [2025-01-10 02:30:43,385 INFO L78 Accepts]: Start accepts. Automaton has 161 states and 207 transitions. Word has length 307 [2025-01-10 02:30:43,386 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-10 02:30:43,386 INFO L471 AbstractCegarLoop]: Abstraction has 161 states and 207 transitions. [2025-01-10 02:30:43,386 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 23 states have (on average 5.391304347826087) internal successors, (124), 23 states have internal predecessors, (124), 14 states have call successors, (20), 1 states have call predecessors, (20), 10 states have return successors, (25), 13 states have call predecessors, (25), 14 states have call successors, (25) [2025-01-10 02:30:43,386 INFO L276 IsEmpty]: Start isEmpty. Operand 161 states and 207 transitions. [2025-01-10 02:30:43,388 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 400 [2025-01-10 02:30:43,388 INFO L210 NwaCegarLoop]: Found error trace [2025-01-10 02:30:43,388 INFO L218 NwaCegarLoop]: trace histogram [41, 40, 33, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 19, 13, 8, 1, 1, 1, 1, 1] [2025-01-10 02:30:43,395 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Ended with exit code 0 [2025-01-10 02:30:43,588 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 15 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable16 [2025-01-10 02:30:43,589 INFO L396 AbstractCegarLoop]: === Iteration 18 === Targeting fibonacciErr5ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-01-10 02:30:43,590 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-10 02:30:43,590 INFO L85 PathProgramCache]: Analyzing trace with hash -2034932484, now seen corresponding path program 7 times [2025-01-10 02:30:43,590 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-10 02:30:43,590 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1328220706] [2025-01-10 02:30:43,590 INFO L95 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2025-01-10 02:30:43,590 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-10 02:30:43,598 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 399 statements into 1 equivalence classes. [2025-01-10 02:30:43,614 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 399 of 399 statements. [2025-01-10 02:30:43,614 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-10 02:30:43,614 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 02:30:44,906 INFO L134 CoverageAnalysis]: Checked inductivity of 5628 backedges. 830 proven. 1470 refuted. 0 times theorem prover too weak. 3328 trivial. 0 not checked. [2025-01-10 02:30:44,906 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-10 02:30:44,906 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1328220706] [2025-01-10 02:30:44,906 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1328220706] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-10 02:30:44,907 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [652822703] [2025-01-10 02:30:44,907 INFO L95 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2025-01-10 02:30:44,907 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-10 02:30:44,907 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-10 02:30:44,909 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-01-10 02:30:44,912 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-01-10 02:30:44,975 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 399 statements into 1 equivalence classes. [2025-01-10 02:30:45,028 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 399 of 399 statements. [2025-01-10 02:30:45,029 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-10 02:30:45,029 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 02:30:45,031 INFO L256 TraceCheckSpWp]: Trace formula consists of 757 conjuncts, 81 conjuncts are in the unsatisfiable core [2025-01-10 02:30:45,037 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-10 02:30:45,368 INFO L134 CoverageAnalysis]: Checked inductivity of 5628 backedges. 820 proven. 1112 refuted. 0 times theorem prover too weak. 3696 trivial. 0 not checked. [2025-01-10 02:30:45,368 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-10 02:30:50,808 INFO L134 CoverageAnalysis]: Checked inductivity of 5628 backedges. 1149 proven. 1015 refuted. 0 times theorem prover too weak. 3464 trivial. 0 not checked. [2025-01-10 02:30:50,809 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [652822703] provided 0 perfect and 2 imperfect interpolant sequences [2025-01-10 02:30:50,809 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-01-10 02:30:50,809 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 18, 29] total 45 [2025-01-10 02:30:50,809 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1069740335] [2025-01-10 02:30:50,809 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-01-10 02:30:50,810 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 46 states [2025-01-10 02:30:50,810 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-10 02:30:50,810 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 46 interpolants. [2025-01-10 02:30:50,811 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=463, Invalid=1607, Unknown=0, NotChecked=0, Total=2070 [2025-01-10 02:30:50,811 INFO L87 Difference]: Start difference. First operand 161 states and 207 transitions. Second operand has 46 states, 45 states have (on average 2.6444444444444444) internal successors, (119), 46 states have internal predecessors, (119), 12 states have call successors, (13), 1 states have call predecessors, (13), 13 states have return successors, (31), 31 states have call predecessors, (31), 12 states have call successors, (31) [2025-01-10 02:30:50,964 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-10 02:30:50,964 INFO L93 Difference]: Finished difference Result 189 states and 251 transitions. [2025-01-10 02:30:50,965 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 26 states. [2025-01-10 02:30:50,965 INFO L78 Accepts]: Start accepts. Automaton has has 46 states, 45 states have (on average 2.6444444444444444) internal successors, (119), 46 states have internal predecessors, (119), 12 states have call successors, (13), 1 states have call predecessors, (13), 13 states have return successors, (31), 31 states have call predecessors, (31), 12 states have call successors, (31) Word has length 399 [2025-01-10 02:30:50,965 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-10 02:30:50,967 INFO L225 Difference]: With dead ends: 189 [2025-01-10 02:30:50,967 INFO L226 Difference]: Without dead ends: 188 [2025-01-10 02:30:50,967 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 881 GetRequests, 782 SyntacticMatches, 51 SemanticMatches, 48 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2454 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=544, Invalid=1906, Unknown=0, NotChecked=0, Total=2450 [2025-01-10 02:30:50,967 INFO L435 NwaCegarLoop]: 20 mSDtfsCounter, 8 mSDsluCounter, 236 mSDsCounter, 0 mSdLazyCounter, 167 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 256 SdHoareTripleChecker+Invalid, 170 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 167 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-01-10 02:30:50,968 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [12 Valid, 256 Invalid, 170 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 167 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-01-10 02:30:50,968 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 188 states. [2025-01-10 02:30:50,978 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 188 to 185. [2025-01-10 02:30:50,978 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 185 states, 149 states have (on average 1.0335570469798658) internal successors, (154), 147 states have internal predecessors, (154), 24 states have call successors, (24), 16 states have call predecessors, (24), 11 states have return successors, (65), 21 states have call predecessors, (65), 23 states have call successors, (65) [2025-01-10 02:30:50,979 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 185 states to 185 states and 243 transitions. [2025-01-10 02:30:50,979 INFO L78 Accepts]: Start accepts. Automaton has 185 states and 243 transitions. Word has length 399 [2025-01-10 02:30:50,981 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-10 02:30:50,981 INFO L471 AbstractCegarLoop]: Abstraction has 185 states and 243 transitions. [2025-01-10 02:30:50,981 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 46 states, 45 states have (on average 2.6444444444444444) internal successors, (119), 46 states have internal predecessors, (119), 12 states have call successors, (13), 1 states have call predecessors, (13), 13 states have return successors, (31), 31 states have call predecessors, (31), 12 states have call successors, (31) [2025-01-10 02:30:50,981 INFO L276 IsEmpty]: Start isEmpty. Operand 185 states and 243 transitions. [2025-01-10 02:30:50,985 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 812 [2025-01-10 02:30:50,986 INFO L210 NwaCegarLoop]: Found error trace [2025-01-10 02:30:50,986 INFO L218 NwaCegarLoop]: trace histogram [83, 82, 67, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 40, 26, 16, 1, 1, 1, 1, 1] [2025-01-10 02:30:50,993 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-01-10 02:30:51,190 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 16 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable17 [2025-01-10 02:30:51,190 INFO L396 AbstractCegarLoop]: === Iteration 19 === Targeting fibonacciErr5ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-01-10 02:30:51,191 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-10 02:30:51,191 INFO L85 PathProgramCache]: Analyzing trace with hash 1430890231, now seen corresponding path program 8 times [2025-01-10 02:30:51,191 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-10 02:30:51,191 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1257368800] [2025-01-10 02:30:51,191 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-01-10 02:30:51,191 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-10 02:30:51,210 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 811 statements into 2 equivalence classes. [2025-01-10 02:30:51,263 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 811 of 811 statements. [2025-01-10 02:30:51,263 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-01-10 02:30:51,263 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 02:30:51,948 INFO L134 CoverageAnalysis]: Checked inductivity of 23859 backedges. 2257 proven. 4945 refuted. 0 times theorem prover too weak. 16657 trivial. 0 not checked. [2025-01-10 02:30:51,948 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-10 02:30:51,948 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1257368800] [2025-01-10 02:30:51,949 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1257368800] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-10 02:30:51,949 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1903556177] [2025-01-10 02:30:51,949 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-01-10 02:30:51,949 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-10 02:30:51,949 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-10 02:30:51,951 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-01-10 02:30:51,952 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-01-10 02:30:52,087 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 811 statements into 2 equivalence classes. [2025-01-10 02:30:52,207 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 811 of 811 statements. [2025-01-10 02:30:52,208 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-01-10 02:30:52,208 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 02:30:52,215 INFO L256 TraceCheckSpWp]: Trace formula consists of 1518 conjuncts, 26 conjuncts are in the unsatisfiable core [2025-01-10 02:30:52,230 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-10 02:30:52,394 INFO L134 CoverageAnalysis]: Checked inductivity of 23859 backedges. 12210 proven. 2667 refuted. 0 times theorem prover too weak. 8982 trivial. 0 not checked. [2025-01-10 02:30:52,396 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-10 02:30:55,337 INFO L134 CoverageAnalysis]: Checked inductivity of 23859 backedges. 2246 proven. 5308 refuted. 0 times theorem prover too weak. 16305 trivial. 0 not checked. [2025-01-10 02:30:55,337 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1903556177] provided 0 perfect and 2 imperfect interpolant sequences [2025-01-10 02:30:55,337 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-01-10 02:30:55,337 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 17, 27] total 32 [2025-01-10 02:30:55,337 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1546270429] [2025-01-10 02:30:55,337 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-01-10 02:30:55,338 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 32 states [2025-01-10 02:30:55,338 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-10 02:30:55,339 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 32 interpolants. [2025-01-10 02:30:55,339 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=179, Invalid=813, Unknown=0, NotChecked=0, Total=992 [2025-01-10 02:30:55,339 INFO L87 Difference]: Start difference. First operand 185 states and 243 transitions. Second operand has 32 states, 32 states have (on average 5.71875) internal successors, (183), 32 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-01-10 02:30:55,740 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-10 02:30:55,740 INFO L93 Difference]: Finished difference Result 361 states and 495 transitions. [2025-01-10 02:30:55,740 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2025-01-10 02:30:55,741 INFO L78 Accepts]: Start accepts. Automaton has has 32 states, 32 states have (on average 5.71875) internal successors, (183), 32 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 811 [2025-01-10 02:30:55,741 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-10 02:30:55,743 INFO L225 Difference]: With dead ends: 361 [2025-01-10 02:30:55,743 INFO L226 Difference]: Without dead ends: 182 [2025-01-10 02:30:55,744 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 1666 GetRequests, 1605 SyntacticMatches, 13 SemanticMatches, 48 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 686 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=632, Invalid=1818, Unknown=0, NotChecked=0, Total=2450 [2025-01-10 02:30:55,744 INFO L435 NwaCegarLoop]: 56 mSDtfsCounter, 161 mSDsluCounter, 217 mSDsCounter, 0 mSdLazyCounter, 633 mSolverCounterSat, 88 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 161 SdHoareTripleChecker+Valid, 273 SdHoareTripleChecker+Invalid, 721 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 88 IncrementalHoareTripleChecker+Valid, 633 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2025-01-10 02:30:55,745 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [161 Valid, 273 Invalid, 721 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [88 Valid, 633 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2025-01-10 02:30:55,745 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 182 states. [2025-01-10 02:30:55,751 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 182 to 164. [2025-01-10 02:30:55,751 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 164 states, 133 states have (on average 1.0300751879699248) internal successors, (137), 130 states have internal predecessors, (137), 21 states have call successors, (21), 17 states have call predecessors, (21), 9 states have return successors, (47), 16 states have call predecessors, (47), 20 states have call successors, (47) [2025-01-10 02:30:55,752 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 164 states to 164 states and 205 transitions. [2025-01-10 02:30:55,752 INFO L78 Accepts]: Start accepts. Automaton has 164 states and 205 transitions. Word has length 811 [2025-01-10 02:30:55,752 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-10 02:30:55,753 INFO L471 AbstractCegarLoop]: Abstraction has 164 states and 205 transitions. [2025-01-10 02:30:55,753 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 32 states, 32 states have (on average 5.71875) internal successors, (183), 32 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-01-10 02:30:55,753 INFO L276 IsEmpty]: Start isEmpty. Operand 164 states and 205 transitions. [2025-01-10 02:30:55,768 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1996 [2025-01-10 02:30:55,768 INFO L210 NwaCegarLoop]: Found error trace [2025-01-10 02:30:55,768 INFO L218 NwaCegarLoop]: trace histogram [205, 201, 166, 103, 103, 103, 103, 101, 101, 101, 101, 101, 100, 100, 100, 99, 63, 39, 1, 1, 1, 1, 1] [2025-01-10 02:30:55,775 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-01-10 02:30:55,969 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable18,17 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-10 02:30:55,969 INFO L396 AbstractCegarLoop]: === Iteration 20 === Targeting fibonacciErr5ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-01-10 02:30:55,970 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-10 02:30:55,970 INFO L85 PathProgramCache]: Analyzing trace with hash -1394743521, now seen corresponding path program 9 times [2025-01-10 02:30:55,970 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-10 02:30:55,970 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [855521211] [2025-01-10 02:30:55,970 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-01-10 02:30:55,970 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-10 02:30:55,999 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 1995 statements into 157 equivalence classes. [2025-01-10 02:30:56,221 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 110 check-sat command(s) and asserted 1395 of 1995 statements. [2025-01-10 02:30:56,221 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 110 check-sat command(s) [2025-01-10 02:30:56,221 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 02:31:21,466 INFO L134 CoverageAnalysis]: Checked inductivity of 146524 backedges. 45861 proven. 15113 refuted. 0 times theorem prover too weak. 85550 trivial. 0 not checked. [2025-01-10 02:31:21,467 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-10 02:31:21,467 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [855521211] [2025-01-10 02:31:21,467 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [855521211] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-10 02:31:21,467 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [893200130] [2025-01-10 02:31:21,467 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-01-10 02:31:21,467 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-10 02:31:21,467 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-10 02:31:21,470 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-01-10 02:31:21,470 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-01-10 02:31:21,696 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 1995 statements into 157 equivalence classes. [2025-01-10 02:31:22,204 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 110 check-sat command(s) and asserted 1395 of 1995 statements. [2025-01-10 02:31:22,205 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 110 check-sat command(s) [2025-01-10 02:31:22,205 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 02:31:22,216 INFO L256 TraceCheckSpWp]: Trace formula consists of 2601 conjuncts, 269 conjuncts are in the unsatisfiable core [2025-01-10 02:31:22,252 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-10 02:31:23,414 INFO L134 CoverageAnalysis]: Checked inductivity of 146524 backedges. 44113 proven. 12050 refuted. 0 times theorem prover too weak. 90361 trivial. 0 not checked. [2025-01-10 02:31:23,415 INFO L312 TraceCheckSpWp]: Computing backward predicates...