./Ultimate.py --spec ../sv-benchmarks/c/properties/no-overflow.prp --file ../sv-benchmarks/c/recursive/Fibonacci04-overflow.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-overflow.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 a4783e070fd2491b45504d9f6f3060ee7c5288027d9d113e851641208eae29b1 --- Real Ultimate output --- This is Ultimate 0.3.0-?-551b009-m [2025-01-10 02:30:15,671 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-01-10 02:30:15,744 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:15,751 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-01-10 02:30:15,752 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-01-10 02:30:15,780 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-01-10 02:30:15,781 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-01-10 02:30:15,781 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-01-10 02:30:15,782 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-01-10 02:30:15,782 INFO L153 SettingsManager]: * Use memory slicer=true [2025-01-10 02:30:15,782 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2025-01-10 02:30:15,783 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2025-01-10 02:30:15,783 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-01-10 02:30:15,783 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-01-10 02:30:15,784 INFO L153 SettingsManager]: * Use SBE=true [2025-01-10 02:30:15,784 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-01-10 02:30:15,784 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2025-01-10 02:30:15,784 INFO L153 SettingsManager]: * sizeof long=4 [2025-01-10 02:30:15,784 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2025-01-10 02:30:15,784 INFO L153 SettingsManager]: * sizeof POINTER=4 [2025-01-10 02:30:15,784 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-01-10 02:30:15,785 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2025-01-10 02:30:15,785 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2025-01-10 02:30:15,785 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2025-01-10 02:30:15,785 INFO L153 SettingsManager]: * Check absence of signed integer overflows=ASSERTandASSUME [2025-01-10 02:30:15,785 INFO L153 SettingsManager]: * Check unreachability of reach_error function=false [2025-01-10 02:30:15,785 INFO L153 SettingsManager]: * sizeof long double=12 [2025-01-10 02:30:15,785 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-01-10 02:30:15,785 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-01-10 02:30:15,785 INFO L153 SettingsManager]: * Use constant arrays=true [2025-01-10 02:30:15,785 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-01-10 02:30:15,785 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-01-10 02:30:15,786 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-01-10 02:30:15,786 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-01-10 02:30:15,786 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-01-10 02:30:15,786 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2025-01-10 02:30:15,786 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-01-10 02:30:15,786 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-01-10 02:30:15,786 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-01-10 02:30:15,786 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-01-10 02:30:15,786 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-01-10 02:30:15,786 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2025-01-10 02:30:15,786 INFO L153 SettingsManager]: * Compute procedure contracts=false [2025-01-10 02:30:15,786 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2025-01-10 02:30:15,786 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2025-01-10 02:30:15,787 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2025-01-10 02:30:15,787 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2025-01-10 02:30:15,788 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2025-01-10 02:30:15,788 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2025-01-10 02:30:15,788 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2025-01-10 02:30:15,788 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 -> a4783e070fd2491b45504d9f6f3060ee7c5288027d9d113e851641208eae29b1 [2025-01-10 02:30:16,071 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-01-10 02:30:16,079 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-01-10 02:30:16,082 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-01-10 02:30:16,083 INFO L270 PluginConnector]: Initializing CDTParser... [2025-01-10 02:30:16,083 INFO L274 PluginConnector]: CDTParser initialized [2025-01-10 02:30:16,085 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/recursive/Fibonacci04-overflow.c [2025-01-10 02:30:17,356 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/9a9b8d00c/0b34eac078604679a35d81424c70cd59/FLAGfaa8ed5ed [2025-01-10 02:30:17,603 INFO L384 CDTParser]: Found 1 translation units. [2025-01-10 02:30:17,604 INFO L180 CDTParser]: Scanning /storage/repos/ultimate-jdk21/releaseScripts/default/sv-benchmarks/c/recursive/Fibonacci04-overflow.c [2025-01-10 02:30:17,621 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/9a9b8d00c/0b34eac078604679a35d81424c70cd59/FLAGfaa8ed5ed [2025-01-10 02:30:17,665 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/9a9b8d00c/0b34eac078604679a35d81424c70cd59 [2025-01-10 02:30:17,667 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-01-10 02:30:17,669 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-01-10 02:30:17,672 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-01-10 02:30:17,672 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-01-10 02:30:17,676 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-01-10 02:30:17,678 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 10.01 02:30:17" (1/1) ... [2025-01-10 02:30:17,678 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@7443a9b5 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.01 02:30:17, skipping insertion in model container [2025-01-10 02:30:17,679 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 10.01 02:30:17" (1/1) ... [2025-01-10 02:30:17,691 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-01-10 02:30:17,837 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-01-10 02:30:17,848 INFO L200 MainTranslator]: Completed pre-run [2025-01-10 02:30:17,863 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-01-10 02:30:17,877 INFO L204 MainTranslator]: Completed translation [2025-01-10 02:30:17,878 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.01 02:30:17 WrapperNode [2025-01-10 02:30:17,878 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-01-10 02:30:17,879 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-01-10 02:30:17,880 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-01-10 02:30:17,880 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-01-10 02:30:17,886 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:17" (1/1) ... [2025-01-10 02:30:17,891 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:17" (1/1) ... [2025-01-10 02:30:17,905 INFO L138 Inliner]: procedures = 13, calls = 11, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 24 [2025-01-10 02:30:17,906 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-01-10 02:30:17,906 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-01-10 02:30:17,907 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-01-10 02:30:17,907 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-01-10 02:30:17,914 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:17" (1/1) ... [2025-01-10 02:30:17,914 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:17" (1/1) ... [2025-01-10 02:30:17,915 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:17" (1/1) ... [2025-01-10 02:30:17,931 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:17,931 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:17" (1/1) ... [2025-01-10 02:30:17,932 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:17" (1/1) ... [2025-01-10 02:30:17,935 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:17" (1/1) ... [2025-01-10 02:30:17,937 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:17" (1/1) ... [2025-01-10 02:30:17,940 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:17" (1/1) ... [2025-01-10 02:30:17,940 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:17" (1/1) ... [2025-01-10 02:30:17,941 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:17" (1/1) ... [2025-01-10 02:30:17,942 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-01-10 02:30:17,942 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2025-01-10 02:30:17,943 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2025-01-10 02:30:17,943 INFO L274 PluginConnector]: RCFGBuilder initialized [2025-01-10 02:30:17,944 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.01 02:30:17" (1/1) ... [2025-01-10 02:30:17,949 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-01-10 02:30:17,962 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-10 02:30:17,978 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:17,985 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:18,001 INFO L130 BoogieDeclarations]: Found specification of procedure fibonacci [2025-01-10 02:30:18,001 INFO L138 BoogieDeclarations]: Found implementation of procedure fibonacci [2025-01-10 02:30:18,001 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2025-01-10 02:30:18,002 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-01-10 02:30:18,002 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-01-10 02:30:18,002 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2025-01-10 02:30:18,054 INFO L234 CfgBuilder]: Building ICFG [2025-01-10 02:30:18,057 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2025-01-10 02:30:18,210 INFO L? ?]: Removed 16 outVars from TransFormulas that were not future-live. [2025-01-10 02:30:18,210 INFO L283 CfgBuilder]: Performing block encoding [2025-01-10 02:30:18,223 INFO L307 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-01-10 02:30:18,224 INFO L312 CfgBuilder]: Removed 0 assume(true) statements. [2025-01-10 02:30:18,226 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 10.01 02:30:18 BoogieIcfgContainer [2025-01-10 02:30:18,226 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2025-01-10 02:30:18,228 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2025-01-10 02:30:18,228 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2025-01-10 02:30:18,232 INFO L274 PluginConnector]: TraceAbstraction initialized [2025-01-10 02:30:18,233 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 10.01 02:30:17" (1/3) ... [2025-01-10 02:30:18,234 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@2266fa35 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 10.01 02:30:18, skipping insertion in model container [2025-01-10 02:30:18,235 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.01 02:30:17" (2/3) ... [2025-01-10 02:30:18,235 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@2266fa35 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 10.01 02:30:18, skipping insertion in model container [2025-01-10 02:30:18,235 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 10.01 02:30:18" (3/3) ... [2025-01-10 02:30:18,236 INFO L128 eAbstractionObserver]: Analyzing ICFG Fibonacci04-overflow.c [2025-01-10 02:30:18,252 INFO L216 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2025-01-10 02:30:18,255 INFO L151 ceAbstractionStarter]: Applying trace abstraction to ICFG Fibonacci04-overflow.c that has 2 procedures, 31 locations, 1 initial locations, 0 loop locations, and 6 error locations. [2025-01-10 02:30:18,308 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2025-01-10 02:30:18,322 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;@22427f81, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2025-01-10 02:30:18,323 INFO L334 AbstractCegarLoop]: Starting to check reachability of 6 error locations. [2025-01-10 02:30:18,327 INFO L276 IsEmpty]: Start isEmpty. Operand has 31 states, 20 states have (on average 1.45) internal successors, (29), 26 states have internal predecessors, (29), 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:18,338 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 8 [2025-01-10 02:30:18,338 INFO L210 NwaCegarLoop]: Found error trace [2025-01-10 02:30:18,339 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2025-01-10 02:30:18,339 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:18,344 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-10 02:30:18,344 INFO L85 PathProgramCache]: Analyzing trace with hash -106871919, now seen corresponding path program 1 times [2025-01-10 02:30:18,352 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-10 02:30:18,353 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1385456398] [2025-01-10 02:30:18,353 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-10 02:30:18,356 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-10 02:30:18,420 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 7 statements into 1 equivalence classes. [2025-01-10 02:30:18,441 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 7 of 7 statements. [2025-01-10 02:30:18,442 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-10 02:30:18,442 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 02:30:18,525 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:18,525 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-10 02:30:18,525 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1385456398] [2025-01-10 02:30:18,526 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1385456398] provided 1 perfect and 0 imperfect interpolant sequences [2025-01-10 02:30:18,526 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-01-10 02:30:18,526 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2025-01-10 02:30:18,527 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [843217660] [2025-01-10 02:30:18,528 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-01-10 02:30:18,533 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2025-01-10 02:30:18,534 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-10 02:30:18,550 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2025-01-10 02:30:18,551 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2025-01-10 02:30:18,552 INFO L87 Difference]: Start difference. First operand has 31 states, 20 states have (on average 1.45) internal successors, (29), 26 states have internal predecessors, (29), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Second operand has 3 states, 2 states have (on average 3.0) internal successors, (6), 3 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-01-10 02:30:18,590 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-10 02:30:18,591 INFO L93 Difference]: Finished difference Result 36 states and 41 transitions. [2025-01-10 02:30:18,592 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2025-01-10 02:30:18,593 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 2 states have (on average 3.0) internal successors, (6), 3 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 7 [2025-01-10 02:30:18,593 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-10 02:30:18,598 INFO L225 Difference]: With dead ends: 36 [2025-01-10 02:30:18,598 INFO L226 Difference]: Without dead ends: 24 [2025-01-10 02:30:18,600 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:18,603 INFO L435 NwaCegarLoop]: 27 mSDtfsCounter, 11 mSDsluCounter, 13 mSDsCounter, 0 mSdLazyCounter, 13 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 40 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:18,603 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [13 Valid, 40 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:18,615 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 24 states. [2025-01-10 02:30:18,629 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 24 to 22. [2025-01-10 02:30:18,630 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 22 states, 14 states have (on average 1.4285714285714286) internal successors, (20), 18 states have internal predecessors, (20), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-01-10 02:30:18,633 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 22 states to 22 states and 25 transitions. [2025-01-10 02:30:18,635 INFO L78 Accepts]: Start accepts. Automaton has 22 states and 25 transitions. Word has length 7 [2025-01-10 02:30:18,635 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-10 02:30:18,635 INFO L471 AbstractCegarLoop]: Abstraction has 22 states and 25 transitions. [2025-01-10 02:30:18,635 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 2 states have (on average 3.0) internal successors, (6), 3 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-01-10 02:30:18,635 INFO L276 IsEmpty]: Start isEmpty. Operand 22 states and 25 transitions. [2025-01-10 02:30:18,636 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 9 [2025-01-10 02:30:18,636 INFO L210 NwaCegarLoop]: Found error trace [2025-01-10 02:30:18,636 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2025-01-10 02:30:18,636 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2025-01-10 02:30:18,637 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:18,637 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-10 02:30:18,637 INFO L85 PathProgramCache]: Analyzing trace with hash 981937849, now seen corresponding path program 1 times [2025-01-10 02:30:18,637 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-10 02:30:18,637 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [74034699] [2025-01-10 02:30:18,637 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-10 02:30:18,637 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-10 02:30:18,642 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 8 statements into 1 equivalence classes. [2025-01-10 02:30:18,647 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 8 of 8 statements. [2025-01-10 02:30:18,647 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-10 02:30:18,647 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 02:30:18,723 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:18,724 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-10 02:30:18,724 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [74034699] [2025-01-10 02:30:18,724 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [74034699] provided 1 perfect and 0 imperfect interpolant sequences [2025-01-10 02:30:18,724 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-01-10 02:30:18,724 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2025-01-10 02:30:18,724 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [724723694] [2025-01-10 02:30:18,724 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-01-10 02:30:18,725 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-01-10 02:30:18,725 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-10 02:30:18,725 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-01-10 02:30:18,726 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-01-10 02:30:18,726 INFO L87 Difference]: Start difference. First operand 22 states and 25 transitions. Second operand has 5 states, 3 states have (on average 2.3333333333333335) internal successors, (7), 4 states have internal predecessors, (7), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-01-10 02:30:18,794 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-10 02:30:18,794 INFO L93 Difference]: Finished difference Result 24 states and 28 transitions. [2025-01-10 02:30:18,795 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-01-10 02:30:18,795 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 3 states have (on average 2.3333333333333335) internal successors, (7), 4 states have internal predecessors, (7), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 8 [2025-01-10 02:30:18,795 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-10 02:30:18,796 INFO L225 Difference]: With dead ends: 24 [2025-01-10 02:30:18,796 INFO L226 Difference]: Without dead ends: 22 [2025-01-10 02:30:18,796 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2025-01-10 02:30:18,797 INFO L435 NwaCegarLoop]: 13 mSDtfsCounter, 26 mSDsluCounter, 16 mSDsCounter, 0 mSdLazyCounter, 32 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 26 SdHoareTripleChecker+Valid, 29 SdHoareTripleChecker+Invalid, 39 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 32 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-01-10 02:30:18,797 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [26 Valid, 29 Invalid, 39 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 32 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-01-10 02:30:18,798 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 22 states. [2025-01-10 02:30:18,801 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 22 to 20. [2025-01-10 02:30:18,801 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 20 states, 14 states have (on average 1.2857142857142858) internal successors, (18), 16 states have internal predecessors, (18), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-01-10 02:30:18,802 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 20 states to 20 states and 23 transitions. [2025-01-10 02:30:18,802 INFO L78 Accepts]: Start accepts. Automaton has 20 states and 23 transitions. Word has length 8 [2025-01-10 02:30:18,802 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-10 02:30:18,802 INFO L471 AbstractCegarLoop]: Abstraction has 20 states and 23 transitions. [2025-01-10 02:30:18,803 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 3 states have (on average 2.3333333333333335) internal successors, (7), 4 states have internal predecessors, (7), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-01-10 02:30:18,803 INFO L276 IsEmpty]: Start isEmpty. Operand 20 states and 23 transitions. [2025-01-10 02:30:18,803 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2025-01-10 02:30:18,803 INFO L210 NwaCegarLoop]: Found error trace [2025-01-10 02:30:18,803 INFO L218 NwaCegarLoop]: trace histogram [4, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-01-10 02:30:18,804 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2025-01-10 02:30:18,804 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:18,804 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-10 02:30:18,805 INFO L85 PathProgramCache]: Analyzing trace with hash -590814878, now seen corresponding path program 1 times [2025-01-10 02:30:18,805 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-10 02:30:18,805 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [869700360] [2025-01-10 02:30:18,805 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-10 02:30:18,805 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-10 02:30:18,814 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 29 statements into 1 equivalence classes. [2025-01-10 02:30:18,838 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 29 of 29 statements. [2025-01-10 02:30:18,838 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-10 02:30:18,838 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 02:30:19,007 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2025-01-10 02:30:19,007 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-10 02:30:19,007 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [869700360] [2025-01-10 02:30:19,008 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [869700360] provided 1 perfect and 0 imperfect interpolant sequences [2025-01-10 02:30:19,008 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-01-10 02:30:19,008 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2025-01-10 02:30:19,008 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1640828968] [2025-01-10 02:30:19,008 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-01-10 02:30:19,008 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-01-10 02:30:19,008 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-10 02:30:19,009 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-01-10 02:30:19,009 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2025-01-10 02:30:19,009 INFO L87 Difference]: Start difference. First operand 20 states and 23 transitions. Second operand has 5 states, 4 states have (on average 3.5) internal successors, (14), 5 states have internal predecessors, (14), 2 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-01-10 02:30:19,055 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-10 02:30:19,056 INFO L93 Difference]: Finished difference Result 34 states and 42 transitions. [2025-01-10 02:30:19,056 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-01-10 02:30:19,056 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 3.5) internal successors, (14), 5 states have internal predecessors, (14), 2 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 29 [2025-01-10 02:30:19,056 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-10 02:30:19,057 INFO L225 Difference]: With dead ends: 34 [2025-01-10 02:30:19,057 INFO L226 Difference]: Without dead ends: 32 [2025-01-10 02:30:19,057 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:19,058 INFO L435 NwaCegarLoop]: 17 mSDtfsCounter, 4 mSDsluCounter, 35 mSDsCounter, 0 mSdLazyCounter, 23 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 52 SdHoareTripleChecker+Invalid, 25 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 23 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-01-10 02:30:19,059 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [5 Valid, 52 Invalid, 25 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 23 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-01-10 02:30:19,059 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 32 states. [2025-01-10 02:30:19,068 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 32 to 29. [2025-01-10 02:30:19,068 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 29 states, 21 states have (on average 1.1904761904761905) internal successors, (25), 23 states have internal predecessors, (25), 4 states have call successors, (4), 1 states have call predecessors, (4), 2 states have return successors, (6), 4 states have call predecessors, (6), 3 states have call successors, (6) [2025-01-10 02:30:19,070 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 29 states to 29 states and 35 transitions. [2025-01-10 02:30:19,070 INFO L78 Accepts]: Start accepts. Automaton has 29 states and 35 transitions. Word has length 29 [2025-01-10 02:30:19,070 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-10 02:30:19,070 INFO L471 AbstractCegarLoop]: Abstraction has 29 states and 35 transitions. [2025-01-10 02:30:19,070 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 3.5) internal successors, (14), 5 states have internal predecessors, (14), 2 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-01-10 02:30:19,071 INFO L276 IsEmpty]: Start isEmpty. Operand 29 states and 35 transitions. [2025-01-10 02:30:19,071 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2025-01-10 02:30:19,071 INFO L210 NwaCegarLoop]: Found error trace [2025-01-10 02:30:19,072 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:19,072 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2025-01-10 02:30:19,072 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:19,072 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-10 02:30:19,072 INFO L85 PathProgramCache]: Analyzing trace with hash -1274820555, now seen corresponding path program 1 times [2025-01-10 02:30:19,072 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-10 02:30:19,073 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [535081312] [2025-01-10 02:30:19,073 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-10 02:30:19,073 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-10 02:30:19,081 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 24 statements into 1 equivalence classes. [2025-01-10 02:30:19,094 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 24 of 24 statements. [2025-01-10 02:30:19,094 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-10 02:30:19,094 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 02:30:19,200 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:19,200 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-10 02:30:19,200 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [535081312] [2025-01-10 02:30:19,200 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [535081312] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-10 02:30:19,200 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1566094502] [2025-01-10 02:30:19,200 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-10 02:30:19,200 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-10 02:30:19,200 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-10 02:30:19,204 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:19,207 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:19,242 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 24 statements into 1 equivalence classes. [2025-01-10 02:30:19,255 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 24 of 24 statements. [2025-01-10 02:30:19,256 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-10 02:30:19,256 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 02:30:19,257 INFO L256 TraceCheckSpWp]: Trace formula consists of 66 conjuncts, 6 conjuncts are in the unsatisfiable core [2025-01-10 02:30:19,262 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-10 02:30:19,355 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 3 proven. 3 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2025-01-10 02:30:19,355 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-10 02:30:19,532 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 3 proven. 3 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2025-01-10 02:30:19,533 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1566094502] provided 0 perfect and 2 imperfect interpolant sequences [2025-01-10 02:30:19,534 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-01-10 02:30:19,534 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 7, 7] total 15 [2025-01-10 02:30:19,534 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1582263347] [2025-01-10 02:30:19,534 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-01-10 02:30:19,535 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2025-01-10 02:30:19,535 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-10 02:30:19,536 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2025-01-10 02:30:19,536 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=35, Invalid=175, Unknown=0, NotChecked=0, Total=210 [2025-01-10 02:30:19,536 INFO L87 Difference]: Start difference. First operand 29 states and 35 transitions. Second operand has 15 states, 15 states have (on average 2.4) internal successors, (36), 15 states have internal predecessors, (36), 4 states have call successors, (5), 1 states have call predecessors, (5), 5 states have return successors, (6), 5 states have call predecessors, (6), 4 states have call successors, (6) [2025-01-10 02:30:19,813 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-10 02:30:19,813 INFO L93 Difference]: Finished difference Result 90 states and 128 transitions. [2025-01-10 02:30:19,814 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2025-01-10 02:30:19,814 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 15 states have (on average 2.4) internal successors, (36), 15 states have internal predecessors, (36), 4 states have call successors, (5), 1 states have call predecessors, (5), 5 states have return successors, (6), 5 states have call predecessors, (6), 4 states have call successors, (6) Word has length 24 [2025-01-10 02:30:19,815 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-10 02:30:19,816 INFO L225 Difference]: With dead ends: 90 [2025-01-10 02:30:19,816 INFO L226 Difference]: Without dead ends: 64 [2025-01-10 02:30:19,817 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 60 GetRequests, 38 SyntacticMatches, 1 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 42 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=111, Invalid=395, Unknown=0, NotChecked=0, Total=506 [2025-01-10 02:30:19,820 INFO L435 NwaCegarLoop]: 12 mSDtfsCounter, 102 mSDsluCounter, 82 mSDsCounter, 0 mSdLazyCounter, 188 mSolverCounterSat, 44 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 102 SdHoareTripleChecker+Valid, 94 SdHoareTripleChecker+Invalid, 232 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 44 IncrementalHoareTripleChecker+Valid, 188 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-01-10 02:30:19,820 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [102 Valid, 94 Invalid, 232 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [44 Valid, 188 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-01-10 02:30:19,821 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 64 states. [2025-01-10 02:30:19,833 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 64 to 52. [2025-01-10 02:30:19,834 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 52 states, 38 states have (on average 1.105263157894737) internal successors, (42), 41 states have internal predecessors, (42), 7 states have call successors, (7), 2 states have call predecessors, (7), 5 states have return successors, (18), 8 states have call predecessors, (18), 6 states have call successors, (18) [2025-01-10 02:30:19,835 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 52 states to 52 states and 67 transitions. [2025-01-10 02:30:19,836 INFO L78 Accepts]: Start accepts. Automaton has 52 states and 67 transitions. Word has length 24 [2025-01-10 02:30:19,836 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-10 02:30:19,836 INFO L471 AbstractCegarLoop]: Abstraction has 52 states and 67 transitions. [2025-01-10 02:30:19,836 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 2.4) internal successors, (36), 15 states have internal predecessors, (36), 4 states have call successors, (5), 1 states have call predecessors, (5), 5 states have return successors, (6), 5 states have call predecessors, (6), 4 states have call successors, (6) [2025-01-10 02:30:19,836 INFO L276 IsEmpty]: Start isEmpty. Operand 52 states and 67 transitions. [2025-01-10 02:30:19,837 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2025-01-10 02:30:19,837 INFO L210 NwaCegarLoop]: Found error trace [2025-01-10 02:30:19,837 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:19,843 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2025-01-10 02:30:20,038 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:20,039 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:20,039 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-10 02:30:20,039 INFO L85 PathProgramCache]: Analyzing trace with hash -254150789, now seen corresponding path program 2 times [2025-01-10 02:30:20,039 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-10 02:30:20,039 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1024108552] [2025-01-10 02:30:20,040 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-01-10 02:30:20,040 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-10 02:30:20,045 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 24 statements into 2 equivalence classes. [2025-01-10 02:30:20,054 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 24 of 24 statements. [2025-01-10 02:30:20,055 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-01-10 02:30:20,055 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 02:30:20,178 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:20,178 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-10 02:30:20,178 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1024108552] [2025-01-10 02:30:20,178 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1024108552] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-10 02:30:20,178 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [895749594] [2025-01-10 02:30:20,178 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-01-10 02:30:20,179 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-10 02:30:20,179 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-10 02:30:20,181 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:20,182 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:20,205 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 24 statements into 2 equivalence classes. [2025-01-10 02:30:20,214 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 24 of 24 statements. [2025-01-10 02:30:20,214 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-01-10 02:30:20,215 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 02:30:20,215 INFO L256 TraceCheckSpWp]: Trace formula consists of 66 conjuncts, 4 conjuncts are in the unsatisfiable core [2025-01-10 02:30:20,216 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-10 02:30:20,262 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:20,263 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-01-10 02:30:20,263 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [895749594] provided 1 perfect and 0 imperfect interpolant sequences [2025-01-10 02:30:20,263 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-01-10 02:30:20,263 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [5] total 7 [2025-01-10 02:30:20,263 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [72798402] [2025-01-10 02:30:20,263 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-01-10 02:30:20,263 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-01-10 02:30:20,263 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-10 02:30:20,264 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-01-10 02:30:20,264 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=38, Unknown=0, NotChecked=0, Total=56 [2025-01-10 02:30:20,264 INFO L87 Difference]: Start difference. First operand 52 states and 67 transitions. Second operand has 5 states, 4 states have (on average 4.0) internal successors, (16), 5 states have internal predecessors, (16), 2 states have call successors, (3), 1 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-01-10 02:30:20,304 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-10 02:30:20,304 INFO L93 Difference]: Finished difference Result 59 states and 75 transitions. [2025-01-10 02:30:20,304 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-01-10 02:30:20,304 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 4.0) internal successors, (16), 5 states have internal predecessors, (16), 2 states have call successors, (3), 1 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 24 [2025-01-10 02:30:20,305 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-10 02:30:20,305 INFO L225 Difference]: With dead ends: 59 [2025-01-10 02:30:20,306 INFO L226 Difference]: Without dead ends: 58 [2025-01-10 02:30:20,306 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 28 GetRequests, 21 SyntacticMatches, 1 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=18, Invalid=38, Unknown=0, NotChecked=0, Total=56 [2025-01-10 02:30:20,307 INFO L435 NwaCegarLoop]: 17 mSDtfsCounter, 3 mSDsluCounter, 44 mSDsCounter, 0 mSdLazyCounter, 23 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 61 SdHoareTripleChecker+Invalid, 25 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 23 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-01-10 02:30:20,307 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 61 Invalid, 25 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 23 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-01-10 02:30:20,309 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 58 states. [2025-01-10 02:30:20,323 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 58 to 54. [2025-01-10 02:30:20,324 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 54 states, 40 states have (on average 1.1) internal successors, (44), 42 states have internal predecessors, (44), 7 states have call successors, (7), 2 states have call predecessors, (7), 5 states have return successors, (18), 9 states have call predecessors, (18), 6 states have call successors, (18) [2025-01-10 02:30:20,325 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 69 transitions. [2025-01-10 02:30:20,328 INFO L78 Accepts]: Start accepts. Automaton has 54 states and 69 transitions. Word has length 24 [2025-01-10 02:30:20,329 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-10 02:30:20,329 INFO L471 AbstractCegarLoop]: Abstraction has 54 states and 69 transitions. [2025-01-10 02:30:20,329 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 4.0) internal successors, (16), 5 states have internal predecessors, (16), 2 states have call successors, (3), 1 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-01-10 02:30:20,329 INFO L276 IsEmpty]: Start isEmpty. Operand 54 states and 69 transitions. [2025-01-10 02:30:20,330 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2025-01-10 02:30:20,330 INFO L210 NwaCegarLoop]: Found error trace [2025-01-10 02:30:20,330 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:20,339 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:20,530 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:20,531 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:20,531 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-10 02:30:20,531 INFO L85 PathProgramCache]: Analyzing trace with hash 1092136320, now seen corresponding path program 1 times [2025-01-10 02:30:20,531 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-10 02:30:20,531 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1701685874] [2025-01-10 02:30:20,531 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-10 02:30:20,531 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-10 02:30:20,535 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 31 statements into 1 equivalence classes. [2025-01-10 02:30:20,542 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 31 of 31 statements. [2025-01-10 02:30:20,542 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-10 02:30:20,542 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 02:30:20,625 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:20,625 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-10 02:30:20,625 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1701685874] [2025-01-10 02:30:20,625 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1701685874] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-10 02:30:20,626 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1394644238] [2025-01-10 02:30:20,626 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-10 02:30:20,626 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-10 02:30:20,626 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-10 02:30:20,628 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:20,630 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:20,655 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 31 statements into 1 equivalence classes. [2025-01-10 02:30:20,666 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 31 of 31 statements. [2025-01-10 02:30:20,666 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-10 02:30:20,667 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 02:30:20,667 INFO L256 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 5 conjuncts are in the unsatisfiable core [2025-01-10 02:30:20,668 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-10 02:30:20,729 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2025-01-10 02:30:20,730 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-01-10 02:30:20,730 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1394644238] provided 1 perfect and 0 imperfect interpolant sequences [2025-01-10 02:30:20,730 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-01-10 02:30:20,730 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [5] total 9 [2025-01-10 02:30:20,730 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [81491571] [2025-01-10 02:30:20,730 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-01-10 02:30:20,730 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2025-01-10 02:30:20,730 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-10 02:30:20,731 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2025-01-10 02:30:20,731 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=64, Unknown=0, NotChecked=0, Total=90 [2025-01-10 02:30:20,731 INFO L87 Difference]: Start difference. First operand 54 states and 69 transitions. Second operand has 6 states, 5 states have (on average 3.4) internal successors, (17), 6 states have internal predecessors, (17), 2 states have call successors, (3), 1 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-01-10 02:30:20,781 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-10 02:30:20,781 INFO L93 Difference]: Finished difference Result 81 states and 116 transitions. [2025-01-10 02:30:20,781 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2025-01-10 02:30:20,781 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 3.4) internal successors, (17), 6 states have internal predecessors, (17), 2 states have call successors, (3), 1 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 31 [2025-01-10 02:30:20,782 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-10 02:30:20,783 INFO L225 Difference]: With dead ends: 81 [2025-01-10 02:30:20,783 INFO L226 Difference]: Without dead ends: 80 [2025-01-10 02:30:20,783 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 35 GetRequests, 27 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 12 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=26, Invalid=64, Unknown=0, NotChecked=0, Total=90 [2025-01-10 02:30:20,784 INFO L435 NwaCegarLoop]: 17 mSDtfsCounter, 2 mSDsluCounter, 63 mSDsCounter, 0 mSdLazyCounter, 33 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 80 SdHoareTripleChecker+Invalid, 34 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 33 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-01-10 02:30:20,784 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 80 Invalid, 34 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 33 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-01-10 02:30:20,785 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 80 states. [2025-01-10 02:30:20,801 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 80 to 63. [2025-01-10 02:30:20,802 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 63 states, 47 states have (on average 1.0851063829787233) internal successors, (51), 49 states have internal predecessors, (51), 8 states have call successors, (8), 2 states have call predecessors, (8), 6 states have return successors, (27), 11 states have call predecessors, (27), 7 states have call successors, (27) [2025-01-10 02:30:20,804 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 63 states to 63 states and 86 transitions. [2025-01-10 02:30:20,804 INFO L78 Accepts]: Start accepts. Automaton has 63 states and 86 transitions. Word has length 31 [2025-01-10 02:30:20,804 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-10 02:30:20,804 INFO L471 AbstractCegarLoop]: Abstraction has 63 states and 86 transitions. [2025-01-10 02:30:20,804 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 3.4) internal successors, (17), 6 states have internal predecessors, (17), 2 states have call successors, (3), 1 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-01-10 02:30:20,804 INFO L276 IsEmpty]: Start isEmpty. Operand 63 states and 86 transitions. [2025-01-10 02:30:20,806 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 52 [2025-01-10 02:30:20,806 INFO L210 NwaCegarLoop]: Found error trace [2025-01-10 02:30:20,806 INFO L218 NwaCegarLoop]: trace histogram [6, 5, 4, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1] [2025-01-10 02:30:20,815 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:21,006 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:21,007 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:21,007 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-10 02:30:21,007 INFO L85 PathProgramCache]: Analyzing trace with hash -940023341, now seen corresponding path program 1 times [2025-01-10 02:30:21,007 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-10 02:30:21,007 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1878972162] [2025-01-10 02:30:21,007 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-10 02:30:21,007 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-10 02:30:21,013 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 51 statements into 1 equivalence classes. [2025-01-10 02:30:21,022 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 51 of 51 statements. [2025-01-10 02:30:21,022 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-10 02:30:21,023 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 02:30:21,158 INFO L134 CoverageAnalysis]: Checked inductivity of 68 backedges. 2 proven. 15 refuted. 0 times theorem prover too weak. 51 trivial. 0 not checked. [2025-01-10 02:30:21,158 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-10 02:30:21,158 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1878972162] [2025-01-10 02:30:21,158 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1878972162] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-10 02:30:21,158 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [327546961] [2025-01-10 02:30:21,158 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-10 02:30:21,158 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-10 02:30:21,158 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-10 02:30:21,160 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:21,162 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:21,186 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 51 statements into 1 equivalence classes. [2025-01-10 02:30:21,203 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 51 of 51 statements. [2025-01-10 02:30:21,203 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-10 02:30:21,203 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 02:30:21,204 INFO L256 TraceCheckSpWp]: Trace formula consists of 114 conjuncts, 9 conjuncts are in the unsatisfiable core [2025-01-10 02:30:21,207 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-10 02:30:21,318 INFO L134 CoverageAnalysis]: Checked inductivity of 68 backedges. 2 proven. 7 refuted. 0 times theorem prover too weak. 59 trivial. 0 not checked. [2025-01-10 02:30:21,318 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-10 02:30:21,549 INFO L134 CoverageAnalysis]: Checked inductivity of 68 backedges. 6 proven. 7 refuted. 0 times theorem prover too weak. 55 trivial. 0 not checked. [2025-01-10 02:30:21,549 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [327546961] provided 0 perfect and 2 imperfect interpolant sequences [2025-01-10 02:30:21,550 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-01-10 02:30:21,550 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 6, 7] total 15 [2025-01-10 02:30:21,550 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1980699734] [2025-01-10 02:30:21,550 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-01-10 02:30:21,550 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2025-01-10 02:30:21,550 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-10 02:30:21,551 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2025-01-10 02:30:21,551 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=62, Invalid=178, Unknown=0, NotChecked=0, Total=240 [2025-01-10 02:30:21,551 INFO L87 Difference]: Start difference. First operand 63 states and 86 transitions. Second operand has 16 states, 15 states have (on average 2.933333333333333) internal successors, (44), 16 states have internal predecessors, (44), 4 states have call successors, (5), 1 states have call predecessors, (5), 5 states have return successors, (9), 9 states have call predecessors, (9), 4 states have call successors, (9) [2025-01-10 02:30:21,787 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-10 02:30:21,787 INFO L93 Difference]: Finished difference Result 140 states and 216 transitions. [2025-01-10 02:30:21,787 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2025-01-10 02:30:21,788 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 15 states have (on average 2.933333333333333) internal successors, (44), 16 states have internal predecessors, (44), 4 states have call successors, (5), 1 states have call predecessors, (5), 5 states have return successors, (9), 9 states have call predecessors, (9), 4 states have call successors, (9) Word has length 51 [2025-01-10 02:30:21,788 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-10 02:30:21,790 INFO L225 Difference]: With dead ends: 140 [2025-01-10 02:30:21,791 INFO L226 Difference]: Without dead ends: 138 [2025-01-10 02:30:21,791 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 115 GetRequests, 93 SyntacticMatches, 2 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 111 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=126, Invalid=336, Unknown=0, NotChecked=0, Total=462 [2025-01-10 02:30:21,792 INFO L435 NwaCegarLoop]: 24 mSDtfsCounter, 14 mSDsluCounter, 161 mSDsCounter, 0 mSdLazyCounter, 151 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 21 SdHoareTripleChecker+Valid, 185 SdHoareTripleChecker+Invalid, 156 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 151 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-01-10 02:30:21,792 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [21 Valid, 185 Invalid, 156 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 151 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-01-10 02:30:21,793 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 138 states. [2025-01-10 02:30:21,809 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 138 to 97. [2025-01-10 02:30:21,809 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 97 states, 75 states have (on average 1.08) internal successors, (81), 74 states have internal predecessors, (81), 11 states have call successors, (11), 2 states have call predecessors, (11), 9 states have return successors, (66), 20 states have call predecessors, (66), 10 states have call successors, (66) [2025-01-10 02:30:21,814 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 97 states to 97 states and 158 transitions. [2025-01-10 02:30:21,814 INFO L78 Accepts]: Start accepts. Automaton has 97 states and 158 transitions. Word has length 51 [2025-01-10 02:30:21,815 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-10 02:30:21,815 INFO L471 AbstractCegarLoop]: Abstraction has 97 states and 158 transitions. [2025-01-10 02:30:21,815 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 15 states have (on average 2.933333333333333) internal successors, (44), 16 states have internal predecessors, (44), 4 states have call successors, (5), 1 states have call predecessors, (5), 5 states have return successors, (9), 9 states have call predecessors, (9), 4 states have call successors, (9) [2025-01-10 02:30:21,815 INFO L276 IsEmpty]: Start isEmpty. Operand 97 states and 158 transitions. [2025-01-10 02:30:21,820 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 88 [2025-01-10 02:30:21,820 INFO L210 NwaCegarLoop]: Found error trace [2025-01-10 02:30:21,820 INFO L218 NwaCegarLoop]: trace histogram [10, 8, 6, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 1, 1, 1, 1, 1] [2025-01-10 02:30:21,830 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:22,021 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:22,021 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:22,021 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-10 02:30:22,021 INFO L85 PathProgramCache]: Analyzing trace with hash 699737977, now seen corresponding path program 1 times [2025-01-10 02:30:22,021 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-10 02:30:22,022 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [529525280] [2025-01-10 02:30:22,022 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-10 02:30:22,022 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-10 02:30:22,029 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 87 statements into 1 equivalence classes. [2025-01-10 02:30:22,037 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 87 of 87 statements. [2025-01-10 02:30:22,037 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-10 02:30:22,037 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 02:30:22,199 INFO L134 CoverageAnalysis]: Checked inductivity of 230 backedges. 50 proven. 80 refuted. 0 times theorem prover too weak. 100 trivial. 0 not checked. [2025-01-10 02:30:22,199 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-10 02:30:22,199 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [529525280] [2025-01-10 02:30:22,199 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [529525280] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-10 02:30:22,199 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1386571109] [2025-01-10 02:30:22,199 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-10 02:30:22,199 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-10 02:30:22,199 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-10 02:30:22,201 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:22,204 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:22,232 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 87 statements into 1 equivalence classes. [2025-01-10 02:30:22,259 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 87 of 87 statements. [2025-01-10 02:30:22,260 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-10 02:30:22,260 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 02:30:22,261 INFO L256 TraceCheckSpWp]: Trace formula consists of 181 conjuncts, 10 conjuncts are in the unsatisfiable core [2025-01-10 02:30:22,263 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-10 02:30:22,369 INFO L134 CoverageAnalysis]: Checked inductivity of 230 backedges. 67 proven. 84 refuted. 0 times theorem prover too weak. 79 trivial. 0 not checked. [2025-01-10 02:30:22,370 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-10 02:30:22,763 INFO L134 CoverageAnalysis]: Checked inductivity of 230 backedges. 67 proven. 87 refuted. 0 times theorem prover too weak. 76 trivial. 0 not checked. [2025-01-10 02:30:22,764 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1386571109] provided 0 perfect and 2 imperfect interpolant sequences [2025-01-10 02:30:22,764 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-01-10 02:30:22,764 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 9, 11] total 16 [2025-01-10 02:30:22,764 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1214418234] [2025-01-10 02:30:22,764 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-01-10 02:30:22,765 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2025-01-10 02:30:22,765 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-10 02:30:22,765 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2025-01-10 02:30:22,765 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=53, Invalid=187, Unknown=0, NotChecked=0, Total=240 [2025-01-10 02:30:22,766 INFO L87 Difference]: Start difference. First operand 97 states and 158 transitions. Second operand has 16 states, 16 states have (on average 5.0) internal successors, (80), 16 states have internal predecessors, (80), 10 states have call successors, (14), 1 states have call predecessors, (14), 5 states have return successors, (14), 7 states have call predecessors, (14), 10 states have call successors, (14) [2025-01-10 02:30:22,944 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-10 02:30:22,944 INFO L93 Difference]: Finished difference Result 173 states and 298 transitions. [2025-01-10 02:30:22,944 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2025-01-10 02:30:22,944 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 16 states have (on average 5.0) internal successors, (80), 16 states have internal predecessors, (80), 10 states have call successors, (14), 1 states have call predecessors, (14), 5 states have return successors, (14), 7 states have call predecessors, (14), 10 states have call successors, (14) Word has length 87 [2025-01-10 02:30:22,945 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-10 02:30:22,946 INFO L225 Difference]: With dead ends: 173 [2025-01-10 02:30:22,946 INFO L226 Difference]: Without dead ends: 79 [2025-01-10 02:30:22,950 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 194 GetRequests, 167 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:22,952 INFO L435 NwaCegarLoop]: 15 mSDtfsCounter, 88 mSDsluCounter, 46 mSDsCounter, 0 mSdLazyCounter, 111 mSolverCounterSat, 37 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 88 SdHoareTripleChecker+Valid, 61 SdHoareTripleChecker+Invalid, 148 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 37 IncrementalHoareTripleChecker+Valid, 111 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-01-10 02:30:22,952 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [88 Valid, 61 Invalid, 148 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [37 Valid, 111 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-01-10 02:30:22,954 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 79 states. [2025-01-10 02:30:22,967 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 79 to 69. [2025-01-10 02:30:22,968 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 69 states, 54 states have (on average 1.1111111111111112) internal successors, (60), 52 states have internal predecessors, (60), 7 states have call successors, (7), 4 states have call predecessors, (7), 6 states have return successors, (26), 12 states have call predecessors, (26), 6 states have call successors, (26) [2025-01-10 02:30:22,970 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 69 states to 69 states and 93 transitions. [2025-01-10 02:30:22,972 INFO L78 Accepts]: Start accepts. Automaton has 69 states and 93 transitions. Word has length 87 [2025-01-10 02:30:22,973 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-10 02:30:22,973 INFO L471 AbstractCegarLoop]: Abstraction has 69 states and 93 transitions. [2025-01-10 02:30:22,973 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 16 states have (on average 5.0) internal successors, (80), 16 states have internal predecessors, (80), 10 states have call successors, (14), 1 states have call predecessors, (14), 5 states have return successors, (14), 7 states have call predecessors, (14), 10 states have call successors, (14) [2025-01-10 02:30:22,973 INFO L276 IsEmpty]: Start isEmpty. Operand 69 states and 93 transitions. [2025-01-10 02:30:22,975 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 129 [2025-01-10 02:30:22,975 INFO L210 NwaCegarLoop]: Found error trace [2025-01-10 02:30:22,975 INFO L218 NwaCegarLoop]: trace histogram [14, 12, 11, 7, 7, 7, 7, 6, 6, 6, 6, 6, 6, 6, 5, 5, 4, 3, 1, 1, 1, 1] [2025-01-10 02:30:22,985 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2025-01-10 02:30:23,175 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:23,176 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:23,176 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-10 02:30:23,176 INFO L85 PathProgramCache]: Analyzing trace with hash -1610964705, now seen corresponding path program 2 times [2025-01-10 02:30:23,176 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-10 02:30:23,176 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1171462941] [2025-01-10 02:30:23,176 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-01-10 02:30:23,176 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-10 02:30:23,185 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 128 statements into 2 equivalence classes. [2025-01-10 02:30:23,198 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 128 of 128 statements. [2025-01-10 02:30:23,198 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-01-10 02:30:23,199 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 02:30:23,360 INFO L134 CoverageAnalysis]: Checked inductivity of 532 backedges. 55 proven. 135 refuted. 0 times theorem prover too weak. 342 trivial. 0 not checked. [2025-01-10 02:30:23,360 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-10 02:30:23,360 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1171462941] [2025-01-10 02:30:23,360 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1171462941] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-10 02:30:23,360 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1522071058] [2025-01-10 02:30:23,360 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-01-10 02:30:23,360 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-10 02:30:23,360 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-10 02:30:23,362 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:23,364 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:23,396 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 128 statements into 2 equivalence classes. [2025-01-10 02:30:23,427 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 128 of 128 statements. [2025-01-10 02:30:23,427 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-01-10 02:30:23,427 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 02:30:23,429 INFO L256 TraceCheckSpWp]: Trace formula consists of 257 conjuncts, 8 conjuncts are in the unsatisfiable core [2025-01-10 02:30:23,431 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-10 02:30:23,501 INFO L134 CoverageAnalysis]: Checked inductivity of 532 backedges. 305 proven. 15 refuted. 0 times theorem prover too weak. 212 trivial. 0 not checked. [2025-01-10 02:30:23,502 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-10 02:30:23,839 INFO L134 CoverageAnalysis]: Checked inductivity of 532 backedges. 58 proven. 168 refuted. 0 times theorem prover too weak. 306 trivial. 0 not checked. [2025-01-10 02:30:23,841 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1522071058] provided 0 perfect and 2 imperfect interpolant sequences [2025-01-10 02:30:23,841 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-01-10 02:30:23,841 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 8, 9] total 14 [2025-01-10 02:30:23,842 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1907935064] [2025-01-10 02:30:23,843 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-01-10 02:30:23,844 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2025-01-10 02:30:23,844 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-10 02:30:23,844 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2025-01-10 02:30:23,845 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=47, Invalid=135, Unknown=0, NotChecked=0, Total=182 [2025-01-10 02:30:23,845 INFO L87 Difference]: Start difference. First operand 69 states and 93 transitions. Second operand has 14 states, 14 states have (on average 4.928571428571429) internal successors, (69), 14 states have internal predecessors, (69), 7 states have call successors, (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:23,950 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-10 02:30:23,950 INFO L93 Difference]: Finished difference Result 128 states and 178 transitions. [2025-01-10 02:30:23,951 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2025-01-10 02:30:23,951 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 4.928571428571429) internal successors, (69), 14 states have internal predecessors, (69), 7 states have call successors, (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 128 [2025-01-10 02:30:23,951 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-10 02:30:23,952 INFO L225 Difference]: With dead ends: 128 [2025-01-10 02:30:23,952 INFO L226 Difference]: Without dead ends: 62 [2025-01-10 02:30:23,953 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 268 GetRequests, 248 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:23,953 INFO L435 NwaCegarLoop]: 21 mSDtfsCounter, 48 mSDsluCounter, 43 mSDsCounter, 0 mSdLazyCounter, 87 mSolverCounterSat, 18 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 48 SdHoareTripleChecker+Valid, 64 SdHoareTripleChecker+Invalid, 105 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 18 IncrementalHoareTripleChecker+Valid, 87 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-01-10 02:30:23,953 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [48 Valid, 64 Invalid, 105 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [18 Valid, 87 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-01-10 02:30:23,954 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 62 states. [2025-01-10 02:30:23,964 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 62 to 60. [2025-01-10 02:30:23,965 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 60 states, 47 states have (on average 1.1063829787234043) internal successors, (52), 45 states have internal predecessors, (52), 6 states have call successors, (6), 4 states have call predecessors, (6), 5 states have return successors, (14), 10 states have call predecessors, (14), 5 states have call successors, (14) [2025-01-10 02:30:23,966 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 60 states to 60 states and 72 transitions. [2025-01-10 02:30:23,967 INFO L78 Accepts]: Start accepts. Automaton has 60 states and 72 transitions. Word has length 128 [2025-01-10 02:30:23,967 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-10 02:30:23,967 INFO L471 AbstractCegarLoop]: Abstraction has 60 states and 72 transitions. [2025-01-10 02:30:23,968 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 4.928571428571429) internal successors, (69), 14 states have internal predecessors, (69), 7 states have call successors, (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:23,968 INFO L276 IsEmpty]: Start isEmpty. Operand 60 states and 72 transitions. [2025-01-10 02:30:23,970 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 90 [2025-01-10 02:30:23,970 INFO L210 NwaCegarLoop]: Found error trace [2025-01-10 02:30:23,970 INFO L218 NwaCegarLoop]: trace histogram [10, 8, 8, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 2, 1, 1, 1, 1] [2025-01-10 02:30:23,979 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:24,174 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:24,174 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:24,174 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-10 02:30:24,175 INFO L85 PathProgramCache]: Analyzing trace with hash 899607631, now seen corresponding path program 3 times [2025-01-10 02:30:24,175 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-10 02:30:24,175 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [705348484] [2025-01-10 02:30:24,175 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-01-10 02:30:24,175 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-10 02:30:24,181 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 89 statements into 8 equivalence classes. [2025-01-10 02:30:24,192 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) and asserted 50 of 89 statements. [2025-01-10 02:30:24,193 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2025-01-10 02:30:24,193 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 02:30:24,327 INFO L134 CoverageAnalysis]: Checked inductivity of 243 backedges. 58 proven. 8 refuted. 0 times theorem prover too weak. 177 trivial. 0 not checked. [2025-01-10 02:30:24,327 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-10 02:30:24,327 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [705348484] [2025-01-10 02:30:24,327 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [705348484] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-10 02:30:24,328 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1829226435] [2025-01-10 02:30:24,328 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-01-10 02:30:24,328 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-10 02:30:24,328 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-10 02:30:24,330 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:24,333 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:24,361 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 89 statements into 8 equivalence classes. [2025-01-10 02:30:24,376 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) and asserted 50 of 89 statements. [2025-01-10 02:30:24,376 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2025-01-10 02:30:24,376 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 02:30:24,378 INFO L256 TraceCheckSpWp]: Trace formula consists of 113 conjuncts, 8 conjuncts are in the unsatisfiable core [2025-01-10 02:30:24,380 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-10 02:30:24,462 INFO L134 CoverageAnalysis]: Checked inductivity of 243 backedges. 60 proven. 4 refuted. 0 times theorem prover too weak. 179 trivial. 0 not checked. [2025-01-10 02:30:24,462 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-10 02:30:24,659 INFO L134 CoverageAnalysis]: Checked inductivity of 243 backedges. 60 proven. 4 refuted. 0 times theorem prover too weak. 179 trivial. 0 not checked. [2025-01-10 02:30:24,660 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1829226435] provided 0 perfect and 2 imperfect interpolant sequences [2025-01-10 02:30:24,661 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-01-10 02:30:24,661 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 7, 7] total 15 [2025-01-10 02:30:24,662 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [311649747] [2025-01-10 02:30:24,662 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-01-10 02:30:24,662 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2025-01-10 02:30:24,663 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-10 02:30:24,663 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2025-01-10 02:30:24,664 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=60, Invalid=180, Unknown=0, NotChecked=0, Total=240 [2025-01-10 02:30:24,664 INFO L87 Difference]: Start difference. First operand 60 states and 72 transitions. Second operand has 16 states, 15 states have (on average 3.4) internal successors, (51), 16 states have internal predecessors, (51), 5 states have call successors, (7), 1 states have call predecessors, (7), 5 states have return successors, (10), 9 states have call predecessors, (10), 5 states have call successors, (10) [2025-01-10 02:30:24,738 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-10 02:30:24,738 INFO L93 Difference]: Finished difference Result 60 states and 72 transitions. [2025-01-10 02:30:24,738 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2025-01-10 02:30:24,738 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 15 states have (on average 3.4) internal successors, (51), 16 states have internal predecessors, (51), 5 states have call successors, (7), 1 states have call predecessors, (7), 5 states have return successors, (10), 9 states have call predecessors, (10), 5 states have call successors, (10) Word has length 89 [2025-01-10 02:30:24,739 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-10 02:30:24,739 INFO L225 Difference]: With dead ends: 60 [2025-01-10 02:30:24,739 INFO L226 Difference]: Without dead ends: 59 [2025-01-10 02:30:24,740 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 186 GetRequests, 166 SyntacticMatches, 4 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 109 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=82, Invalid=224, Unknown=0, NotChecked=0, Total=306 [2025-01-10 02:30:24,740 INFO L435 NwaCegarLoop]: 19 mSDtfsCounter, 4 mSDsluCounter, 112 mSDsCounter, 0 mSdLazyCounter, 62 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 131 SdHoareTripleChecker+Invalid, 63 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 62 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-01-10 02:30:24,740 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [5 Valid, 131 Invalid, 63 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 62 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-01-10 02:30:24,741 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 59 states. [2025-01-10 02:30:24,751 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 59 to 55. [2025-01-10 02:30:24,752 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 55 states, 43 states have (on average 1.069767441860465) internal successors, (46), 42 states have internal predecessors, (46), 6 states have call successors, (6), 4 states have call predecessors, (6), 5 states have return successors, (14), 8 states have call predecessors, (14), 5 states have call successors, (14) [2025-01-10 02:30:24,752 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 55 states to 55 states and 66 transitions. [2025-01-10 02:30:24,754 INFO L78 Accepts]: Start accepts. Automaton has 55 states and 66 transitions. Word has length 89 [2025-01-10 02:30:24,755 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-10 02:30:24,755 INFO L471 AbstractCegarLoop]: Abstraction has 55 states and 66 transitions. [2025-01-10 02:30:24,755 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 15 states have (on average 3.4) internal successors, (51), 16 states have internal predecessors, (51), 5 states have call successors, (7), 1 states have call predecessors, (7), 5 states have return successors, (10), 9 states have call predecessors, (10), 5 states have call successors, (10) [2025-01-10 02:30:24,755 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 66 transitions. [2025-01-10 02:30:24,756 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 105 [2025-01-10 02:30:24,756 INFO L210 NwaCegarLoop]: Found error trace [2025-01-10 02:30:24,756 INFO L218 NwaCegarLoop]: trace histogram [11, 10, 9, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 4, 2, 1, 1, 1, 1] [2025-01-10 02:30:24,765 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:24,956 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:24,957 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting fibonacciErr5ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-01-10 02:30:24,957 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-10 02:30:24,957 INFO L85 PathProgramCache]: Analyzing trace with hash -1067637415, now seen corresponding path program 2 times [2025-01-10 02:30:24,957 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-10 02:30:24,957 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [757536161] [2025-01-10 02:30:24,957 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-01-10 02:30:24,957 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-10 02:30:24,963 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 104 statements into 2 equivalence classes. [2025-01-10 02:30:24,978 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 104 of 104 statements. [2025-01-10 02:30:24,978 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-01-10 02:30:24,978 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 02:30:25,206 INFO L134 CoverageAnalysis]: Checked inductivity of 336 backedges. 72 proven. 159 refuted. 0 times theorem prover too weak. 105 trivial. 0 not checked. [2025-01-10 02:30:25,206 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-10 02:30:25,206 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [757536161] [2025-01-10 02:30:25,206 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [757536161] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-10 02:30:25,206 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1909474001] [2025-01-10 02:30:25,206 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-01-10 02:30:25,207 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-10 02:30:25,207 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-10 02:30:25,209 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:25,211 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:25,245 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 104 statements into 2 equivalence classes. [2025-01-10 02:30:25,268 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 104 of 104 statements. [2025-01-10 02:30:25,269 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-01-10 02:30:25,269 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 02:30:25,270 INFO L256 TraceCheckSpWp]: Trace formula consists of 213 conjuncts, 14 conjuncts are in the unsatisfiable core [2025-01-10 02:30:25,272 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-10 02:30:25,389 INFO L134 CoverageAnalysis]: Checked inductivity of 336 backedges. 82 proven. 158 refuted. 0 times theorem prover too weak. 96 trivial. 0 not checked. [2025-01-10 02:30:25,392 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-10 02:30:26,013 INFO L134 CoverageAnalysis]: Checked inductivity of 336 backedges. 82 proven. 174 refuted. 0 times theorem prover too weak. 80 trivial. 0 not checked. [2025-01-10 02:30:26,013 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1909474001] provided 0 perfect and 2 imperfect interpolant sequences [2025-01-10 02:30:26,013 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-01-10 02:30:26,014 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 11, 15] total 20 [2025-01-10 02:30:26,014 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [923749859] [2025-01-10 02:30:26,014 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-01-10 02:30:26,014 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2025-01-10 02:30:26,015 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-10 02:30:26,016 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2025-01-10 02:30:26,016 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=76, Invalid=304, Unknown=0, NotChecked=0, Total=380 [2025-01-10 02:30:26,017 INFO L87 Difference]: Start difference. First operand 55 states and 66 transitions. Second operand has 20 states, 20 states have (on average 4.6) internal successors, (92), 20 states have internal predecessors, (92), 13 states have call successors, (15), 1 states have call predecessors, (15), 7 states have return successors, (16), 7 states have call predecessors, (16), 13 states have call successors, (16) [2025-01-10 02:30:26,299 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-10 02:30:26,299 INFO L93 Difference]: Finished difference Result 133 states and 168 transitions. [2025-01-10 02:30:26,299 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2025-01-10 02:30:26,300 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 20 states have (on average 4.6) internal successors, (92), 20 states have internal predecessors, (92), 13 states have call successors, (15), 1 states have call predecessors, (15), 7 states have return successors, (16), 7 states have call predecessors, (16), 13 states have call successors, (16) Word has length 104 [2025-01-10 02:30:26,300 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-10 02:30:26,301 INFO L225 Difference]: With dead ends: 133 [2025-01-10 02:30:26,301 INFO L226 Difference]: Without dead ends: 83 [2025-01-10 02:30:26,302 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 237 GetRequests, 200 SyntacticMatches, 7 SemanticMatches, 30 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 179 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=281, Invalid=711, Unknown=0, NotChecked=0, Total=992 [2025-01-10 02:30:26,302 INFO L435 NwaCegarLoop]: 21 mSDtfsCounter, 133 mSDsluCounter, 73 mSDsCounter, 0 mSdLazyCounter, 188 mSolverCounterSat, 74 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 133 SdHoareTripleChecker+Valid, 94 SdHoareTripleChecker+Invalid, 262 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 74 IncrementalHoareTripleChecker+Valid, 188 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-01-10 02:30:26,302 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [133 Valid, 94 Invalid, 262 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [74 Valid, 188 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-01-10 02:30:26,303 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 83 states. [2025-01-10 02:30:26,313 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 83 to 73. [2025-01-10 02:30:26,313 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 73 states, 58 states have (on average 1.0862068965517242) internal successors, (63), 56 states have internal predecessors, (63), 8 states have call successors, (8), 5 states have call predecessors, (8), 6 states have return successors, (17), 11 states have call predecessors, (17), 7 states have call successors, (17) [2025-01-10 02:30:26,314 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 73 states to 73 states and 88 transitions. [2025-01-10 02:30:26,314 INFO L78 Accepts]: Start accepts. Automaton has 73 states and 88 transitions. Word has length 104 [2025-01-10 02:30:26,314 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-10 02:30:26,314 INFO L471 AbstractCegarLoop]: Abstraction has 73 states and 88 transitions. [2025-01-10 02:30:26,314 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 20 states have (on average 4.6) internal successors, (92), 20 states have internal predecessors, (92), 13 states have call successors, (15), 1 states have call predecessors, (15), 7 states have return successors, (16), 7 states have call predecessors, (16), 13 states have call successors, (16) [2025-01-10 02:30:26,315 INFO L276 IsEmpty]: Start isEmpty. Operand 73 states and 88 transitions. [2025-01-10 02:30:26,315 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 92 [2025-01-10 02:30:26,315 INFO L210 NwaCegarLoop]: Found error trace [2025-01-10 02:30:26,315 INFO L218 NwaCegarLoop]: trace histogram [10, 9, 8, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 1, 1, 1, 1, 1] [2025-01-10 02:30:26,323 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:26,516 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:26,516 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting fibonacciErr5ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-01-10 02:30:26,517 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-10 02:30:26,517 INFO L85 PathProgramCache]: Analyzing trace with hash -1152563911, now seen corresponding path program 3 times [2025-01-10 02:30:26,517 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-10 02:30:26,517 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [961696319] [2025-01-10 02:30:26,517 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-01-10 02:30:26,517 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-10 02:30:26,523 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 91 statements into 8 equivalence classes. [2025-01-10 02:30:26,531 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) and asserted 79 of 91 statements. [2025-01-10 02:30:26,532 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2025-01-10 02:30:26,532 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 02:30:26,644 INFO L134 CoverageAnalysis]: Checked inductivity of 254 backedges. 102 proven. 38 refuted. 0 times theorem prover too weak. 114 trivial. 0 not checked. [2025-01-10 02:30:26,645 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-10 02:30:26,645 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [961696319] [2025-01-10 02:30:26,645 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [961696319] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-10 02:30:26,645 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1254377148] [2025-01-10 02:30:26,645 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-01-10 02:30:26,645 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-10 02:30:26,645 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-10 02:30:26,647 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:26,649 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:26,681 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 91 statements into 8 equivalence classes. [2025-01-10 02:30:26,701 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) and asserted 79 of 91 statements. [2025-01-10 02:30:26,702 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2025-01-10 02:30:26,702 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 02:30:26,703 INFO L256 TraceCheckSpWp]: Trace formula consists of 168 conjuncts, 17 conjuncts are in the unsatisfiable core [2025-01-10 02:30:26,707 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-10 02:30:26,913 INFO L134 CoverageAnalysis]: Checked inductivity of 254 backedges. 8 proven. 66 refuted. 0 times theorem prover too weak. 180 trivial. 0 not checked. [2025-01-10 02:30:26,913 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-10 02:30:27,726 INFO L134 CoverageAnalysis]: Checked inductivity of 254 backedges. 20 proven. 66 refuted. 0 times theorem prover too weak. 168 trivial. 0 not checked. [2025-01-10 02:30:27,728 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1254377148] provided 0 perfect and 2 imperfect interpolant sequences [2025-01-10 02:30:27,728 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-01-10 02:30:27,728 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 12, 13] total 30 [2025-01-10 02:30:27,728 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [142405865] [2025-01-10 02:30:27,729 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-01-10 02:30:27,729 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 30 states [2025-01-10 02:30:27,729 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-10 02:30:27,730 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 30 interpolants. [2025-01-10 02:30:27,730 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=144, Invalid=726, Unknown=0, NotChecked=0, Total=870 [2025-01-10 02:30:27,731 INFO L87 Difference]: Start difference. First operand 73 states and 88 transitions. Second operand has 30 states, 30 states have (on average 3.3) internal successors, (99), 30 states have internal predecessors, (99), 10 states have call successors, (13), 1 states have call predecessors, (13), 12 states have return successors, (22), 19 states have call predecessors, (22), 10 states have call successors, (22) [2025-01-10 02:30:28,488 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-10 02:30:28,488 INFO L93 Difference]: Finished difference Result 192 states and 278 transitions. [2025-01-10 02:30:28,488 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 30 states. [2025-01-10 02:30:28,489 INFO L78 Accepts]: Start accepts. Automaton has has 30 states, 30 states have (on average 3.3) internal successors, (99), 30 states have internal predecessors, (99), 10 states have call successors, (13), 1 states have call predecessors, (13), 12 states have return successors, (22), 19 states have call predecessors, (22), 10 states have call successors, (22) Word has length 91 [2025-01-10 02:30:28,489 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-10 02:30:28,490 INFO L225 Difference]: With dead ends: 192 [2025-01-10 02:30:28,490 INFO L226 Difference]: Without dead ends: 124 [2025-01-10 02:30:28,492 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 218 GetRequests, 158 SyntacticMatches, 4 SemanticMatches, 56 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 864 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=597, Invalid=2709, Unknown=0, NotChecked=0, Total=3306 [2025-01-10 02:30:28,493 INFO L435 NwaCegarLoop]: 12 mSDtfsCounter, 170 mSDsluCounter, 106 mSDsCounter, 0 mSdLazyCounter, 460 mSolverCounterSat, 102 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 170 SdHoareTripleChecker+Valid, 118 SdHoareTripleChecker+Invalid, 562 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 102 IncrementalHoareTripleChecker+Valid, 460 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2025-01-10 02:30:28,493 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [170 Valid, 118 Invalid, 562 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [102 Valid, 460 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2025-01-10 02:30:28,494 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 124 states. [2025-01-10 02:30:28,522 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 124 to 97. [2025-01-10 02:30:28,523 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 97 states, 76 states have (on average 1.0526315789473684) internal successors, (80), 75 states have internal predecessors, (80), 11 states have call successors, (11), 5 states have call predecessors, (11), 9 states have return successors, (47), 16 states have call predecessors, (47), 10 states have call successors, (47) [2025-01-10 02:30:28,524 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 97 states to 97 states and 138 transitions. [2025-01-10 02:30:28,524 INFO L78 Accepts]: Start accepts. Automaton has 97 states and 138 transitions. Word has length 91 [2025-01-10 02:30:28,525 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-10 02:30:28,525 INFO L471 AbstractCegarLoop]: Abstraction has 97 states and 138 transitions. [2025-01-10 02:30:28,525 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 30 states, 30 states have (on average 3.3) internal successors, (99), 30 states have internal predecessors, (99), 10 states have call successors, (13), 1 states have call predecessors, (13), 12 states have return successors, (22), 19 states have call predecessors, (22), 10 states have call successors, (22) [2025-01-10 02:30:28,525 INFO L276 IsEmpty]: Start isEmpty. Operand 97 states and 138 transitions. [2025-01-10 02:30:28,527 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 340 [2025-01-10 02:30:28,529 INFO L210 NwaCegarLoop]: Found error trace [2025-01-10 02:30:28,529 INFO L218 NwaCegarLoop]: trace histogram [35, 34, 28, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 16, 11, 7, 1, 1, 1, 1] [2025-01-10 02:30:28,537 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:28,729 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:28,730 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:28,730 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-10 02:30:28,731 INFO L85 PathProgramCache]: Analyzing trace with hash 176076421, now seen corresponding path program 4 times [2025-01-10 02:30:28,731 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-10 02:30:28,731 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1145420368] [2025-01-10 02:30:28,731 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-01-10 02:30:28,731 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-10 02:30:28,743 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 339 statements into 2 equivalence classes. [2025-01-10 02:30:28,765 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) and asserted 201 of 339 statements. [2025-01-10 02:30:28,765 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) [2025-01-10 02:30:28,765 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 02:30:29,069 INFO L134 CoverageAnalysis]: Checked inductivity of 4050 backedges. 394 proven. 1064 refuted. 0 times theorem prover too weak. 2592 trivial. 0 not checked. [2025-01-10 02:30:29,069 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-10 02:30:29,069 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1145420368] [2025-01-10 02:30:29,069 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1145420368] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-10 02:30:29,069 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1481874645] [2025-01-10 02:30:29,069 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-01-10 02:30:29,069 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-10 02:30:29,070 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-10 02:30:29,073 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:29,074 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:29,134 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 339 statements into 2 equivalence classes. [2025-01-10 02:30:29,173 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) and asserted 201 of 339 statements. [2025-01-10 02:30:29,173 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) [2025-01-10 02:30:29,174 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 02:30:29,175 INFO L256 TraceCheckSpWp]: Trace formula consists of 424 conjuncts, 18 conjuncts are in the unsatisfiable core [2025-01-10 02:30:29,181 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-10 02:30:29,337 INFO L134 CoverageAnalysis]: Checked inductivity of 4050 backedges. 369 proven. 1469 refuted. 0 times theorem prover too weak. 2212 trivial. 0 not checked. [2025-01-10 02:30:29,337 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-10 02:30:30,561 INFO L134 CoverageAnalysis]: Checked inductivity of 4050 backedges. 369 proven. 1508 refuted. 0 times theorem prover too weak. 2173 trivial. 0 not checked. [2025-01-10 02:30:30,562 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1481874645] provided 0 perfect and 2 imperfect interpolant sequences [2025-01-10 02:30:30,562 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-01-10 02:30:30,562 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 13, 19] total 24 [2025-01-10 02:30:30,562 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1291400916] [2025-01-10 02:30:30,562 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-01-10 02:30:30,564 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 24 states [2025-01-10 02:30:30,564 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-10 02:30:30,565 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2025-01-10 02:30:30,565 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=103, Invalid=449, Unknown=0, NotChecked=0, Total=552 [2025-01-10 02:30:30,565 INFO L87 Difference]: Start difference. First operand 97 states and 138 transitions. Second operand has 24 states, 24 states have (on average 5.541666666666667) internal successors, (133), 24 states have internal predecessors, (133), 18 states have call successors, (23), 1 states have call predecessors, (23), 9 states have return successors, (28), 12 states have call predecessors, (28), 18 states have call successors, (28) [2025-01-10 02:30:30,913 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-10 02:30:30,913 INFO L93 Difference]: Finished difference Result 247 states and 397 transitions. [2025-01-10 02:30:30,914 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2025-01-10 02:30:30,914 INFO L78 Accepts]: Start accepts. Automaton has has 24 states, 24 states have (on average 5.541666666666667) internal successors, (133), 24 states have internal predecessors, (133), 18 states have call successors, (23), 1 states have call predecessors, (23), 9 states have return successors, (28), 12 states have call predecessors, (28), 18 states have call successors, (28) Word has length 339 [2025-01-10 02:30:30,914 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-10 02:30:30,916 INFO L225 Difference]: With dead ends: 247 [2025-01-10 02:30:30,916 INFO L226 Difference]: Without dead ends: 155 [2025-01-10 02:30:30,920 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 712 GetRequests, 665 SyntacticMatches, 9 SemanticMatches, 38 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 328 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=416, Invalid=1144, Unknown=0, NotChecked=0, Total=1560 [2025-01-10 02:30:30,920 INFO L435 NwaCegarLoop]: 28 mSDtfsCounter, 160 mSDsluCounter, 97 mSDsCounter, 0 mSdLazyCounter, 258 mSolverCounterSat, 91 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 160 SdHoareTripleChecker+Valid, 125 SdHoareTripleChecker+Invalid, 349 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 91 IncrementalHoareTripleChecker+Valid, 258 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-01-10 02:30:30,921 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [160 Valid, 125 Invalid, 349 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [91 Valid, 258 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-01-10 02:30:30,921 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 155 states. [2025-01-10 02:30:30,938 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 155 to 139. [2025-01-10 02:30:30,939 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 139 states, 111 states have (on average 1.045045045045045) internal successors, (116), 107 states have internal predecessors, (116), 15 states have call successors, (15), 8 states have call predecessors, (15), 12 states have return successors, (57), 23 states have call predecessors, (57), 14 states have call successors, (57) [2025-01-10 02:30:30,941 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 139 states to 139 states and 188 transitions. [2025-01-10 02:30:30,941 INFO L78 Accepts]: Start accepts. Automaton has 139 states and 188 transitions. Word has length 339 [2025-01-10 02:30:30,942 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-10 02:30:30,942 INFO L471 AbstractCegarLoop]: Abstraction has 139 states and 188 transitions. [2025-01-10 02:30:30,943 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 24 states, 24 states have (on average 5.541666666666667) internal successors, (133), 24 states have internal predecessors, (133), 18 states have call successors, (23), 1 states have call predecessors, (23), 9 states have return successors, (28), 12 states have call predecessors, (28), 18 states have call successors, (28) [2025-01-10 02:30:30,943 INFO L276 IsEmpty]: Start isEmpty. Operand 139 states and 188 transitions. [2025-01-10 02:30:30,952 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 498 [2025-01-10 02:30:30,952 INFO L210 NwaCegarLoop]: Found error trace [2025-01-10 02:30:30,953 INFO L218 NwaCegarLoop]: trace histogram [52, 49, 42, 26, 26, 26, 26, 25, 25, 25, 25, 25, 24, 24, 24, 23, 16, 10, 1, 1, 1, 1] [2025-01-10 02:30:30,961 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2025-01-10 02:30:31,153 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:31,154 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:31,154 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-10 02:30:31,154 INFO L85 PathProgramCache]: Analyzing trace with hash 1320851795, now seen corresponding path program 5 times [2025-01-10 02:30:31,154 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-10 02:30:31,154 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [298346791] [2025-01-10 02:30:31,154 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2025-01-10 02:30:31,155 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-10 02:30:31,179 INFO L108 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 partitioned 497 statements into 39 equivalence classes. [2025-01-10 02:30:31,239 INFO L111 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 27 check-sat command(s) and asserted 349 of 497 statements. [2025-01-10 02:30:31,240 INFO L114 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 27 check-sat command(s) [2025-01-10 02:30:31,240 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 02:30:31,761 INFO L134 CoverageAnalysis]: Checked inductivity of 8868 backedges. 1798 proven. 1144 refuted. 0 times theorem prover too weak. 5926 trivial. 0 not checked. [2025-01-10 02:30:31,761 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-10 02:30:31,762 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [298346791] [2025-01-10 02:30:31,762 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [298346791] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-10 02:30:31,762 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [919965904] [2025-01-10 02:30:31,762 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2025-01-10 02:30:31,762 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-10 02:30:31,763 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-10 02:30:31,765 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:31,767 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:31,839 INFO L108 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 partitioned 497 statements into 39 equivalence classes. [2025-01-10 02:30:31,930 INFO L111 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 27 check-sat command(s) and asserted 349 of 497 statements. [2025-01-10 02:30:31,930 INFO L114 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 27 check-sat command(s) [2025-01-10 02:30:31,930 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 02:30:31,933 INFO L256 TraceCheckSpWp]: Trace formula consists of 646 conjuncts, 18 conjuncts are in the unsatisfiable core [2025-01-10 02:30:31,940 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-10 02:30:32,079 INFO L134 CoverageAnalysis]: Checked inductivity of 8868 backedges. 5049 proven. 686 refuted. 0 times theorem prover too weak. 3133 trivial. 0 not checked. [2025-01-10 02:30:32,079 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-10 02:30:33,191 INFO L134 CoverageAnalysis]: Checked inductivity of 8868 backedges. 908 proven. 1815 refuted. 0 times theorem prover too weak. 6145 trivial. 0 not checked. [2025-01-10 02:30:33,191 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [919965904] provided 0 perfect and 2 imperfect interpolant sequences [2025-01-10 02:30:33,191 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-01-10 02:30:33,191 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 14, 19] total 28 [2025-01-10 02:30:33,192 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [20071356] [2025-01-10 02:30:33,192 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-01-10 02:30:33,192 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 28 states [2025-01-10 02:30:33,192 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-10 02:30:33,193 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 28 interpolants. [2025-01-10 02:30:33,193 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=124, Invalid=632, Unknown=0, NotChecked=0, Total=756 [2025-01-10 02:30:33,194 INFO L87 Difference]: Start difference. First operand 139 states and 188 transitions. Second operand has 28 states, 28 states have (on average 5.785714285714286) internal successors, (162), 28 states have internal predecessors, (162), 19 states have call successors, (30), 4 states have call predecessors, (30), 12 states have return successors, (35), 18 states have call predecessors, (35), 18 states have call successors, (35) [2025-01-10 02:30:33,716 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-10 02:30:33,716 INFO L93 Difference]: Finished difference Result 300 states and 484 transitions. [2025-01-10 02:30:33,717 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 30 states. [2025-01-10 02:30:33,717 INFO L78 Accepts]: Start accepts. Automaton has has 28 states, 28 states have (on average 5.785714285714286) internal successors, (162), 28 states have internal predecessors, (162), 19 states have call successors, (30), 4 states have call predecessors, (30), 12 states have return successors, (35), 18 states have call predecessors, (35), 18 states have call successors, (35) Word has length 497 [2025-01-10 02:30:33,717 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-10 02:30:33,719 INFO L225 Difference]: With dead ends: 300 [2025-01-10 02:30:33,719 INFO L226 Difference]: Without dead ends: 166 [2025-01-10 02:30:33,723 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 1041 GetRequests, 984 SyntacticMatches, 7 SemanticMatches, 50 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 620 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=654, Invalid=1998, Unknown=0, NotChecked=0, Total=2652 [2025-01-10 02:30:33,724 INFO L435 NwaCegarLoop]: 36 mSDtfsCounter, 248 mSDsluCounter, 135 mSDsCounter, 0 mSdLazyCounter, 377 mSolverCounterSat, 119 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 248 SdHoareTripleChecker+Valid, 171 SdHoareTripleChecker+Invalid, 496 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 119 IncrementalHoareTripleChecker+Valid, 377 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2025-01-10 02:30:33,724 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [248 Valid, 171 Invalid, 496 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [119 Valid, 377 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2025-01-10 02:30:33,724 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 166 states. [2025-01-10 02:30:33,735 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 166 to 142. [2025-01-10 02:30:33,736 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 142 states, 115 states have (on average 1.0521739130434782) internal successors, (121), 111 states have internal predecessors, (121), 17 states have call successors, (17), 13 states have call predecessors, (17), 9 states have return successors, (44), 17 states have call predecessors, (44), 16 states have call successors, (44) [2025-01-10 02:30:33,737 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 142 states to 142 states and 182 transitions. [2025-01-10 02:30:33,738 INFO L78 Accepts]: Start accepts. Automaton has 142 states and 182 transitions. Word has length 497 [2025-01-10 02:30:33,739 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-10 02:30:33,739 INFO L471 AbstractCegarLoop]: Abstraction has 142 states and 182 transitions. [2025-01-10 02:30:33,739 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 28 states, 28 states have (on average 5.785714285714286) internal successors, (162), 28 states have internal predecessors, (162), 19 states have call successors, (30), 4 states have call predecessors, (30), 12 states have return successors, (35), 18 states have call predecessors, (35), 18 states have call successors, (35) [2025-01-10 02:30:33,739 INFO L276 IsEmpty]: Start isEmpty. Operand 142 states and 182 transitions. [2025-01-10 02:30:33,744 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 301 [2025-01-10 02:30:33,745 INFO L210 NwaCegarLoop]: Found error trace [2025-01-10 02:30:33,745 INFO L218 NwaCegarLoop]: trace histogram [31, 30, 25, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 14, 10, 6, 1, 1, 1, 1] [2025-01-10 02:30:33,753 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:33,948 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:33,949 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:33,949 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-10 02:30:33,949 INFO L85 PathProgramCache]: Analyzing trace with hash -816198827, now seen corresponding path program 6 times [2025-01-10 02:30:33,949 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-10 02:30:33,949 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1608087798] [2025-01-10 02:30:33,949 INFO L95 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2025-01-10 02:30:33,949 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-10 02:30:33,958 INFO L108 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE partitioned 300 statements into 21 equivalence classes. [2025-01-10 02:30:33,995 INFO L111 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 18 check-sat command(s) and asserted 264 of 300 statements. [2025-01-10 02:30:33,995 INFO L114 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 18 check-sat command(s) [2025-01-10 02:30:33,995 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 02:30:34,345 INFO L134 CoverageAnalysis]: Checked inductivity of 3150 backedges. 688 proven. 797 refuted. 0 times theorem prover too weak. 1665 trivial. 0 not checked. [2025-01-10 02:30:34,346 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-10 02:30:34,346 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1608087798] [2025-01-10 02:30:34,346 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1608087798] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-10 02:30:34,346 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1834726123] [2025-01-10 02:30:34,346 INFO L95 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2025-01-10 02:30:34,346 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-10 02:30:34,346 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-10 02:30:34,348 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:34,350 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:34,411 INFO L108 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE partitioned 300 statements into 21 equivalence classes. [2025-01-10 02:30:34,474 INFO L111 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 18 check-sat command(s) and asserted 264 of 300 statements. [2025-01-10 02:30:34,474 INFO L114 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 18 check-sat command(s) [2025-01-10 02:30:34,474 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 02:30:34,476 INFO L256 TraceCheckSpWp]: Trace formula consists of 511 conjuncts, 18 conjuncts are in the unsatisfiable core [2025-01-10 02:30:34,481 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-10 02:30:34,607 INFO L134 CoverageAnalysis]: Checked inductivity of 3150 backedges. 690 proven. 797 refuted. 0 times theorem prover too weak. 1663 trivial. 0 not checked. [2025-01-10 02:30:34,607 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-10 02:30:35,878 INFO L134 CoverageAnalysis]: Checked inductivity of 3150 backedges. 706 proven. 824 refuted. 0 times theorem prover too weak. 1620 trivial. 0 not checked. [2025-01-10 02:30:35,878 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1834726123] provided 0 perfect and 2 imperfect interpolant sequences [2025-01-10 02:30:35,878 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-01-10 02:30:35,878 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 13, 19] total 24 [2025-01-10 02:30:35,878 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2042127995] [2025-01-10 02:30:35,878 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-01-10 02:30:35,879 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 24 states [2025-01-10 02:30:35,879 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-10 02:30:35,879 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2025-01-10 02:30:35,880 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=120, Invalid=432, Unknown=0, NotChecked=0, Total=552 [2025-01-10 02:30:35,880 INFO L87 Difference]: Start difference. First operand 142 states and 182 transitions. Second operand has 24 states, 24 states have (on average 5.416666666666667) internal successors, (130), 24 states have internal predecessors, (130), 16 states have call successors, (22), 1 states have call predecessors, (22), 10 states have return successors, (27), 14 states have call predecessors, (27), 16 states have call successors, (27) [2025-01-10 02:30:36,196 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-10 02:30:36,196 INFO L93 Difference]: Finished difference Result 292 states and 399 transitions. [2025-01-10 02:30:36,197 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2025-01-10 02:30:36,197 INFO L78 Accepts]: Start accepts. Automaton has has 24 states, 24 states have (on average 5.416666666666667) internal successors, (130), 24 states have internal predecessors, (130), 16 states have call successors, (22), 1 states have call predecessors, (22), 10 states have return successors, (27), 14 states have call predecessors, (27), 16 states have call successors, (27) Word has length 300 [2025-01-10 02:30:36,197 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-10 02:30:36,199 INFO L225 Difference]: With dead ends: 292 [2025-01-10 02:30:36,199 INFO L226 Difference]: Without dead ends: 155 [2025-01-10 02:30:36,201 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 632 GetRequests, 588 SyntacticMatches, 9 SemanticMatches, 35 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 380 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=347, Invalid=985, Unknown=0, NotChecked=0, Total=1332 [2025-01-10 02:30:36,202 INFO L435 NwaCegarLoop]: 47 mSDtfsCounter, 89 mSDsluCounter, 155 mSDsCounter, 0 mSdLazyCounter, 460 mSolverCounterSat, 39 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 90 SdHoareTripleChecker+Valid, 202 SdHoareTripleChecker+Invalid, 499 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 39 IncrementalHoareTripleChecker+Valid, 460 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-01-10 02:30:36,202 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [90 Valid, 202 Invalid, 499 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [39 Valid, 460 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-01-10 02:30:36,202 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 155 states. [2025-01-10 02:30:36,213 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 155 to 133. [2025-01-10 02:30:36,213 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 133 states, 106 states have (on average 1.0377358490566038) internal successors, (110), 106 states have internal predecessors, (110), 18 states have call successors, (18), 13 states have call predecessors, (18), 8 states have return successors, (37), 13 states have call predecessors, (37), 17 states have call successors, (37) [2025-01-10 02:30:36,214 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 133 states to 133 states and 165 transitions. [2025-01-10 02:30:36,215 INFO L78 Accepts]: Start accepts. Automaton has 133 states and 165 transitions. Word has length 300 [2025-01-10 02:30:36,215 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-10 02:30:36,215 INFO L471 AbstractCegarLoop]: Abstraction has 133 states and 165 transitions. [2025-01-10 02:30:36,216 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 24 states, 24 states have (on average 5.416666666666667) internal successors, (130), 24 states have internal predecessors, (130), 16 states have call successors, (22), 1 states have call predecessors, (22), 10 states have return successors, (27), 14 states have call predecessors, (27), 16 states have call successors, (27) [2025-01-10 02:30:36,216 INFO L276 IsEmpty]: Start isEmpty. Operand 133 states and 165 transitions. [2025-01-10 02:30:36,229 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 405 [2025-01-10 02:30:36,230 INFO L210 NwaCegarLoop]: Found error trace [2025-01-10 02:30:36,230 INFO L218 NwaCegarLoop]: trace histogram [42, 40, 34, 21, 21, 21, 21, 20, 20, 20, 20, 20, 20, 20, 20, 19, 13, 8, 1, 1, 1, 1] [2025-01-10 02:30:36,237 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:36,430 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:36,430 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:36,431 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-10 02:30:36,431 INFO L85 PathProgramCache]: Analyzing trace with hash 2135557449, now seen corresponding path program 7 times [2025-01-10 02:30:36,431 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-10 02:30:36,431 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1497149894] [2025-01-10 02:30:36,431 INFO L95 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2025-01-10 02:30:36,431 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-10 02:30:36,443 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 404 statements into 1 equivalence classes. [2025-01-10 02:30:36,479 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 404 of 404 statements. [2025-01-10 02:30:36,479 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-10 02:30:36,479 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 02:30:38,579 INFO L134 CoverageAnalysis]: Checked inductivity of 5803 backedges. 830 proven. 1470 refuted. 0 times theorem prover too weak. 3503 trivial. 0 not checked. [2025-01-10 02:30:38,580 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-10 02:30:38,580 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1497149894] [2025-01-10 02:30:38,580 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1497149894] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-10 02:30:38,580 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [721193839] [2025-01-10 02:30:38,580 INFO L95 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2025-01-10 02:30:38,581 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-10 02:30:38,581 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-10 02:30:38,583 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:38,585 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:38,659 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 404 statements into 1 equivalence classes. [2025-01-10 02:30:38,738 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 404 of 404 statements. [2025-01-10 02:30:38,738 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-10 02:30:38,738 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 02:30:38,740 INFO L256 TraceCheckSpWp]: Trace formula consists of 766 conjuncts, 81 conjuncts are in the unsatisfiable core [2025-01-10 02:30:38,750 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-10 02:30:39,179 INFO L134 CoverageAnalysis]: Checked inductivity of 5803 backedges. 820 proven. 1112 refuted. 0 times theorem prover too weak. 3871 trivial. 0 not checked. [2025-01-10 02:30:39,179 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-10 02:30:45,481 INFO L134 CoverageAnalysis]: Checked inductivity of 5803 backedges. 1149 proven. 1015 refuted. 0 times theorem prover too weak. 3639 trivial. 0 not checked. [2025-01-10 02:30:45,481 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [721193839] provided 0 perfect and 2 imperfect interpolant sequences [2025-01-10 02:30:45,481 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-01-10 02:30:45,482 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 18, 29] total 45 [2025-01-10 02:30:45,482 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1487591242] [2025-01-10 02:30:45,482 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-01-10 02:30:45,483 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 46 states [2025-01-10 02:30:45,483 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-10 02:30:45,484 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 46 interpolants. [2025-01-10 02:30:45,484 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=463, Invalid=1607, Unknown=0, NotChecked=0, Total=2070 [2025-01-10 02:30:45,484 INFO L87 Difference]: Start difference. First operand 133 states and 165 transitions. Second operand has 46 states, 45 states have (on average 2.6222222222222222) internal successors, (118), 46 states have internal predecessors, (118), 12 states have call successors, (13), 1 states have call predecessors, (13), 13 states have return successors, (31), 31 states have call predecessors, (31), 12 states have call successors, (31) [2025-01-10 02:30:45,656 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-10 02:30:45,657 INFO L93 Difference]: Finished difference Result 164 states and 219 transitions. [2025-01-10 02:30:45,657 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 26 states. [2025-01-10 02:30:45,657 INFO L78 Accepts]: Start accepts. Automaton has has 46 states, 45 states have (on average 2.6222222222222222) internal successors, (118), 46 states have internal predecessors, (118), 12 states have call successors, (13), 1 states have call predecessors, (13), 13 states have return successors, (31), 31 states have call predecessors, (31), 12 states have call successors, (31) Word has length 404 [2025-01-10 02:30:45,658 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-10 02:30:45,661 INFO L225 Difference]: With dead ends: 164 [2025-01-10 02:30:45,662 INFO L226 Difference]: Without dead ends: 163 [2025-01-10 02:30:45,663 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 891 GetRequests, 792 SyntacticMatches, 51 SemanticMatches, 48 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2454 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=544, Invalid=1906, Unknown=0, NotChecked=0, Total=2450 [2025-01-10 02:30:45,663 INFO L435 NwaCegarLoop]: 19 mSDtfsCounter, 10 mSDsluCounter, 222 mSDsCounter, 0 mSdLazyCounter, 186 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 15 SdHoareTripleChecker+Valid, 241 SdHoareTripleChecker+Invalid, 193 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 186 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-01-10 02:30:45,664 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [15 Valid, 241 Invalid, 193 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 186 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-01-10 02:30:45,664 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 163 states. [2025-01-10 02:30:45,674 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 163 to 154. [2025-01-10 02:30:45,675 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 154 states, 123 states have (on average 1.032520325203252) internal successors, (127), 122 states have internal predecessors, (127), 20 states have call successors, (20), 13 states have call predecessors, (20), 10 states have return successors, (57), 18 states have call predecessors, (57), 19 states have call successors, (57) [2025-01-10 02:30:45,676 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 154 states to 154 states and 204 transitions. [2025-01-10 02:30:45,677 INFO L78 Accepts]: Start accepts. Automaton has 154 states and 204 transitions. Word has length 404 [2025-01-10 02:30:45,677 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-10 02:30:45,678 INFO L471 AbstractCegarLoop]: Abstraction has 154 states and 204 transitions. [2025-01-10 02:30:45,678 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 46 states, 45 states have (on average 2.6222222222222222) internal successors, (118), 46 states have internal predecessors, (118), 12 states have call successors, (13), 1 states have call predecessors, (13), 13 states have return successors, (31), 31 states have call predecessors, (31), 12 states have call successors, (31) [2025-01-10 02:30:45,678 INFO L276 IsEmpty]: Start isEmpty. Operand 154 states and 204 transitions. [2025-01-10 02:30:45,687 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1224 [2025-01-10 02:30:45,687 INFO L210 NwaCegarLoop]: Found error trace [2025-01-10 02:30:45,687 INFO L218 NwaCegarLoop]: trace histogram [126, 123, 102, 63, 63, 63, 63, 62, 62, 62, 62, 62, 61, 61, 61, 60, 39, 24, 1, 1, 1, 1] [2025-01-10 02:30:45,694 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:45,888 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:45,888 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:45,888 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-10 02:30:45,889 INFO L85 PathProgramCache]: Analyzing trace with hash -1043711412, now seen corresponding path program 8 times [2025-01-10 02:30:45,889 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-10 02:30:45,889 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [633724771] [2025-01-10 02:30:45,889 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-01-10 02:30:45,889 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-10 02:30:45,919 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 1223 statements into 2 equivalence classes. [2025-01-10 02:30:46,032 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 1223 of 1223 statements. [2025-01-10 02:30:46,032 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-01-10 02:30:46,032 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 02:30:47,732 INFO L134 CoverageAnalysis]: Checked inductivity of 54820 backedges. 2272 proven. 8825 refuted. 0 times theorem prover too weak. 43723 trivial. 0 not checked. [2025-01-10 02:30:47,733 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-10 02:30:47,733 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [633724771] [2025-01-10 02:30:47,733 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [633724771] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-10 02:30:47,733 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1509970484] [2025-01-10 02:30:47,733 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-01-10 02:30:47,733 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-10 02:30:47,733 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-10 02:30:47,736 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:47,743 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:47,938 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 1223 statements into 2 equivalence classes. [2025-01-10 02:30:48,134 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 1223 of 1223 statements. [2025-01-10 02:30:48,134 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-01-10 02:30:48,134 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 02:30:48,143 INFO L256 TraceCheckSpWp]: Trace formula consists of 2279 conjuncts, 30 conjuncts are in the unsatisfiable core [2025-01-10 02:30:48,171 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-10 02:30:48,388 INFO L134 CoverageAnalysis]: Checked inductivity of 54820 backedges. 26937 proven. 5564 refuted. 0 times theorem prover too weak. 22319 trivial. 0 not checked. [2025-01-10 02:30:48,388 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-10 02:30:51,501 INFO L134 CoverageAnalysis]: Checked inductivity of 54820 backedges. 2766 proven. 10267 refuted. 0 times theorem prover too weak. 41787 trivial. 0 not checked. [2025-01-10 02:30:51,502 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1509970484] provided 0 perfect and 2 imperfect interpolant sequences [2025-01-10 02:30:51,502 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-01-10 02:30:51,502 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 19, 29] total 34 [2025-01-10 02:30:51,502 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1059808900] [2025-01-10 02:30:51,502 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-01-10 02:30:51,504 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 34 states [2025-01-10 02:30:51,504 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-10 02:30:51,505 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 34 interpolants. [2025-01-10 02:30:51,505 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=175, Invalid=947, Unknown=0, NotChecked=0, Total=1122 [2025-01-10 02:30:51,505 INFO L87 Difference]: Start difference. First operand 154 states and 204 transitions. Second operand has 34 states, 34 states have (on average 5.970588235294118) internal successors, (203), 34 states have internal predecessors, (203), 29 states have call successors, (36), 4 states have call predecessors, (36), 14 states have return successors, (43), 16 states have call predecessors, (43), 27 states have call successors, (43) [2025-01-10 02:30:52,121 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-10 02:30:52,121 INFO L93 Difference]: Finished difference Result 367 states and 528 transitions. [2025-01-10 02:30:52,122 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 41 states. [2025-01-10 02:30:52,122 INFO L78 Accepts]: Start accepts. Automaton has has 34 states, 34 states have (on average 5.970588235294118) internal successors, (203), 34 states have internal predecessors, (203), 29 states have call successors, (36), 4 states have call predecessors, (36), 14 states have return successors, (43), 16 states have call predecessors, (43), 27 states have call successors, (43) Word has length 1223 [2025-01-10 02:30:52,123 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-10 02:30:52,125 INFO L225 Difference]: With dead ends: 367 [2025-01-10 02:30:52,125 INFO L226 Difference]: Without dead ends: 218 [2025-01-10 02:30:52,128 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 2511 GetRequests, 2427 SyntacticMatches, 17 SemanticMatches, 67 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1192 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=1170, Invalid=3522, Unknown=0, NotChecked=0, Total=4692 [2025-01-10 02:30:52,128 INFO L435 NwaCegarLoop]: 35 mSDtfsCounter, 533 mSDsluCounter, 154 mSDsCounter, 0 mSdLazyCounter, 403 mSolverCounterSat, 188 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 533 SdHoareTripleChecker+Valid, 189 SdHoareTripleChecker+Invalid, 591 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 188 IncrementalHoareTripleChecker+Valid, 403 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2025-01-10 02:30:52,128 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [533 Valid, 189 Invalid, 591 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [188 Valid, 403 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2025-01-10 02:30:52,129 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 218 states. [2025-01-10 02:30:52,139 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 218 to 187. [2025-01-10 02:30:52,140 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 187 states, 151 states have (on average 1.0397350993377483) internal successors, (157), 148 states have internal predecessors, (157), 24 states have call successors, (24), 17 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:52,141 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 187 states to 187 states and 246 transitions. [2025-01-10 02:30:52,141 INFO L78 Accepts]: Start accepts. Automaton has 187 states and 246 transitions. Word has length 1223 [2025-01-10 02:30:52,142 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-10 02:30:52,142 INFO L471 AbstractCegarLoop]: Abstraction has 187 states and 246 transitions. [2025-01-10 02:30:52,143 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 34 states, 34 states have (on average 5.970588235294118) internal successors, (203), 34 states have internal predecessors, (203), 29 states have call successors, (36), 4 states have call predecessors, (36), 14 states have return successors, (43), 16 states have call predecessors, (43), 27 states have call successors, (43) [2025-01-10 02:30:52,143 INFO L276 IsEmpty]: Start isEmpty. Operand 187 states and 246 transitions. [2025-01-10 02:30:52,147 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 811 [2025-01-10 02:30:52,147 INFO L210 NwaCegarLoop]: Found error trace [2025-01-10 02:30:52,147 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] [2025-01-10 02:30:52,157 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:52,351 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:52,351 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:52,352 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-10 02:30:52,352 INFO L85 PathProgramCache]: Analyzing trace with hash -975339641, now seen corresponding path program 9 times [2025-01-10 02:30:52,352 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-10 02:30:52,352 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1206467250] [2025-01-10 02:30:52,352 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-01-10 02:30:52,352 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-10 02:30:52,374 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 810 statements into 60 equivalence classes. [2025-01-10 02:30:52,460 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 45 check-sat command(s) and asserted 599 of 810 statements. [2025-01-10 02:30:52,460 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 45 check-sat command(s) [2025-01-10 02:30:52,460 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 02:30:53,060 INFO L134 CoverageAnalysis]: Checked inductivity of 23859 backedges. 3562 proven. 2169 refuted. 0 times theorem prover too weak. 18128 trivial. 0 not checked. [2025-01-10 02:30:53,060 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-10 02:30:53,060 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1206467250] [2025-01-10 02:30:53,060 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1206467250] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-10 02:30:53,060 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [427012956] [2025-01-10 02:30:53,060 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-01-10 02:30:53,061 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-10 02:30:53,061 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-10 02:30:53,063 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:53,064 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:53,240 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 810 statements into 60 equivalence classes. [2025-01-10 02:30:53,377 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 45 check-sat command(s) and asserted 599 of 810 statements. [2025-01-10 02:30:53,377 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 45 check-sat command(s) [2025-01-10 02:30:53,377 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 02:30:53,380 INFO L256 TraceCheckSpWp]: Trace formula consists of 1123 conjuncts, 20 conjuncts are in the unsatisfiable core [2025-01-10 02:30:53,388 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-10 02:30:53,504 INFO L134 CoverageAnalysis]: Checked inductivity of 23859 backedges. 3424 proven. 1968 refuted. 0 times theorem prover too weak. 18467 trivial. 0 not checked. [2025-01-10 02:30:53,504 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-10 02:30:55,220 INFO L134 CoverageAnalysis]: Checked inductivity of 23859 backedges. 3444 proven. 2023 refuted. 0 times theorem prover too weak. 18392 trivial. 0 not checked. [2025-01-10 02:30:55,220 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [427012956] provided 0 perfect and 2 imperfect interpolant sequences [2025-01-10 02:30:55,220 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-01-10 02:30:55,220 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 14, 21] total 27 [2025-01-10 02:30:55,221 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [211025523] [2025-01-10 02:30:55,221 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-01-10 02:30:55,221 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 27 states [2025-01-10 02:30:55,221 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-10 02:30:55,222 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 27 interpolants. [2025-01-10 02:30:55,222 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=132, Invalid=570, Unknown=0, NotChecked=0, Total=702 [2025-01-10 02:30:55,223 INFO L87 Difference]: Start difference. First operand 187 states and 246 transitions. Second operand has 27 states, 27 states have (on average 5.444444444444445) internal successors, (147), 27 states have internal predecessors, (147), 15 states have call successors, (25), 1 states have call predecessors, (25), 11 states have return successors, (31), 19 states have call predecessors, (31), 15 states have call successors, (31) [2025-01-10 02:30:55,684 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-10 02:30:55,684 INFO L93 Difference]: Finished difference Result 456 states and 600 transitions. [2025-01-10 02:30:55,685 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 29 states. [2025-01-10 02:30:55,685 INFO L78 Accepts]: Start accepts. Automaton has has 27 states, 27 states have (on average 5.444444444444445) internal successors, (147), 27 states have internal predecessors, (147), 15 states have call successors, (25), 1 states have call predecessors, (25), 11 states have return successors, (31), 19 states have call predecessors, (31), 15 states have call successors, (31) Word has length 810 [2025-01-10 02:30:55,686 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-10 02:30:55,690 INFO L225 Difference]: With dead ends: 456 [2025-01-10 02:30:55,691 INFO L226 Difference]: Without dead ends: 217 [2025-01-10 02:30:55,693 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 1663 GetRequests, 1607 SyntacticMatches, 10 SemanticMatches, 46 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 572 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=571, Invalid=1685, Unknown=0, NotChecked=0, Total=2256 [2025-01-10 02:30:55,693 INFO L435 NwaCegarLoop]: 49 mSDtfsCounter, 81 mSDsluCounter, 175 mSDsCounter, 0 mSdLazyCounter, 626 mSolverCounterSat, 53 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 81 SdHoareTripleChecker+Valid, 224 SdHoareTripleChecker+Invalid, 679 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 53 IncrementalHoareTripleChecker+Valid, 626 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2025-01-10 02:30:55,693 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [81 Valid, 224 Invalid, 679 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [53 Valid, 626 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2025-01-10 02:30:55,694 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 217 states. [2025-01-10 02:30:55,708 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 217 to 174. [2025-01-10 02:30:55,708 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 174 states, 141 states have (on average 1.0354609929078014) internal successors, (146), 138 states have internal predecessors, (146), 22 states have call successors, (22), 18 states have call predecessors, (22), 10 states have return successors, (44), 17 states have call predecessors, (44), 21 states have call successors, (44) [2025-01-10 02:30:55,709 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 174 states to 174 states and 212 transitions. [2025-01-10 02:30:55,709 INFO L78 Accepts]: Start accepts. Automaton has 174 states and 212 transitions. Word has length 810 [2025-01-10 02:30:55,710 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-10 02:30:55,710 INFO L471 AbstractCegarLoop]: Abstraction has 174 states and 212 transitions. [2025-01-10 02:30:55,711 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 27 states, 27 states have (on average 5.444444444444445) internal successors, (147), 27 states have internal predecessors, (147), 15 states have call successors, (25), 1 states have call predecessors, (25), 11 states have return successors, (31), 19 states have call predecessors, (31), 15 states have call successors, (31) [2025-01-10 02:30:55,711 INFO L276 IsEmpty]: Start isEmpty. Operand 174 states and 212 transitions. [2025-01-10 02:30:55,728 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1734 [2025-01-10 02:30:55,728 INFO L210 NwaCegarLoop]: Found error trace [2025-01-10 02:30:55,728 INFO L218 NwaCegarLoop]: trace histogram [178, 175, 144, 89, 89, 89, 89, 88, 88, 88, 88, 88, 87, 87, 87, 86, 55, 34, 1, 1, 1, 1] [2025-01-10 02:30:55,737 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Forceful destruction successful, exit code 0 [2025-01-10 02:30:55,929 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:55,929 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:55,929 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-10 02:30:55,930 INFO L85 PathProgramCache]: Analyzing trace with hash 247252968, now seen corresponding path program 10 times [2025-01-10 02:30:55,930 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-10 02:30:55,930 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1833850358] [2025-01-10 02:30:55,930 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-01-10 02:30:55,930 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-10 02:30:55,958 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 1733 statements into 2 equivalence classes. [2025-01-10 02:30:56,068 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) and asserted 1028 of 1733 statements. [2025-01-10 02:30:56,069 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) [2025-01-10 02:30:56,069 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 02:30:57,450 INFO L134 CoverageAnalysis]: Checked inductivity of 110535 backedges. 4409 proven. 14460 refuted. 0 times theorem prover too weak. 91666 trivial. 0 not checked. [2025-01-10 02:30:57,451 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-10 02:30:57,451 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1833850358] [2025-01-10 02:30:57,451 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1833850358] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-10 02:30:57,451 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1406476510] [2025-01-10 02:30:57,451 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-01-10 02:30:57,451 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-10 02:30:57,452 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-10 02:30:57,454 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:57,456 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:57,679 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 1733 statements into 2 equivalence classes. [2025-01-10 02:30:57,853 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) and asserted 1028 of 1733 statements. [2025-01-10 02:30:57,853 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) [2025-01-10 02:30:57,853 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 02:30:57,859 INFO L256 TraceCheckSpWp]: Trace formula consists of 2150 conjuncts, 34 conjuncts are in the unsatisfiable core [2025-01-10 02:30:57,876 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-10 02:30:58,101 INFO L134 CoverageAnalysis]: Checked inductivity of 110535 backedges. 44623 proven. 10901 refuted. 0 times theorem prover too weak. 55011 trivial. 0 not checked. [2025-01-10 02:30:58,101 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-10 02:31:02,722 INFO L134 CoverageAnalysis]: Checked inductivity of 110535 backedges. 5338 proven. 16369 refuted. 0 times theorem prover too weak. 88828 trivial. 0 not checked. [2025-01-10 02:31:02,722 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1406476510] provided 0 perfect and 2 imperfect interpolant sequences [2025-01-10 02:31:02,722 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-01-10 02:31:02,722 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 21, 33] total 38 [2025-01-10 02:31:02,723 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [334672507] [2025-01-10 02:31:02,723 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-01-10 02:31:02,724 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 38 states [2025-01-10 02:31:02,725 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-10 02:31:02,726 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 38 interpolants. [2025-01-10 02:31:02,726 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=214, Invalid=1192, Unknown=0, NotChecked=0, Total=1406 [2025-01-10 02:31:02,727 INFO L87 Difference]: Start difference. First operand 174 states and 212 transitions. Second operand has 38 states, 38 states have (on average 5.973684210526316) internal successors, (227), 38 states have internal predecessors, (227), 33 states have call successors, (40), 4 states have call predecessors, (40), 16 states have return successors, (49), 18 states have call predecessors, (49), 31 states have call successors, (49) [2025-01-10 02:31:03,518 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-10 02:31:03,518 INFO L93 Difference]: Finished difference Result 409 states and 542 transitions. [2025-01-10 02:31:03,519 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 51 states. [2025-01-10 02:31:03,519 INFO L78 Accepts]: Start accepts. Automaton has has 38 states, 38 states have (on average 5.973684210526316) internal successors, (227), 38 states have internal predecessors, (227), 33 states have call successors, (40), 4 states have call predecessors, (40), 16 states have return successors, (49), 18 states have call predecessors, (49), 31 states have call successors, (49) Word has length 1733 [2025-01-10 02:31:03,520 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-10 02:31:03,523 INFO L225 Difference]: With dead ends: 409 [2025-01-10 02:31:03,523 INFO L226 Difference]: Without dead ends: 240 [2025-01-10 02:31:03,526 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 3543 GetRequests, 3444 SyntacticMatches, 19 SemanticMatches, 80 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1755 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=1599, Invalid=5043, Unknown=0, NotChecked=0, Total=6642 [2025-01-10 02:31:03,526 INFO L435 NwaCegarLoop]: 41 mSDtfsCounter, 500 mSDsluCounter, 176 mSDsCounter, 0 mSdLazyCounter, 488 mSolverCounterSat, 174 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 500 SdHoareTripleChecker+Valid, 217 SdHoareTripleChecker+Invalid, 662 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 174 IncrementalHoareTripleChecker+Valid, 488 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2025-01-10 02:31:03,527 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [500 Valid, 217 Invalid, 662 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [174 Valid, 488 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2025-01-10 02:31:03,528 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 240 states. [2025-01-10 02:31:03,546 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 240 to 213. [2025-01-10 02:31:03,546 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 213 states, 173 states have (on average 1.0346820809248556) internal successors, (179), 170 states have internal predecessors, (179), 28 states have call successors, (28), 24 states have call predecessors, (28), 11 states have return successors, (55), 18 states have call predecessors, (55), 27 states have call successors, (55) [2025-01-10 02:31:03,548 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 213 states to 213 states and 262 transitions. [2025-01-10 02:31:03,548 INFO L78 Accepts]: Start accepts. Automaton has 213 states and 262 transitions. Word has length 1733 [2025-01-10 02:31:03,549 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-10 02:31:03,549 INFO L471 AbstractCegarLoop]: Abstraction has 213 states and 262 transitions. [2025-01-10 02:31:03,549 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 38 states, 38 states have (on average 5.973684210526316) internal successors, (227), 38 states have internal predecessors, (227), 33 states have call successors, (40), 4 states have call predecessors, (40), 16 states have return successors, (49), 18 states have call predecessors, (49), 31 states have call successors, (49) [2025-01-10 02:31:03,550 INFO L276 IsEmpty]: Start isEmpty. Operand 213 states and 262 transitions. [2025-01-10 02:31:03,557 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1072 [2025-01-10 02:31:03,557 INFO L210 NwaCegarLoop]: Found error trace [2025-01-10 02:31:03,557 INFO L218 NwaCegarLoop]: trace histogram [110, 108, 89, 55, 55, 55, 55, 54, 54, 54, 54, 54, 54, 54, 54, 53, 34, 21, 1, 1, 1, 1] [2025-01-10 02:31:03,568 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Ended with exit code 0 [2025-01-10 02:31:03,758 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:31:03,758 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:31:03,758 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-10 02:31:03,758 INFO L85 PathProgramCache]: Analyzing trace with hash 219479183, now seen corresponding path program 11 times [2025-01-10 02:31:03,759 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-10 02:31:03,759 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1721713850] [2025-01-10 02:31:03,759 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2025-01-10 02:31:03,759 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-10 02:31:03,777 INFO L108 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 partitioned 1071 statements into 76 equivalence classes. [2025-01-10 02:31:03,910 INFO L111 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 76 check-sat command(s) and asserted 1071 of 1071 statements. [2025-01-10 02:31:03,910 INFO L114 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 76 check-sat command(s) [2025-01-10 02:31:03,910 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 02:31:22,046 INFO L134 CoverageAnalysis]: Checked inductivity of 41934 backedges. 7588 proven. 10182 refuted. 0 times theorem prover too weak. 24164 trivial. 0 not checked. [2025-01-10 02:31:22,046 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-10 02:31:22,046 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1721713850] [2025-01-10 02:31:22,046 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1721713850] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-10 02:31:22,046 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1353870793] [2025-01-10 02:31:22,046 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2025-01-10 02:31:22,046 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-10 02:31:22,046 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-10 02:31:22,048 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:22,049 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:22,268 INFO L108 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 partitioned 1071 statements into 76 equivalence classes. [2025-01-10 02:31:22,561 INFO L111 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 76 check-sat command(s) and asserted 1071 of 1071 statements. [2025-01-10 02:31:22,561 INFO L114 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 76 check-sat command(s) [2025-01-10 02:31:22,561 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 02:31:22,568 INFO L256 TraceCheckSpWp]: Trace formula consists of 1998 conjuncts, 217 conjuncts are in the unsatisfiable core [2025-01-10 02:31:22,583 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-10 02:31:23,344 INFO L134 CoverageAnalysis]: Checked inductivity of 41934 backedges. 6686 proven. 7855 refuted. 0 times theorem prover too weak. 27393 trivial. 0 not checked. [2025-01-10 02:31:23,344 INFO L312 TraceCheckSpWp]: Computing backward predicates...