./Ultimate.py --spec ../sv-benchmarks/c/properties/no-overflow.prp --file ../sv-benchmarks/c/recursive/Fibonacci03.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for overflows Using default analysis Version c00e63dc 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/Fibonacci03.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 be0a584ba9648c80e7a0523ff51ba530f1926c55cecd3c62f2cee05fbbff42e3 --- Real Ultimate output --- This is Ultimate 0.3.0-?-c00e63d-m [2025-02-06 14:29:26,446 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-02-06 14:29:26,507 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/config/svcomp-Overflow-32bit-Automizer_Default.epf [2025-02-06 14:29:26,512 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-02-06 14:29:26,513 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-02-06 14:29:26,531 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-02-06 14:29:26,531 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-02-06 14:29:26,532 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-02-06 14:29:26,532 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-02-06 14:29:26,532 INFO L153 SettingsManager]: * Use memory slicer=true [2025-02-06 14:29:26,532 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2025-02-06 14:29:26,532 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2025-02-06 14:29:26,532 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-02-06 14:29:26,533 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-02-06 14:29:26,533 INFO L153 SettingsManager]: * Use SBE=true [2025-02-06 14:29:26,533 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-02-06 14:29:26,533 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2025-02-06 14:29:26,533 INFO L153 SettingsManager]: * sizeof long=4 [2025-02-06 14:29:26,533 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2025-02-06 14:29:26,533 INFO L153 SettingsManager]: * sizeof POINTER=4 [2025-02-06 14:29:26,533 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-02-06 14:29:26,533 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2025-02-06 14:29:26,533 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2025-02-06 14:29:26,536 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2025-02-06 14:29:26,536 INFO L153 SettingsManager]: * Check absence of signed integer overflows=ASSERTandASSUME [2025-02-06 14:29:26,536 INFO L153 SettingsManager]: * Check unreachability of reach_error function=false [2025-02-06 14:29:26,536 INFO L153 SettingsManager]: * sizeof long double=12 [2025-02-06 14:29:26,536 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-02-06 14:29:26,536 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-02-06 14:29:26,537 INFO L153 SettingsManager]: * Use constant arrays=true [2025-02-06 14:29:26,537 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-02-06 14:29:26,537 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-02-06 14:29:26,537 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-02-06 14:29:26,538 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-02-06 14:29:26,538 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-02-06 14:29:26,538 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-02-06 14:29:26,538 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2025-02-06 14:29:26,538 INFO L153 SettingsManager]: * Compute procedure contracts=false [2025-02-06 14:29:26,538 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2025-02-06 14:29:26,538 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2025-02-06 14:29:26,538 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2025-02-06 14:29:26,538 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2025-02-06 14:29:26,538 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2025-02-06 14:29:26,538 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2025-02-06 14:29:26,538 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2025-02-06 14:29:26,538 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 -> be0a584ba9648c80e7a0523ff51ba530f1926c55cecd3c62f2cee05fbbff42e3 [2025-02-06 14:29:26,813 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-02-06 14:29:26,824 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-02-06 14:29:26,827 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-02-06 14:29:26,828 INFO L270 PluginConnector]: Initializing CDTParser... [2025-02-06 14:29:26,828 INFO L274 PluginConnector]: CDTParser initialized [2025-02-06 14:29:26,830 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/recursive/Fibonacci03.c [2025-02-06 14:29:28,125 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/71f8dd8db/0867c1ee6c134c30b9a04d402660ae2a/FLAG62f0e81b9 [2025-02-06 14:29:28,349 INFO L384 CDTParser]: Found 1 translation units. [2025-02-06 14:29:28,350 INFO L180 CDTParser]: Scanning /storage/repos/ultimate-jdk21/releaseScripts/default/sv-benchmarks/c/recursive/Fibonacci03.c [2025-02-06 14:29:28,366 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/71f8dd8db/0867c1ee6c134c30b9a04d402660ae2a/FLAG62f0e81b9 [2025-02-06 14:29:28,384 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/71f8dd8db/0867c1ee6c134c30b9a04d402660ae2a [2025-02-06 14:29:28,388 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-02-06 14:29:28,389 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-02-06 14:29:28,390 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-02-06 14:29:28,390 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-02-06 14:29:28,393 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-02-06 14:29:28,393 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 06.02 02:29:28" (1/1) ... [2025-02-06 14:29:28,394 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@5723e4d6 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.02 02:29:28, skipping insertion in model container [2025-02-06 14:29:28,394 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 06.02 02:29:28" (1/1) ... [2025-02-06 14:29:28,405 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-02-06 14:29:28,552 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-02-06 14:29:28,562 INFO L200 MainTranslator]: Completed pre-run [2025-02-06 14:29:28,576 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-02-06 14:29:28,589 INFO L204 MainTranslator]: Completed translation [2025-02-06 14:29:28,590 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.02 02:29:28 WrapperNode [2025-02-06 14:29:28,590 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-02-06 14:29:28,591 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-02-06 14:29:28,591 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-02-06 14:29:28,591 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-02-06 14:29:28,597 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.02 02:29:28" (1/1) ... [2025-02-06 14:29:28,603 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.02 02:29:28" (1/1) ... [2025-02-06 14:29:28,616 INFO L138 Inliner]: procedures = 13, calls = 11, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 27 [2025-02-06 14:29:28,617 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-02-06 14:29:28,618 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-02-06 14:29:28,619 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-02-06 14:29:28,620 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-02-06 14:29:28,626 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.02 02:29:28" (1/1) ... [2025-02-06 14:29:28,626 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.02 02:29:28" (1/1) ... [2025-02-06 14:29:28,627 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.02 02:29:28" (1/1) ... [2025-02-06 14:29:28,639 INFO L175 MemorySlicer]: Split 2 memory accesses to 1 slices as follows [2]. 100 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2]. The 0 writes are split as follows [0]. [2025-02-06 14:29:28,643 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.02 02:29:28" (1/1) ... [2025-02-06 14:29:28,643 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.02 02:29:28" (1/1) ... [2025-02-06 14:29:28,645 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.02 02:29:28" (1/1) ... [2025-02-06 14:29:28,646 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.02 02:29:28" (1/1) ... [2025-02-06 14:29:28,647 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.02 02:29:28" (1/1) ... [2025-02-06 14:29:28,648 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.02 02:29:28" (1/1) ... [2025-02-06 14:29:28,649 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-02-06 14:29:28,653 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2025-02-06 14:29:28,653 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2025-02-06 14:29:28,653 INFO L274 PluginConnector]: IcfgBuilder initialized [2025-02-06 14:29:28,654 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.02 02:29:28" (1/1) ... [2025-02-06 14:29:28,659 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-02-06 14:29:28,670 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 14:29:28,683 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2025-02-06 14:29:28,687 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2025-02-06 14:29:28,707 INFO L130 BoogieDeclarations]: Found specification of procedure fibonacci [2025-02-06 14:29:28,708 INFO L138 BoogieDeclarations]: Found implementation of procedure fibonacci [2025-02-06 14:29:28,708 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2025-02-06 14:29:28,708 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-02-06 14:29:28,708 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-02-06 14:29:28,708 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2025-02-06 14:29:28,758 INFO L257 CfgBuilder]: Building ICFG [2025-02-06 14:29:28,760 INFO L287 CfgBuilder]: Building CFG for each procedure with an implementation [2025-02-06 14:29:28,852 INFO L1309 $ProcedureCfgBuilder]: dead code at ProgramPoint L22: havoc #t~ret4;havoc #t~ret5; [2025-02-06 14:29:28,896 INFO L? ?]: Removed 17 outVars from TransFormulas that were not future-live. [2025-02-06 14:29:28,897 INFO L308 CfgBuilder]: Performing block encoding [2025-02-06 14:29:28,908 INFO L332 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-02-06 14:29:28,908 INFO L337 CfgBuilder]: Removed 0 assume(true) statements. [2025-02-06 14:29:28,909 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 06.02 02:29:28 BoogieIcfgContainer [2025-02-06 14:29:28,909 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2025-02-06 14:29:28,911 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2025-02-06 14:29:28,911 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2025-02-06 14:29:28,914 INFO L274 PluginConnector]: TraceAbstraction initialized [2025-02-06 14:29:28,915 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 06.02 02:29:28" (1/3) ... [2025-02-06 14:29:28,915 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6c6e74e1 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 06.02 02:29:28, skipping insertion in model container [2025-02-06 14:29:28,915 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.02 02:29:28" (2/3) ... [2025-02-06 14:29:28,916 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6c6e74e1 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 06.02 02:29:28, skipping insertion in model container [2025-02-06 14:29:28,916 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 06.02 02:29:28" (3/3) ... [2025-02-06 14:29:28,917 INFO L128 eAbstractionObserver]: Analyzing ICFG Fibonacci03.c [2025-02-06 14:29:28,928 INFO L216 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2025-02-06 14:29:28,929 INFO L151 ceAbstractionStarter]: Applying trace abstraction to ICFG Fibonacci03.c that has 2 procedures, 32 locations, 1 initial locations, 0 loop locations, and 6 error locations. [2025-02-06 14:29:28,969 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2025-02-06 14:29:28,981 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;@bcad64c, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2025-02-06 14:29:28,981 INFO L334 AbstractCegarLoop]: Starting to check reachability of 6 error locations. [2025-02-06 14:29:28,985 INFO L276 IsEmpty]: Start isEmpty. Operand has 32 states, 21 states have (on average 1.4761904761904763) internal successors, (31), 27 states have internal predecessors, (31), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2025-02-06 14:29:28,990 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 9 [2025-02-06 14:29:28,990 INFO L210 NwaCegarLoop]: Found error trace [2025-02-06 14:29:28,991 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2025-02-06 14:29:28,991 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting fibonacciErr5ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-02-06 14:29:28,995 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-06 14:29:28,996 INFO L85 PathProgramCache]: Analyzing trace with hash 154990982, now seen corresponding path program 1 times [2025-02-06 14:29:29,001 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-06 14:29:29,005 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1733490869] [2025-02-06 14:29:29,005 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-06 14:29:29,005 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-06 14:29:29,057 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 8 statements into 1 equivalence classes. [2025-02-06 14:29:29,071 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 8 of 8 statements. [2025-02-06 14:29:29,072 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-06 14:29:29,072 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 14:29:29,148 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-02-06 14:29:29,150 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-06 14:29:29,151 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1733490869] [2025-02-06 14:29:29,151 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1733490869] provided 1 perfect and 0 imperfect interpolant sequences [2025-02-06 14:29:29,151 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-02-06 14:29:29,152 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2025-02-06 14:29:29,153 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [67469282] [2025-02-06 14:29:29,154 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-02-06 14:29:29,157 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2025-02-06 14:29:29,158 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-06 14:29:29,175 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2025-02-06 14:29:29,176 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2025-02-06 14:29:29,177 INFO L87 Difference]: Start difference. First operand has 32 states, 21 states have (on average 1.4761904761904763) internal successors, (31), 27 states have internal predecessors, (31), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Second operand has 3 states, 2 states have (on average 3.5) internal successors, (7), 3 states have internal predecessors, (7), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-02-06 14:29:29,228 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-06 14:29:29,230 INFO L93 Difference]: Finished difference Result 37 states and 43 transitions. [2025-02-06 14:29:29,231 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2025-02-06 14:29:29,232 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 2 states have (on average 3.5) internal successors, (7), 3 states have internal predecessors, (7), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 8 [2025-02-06 14:29:29,232 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-06 14:29:29,237 INFO L225 Difference]: With dead ends: 37 [2025-02-06 14:29:29,237 INFO L226 Difference]: Without dead ends: 25 [2025-02-06 14:29:29,240 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2025-02-06 14:29:29,243 INFO L435 NwaCegarLoop]: 29 mSDtfsCounter, 11 mSDsluCounter, 15 mSDsCounter, 0 mSdLazyCounter, 13 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 44 SdHoareTripleChecker+Invalid, 14 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 13 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-02-06 14:29:29,244 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [13 Valid, 44 Invalid, 14 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 13 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-02-06 14:29:29,255 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 25 states. [2025-02-06 14:29:29,269 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 25 to 23. [2025-02-06 14:29:29,272 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 23 states, 15 states have (on average 1.4) internal successors, (21), 19 states have internal predecessors, (21), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-02-06 14:29:29,276 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 23 states to 23 states and 26 transitions. [2025-02-06 14:29:29,280 INFO L78 Accepts]: Start accepts. Automaton has 23 states and 26 transitions. Word has length 8 [2025-02-06 14:29:29,280 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-06 14:29:29,280 INFO L471 AbstractCegarLoop]: Abstraction has 23 states and 26 transitions. [2025-02-06 14:29:29,281 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 2 states have (on average 3.5) internal successors, (7), 3 states have internal predecessors, (7), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-02-06 14:29:29,281 INFO L276 IsEmpty]: Start isEmpty. Operand 23 states and 26 transitions. [2025-02-06 14:29:29,282 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 10 [2025-02-06 14:29:29,282 INFO L210 NwaCegarLoop]: Found error trace [2025-02-06 14:29:29,283 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-02-06 14:29:29,283 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2025-02-06 14:29:29,283 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting fibonacciErr4ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-02-06 14:29:29,284 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-06 14:29:29,284 INFO L85 PathProgramCache]: Analyzing trace with hash 509753131, now seen corresponding path program 1 times [2025-02-06 14:29:29,284 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-06 14:29:29,284 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1614486160] [2025-02-06 14:29:29,284 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-06 14:29:29,284 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-06 14:29:29,290 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 9 statements into 1 equivalence classes. [2025-02-06 14:29:29,299 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 9 of 9 statements. [2025-02-06 14:29:29,300 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-06 14:29:29,300 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 14:29:29,376 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-02-06 14:29:29,376 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-06 14:29:29,376 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1614486160] [2025-02-06 14:29:29,378 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1614486160] provided 1 perfect and 0 imperfect interpolant sequences [2025-02-06 14:29:29,378 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-02-06 14:29:29,378 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2025-02-06 14:29:29,378 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [405404221] [2025-02-06 14:29:29,378 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-02-06 14:29:29,379 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-02-06 14:29:29,379 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-06 14:29:29,379 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-02-06 14:29:29,380 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-02-06 14:29:29,380 INFO L87 Difference]: Start difference. First operand 23 states and 26 transitions. Second operand has 5 states, 3 states have (on average 2.6666666666666665) internal successors, (8), 4 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-02-06 14:29:29,453 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-06 14:29:29,453 INFO L93 Difference]: Finished difference Result 25 states and 29 transitions. [2025-02-06 14:29:29,454 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-02-06 14:29:29,454 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 3 states have (on average 2.6666666666666665) internal successors, (8), 4 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 9 [2025-02-06 14:29:29,455 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-06 14:29:29,455 INFO L225 Difference]: With dead ends: 25 [2025-02-06 14:29:29,455 INFO L226 Difference]: Without dead ends: 23 [2025-02-06 14:29:29,456 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2025-02-06 14:29:29,457 INFO L435 NwaCegarLoop]: 14 mSDtfsCounter, 26 mSDsluCounter, 18 mSDsCounter, 0 mSdLazyCounter, 33 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 26 SdHoareTripleChecker+Valid, 32 SdHoareTripleChecker+Invalid, 40 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 33 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-02-06 14:29:29,458 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [26 Valid, 32 Invalid, 40 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 33 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-02-06 14:29:29,459 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 23 states. [2025-02-06 14:29:29,462 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 23 to 21. [2025-02-06 14:29:29,462 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 21 states, 15 states have (on average 1.2666666666666666) internal successors, (19), 17 states have internal predecessors, (19), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-02-06 14:29:29,463 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 21 states to 21 states and 24 transitions. [2025-02-06 14:29:29,463 INFO L78 Accepts]: Start accepts. Automaton has 21 states and 24 transitions. Word has length 9 [2025-02-06 14:29:29,463 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-06 14:29:29,464 INFO L471 AbstractCegarLoop]: Abstraction has 21 states and 24 transitions. [2025-02-06 14:29:29,464 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 3 states have (on average 2.6666666666666665) internal successors, (8), 4 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-02-06 14:29:29,464 INFO L276 IsEmpty]: Start isEmpty. Operand 21 states and 24 transitions. [2025-02-06 14:29:29,464 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2025-02-06 14:29:29,465 INFO L210 NwaCegarLoop]: Found error trace [2025-02-06 14:29:29,465 INFO L218 NwaCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-02-06 14:29:29,465 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2025-02-06 14:29:29,465 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-02-06 14:29:29,466 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-06 14:29:29,466 INFO L85 PathProgramCache]: Analyzing trace with hash -984405394, now seen corresponding path program 1 times [2025-02-06 14:29:29,466 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-06 14:29:29,466 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1634543173] [2025-02-06 14:29:29,466 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-06 14:29:29,466 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-06 14:29:29,473 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 24 statements into 1 equivalence classes. [2025-02-06 14:29:29,487 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 24 of 24 statements. [2025-02-06 14:29:29,487 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-06 14:29:29,488 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 14:29:29,640 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2025-02-06 14:29:29,641 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-06 14:29:29,641 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1634543173] [2025-02-06 14:29:29,641 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1634543173] provided 1 perfect and 0 imperfect interpolant sequences [2025-02-06 14:29:29,641 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-02-06 14:29:29,641 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2025-02-06 14:29:29,642 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [483165202] [2025-02-06 14:29:29,642 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-02-06 14:29:29,643 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-02-06 14:29:29,643 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-06 14:29:29,644 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-02-06 14:29:29,644 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2025-02-06 14:29:29,644 INFO L87 Difference]: Start difference. First operand 21 states and 24 transitions. Second operand has 5 states, 4 states have (on average 3.75) internal successors, (15), 5 states have internal predecessors, (15), 2 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-02-06 14:29:29,691 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-06 14:29:29,692 INFO L93 Difference]: Finished difference Result 35 states and 43 transitions. [2025-02-06 14:29:29,693 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-02-06 14:29:29,693 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 3.75) internal successors, (15), 5 states have internal predecessors, (15), 2 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 24 [2025-02-06 14:29:29,693 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-06 14:29:29,694 INFO L225 Difference]: With dead ends: 35 [2025-02-06 14:29:29,694 INFO L226 Difference]: Without dead ends: 33 [2025-02-06 14:29:29,694 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2025-02-06 14:29:29,695 INFO L435 NwaCegarLoop]: 18 mSDtfsCounter, 3 mSDsluCounter, 51 mSDsCounter, 0 mSdLazyCounter, 27 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 69 SdHoareTripleChecker+Invalid, 29 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 27 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-02-06 14:29:29,695 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 69 Invalid, 29 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 27 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-02-06 14:29:29,698 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 33 states. [2025-02-06 14:29:29,705 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 33 to 30. [2025-02-06 14:29:29,705 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 30 states, 22 states have (on average 1.1818181818181819) internal successors, (26), 24 states have internal predecessors, (26), 4 states have call successors, (4), 1 states have call predecessors, (4), 2 states have return successors, (6), 4 states have call predecessors, (6), 3 states have call successors, (6) [2025-02-06 14:29:29,706 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 30 states to 30 states and 36 transitions. [2025-02-06 14:29:29,707 INFO L78 Accepts]: Start accepts. Automaton has 30 states and 36 transitions. Word has length 24 [2025-02-06 14:29:29,707 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-06 14:29:29,707 INFO L471 AbstractCegarLoop]: Abstraction has 30 states and 36 transitions. [2025-02-06 14:29:29,707 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 3.75) internal successors, (15), 5 states have internal predecessors, (15), 2 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-02-06 14:29:29,707 INFO L276 IsEmpty]: Start isEmpty. Operand 30 states and 36 transitions. [2025-02-06 14:29:29,709 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2025-02-06 14:29:29,709 INFO L210 NwaCegarLoop]: Found error trace [2025-02-06 14:29:29,710 INFO L218 NwaCegarLoop]: trace histogram [4, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-02-06 14:29:29,710 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2025-02-06 14:29:29,710 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-02-06 14:29:29,710 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-06 14:29:29,711 INFO L85 PathProgramCache]: Analyzing trace with hash -119709208, now seen corresponding path program 1 times [2025-02-06 14:29:29,711 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-06 14:29:29,711 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1111721849] [2025-02-06 14:29:29,711 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-06 14:29:29,711 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-06 14:29:29,722 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 31 statements into 1 equivalence classes. [2025-02-06 14:29:29,735 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 31 of 31 statements. [2025-02-06 14:29:29,736 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-06 14:29:29,736 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 14:29:29,860 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2025-02-06 14:29:29,860 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-06 14:29:29,861 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1111721849] [2025-02-06 14:29:29,861 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1111721849] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-06 14:29:29,861 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1585928436] [2025-02-06 14:29:29,861 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-06 14:29:29,861 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-06 14:29:29,861 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 14:29:29,865 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-02-06 14:29:29,867 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2025-02-06 14:29:29,902 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 31 statements into 1 equivalence classes. [2025-02-06 14:29:29,922 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 31 of 31 statements. [2025-02-06 14:29:29,922 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-06 14:29:29,922 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 14:29:29,924 INFO L256 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 6 conjuncts are in the unsatisfiable core [2025-02-06 14:29:29,929 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-06 14:29:30,046 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 6 proven. 3 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2025-02-06 14:29:30,047 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-06 14:29:30,221 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 6 proven. 3 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2025-02-06 14:29:30,224 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1585928436] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-06 14:29:30,224 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-06 14:29:30,224 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 7, 7] total 15 [2025-02-06 14:29:30,224 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1408275008] [2025-02-06 14:29:30,225 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-06 14:29:30,225 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2025-02-06 14:29:30,226 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-06 14:29:30,227 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2025-02-06 14:29:30,228 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=35, Invalid=175, Unknown=0, NotChecked=0, Total=210 [2025-02-06 14:29:30,229 INFO L87 Difference]: Start difference. First operand 30 states and 36 transitions. Second operand has 15 states, 15 states have (on average 2.466666666666667) internal successors, (37), 15 states have internal predecessors, (37), 4 states have call successors, (5), 1 states have call predecessors, (5), 5 states have return successors, (6), 5 states have call predecessors, (6), 4 states have call successors, (6) [2025-02-06 14:29:30,501 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-06 14:29:30,502 INFO L93 Difference]: Finished difference Result 91 states and 129 transitions. [2025-02-06 14:29:30,502 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2025-02-06 14:29:30,502 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 15 states have (on average 2.466666666666667) internal successors, (37), 15 states have internal predecessors, (37), 4 states have call successors, (5), 1 states have call predecessors, (5), 5 states have return successors, (6), 5 states have call predecessors, (6), 4 states have call successors, (6) Word has length 31 [2025-02-06 14:29:30,503 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-06 14:29:30,504 INFO L225 Difference]: With dead ends: 91 [2025-02-06 14:29:30,504 INFO L226 Difference]: Without dead ends: 65 [2025-02-06 14:29:30,505 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 74 GetRequests, 52 SyntacticMatches, 1 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 42 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=111, Invalid=395, Unknown=0, NotChecked=0, Total=506 [2025-02-06 14:29:30,506 INFO L435 NwaCegarLoop]: 13 mSDtfsCounter, 134 mSDsluCounter, 79 mSDsCounter, 0 mSdLazyCounter, 174 mSolverCounterSat, 56 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 134 SdHoareTripleChecker+Valid, 92 SdHoareTripleChecker+Invalid, 230 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 56 IncrementalHoareTripleChecker+Valid, 174 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-02-06 14:29:30,506 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [134 Valid, 92 Invalid, 230 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [56 Valid, 174 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-02-06 14:29:30,507 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 65 states. [2025-02-06 14:29:30,518 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 65 to 53. [2025-02-06 14:29:30,519 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 53 states, 39 states have (on average 1.1025641025641026) internal successors, (43), 42 states have internal predecessors, (43), 7 states have call successors, (7), 2 states have call predecessors, (7), 5 states have return successors, (18), 8 states have call predecessors, (18), 6 states have call successors, (18) [2025-02-06 14:29:30,521 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 53 states to 53 states and 68 transitions. [2025-02-06 14:29:30,522 INFO L78 Accepts]: Start accepts. Automaton has 53 states and 68 transitions. Word has length 31 [2025-02-06 14:29:30,522 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-06 14:29:30,524 INFO L471 AbstractCegarLoop]: Abstraction has 53 states and 68 transitions. [2025-02-06 14:29:30,524 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 2.466666666666667) internal successors, (37), 15 states have internal predecessors, (37), 4 states have call successors, (5), 1 states have call predecessors, (5), 5 states have return successors, (6), 5 states have call predecessors, (6), 4 states have call successors, (6) [2025-02-06 14:29:30,525 INFO L276 IsEmpty]: Start isEmpty. Operand 53 states and 68 transitions. [2025-02-06 14:29:30,525 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2025-02-06 14:29:30,525 INFO L210 NwaCegarLoop]: Found error trace [2025-02-06 14:29:30,526 INFO L218 NwaCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-02-06 14:29:30,533 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2025-02-06 14:29:30,726 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,2 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-06 14:29:30,726 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-02-06 14:29:30,727 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-06 14:29:30,727 INFO L85 PathProgramCache]: Analyzing trace with hash 1220480843, now seen corresponding path program 2 times [2025-02-06 14:29:30,727 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-06 14:29:30,727 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [524127552] [2025-02-06 14:29:30,727 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-02-06 14:29:30,727 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-06 14:29:30,733 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 25 statements into 2 equivalence classes. [2025-02-06 14:29:30,739 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 25 of 25 statements. [2025-02-06 14:29:30,739 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-02-06 14:29:30,739 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 14:29:30,831 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2025-02-06 14:29:30,832 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-06 14:29:30,832 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [524127552] [2025-02-06 14:29:30,833 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [524127552] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-06 14:29:30,833 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1180088269] [2025-02-06 14:29:30,833 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-02-06 14:29:30,833 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-06 14:29:30,833 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 14:29:30,835 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-02-06 14:29:30,837 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2025-02-06 14:29:30,863 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 25 statements into 2 equivalence classes. [2025-02-06 14:29:30,874 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 25 of 25 statements. [2025-02-06 14:29:30,874 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-02-06 14:29:30,874 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 14:29:30,875 INFO L256 TraceCheckSpWp]: Trace formula consists of 67 conjuncts, 4 conjuncts are in the unsatisfiable core [2025-02-06 14:29:30,876 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-06 14:29:30,932 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2025-02-06 14:29:30,932 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-02-06 14:29:30,932 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1180088269] provided 1 perfect and 0 imperfect interpolant sequences [2025-02-06 14:29:30,932 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-02-06 14:29:30,932 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [5] total 7 [2025-02-06 14:29:30,933 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2113238435] [2025-02-06 14:29:30,933 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-02-06 14:29:30,933 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-02-06 14:29:30,933 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-06 14:29:30,933 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-02-06 14:29:30,933 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=38, Unknown=0, NotChecked=0, Total=56 [2025-02-06 14:29:30,934 INFO L87 Difference]: Start difference. First operand 53 states and 68 transitions. Second operand has 5 states, 4 states have (on average 4.25) internal successors, (17), 5 states have internal predecessors, (17), 2 states have call successors, (3), 1 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-02-06 14:29:30,968 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-06 14:29:30,968 INFO L93 Difference]: Finished difference Result 60 states and 76 transitions. [2025-02-06 14:29:30,969 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-02-06 14:29:30,969 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 4.25) internal successors, (17), 5 states have internal predecessors, (17), 2 states have call successors, (3), 1 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 25 [2025-02-06 14:29:30,969 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-06 14:29:30,970 INFO L225 Difference]: With dead ends: 60 [2025-02-06 14:29:30,970 INFO L226 Difference]: Without dead ends: 59 [2025-02-06 14:29:30,971 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 29 GetRequests, 22 SyntacticMatches, 1 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=18, Invalid=38, Unknown=0, NotChecked=0, Total=56 [2025-02-06 14:29:30,971 INFO L435 NwaCegarLoop]: 18 mSDtfsCounter, 4 mSDsluCounter, 33 mSDsCounter, 0 mSdLazyCounter, 20 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 51 SdHoareTripleChecker+Invalid, 22 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 20 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-02-06 14:29:30,971 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [5 Valid, 51 Invalid, 22 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 20 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-02-06 14:29:30,972 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 59 states. [2025-02-06 14:29:30,980 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 59 to 55. [2025-02-06 14:29:30,980 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 55 states, 41 states have (on average 1.0975609756097562) internal successors, (45), 43 states have internal predecessors, (45), 7 states have call successors, (7), 2 states have call predecessors, (7), 5 states have return successors, (18), 9 states have call predecessors, (18), 6 states have call successors, (18) [2025-02-06 14:29:30,981 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 55 states to 55 states and 70 transitions. [2025-02-06 14:29:30,981 INFO L78 Accepts]: Start accepts. Automaton has 55 states and 70 transitions. Word has length 25 [2025-02-06 14:29:30,982 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-06 14:29:30,982 INFO L471 AbstractCegarLoop]: Abstraction has 55 states and 70 transitions. [2025-02-06 14:29:30,982 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 4.25) internal successors, (17), 5 states have internal predecessors, (17), 2 states have call successors, (3), 1 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-02-06 14:29:30,982 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 70 transitions. [2025-02-06 14:29:30,983 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2025-02-06 14:29:30,983 INFO L210 NwaCegarLoop]: Found error trace [2025-02-06 14:29:30,983 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, 1] [2025-02-06 14:29:30,990 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2025-02-06 14:29:31,183 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,3 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-06 14:29:31,184 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-02-06 14:29:31,184 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-06 14:29:31,184 INFO L85 PathProgramCache]: Analyzing trace with hash 929820207, now seen corresponding path program 1 times [2025-02-06 14:29:31,184 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-06 14:29:31,185 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1054235531] [2025-02-06 14:29:31,185 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-06 14:29:31,185 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-06 14:29:31,190 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 32 statements into 1 equivalence classes. [2025-02-06 14:29:31,195 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 32 of 32 statements. [2025-02-06 14:29:31,195 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-06 14:29:31,195 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 14:29:31,280 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2025-02-06 14:29:31,281 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-06 14:29:31,281 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1054235531] [2025-02-06 14:29:31,281 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1054235531] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-06 14:29:31,281 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [751128433] [2025-02-06 14:29:31,281 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-06 14:29:31,281 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-06 14:29:31,281 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 14:29:31,284 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-02-06 14:29:31,285 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2025-02-06 14:29:31,309 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 32 statements into 1 equivalence classes. [2025-02-06 14:29:31,321 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 32 of 32 statements. [2025-02-06 14:29:31,321 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-06 14:29:31,322 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 14:29:31,322 INFO L256 TraceCheckSpWp]: Trace formula consists of 78 conjuncts, 5 conjuncts are in the unsatisfiable core [2025-02-06 14:29:31,324 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-06 14:29:31,391 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2025-02-06 14:29:31,391 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-02-06 14:29:31,391 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [751128433] provided 1 perfect and 0 imperfect interpolant sequences [2025-02-06 14:29:31,391 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-02-06 14:29:31,391 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [5] total 9 [2025-02-06 14:29:31,391 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [602485339] [2025-02-06 14:29:31,392 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-02-06 14:29:31,392 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2025-02-06 14:29:31,392 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-06 14:29:31,393 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2025-02-06 14:29:31,393 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=64, Unknown=0, NotChecked=0, Total=90 [2025-02-06 14:29:31,393 INFO L87 Difference]: Start difference. First operand 55 states and 70 transitions. Second operand has 6 states, 5 states have (on average 3.6) internal successors, (18), 6 states have internal predecessors, (18), 2 states have call successors, (3), 1 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-02-06 14:29:31,432 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-06 14:29:31,432 INFO L93 Difference]: Finished difference Result 82 states and 117 transitions. [2025-02-06 14:29:31,433 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2025-02-06 14:29:31,433 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 3.6) internal successors, (18), 6 states have internal predecessors, (18), 2 states have call successors, (3), 1 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 32 [2025-02-06 14:29:31,433 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-06 14:29:31,434 INFO L225 Difference]: With dead ends: 82 [2025-02-06 14:29:31,434 INFO L226 Difference]: Without dead ends: 81 [2025-02-06 14:29:31,435 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 36 GetRequests, 28 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 12 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=26, Invalid=64, Unknown=0, NotChecked=0, Total=90 [2025-02-06 14:29:31,435 INFO L435 NwaCegarLoop]: 18 mSDtfsCounter, 2 mSDsluCounter, 53 mSDsCounter, 0 mSdLazyCounter, 29 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 71 SdHoareTripleChecker+Invalid, 30 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 29 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-02-06 14:29:31,435 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 71 Invalid, 30 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 29 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-02-06 14:29:31,436 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 81 states. [2025-02-06 14:29:31,448 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 81 to 64. [2025-02-06 14:29:31,449 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 64 states, 48 states have (on average 1.0833333333333333) internal successors, (52), 50 states have internal predecessors, (52), 8 states have call successors, (8), 2 states have call predecessors, (8), 6 states have return successors, (27), 11 states have call predecessors, (27), 7 states have call successors, (27) [2025-02-06 14:29:31,450 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 64 states to 64 states and 87 transitions. [2025-02-06 14:29:31,450 INFO L78 Accepts]: Start accepts. Automaton has 64 states and 87 transitions. Word has length 32 [2025-02-06 14:29:31,450 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-06 14:29:31,451 INFO L471 AbstractCegarLoop]: Abstraction has 64 states and 87 transitions. [2025-02-06 14:29:31,451 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 3.6) internal successors, (18), 6 states have internal predecessors, (18), 2 states have call successors, (3), 1 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-02-06 14:29:31,451 INFO L276 IsEmpty]: Start isEmpty. Operand 64 states and 87 transitions. [2025-02-06 14:29:31,452 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 47 [2025-02-06 14:29:31,452 INFO L210 NwaCegarLoop]: Found error trace [2025-02-06 14:29:31,452 INFO L218 NwaCegarLoop]: trace histogram [5, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1] [2025-02-06 14:29:31,459 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2025-02-06 14:29:31,653 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,4 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-06 14:29:31,653 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-02-06 14:29:31,653 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-06 14:29:31,654 INFO L85 PathProgramCache]: Analyzing trace with hash -1465088786, now seen corresponding path program 1 times [2025-02-06 14:29:31,654 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-06 14:29:31,654 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [872899041] [2025-02-06 14:29:31,654 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-06 14:29:31,654 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-06 14:29:31,659 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 46 statements into 1 equivalence classes. [2025-02-06 14:29:31,669 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 46 of 46 statements. [2025-02-06 14:29:31,669 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-06 14:29:31,669 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 14:29:31,829 INFO L134 CoverageAnalysis]: Checked inductivity of 48 backedges. 2 proven. 15 refuted. 0 times theorem prover too weak. 31 trivial. 0 not checked. [2025-02-06 14:29:31,829 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-06 14:29:31,829 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [872899041] [2025-02-06 14:29:31,829 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [872899041] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-06 14:29:31,829 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1229348895] [2025-02-06 14:29:31,829 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-06 14:29:31,830 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-06 14:29:31,830 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 14:29:31,833 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-02-06 14:29:31,835 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2025-02-06 14:29:31,859 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 46 statements into 1 equivalence classes. [2025-02-06 14:29:31,872 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 46 of 46 statements. [2025-02-06 14:29:31,872 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-06 14:29:31,872 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 14:29:31,873 INFO L256 TraceCheckSpWp]: Trace formula consists of 105 conjuncts, 9 conjuncts are in the unsatisfiable core [2025-02-06 14:29:31,877 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-06 14:29:31,981 INFO L134 CoverageAnalysis]: Checked inductivity of 48 backedges. 2 proven. 7 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2025-02-06 14:29:31,981 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-06 14:29:32,197 INFO L134 CoverageAnalysis]: Checked inductivity of 48 backedges. 6 proven. 7 refuted. 0 times theorem prover too weak. 35 trivial. 0 not checked. [2025-02-06 14:29:32,198 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1229348895] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-06 14:29:32,198 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-06 14:29:32,198 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 6, 7] total 15 [2025-02-06 14:29:32,198 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1105023386] [2025-02-06 14:29:32,198 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-06 14:29:32,198 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2025-02-06 14:29:32,198 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-06 14:29:32,199 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2025-02-06 14:29:32,199 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=62, Invalid=178, Unknown=0, NotChecked=0, Total=240 [2025-02-06 14:29:32,199 INFO L87 Difference]: Start difference. First operand 64 states and 87 transitions. Second operand has 16 states, 15 states have (on average 3.0) internal successors, (45), 16 states have internal predecessors, (45), 4 states have call successors, (5), 1 states have call predecessors, (5), 5 states have return successors, (9), 9 states have call predecessors, (9), 4 states have call successors, (9) [2025-02-06 14:29:32,418 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-06 14:29:32,419 INFO L93 Difference]: Finished difference Result 141 states and 217 transitions. [2025-02-06 14:29:32,419 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2025-02-06 14:29:32,419 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 15 states have (on average 3.0) internal successors, (45), 16 states have internal predecessors, (45), 4 states have call successors, (5), 1 states have call predecessors, (5), 5 states have return successors, (9), 9 states have call predecessors, (9), 4 states have call successors, (9) Word has length 46 [2025-02-06 14:29:32,419 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-06 14:29:32,424 INFO L225 Difference]: With dead ends: 141 [2025-02-06 14:29:32,424 INFO L226 Difference]: Without dead ends: 139 [2025-02-06 14:29:32,425 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 105 GetRequests, 83 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-02-06 14:29:32,426 INFO L435 NwaCegarLoop]: 25 mSDtfsCounter, 14 mSDsluCounter, 169 mSDsCounter, 0 mSdLazyCounter, 166 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 21 SdHoareTripleChecker+Valid, 194 SdHoareTripleChecker+Invalid, 171 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 166 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-02-06 14:29:32,426 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [21 Valid, 194 Invalid, 171 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 166 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-02-06 14:29:32,427 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 139 states. [2025-02-06 14:29:32,451 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 139 to 98. [2025-02-06 14:29:32,452 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 98 states, 76 states have (on average 1.0789473684210527) internal successors, (82), 75 states have internal predecessors, (82), 11 states have call successors, (11), 2 states have call predecessors, (11), 9 states have return successors, (66), 20 states have call predecessors, (66), 10 states have call successors, (66) [2025-02-06 14:29:32,454 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 98 states to 98 states and 159 transitions. [2025-02-06 14:29:32,456 INFO L78 Accepts]: Start accepts. Automaton has 98 states and 159 transitions. Word has length 46 [2025-02-06 14:29:32,456 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-06 14:29:32,456 INFO L471 AbstractCegarLoop]: Abstraction has 98 states and 159 transitions. [2025-02-06 14:29:32,457 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 15 states have (on average 3.0) internal successors, (45), 16 states have internal predecessors, (45), 4 states have call successors, (5), 1 states have call predecessors, (5), 5 states have return successors, (9), 9 states have call predecessors, (9), 4 states have call successors, (9) [2025-02-06 14:29:32,457 INFO L276 IsEmpty]: Start isEmpty. Operand 98 states and 159 transitions. [2025-02-06 14:29:32,459 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 83 [2025-02-06 14:29:32,462 INFO L210 NwaCegarLoop]: Found error trace [2025-02-06 14:29:32,462 INFO L218 NwaCegarLoop]: trace histogram [9, 8, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 1, 1, 1, 1, 1, 1] [2025-02-06 14:29:32,469 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-02-06 14:29:32,663 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 5 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable6 [2025-02-06 14:29:32,663 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-02-06 14:29:32,664 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-06 14:29:32,664 INFO L85 PathProgramCache]: Analyzing trace with hash 1138642878, now seen corresponding path program 1 times [2025-02-06 14:29:32,664 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-06 14:29:32,664 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [536123167] [2025-02-06 14:29:32,664 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-06 14:29:32,664 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-06 14:29:32,672 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 82 statements into 1 equivalence classes. [2025-02-06 14:29:32,684 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 82 of 82 statements. [2025-02-06 14:29:32,684 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-06 14:29:32,685 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 14:29:32,865 INFO L134 CoverageAnalysis]: Checked inductivity of 195 backedges. 38 proven. 80 refuted. 0 times theorem prover too weak. 77 trivial. 0 not checked. [2025-02-06 14:29:32,866 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-06 14:29:32,866 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [536123167] [2025-02-06 14:29:32,866 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [536123167] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-06 14:29:32,866 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1799310318] [2025-02-06 14:29:32,866 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-06 14:29:32,866 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-06 14:29:32,866 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 14:29:32,869 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-02-06 14:29:32,871 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2025-02-06 14:29:32,897 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 82 statements into 1 equivalence classes. [2025-02-06 14:29:32,916 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 82 of 82 statements. [2025-02-06 14:29:32,916 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-06 14:29:32,917 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 14:29:32,918 INFO L256 TraceCheckSpWp]: Trace formula consists of 172 conjuncts, 10 conjuncts are in the unsatisfiable core [2025-02-06 14:29:32,921 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-06 14:29:33,021 INFO L134 CoverageAnalysis]: Checked inductivity of 195 backedges. 50 proven. 84 refuted. 0 times theorem prover too weak. 61 trivial. 0 not checked. [2025-02-06 14:29:33,021 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-06 14:29:33,402 INFO L134 CoverageAnalysis]: Checked inductivity of 195 backedges. 50 proven. 87 refuted. 0 times theorem prover too weak. 58 trivial. 0 not checked. [2025-02-06 14:29:33,403 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1799310318] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-06 14:29:33,403 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-06 14:29:33,403 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 9, 11] total 16 [2025-02-06 14:29:33,403 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [149707572] [2025-02-06 14:29:33,403 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-06 14:29:33,403 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2025-02-06 14:29:33,404 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-06 14:29:33,404 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2025-02-06 14:29:33,404 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=53, Invalid=187, Unknown=0, NotChecked=0, Total=240 [2025-02-06 14:29:33,405 INFO L87 Difference]: Start difference. First operand 98 states and 159 transitions. Second operand has 16 states, 16 states have (on average 5.0625) internal successors, (81), 16 states have internal predecessors, (81), 10 states have call successors, (14), 1 states have call predecessors, (14), 5 states have return successors, (14), 7 states have call predecessors, (14), 10 states have call successors, (14) [2025-02-06 14:29:33,592 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-06 14:29:33,592 INFO L93 Difference]: Finished difference Result 174 states and 299 transitions. [2025-02-06 14:29:33,593 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2025-02-06 14:29:33,593 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 16 states have (on average 5.0625) internal successors, (81), 16 states have internal predecessors, (81), 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 82 [2025-02-06 14:29:33,593 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-06 14:29:33,594 INFO L225 Difference]: With dead ends: 174 [2025-02-06 14:29:33,594 INFO L226 Difference]: Without dead ends: 80 [2025-02-06 14:29:33,597 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 184 GetRequests, 157 SyntacticMatches, 5 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 73 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=164, Invalid=388, Unknown=0, NotChecked=0, Total=552 [2025-02-06 14:29:33,598 INFO L435 NwaCegarLoop]: 16 mSDtfsCounter, 101 mSDsluCounter, 49 mSDsCounter, 0 mSdLazyCounter, 106 mSolverCounterSat, 45 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 101 SdHoareTripleChecker+Valid, 65 SdHoareTripleChecker+Invalid, 151 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 45 IncrementalHoareTripleChecker+Valid, 106 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-02-06 14:29:33,598 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [101 Valid, 65 Invalid, 151 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [45 Valid, 106 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-02-06 14:29:33,599 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 80 states. [2025-02-06 14:29:33,605 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 80 to 70. [2025-02-06 14:29:33,606 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 70 states, 55 states have (on average 1.1090909090909091) internal successors, (61), 53 states have internal predecessors, (61), 7 states have call successors, (7), 4 states have call predecessors, (7), 6 states have return successors, (26), 12 states have call predecessors, (26), 6 states have call successors, (26) [2025-02-06 14:29:33,607 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 70 states to 70 states and 94 transitions. [2025-02-06 14:29:33,607 INFO L78 Accepts]: Start accepts. Automaton has 70 states and 94 transitions. Word has length 82 [2025-02-06 14:29:33,607 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-06 14:29:33,608 INFO L471 AbstractCegarLoop]: Abstraction has 70 states and 94 transitions. [2025-02-06 14:29:33,608 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 16 states have (on average 5.0625) internal successors, (81), 16 states have internal predecessors, (81), 10 states have call successors, (14), 1 states have call predecessors, (14), 5 states have return successors, (14), 7 states have call predecessors, (14), 10 states have call successors, (14) [2025-02-06 14:29:33,608 INFO L276 IsEmpty]: Start isEmpty. Operand 70 states and 94 transitions. [2025-02-06 14:29:33,611 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 177 [2025-02-06 14:29:33,611 INFO L210 NwaCegarLoop]: Found error trace [2025-02-06 14:29:33,611 INFO L218 NwaCegarLoop]: trace histogram [19, 17, 14, 9, 9, 9, 9, 9, 9, 9, 9, 9, 8, 8, 7, 7, 5, 5, 1, 1, 1, 1, 1] [2025-02-06 14:29:33,619 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2025-02-06 14:29:33,816 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,6 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-06 14:29:33,816 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-02-06 14:29:33,816 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-06 14:29:33,817 INFO L85 PathProgramCache]: Analyzing trace with hash 1550196080, now seen corresponding path program 2 times [2025-02-06 14:29:33,817 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-06 14:29:33,817 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [394625217] [2025-02-06 14:29:33,817 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-02-06 14:29:33,817 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-06 14:29:33,826 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 176 statements into 2 equivalence classes. [2025-02-06 14:29:33,855 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 176 of 176 statements. [2025-02-06 14:29:33,856 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-02-06 14:29:33,856 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 14:29:34,198 INFO L134 CoverageAnalysis]: Checked inductivity of 1034 backedges. 93 proven. 424 refuted. 0 times theorem prover too weak. 517 trivial. 0 not checked. [2025-02-06 14:29:34,198 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-06 14:29:34,198 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [394625217] [2025-02-06 14:29:34,198 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [394625217] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-06 14:29:34,198 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1635177742] [2025-02-06 14:29:34,198 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-02-06 14:29:34,198 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-06 14:29:34,199 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 14:29:34,201 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-02-06 14:29:34,203 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2025-02-06 14:29:34,234 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 176 statements into 2 equivalence classes. [2025-02-06 14:29:34,269 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 176 of 176 statements. [2025-02-06 14:29:34,270 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-02-06 14:29:34,270 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 14:29:34,271 INFO L256 TraceCheckSpWp]: Trace formula consists of 346 conjuncts, 14 conjuncts are in the unsatisfiable core [2025-02-06 14:29:34,275 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-06 14:29:34,401 INFO L134 CoverageAnalysis]: Checked inductivity of 1034 backedges. 606 proven. 183 refuted. 0 times theorem prover too weak. 245 trivial. 0 not checked. [2025-02-06 14:29:34,401 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-06 14:29:34,960 INFO L134 CoverageAnalysis]: Checked inductivity of 1034 backedges. 109 proven. 495 refuted. 0 times theorem prover too weak. 430 trivial. 0 not checked. [2025-02-06 14:29:34,961 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1635177742] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-06 14:29:34,961 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-06 14:29:34,961 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 11, 14] total 19 [2025-02-06 14:29:34,961 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1894702308] [2025-02-06 14:29:34,961 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-06 14:29:34,962 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2025-02-06 14:29:34,962 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-06 14:29:34,962 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2025-02-06 14:29:34,963 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=66, Invalid=276, Unknown=0, NotChecked=0, Total=342 [2025-02-06 14:29:34,963 INFO L87 Difference]: Start difference. First operand 70 states and 94 transitions. Second operand has 19 states, 19 states have (on average 5.894736842105263) internal successors, (112), 19 states have internal predecessors, (112), 14 states have call successors, (20), 3 states have call predecessors, (20), 7 states have return successors, (20), 8 states have call predecessors, (20), 13 states have call successors, (20) [2025-02-06 14:29:35,201 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-06 14:29:35,201 INFO L93 Difference]: Finished difference Result 173 states and 254 transitions. [2025-02-06 14:29:35,202 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2025-02-06 14:29:35,202 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 19 states have (on average 5.894736842105263) internal successors, (112), 19 states have internal predecessors, (112), 14 states have call successors, (20), 3 states have call predecessors, (20), 7 states have return successors, (20), 8 states have call predecessors, (20), 13 states have call successors, (20) Word has length 176 [2025-02-06 14:29:35,203 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-06 14:29:35,204 INFO L225 Difference]: With dead ends: 173 [2025-02-06 14:29:35,204 INFO L226 Difference]: Without dead ends: 107 [2025-02-06 14:29:35,205 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 379 GetRequests, 343 SyntacticMatches, 8 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 147 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=252, Invalid=618, Unknown=0, NotChecked=0, Total=870 [2025-02-06 14:29:35,206 INFO L435 NwaCegarLoop]: 17 mSDtfsCounter, 169 mSDsluCounter, 67 mSDsCounter, 0 mSdLazyCounter, 136 mSolverCounterSat, 71 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 169 SdHoareTripleChecker+Valid, 84 SdHoareTripleChecker+Invalid, 207 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 71 IncrementalHoareTripleChecker+Valid, 136 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-02-06 14:29:35,206 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [169 Valid, 84 Invalid, 207 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [71 Valid, 136 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-02-06 14:29:35,207 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 107 states. [2025-02-06 14:29:35,227 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 107 to 95. [2025-02-06 14:29:35,228 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 95 states, 75 states have (on average 1.12) internal successors, (84), 73 states have internal predecessors, (84), 10 states have call successors, (10), 6 states have call predecessors, (10), 8 states have return successors, (36), 15 states have call predecessors, (36), 9 states have call successors, (36) [2025-02-06 14:29:35,230 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 95 states to 95 states and 130 transitions. [2025-02-06 14:29:35,230 INFO L78 Accepts]: Start accepts. Automaton has 95 states and 130 transitions. Word has length 176 [2025-02-06 14:29:35,231 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-06 14:29:35,231 INFO L471 AbstractCegarLoop]: Abstraction has 95 states and 130 transitions. [2025-02-06 14:29:35,231 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 19 states have (on average 5.894736842105263) internal successors, (112), 19 states have internal predecessors, (112), 14 states have call successors, (20), 3 states have call predecessors, (20), 7 states have return successors, (20), 8 states have call predecessors, (20), 13 states have call successors, (20) [2025-02-06 14:29:35,231 INFO L276 IsEmpty]: Start isEmpty. Operand 95 states and 130 transitions. [2025-02-06 14:29:35,232 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 85 [2025-02-06 14:29:35,232 INFO L210 NwaCegarLoop]: Found error trace [2025-02-06 14:29:35,232 INFO L218 NwaCegarLoop]: trace histogram [9, 8, 7, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 2, 1, 1, 1, 1, 1] [2025-02-06 14:29:35,241 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2025-02-06 14:29:35,432 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 7 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable8 [2025-02-06 14:29:35,433 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-02-06 14:29:35,433 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-06 14:29:35,433 INFO L85 PathProgramCache]: Analyzing trace with hash -1565790802, now seen corresponding path program 3 times [2025-02-06 14:29:35,433 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-06 14:29:35,433 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [776642934] [2025-02-06 14:29:35,433 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-02-06 14:29:35,434 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-06 14:29:35,439 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 84 statements into 8 equivalence classes. [2025-02-06 14:29:35,448 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) and asserted 51 of 84 statements. [2025-02-06 14:29:35,449 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2025-02-06 14:29:35,449 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 14:29:35,575 INFO L134 CoverageAnalysis]: Checked inductivity of 206 backedges. 58 proven. 8 refuted. 0 times theorem prover too weak. 140 trivial. 0 not checked. [2025-02-06 14:29:35,575 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-06 14:29:35,575 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [776642934] [2025-02-06 14:29:35,575 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [776642934] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-06 14:29:35,576 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [179283066] [2025-02-06 14:29:35,576 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-02-06 14:29:35,576 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-06 14:29:35,576 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 14:29:35,578 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-02-06 14:29:35,581 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2025-02-06 14:29:35,608 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 84 statements into 8 equivalence classes. [2025-02-06 14:29:35,629 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) and asserted 51 of 84 statements. [2025-02-06 14:29:35,629 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2025-02-06 14:29:35,629 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 14:29:35,630 INFO L256 TraceCheckSpWp]: Trace formula consists of 114 conjuncts, 8 conjuncts are in the unsatisfiable core [2025-02-06 14:29:35,632 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-06 14:29:35,712 INFO L134 CoverageAnalysis]: Checked inductivity of 206 backedges. 60 proven. 4 refuted. 0 times theorem prover too weak. 142 trivial. 0 not checked. [2025-02-06 14:29:35,713 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-06 14:29:35,895 INFO L134 CoverageAnalysis]: Checked inductivity of 206 backedges. 60 proven. 4 refuted. 0 times theorem prover too weak. 142 trivial. 0 not checked. [2025-02-06 14:29:35,895 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [179283066] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-06 14:29:35,895 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-06 14:29:35,896 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 7, 7] total 15 [2025-02-06 14:29:35,896 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1587472100] [2025-02-06 14:29:35,896 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-06 14:29:35,896 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2025-02-06 14:29:35,896 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-06 14:29:35,897 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2025-02-06 14:29:35,897 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=60, Invalid=180, Unknown=0, NotChecked=0, Total=240 [2025-02-06 14:29:35,897 INFO L87 Difference]: Start difference. First operand 95 states and 130 transitions. Second operand has 16 states, 15 states have (on average 3.466666666666667) internal successors, (52), 16 states have internal predecessors, (52), 5 states have call successors, (7), 1 states have call predecessors, (7), 5 states have return successors, (10), 9 states have call predecessors, (10), 5 states have call successors, (10) [2025-02-06 14:29:35,964 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-06 14:29:35,964 INFO L93 Difference]: Finished difference Result 101 states and 137 transitions. [2025-02-06 14:29:35,964 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2025-02-06 14:29:35,965 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 15 states have (on average 3.466666666666667) internal successors, (52), 16 states have internal predecessors, (52), 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 84 [2025-02-06 14:29:35,965 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-06 14:29:35,966 INFO L225 Difference]: With dead ends: 101 [2025-02-06 14:29:35,966 INFO L226 Difference]: Without dead ends: 100 [2025-02-06 14:29:35,966 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 176 GetRequests, 156 SyntacticMatches, 4 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 109 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=82, Invalid=224, Unknown=0, NotChecked=0, Total=306 [2025-02-06 14:29:35,967 INFO L435 NwaCegarLoop]: 20 mSDtfsCounter, 4 mSDsluCounter, 118 mSDsCounter, 0 mSdLazyCounter, 70 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 138 SdHoareTripleChecker+Invalid, 71 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 70 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-02-06 14:29:35,967 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [5 Valid, 138 Invalid, 71 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 70 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-02-06 14:29:35,968 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 100 states. [2025-02-06 14:29:35,975 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 100 to 94. [2025-02-06 14:29:35,976 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 94 states, 75 states have (on average 1.0933333333333333) internal successors, (82), 72 states have internal predecessors, (82), 10 states have call successors, (10), 6 states have call predecessors, (10), 8 states have return successors, (36), 15 states have call predecessors, (36), 9 states have call successors, (36) [2025-02-06 14:29:35,977 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 94 states to 94 states and 128 transitions. [2025-02-06 14:29:35,977 INFO L78 Accepts]: Start accepts. Automaton has 94 states and 128 transitions. Word has length 84 [2025-02-06 14:29:35,977 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-06 14:29:35,977 INFO L471 AbstractCegarLoop]: Abstraction has 94 states and 128 transitions. [2025-02-06 14:29:35,977 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 15 states have (on average 3.466666666666667) internal successors, (52), 16 states have internal predecessors, (52), 5 states have call successors, (7), 1 states have call predecessors, (7), 5 states have return successors, (10), 9 states have call predecessors, (10), 5 states have call successors, (10) [2025-02-06 14:29:35,978 INFO L276 IsEmpty]: Start isEmpty. Operand 94 states and 128 transitions. [2025-02-06 14:29:35,978 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 92 [2025-02-06 14:29:35,978 INFO L210 NwaCegarLoop]: Found error trace [2025-02-06 14:29:35,979 INFO L218 NwaCegarLoop]: trace histogram [10, 8, 8, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 2, 1, 1, 1, 1, 1] [2025-02-06 14:29:35,986 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-02-06 14:29:36,179 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,8 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-06 14:29:36,180 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-02-06 14:29:36,180 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-06 14:29:36,181 INFO L85 PathProgramCache]: Analyzing trace with hash 1944773268, now seen corresponding path program 2 times [2025-02-06 14:29:36,181 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-06 14:29:36,181 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [938708137] [2025-02-06 14:29:36,181 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-02-06 14:29:36,181 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-06 14:29:36,186 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 91 statements into 2 equivalence classes. [2025-02-06 14:29:36,192 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 91 of 91 statements. [2025-02-06 14:29:36,192 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-02-06 14:29:36,192 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 14:29:36,277 INFO L134 CoverageAnalysis]: Checked inductivity of 246 backedges. 32 proven. 0 refuted. 0 times theorem prover too weak. 214 trivial. 0 not checked. [2025-02-06 14:29:36,277 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-06 14:29:36,277 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [938708137] [2025-02-06 14:29:36,278 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [938708137] provided 1 perfect and 0 imperfect interpolant sequences [2025-02-06 14:29:36,278 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-02-06 14:29:36,278 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2025-02-06 14:29:36,278 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2136057769] [2025-02-06 14:29:36,278 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-02-06 14:29:36,278 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-02-06 14:29:36,278 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-06 14:29:36,279 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-02-06 14:29:36,279 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2025-02-06 14:29:36,279 INFO L87 Difference]: Start difference. First operand 94 states and 128 transitions. Second operand has 5 states, 4 states have (on average 6.25) internal successors, (25), 5 states have internal predecessors, (25), 2 states have call successors, (4), 1 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2025-02-06 14:29:36,301 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-06 14:29:36,301 INFO L93 Difference]: Finished difference Result 101 states and 135 transitions. [2025-02-06 14:29:36,301 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-02-06 14:29:36,302 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 6.25) internal successors, (25), 5 states have internal predecessors, (25), 2 states have call successors, (4), 1 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 91 [2025-02-06 14:29:36,302 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-06 14:29:36,304 INFO L225 Difference]: With dead ends: 101 [2025-02-06 14:29:36,304 INFO L226 Difference]: Without dead ends: 100 [2025-02-06 14:29:36,304 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2025-02-06 14:29:36,304 INFO L435 NwaCegarLoop]: 19 mSDtfsCounter, 2 mSDsluCounter, 49 mSDsCounter, 0 mSdLazyCounter, 17 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3 SdHoareTripleChecker+Valid, 68 SdHoareTripleChecker+Invalid, 17 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 17 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-02-06 14:29:36,305 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [3 Valid, 68 Invalid, 17 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 17 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-02-06 14:29:36,306 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 100 states. [2025-02-06 14:29:36,317 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 100 to 94. [2025-02-06 14:29:36,318 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 94 states, 75 states have (on average 1.0933333333333333) internal successors, (82), 72 states have internal predecessors, (82), 10 states have call successors, (10), 6 states have call predecessors, (10), 8 states have return successors, (36), 15 states have call predecessors, (36), 9 states have call successors, (36) [2025-02-06 14:29:36,320 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 94 states to 94 states and 128 transitions. [2025-02-06 14:29:36,320 INFO L78 Accepts]: Start accepts. Automaton has 94 states and 128 transitions. Word has length 91 [2025-02-06 14:29:36,320 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-06 14:29:36,321 INFO L471 AbstractCegarLoop]: Abstraction has 94 states and 128 transitions. [2025-02-06 14:29:36,321 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 6.25) internal successors, (25), 5 states have internal predecessors, (25), 2 states have call successors, (4), 1 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2025-02-06 14:29:36,321 INFO L276 IsEmpty]: Start isEmpty. Operand 94 states and 128 transitions. [2025-02-06 14:29:36,322 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 87 [2025-02-06 14:29:36,323 INFO L210 NwaCegarLoop]: Found error trace [2025-02-06 14:29:36,323 INFO L218 NwaCegarLoop]: trace histogram [9, 8, 8, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 1, 1, 1, 1, 1, 1] [2025-02-06 14:29:36,323 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10 [2025-02-06 14:29:36,323 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-02-06 14:29:36,323 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-06 14:29:36,323 INFO L85 PathProgramCache]: Analyzing trace with hash 253207638, now seen corresponding path program 3 times [2025-02-06 14:29:36,323 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-06 14:29:36,323 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [11642947] [2025-02-06 14:29:36,324 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-02-06 14:29:36,324 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-06 14:29:36,331 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 86 statements into 7 equivalence classes. [2025-02-06 14:29:36,345 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) and asserted 80 of 86 statements. [2025-02-06 14:29:36,345 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2025-02-06 14:29:36,346 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 14:29:36,469 INFO L134 CoverageAnalysis]: Checked inductivity of 216 backedges. 89 proven. 48 refuted. 0 times theorem prover too weak. 79 trivial. 0 not checked. [2025-02-06 14:29:36,470 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-06 14:29:36,470 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [11642947] [2025-02-06 14:29:36,470 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [11642947] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-06 14:29:36,470 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1228206440] [2025-02-06 14:29:36,470 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-02-06 14:29:36,470 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-06 14:29:36,470 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 14:29:36,472 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-02-06 14:29:36,475 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2025-02-06 14:29:36,501 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 86 statements into 7 equivalence classes. [2025-02-06 14:29:36,520 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) and asserted 80 of 86 statements. [2025-02-06 14:29:36,521 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2025-02-06 14:29:36,521 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 14:29:36,523 INFO L256 TraceCheckSpWp]: Trace formula consists of 169 conjuncts, 17 conjuncts are in the unsatisfiable core [2025-02-06 14:29:36,525 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-06 14:29:36,729 INFO L134 CoverageAnalysis]: Checked inductivity of 216 backedges. 8 proven. 66 refuted. 0 times theorem prover too weak. 142 trivial. 0 not checked. [2025-02-06 14:29:36,729 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-06 14:29:37,521 INFO L134 CoverageAnalysis]: Checked inductivity of 216 backedges. 20 proven. 66 refuted. 0 times theorem prover too weak. 130 trivial. 0 not checked. [2025-02-06 14:29:37,521 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1228206440] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-06 14:29:37,521 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-06 14:29:37,521 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 12, 13] total 32 [2025-02-06 14:29:37,522 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1283093616] [2025-02-06 14:29:37,522 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-06 14:29:37,522 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 32 states [2025-02-06 14:29:37,522 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-06 14:29:37,523 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 32 interpolants. [2025-02-06 14:29:37,523 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=153, Invalid=839, Unknown=0, NotChecked=0, Total=992 [2025-02-06 14:29:37,524 INFO L87 Difference]: Start difference. First operand 94 states and 128 transitions. Second operand has 32 states, 32 states have (on average 3.1875) internal successors, (102), 32 states have internal predecessors, (102), 12 states have call successors, (14), 1 states have call predecessors, (14), 12 states have return successors, (22), 19 states have call predecessors, (22), 12 states have call successors, (22) [2025-02-06 14:29:38,593 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-06 14:29:38,593 INFO L93 Difference]: Finished difference Result 250 states and 418 transitions. [2025-02-06 14:29:38,593 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 42 states. [2025-02-06 14:29:38,594 INFO L78 Accepts]: Start accepts. Automaton has has 32 states, 32 states have (on average 3.1875) internal successors, (102), 32 states have internal predecessors, (102), 12 states have call successors, (14), 1 states have call predecessors, (14), 12 states have return successors, (22), 19 states have call predecessors, (22), 12 states have call successors, (22) Word has length 86 [2025-02-06 14:29:38,594 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-06 14:29:38,597 INFO L225 Difference]: With dead ends: 250 [2025-02-06 14:29:38,597 INFO L226 Difference]: Without dead ends: 160 [2025-02-06 14:29:38,600 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 229 GetRequests, 156 SyntacticMatches, 4 SemanticMatches, 69 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1316 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=1020, Invalid=3950, Unknown=0, NotChecked=0, Total=4970 [2025-02-06 14:29:38,601 INFO L435 NwaCegarLoop]: 13 mSDtfsCounter, 328 mSDsluCounter, 76 mSDsCounter, 0 mSdLazyCounter, 445 mSolverCounterSat, 212 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 328 SdHoareTripleChecker+Valid, 89 SdHoareTripleChecker+Invalid, 657 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 212 IncrementalHoareTripleChecker+Valid, 445 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2025-02-06 14:29:38,601 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [328 Valid, 89 Invalid, 657 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [212 Valid, 445 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2025-02-06 14:29:38,601 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 160 states. [2025-02-06 14:29:38,612 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 160 to 121. [2025-02-06 14:29:38,612 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 121 states, 96 states have (on average 1.0416666666666667) internal successors, (100), 93 states have internal predecessors, (100), 13 states have call successors, (13), 7 states have call predecessors, (13), 11 states have return successors, (70), 20 states have call predecessors, (70), 12 states have call successors, (70) [2025-02-06 14:29:38,614 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 121 states to 121 states and 183 transitions. [2025-02-06 14:29:38,615 INFO L78 Accepts]: Start accepts. Automaton has 121 states and 183 transitions. Word has length 86 [2025-02-06 14:29:38,615 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-06 14:29:38,615 INFO L471 AbstractCegarLoop]: Abstraction has 121 states and 183 transitions. [2025-02-06 14:29:38,615 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 32 states, 32 states have (on average 3.1875) internal successors, (102), 32 states have internal predecessors, (102), 12 states have call successors, (14), 1 states have call predecessors, (14), 12 states have return successors, (22), 19 states have call predecessors, (22), 12 states have call successors, (22) [2025-02-06 14:29:38,615 INFO L276 IsEmpty]: Start isEmpty. Operand 121 states and 183 transitions. [2025-02-06 14:29:38,620 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 383 [2025-02-06 14:29:38,620 INFO L210 NwaCegarLoop]: Found error trace [2025-02-06 14:29:38,621 INFO L218 NwaCegarLoop]: trace histogram [40, 38, 29, 20, 20, 20, 20, 19, 19, 19, 19, 19, 19, 19, 19, 18, 11, 9, 1, 1, 1, 1, 1] [2025-02-06 14:29:38,628 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2025-02-06 14:29:38,821 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11,9 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-06 14:29:38,822 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-02-06 14:29:38,822 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-06 14:29:38,822 INFO L85 PathProgramCache]: Analyzing trace with hash -1489373193, now seen corresponding path program 4 times [2025-02-06 14:29:38,822 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-06 14:29:38,822 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1154153224] [2025-02-06 14:29:38,822 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-02-06 14:29:38,822 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-06 14:29:38,836 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 382 statements into 2 equivalence classes. [2025-02-06 14:29:38,850 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) and asserted 225 of 382 statements. [2025-02-06 14:29:38,850 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) [2025-02-06 14:29:38,850 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 14:29:38,999 INFO L134 CoverageAnalysis]: Checked inductivity of 5139 backedges. 133 proven. 760 refuted. 0 times theorem prover too weak. 4246 trivial. 0 not checked. [2025-02-06 14:29:39,001 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-06 14:29:39,001 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1154153224] [2025-02-06 14:29:39,001 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1154153224] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-06 14:29:39,001 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1697673307] [2025-02-06 14:29:39,001 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-02-06 14:29:39,002 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-06 14:29:39,002 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 14:29:39,004 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-02-06 14:29:39,007 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2025-02-06 14:29:39,065 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 382 statements into 2 equivalence classes. [2025-02-06 14:29:39,112 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) and asserted 225 of 382 statements. [2025-02-06 14:29:39,112 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) [2025-02-06 14:29:39,112 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 14:29:39,114 INFO L256 TraceCheckSpWp]: Trace formula consists of 474 conjuncts, 8 conjuncts are in the unsatisfiable core [2025-02-06 14:29:39,121 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-06 14:29:39,200 INFO L134 CoverageAnalysis]: Checked inductivity of 5139 backedges. 1376 proven. 15 refuted. 0 times theorem prover too weak. 3748 trivial. 0 not checked. [2025-02-06 14:29:39,201 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-06 14:29:39,863 INFO L134 CoverageAnalysis]: Checked inductivity of 5139 backedges. 138 proven. 885 refuted. 0 times theorem prover too weak. 4116 trivial. 0 not checked. [2025-02-06 14:29:39,864 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1697673307] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-06 14:29:39,864 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-06 14:29:39,864 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 8, 9] total 14 [2025-02-06 14:29:39,864 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1175236500] [2025-02-06 14:29:39,864 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-06 14:29:39,865 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2025-02-06 14:29:39,865 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-06 14:29:39,866 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2025-02-06 14:29:39,866 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=47, Invalid=135, Unknown=0, NotChecked=0, Total=182 [2025-02-06 14:29:39,866 INFO L87 Difference]: Start difference. First operand 121 states and 183 transitions. Second operand has 14 states, 14 states have (on average 5.0) internal successors, (70), 14 states have internal predecessors, (70), 7 states have call successors, (12), 2 states have call predecessors, (12), 5 states have return successors, (13), 5 states have call predecessors, (13), 7 states have call successors, (13) [2025-02-06 14:29:39,957 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-06 14:29:39,958 INFO L93 Difference]: Finished difference Result 218 states and 363 transitions. [2025-02-06 14:29:39,958 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2025-02-06 14:29:39,958 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 5.0) internal successors, (70), 14 states have internal predecessors, (70), 7 states have call successors, (12), 2 states have call predecessors, (12), 5 states have return successors, (13), 5 states have call predecessors, (13), 7 states have call successors, (13) Word has length 382 [2025-02-06 14:29:39,959 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-06 14:29:39,960 INFO L225 Difference]: With dead ends: 218 [2025-02-06 14:29:39,960 INFO L226 Difference]: Without dead ends: 103 [2025-02-06 14:29:39,961 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 776 GetRequests, 756 SyntacticMatches, 4 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 55 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=96, Invalid=210, Unknown=0, NotChecked=0, Total=306 [2025-02-06 14:29:39,965 INFO L435 NwaCegarLoop]: 21 mSDtfsCounter, 33 mSDsluCounter, 59 mSDsCounter, 0 mSdLazyCounter, 105 mSolverCounterSat, 16 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 33 SdHoareTripleChecker+Valid, 80 SdHoareTripleChecker+Invalid, 121 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 16 IncrementalHoareTripleChecker+Valid, 105 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-02-06 14:29:39,965 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [33 Valid, 80 Invalid, 121 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [16 Valid, 105 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-02-06 14:29:39,966 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 103 states. [2025-02-06 14:29:39,976 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 103 to 101. [2025-02-06 14:29:39,977 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 101 states, 80 states have (on average 1.0375) internal successors, (83), 78 states have internal predecessors, (83), 11 states have call successors, (11), 6 states have call predecessors, (11), 9 states have return successors, (47), 16 states have call predecessors, (47), 10 states have call successors, (47) [2025-02-06 14:29:39,978 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 101 states to 101 states and 141 transitions. [2025-02-06 14:29:39,978 INFO L78 Accepts]: Start accepts. Automaton has 101 states and 141 transitions. Word has length 382 [2025-02-06 14:29:39,978 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-06 14:29:39,978 INFO L471 AbstractCegarLoop]: Abstraction has 101 states and 141 transitions. [2025-02-06 14:29:39,979 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 5.0) internal successors, (70), 14 states have internal predecessors, (70), 7 states have call successors, (12), 2 states have call predecessors, (12), 5 states have return successors, (13), 5 states have call predecessors, (13), 7 states have call successors, (13) [2025-02-06 14:29:39,979 INFO L276 IsEmpty]: Start isEmpty. Operand 101 states and 141 transitions. [2025-02-06 14:29:39,983 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 327 [2025-02-06 14:29:39,984 INFO L210 NwaCegarLoop]: Found error trace [2025-02-06 14:29:39,984 INFO L218 NwaCegarLoop]: trace histogram [34, 32, 27, 17, 17, 17, 17, 16, 16, 16, 16, 16, 16, 16, 16, 15, 10, 7, 1, 1, 1, 1, 1] [2025-02-06 14:29:39,992 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2025-02-06 14:29:40,184 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable12,10 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-06 14:29:40,185 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-02-06 14:29:40,185 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-06 14:29:40,185 INFO L85 PathProgramCache]: Analyzing trace with hash 1905679565, now seen corresponding path program 5 times [2025-02-06 14:29:40,185 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-06 14:29:40,186 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [793462772] [2025-02-06 14:29:40,186 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2025-02-06 14:29:40,186 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-06 14:29:40,210 INFO L108 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 partitioned 326 statements into 21 equivalence classes. [2025-02-06 14:29:40,224 INFO L111 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 9 check-sat command(s) and asserted 137 of 326 statements. [2025-02-06 14:29:40,225 INFO L114 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 9 check-sat command(s) [2025-02-06 14:29:40,225 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 14:29:40,452 INFO L134 CoverageAnalysis]: Checked inductivity of 3713 backedges. 415 proven. 972 refuted. 0 times theorem prover too weak. 2326 trivial. 0 not checked. [2025-02-06 14:29:40,452 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-06 14:29:40,452 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [793462772] [2025-02-06 14:29:40,452 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [793462772] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-06 14:29:40,452 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [783093786] [2025-02-06 14:29:40,453 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2025-02-06 14:29:40,453 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-06 14:29:40,453 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 14:29:40,455 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-02-06 14:29:40,457 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2025-02-06 14:29:40,510 INFO L108 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 partitioned 326 statements into 21 equivalence classes. [2025-02-06 14:29:40,540 INFO L111 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 9 check-sat command(s) and asserted 137 of 326 statements. [2025-02-06 14:29:40,541 INFO L114 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 9 check-sat command(s) [2025-02-06 14:29:40,541 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 14:29:40,542 INFO L256 TraceCheckSpWp]: Trace formula consists of 255 conjuncts, 15 conjuncts are in the unsatisfiable core [2025-02-06 14:29:40,546 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-06 14:29:40,681 INFO L134 CoverageAnalysis]: Checked inductivity of 3713 backedges. 419 proven. 966 refuted. 0 times theorem prover too weak. 2328 trivial. 0 not checked. [2025-02-06 14:29:40,682 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-06 14:29:41,577 INFO L134 CoverageAnalysis]: Checked inductivity of 3713 backedges. 417 proven. 984 refuted. 0 times theorem prover too weak. 2312 trivial. 0 not checked. [2025-02-06 14:29:41,578 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [783093786] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-06 14:29:41,578 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-06 14:29:41,578 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 12, 16] total 22 [2025-02-06 14:29:41,578 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1911282221] [2025-02-06 14:29:41,578 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-06 14:29:41,579 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2025-02-06 14:29:41,579 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-06 14:29:41,580 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2025-02-06 14:29:41,580 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=95, Invalid=367, Unknown=0, NotChecked=0, Total=462 [2025-02-06 14:29:41,580 INFO L87 Difference]: Start difference. First operand 101 states and 141 transitions. Second operand has 22 states, 22 states have (on average 5.045454545454546) internal successors, (111), 22 states have internal predecessors, (111), 13 states have call successors, (19), 1 states have call predecessors, (19), 7 states have return successors, (21), 11 states have call predecessors, (21), 13 states have call successors, (21) [2025-02-06 14:29:41,924 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-06 14:29:41,925 INFO L93 Difference]: Finished difference Result 221 states and 334 transitions. [2025-02-06 14:29:41,925 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2025-02-06 14:29:41,926 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 22 states have (on average 5.045454545454546) internal successors, (111), 22 states have internal predecessors, (111), 13 states have call successors, (19), 1 states have call predecessors, (19), 7 states have return successors, (21), 11 states have call predecessors, (21), 13 states have call successors, (21) Word has length 326 [2025-02-06 14:29:41,926 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-06 14:29:41,927 INFO L225 Difference]: With dead ends: 221 [2025-02-06 14:29:41,928 INFO L226 Difference]: Without dead ends: 126 [2025-02-06 14:29:41,929 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 683 GetRequests, 642 SyntacticMatches, 7 SemanticMatches, 34 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 243 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=368, Invalid=892, Unknown=0, NotChecked=0, Total=1260 [2025-02-06 14:29:41,930 INFO L435 NwaCegarLoop]: 30 mSDtfsCounter, 128 mSDsluCounter, 90 mSDsCounter, 0 mSdLazyCounter, 241 mSolverCounterSat, 75 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 128 SdHoareTripleChecker+Valid, 120 SdHoareTripleChecker+Invalid, 316 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 75 IncrementalHoareTripleChecker+Valid, 241 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-02-06 14:29:41,930 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [128 Valid, 120 Invalid, 316 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [75 Valid, 241 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-02-06 14:29:41,931 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 126 states. [2025-02-06 14:29:41,942 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 126 to 110. [2025-02-06 14:29:41,943 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 110 states, 88 states have (on average 1.0454545454545454) internal successors, (92), 85 states have internal predecessors, (92), 12 states have call successors, (12), 8 states have call predecessors, (12), 9 states have return successors, (44), 16 states have call predecessors, (44), 11 states have call successors, (44) [2025-02-06 14:29:41,944 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 110 states to 110 states and 148 transitions. [2025-02-06 14:29:41,945 INFO L78 Accepts]: Start accepts. Automaton has 110 states and 148 transitions. Word has length 326 [2025-02-06 14:29:41,945 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-06 14:29:41,945 INFO L471 AbstractCegarLoop]: Abstraction has 110 states and 148 transitions. [2025-02-06 14:29:41,945 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 22 states have (on average 5.045454545454546) internal successors, (111), 22 states have internal predecessors, (111), 13 states have call successors, (19), 1 states have call predecessors, (19), 7 states have return successors, (21), 11 states have call predecessors, (21), 13 states have call successors, (21) [2025-02-06 14:29:41,946 INFO L276 IsEmpty]: Start isEmpty. Operand 110 states and 148 transitions. [2025-02-06 14:29:41,949 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 268 [2025-02-06 14:29:41,949 INFO L210 NwaCegarLoop]: Found error trace [2025-02-06 14:29:41,949 INFO L218 NwaCegarLoop]: trace histogram [28, 26, 22, 14, 14, 14, 14, 13, 13, 13, 13, 13, 13, 13, 13, 12, 8, 6, 1, 1, 1, 1, 1] [2025-02-06 14:29:41,957 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Ended with exit code 0 [2025-02-06 14:29:42,154 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2025-02-06 14:29:42,154 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-02-06 14:29:42,155 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-06 14:29:42,155 INFO L85 PathProgramCache]: Analyzing trace with hash 853046426, now seen corresponding path program 6 times [2025-02-06 14:29:42,155 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-06 14:29:42,155 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1605591400] [2025-02-06 14:29:42,155 INFO L95 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2025-02-06 14:29:42,155 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-06 14:29:42,170 INFO L108 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE partitioned 267 statements into 16 equivalence classes. [2025-02-06 14:29:42,193 INFO L111 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 12 check-sat command(s) and asserted 211 of 267 statements. [2025-02-06 14:29:42,194 INFO L114 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 12 check-sat command(s) [2025-02-06 14:29:42,194 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 14:29:42,385 INFO L134 CoverageAnalysis]: Checked inductivity of 2456 backedges. 278 proven. 640 refuted. 0 times theorem prover too weak. 1538 trivial. 0 not checked. [2025-02-06 14:29:42,385 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-06 14:29:42,385 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1605591400] [2025-02-06 14:29:42,385 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1605591400] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-06 14:29:42,385 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1554514333] [2025-02-06 14:29:42,385 INFO L95 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2025-02-06 14:29:42,386 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-06 14:29:42,386 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 14:29:42,388 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-02-06 14:29:42,389 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2025-02-06 14:29:42,442 INFO L108 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE partitioned 267 statements into 16 equivalence classes. [2025-02-06 14:29:42,487 INFO L111 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 12 check-sat command(s) and asserted 211 of 267 statements. [2025-02-06 14:29:42,488 INFO L114 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 12 check-sat command(s) [2025-02-06 14:29:42,488 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 14:29:42,489 INFO L256 TraceCheckSpWp]: Trace formula consists of 411 conjuncts, 12 conjuncts are in the unsatisfiable core [2025-02-06 14:29:42,492 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-06 14:29:42,557 INFO L134 CoverageAnalysis]: Checked inductivity of 2456 backedges. 1460 proven. 133 refuted. 0 times theorem prover too weak. 863 trivial. 0 not checked. [2025-02-06 14:29:42,557 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-06 14:29:43,255 INFO L134 CoverageAnalysis]: Checked inductivity of 2456 backedges. 282 proven. 646 refuted. 0 times theorem prover too weak. 1528 trivial. 0 not checked. [2025-02-06 14:29:43,255 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1554514333] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-06 14:29:43,255 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-06 14:29:43,255 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10, 13] total 15 [2025-02-06 14:29:43,256 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1420624028] [2025-02-06 14:29:43,256 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-06 14:29:43,256 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2025-02-06 14:29:43,256 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-06 14:29:43,257 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2025-02-06 14:29:43,257 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=47, Invalid=163, Unknown=0, NotChecked=0, Total=210 [2025-02-06 14:29:43,257 INFO L87 Difference]: Start difference. First operand 110 states and 148 transitions. Second operand has 15 states, 15 states have (on average 6.4) internal successors, (96), 15 states have internal predecessors, (96), 9 states have call successors, (17), 2 states have call predecessors, (17), 7 states have return successors, (19), 10 states have call predecessors, (19), 9 states have call successors, (19) [2025-02-06 14:29:43,440 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-06 14:29:43,440 INFO L93 Difference]: Finished difference Result 227 states and 323 transitions. [2025-02-06 14:29:43,441 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2025-02-06 14:29:43,441 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 15 states have (on average 6.4) internal successors, (96), 15 states have internal predecessors, (96), 9 states have call successors, (17), 2 states have call predecessors, (17), 7 states have return successors, (19), 10 states have call predecessors, (19), 9 states have call successors, (19) Word has length 267 [2025-02-06 14:29:43,441 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-06 14:29:43,443 INFO L225 Difference]: With dead ends: 227 [2025-02-06 14:29:43,443 INFO L226 Difference]: Without dead ends: 117 [2025-02-06 14:29:43,444 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 553 GetRequests, 527 SyntacticMatches, 6 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 59 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=132, Invalid=330, Unknown=0, NotChecked=0, Total=462 [2025-02-06 14:29:43,444 INFO L435 NwaCegarLoop]: 32 mSDtfsCounter, 57 mSDsluCounter, 91 mSDsCounter, 0 mSdLazyCounter, 190 mSolverCounterSat, 22 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 57 SdHoareTripleChecker+Valid, 123 SdHoareTripleChecker+Invalid, 212 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 22 IncrementalHoareTripleChecker+Valid, 190 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-02-06 14:29:43,444 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [57 Valid, 123 Invalid, 212 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [22 Valid, 190 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-02-06 14:29:43,447 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 117 states. [2025-02-06 14:29:43,454 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 117 to 98. [2025-02-06 14:29:43,455 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 98 states, 78 states have (on average 1.0512820512820513) internal successors, (82), 77 states have internal predecessors, (82), 12 states have call successors, (12), 8 states have call predecessors, (12), 7 states have return successors, (26), 12 states have call predecessors, (26), 11 states have call successors, (26) [2025-02-06 14:29:43,456 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 98 states to 98 states and 120 transitions. [2025-02-06 14:29:43,456 INFO L78 Accepts]: Start accepts. Automaton has 98 states and 120 transitions. Word has length 267 [2025-02-06 14:29:43,456 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-06 14:29:43,456 INFO L471 AbstractCegarLoop]: Abstraction has 98 states and 120 transitions. [2025-02-06 14:29:43,457 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 6.4) internal successors, (96), 15 states have internal predecessors, (96), 9 states have call successors, (17), 2 states have call predecessors, (17), 7 states have return successors, (19), 10 states have call predecessors, (19), 9 states have call successors, (19) [2025-02-06 14:29:43,457 INFO L276 IsEmpty]: Start isEmpty. Operand 98 states and 120 transitions. [2025-02-06 14:29:43,460 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 308 [2025-02-06 14:29:43,460 INFO L210 NwaCegarLoop]: Found error trace [2025-02-06 14:29:43,461 INFO L218 NwaCegarLoop]: trace histogram [32, 30, 26, 16, 16, 16, 16, 15, 15, 15, 15, 15, 15, 15, 15, 14, 10, 6, 1, 1, 1, 1, 1] [2025-02-06 14:29:43,469 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2025-02-06 14:29:43,664 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2025-02-06 14:29:43,665 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-02-06 14:29:43,665 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-06 14:29:43,665 INFO L85 PathProgramCache]: Analyzing trace with hash -200525822, now seen corresponding path program 7 times [2025-02-06 14:29:43,665 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-06 14:29:43,665 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1084646983] [2025-02-06 14:29:43,665 INFO L95 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2025-02-06 14:29:43,666 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-06 14:29:43,676 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 307 statements into 1 equivalence classes. [2025-02-06 14:29:43,700 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 307 of 307 statements. [2025-02-06 14:29:43,701 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-06 14:29:43,701 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 14:29:44,144 INFO L134 CoverageAnalysis]: Checked inductivity of 3282 backedges. 521 proven. 1076 refuted. 0 times theorem prover too weak. 1685 trivial. 0 not checked. [2025-02-06 14:29:44,144 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-06 14:29:44,144 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1084646983] [2025-02-06 14:29:44,144 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1084646983] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-06 14:29:44,144 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [543148378] [2025-02-06 14:29:44,144 INFO L95 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2025-02-06 14:29:44,145 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-06 14:29:44,145 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 14:29:44,147 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-02-06 14:29:44,149 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2025-02-06 14:29:44,207 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 307 statements into 1 equivalence classes. [2025-02-06 14:29:44,274 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 307 of 307 statements. [2025-02-06 14:29:44,274 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-06 14:29:44,275 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 14:29:44,278 INFO L256 TraceCheckSpWp]: Trace formula consists of 586 conjuncts, 22 conjuncts are in the unsatisfiable core [2025-02-06 14:29:44,287 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-06 14:29:44,452 INFO L134 CoverageAnalysis]: Checked inductivity of 3282 backedges. 613 proven. 1181 refuted. 0 times theorem prover too weak. 1488 trivial. 0 not checked. [2025-02-06 14:29:44,452 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-06 14:29:45,921 INFO L134 CoverageAnalysis]: Checked inductivity of 3282 backedges. 613 proven. 1253 refuted. 0 times theorem prover too weak. 1416 trivial. 0 not checked. [2025-02-06 14:29:45,922 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [543148378] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-06 14:29:45,922 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-06 14:29:45,922 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 15, 23] total 28 [2025-02-06 14:29:45,922 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1432957209] [2025-02-06 14:29:45,922 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-06 14:29:45,923 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 28 states [2025-02-06 14:29:45,923 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-06 14:29:45,923 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 28 interpolants. [2025-02-06 14:29:45,924 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=134, Invalid=622, Unknown=0, NotChecked=0, Total=756 [2025-02-06 14:29:45,924 INFO L87 Difference]: Start difference. First operand 98 states and 120 transitions. Second operand has 28 states, 28 states have (on average 5.357142857142857) internal successors, (150), 28 states have internal predecessors, (150), 21 states have call successors, (25), 1 states have call predecessors, (25), 11 states have return successors, (32), 13 states have call predecessors, (32), 21 states have call successors, (32) [2025-02-06 14:29:46,353 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-06 14:29:46,353 INFO L93 Difference]: Finished difference Result 236 states and 312 transitions. [2025-02-06 14:29:46,354 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2025-02-06 14:29:46,354 INFO L78 Accepts]: Start accepts. Automaton has has 28 states, 28 states have (on average 5.357142857142857) internal successors, (150), 28 states have internal predecessors, (150), 21 states have call successors, (25), 1 states have call predecessors, (25), 11 states have return successors, (32), 13 states have call predecessors, (32), 21 states have call successors, (32) Word has length 307 [2025-02-06 14:29:46,354 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-06 14:29:46,355 INFO L225 Difference]: With dead ends: 236 [2025-02-06 14:29:46,355 INFO L226 Difference]: Without dead ends: 144 [2025-02-06 14:29:46,357 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 657 GetRequests, 599 SyntacticMatches, 11 SemanticMatches, 47 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 544 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=604, Invalid=1748, Unknown=0, NotChecked=0, Total=2352 [2025-02-06 14:29:46,357 INFO L435 NwaCegarLoop]: 35 mSDtfsCounter, 427 mSDsluCounter, 123 mSDsCounter, 0 mSdLazyCounter, 327 mSolverCounterSat, 193 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 427 SdHoareTripleChecker+Valid, 158 SdHoareTripleChecker+Invalid, 520 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 193 IncrementalHoareTripleChecker+Valid, 327 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-02-06 14:29:46,357 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [427 Valid, 158 Invalid, 520 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [193 Valid, 327 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-02-06 14:29:46,358 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 144 states. [2025-02-06 14:29:46,367 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 144 to 122. [2025-02-06 14:29:46,367 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 122 states, 99 states have (on average 1.0505050505050506) internal successors, (104), 95 states have internal predecessors, (104), 14 states have call successors, (14), 11 states have call predecessors, (14), 8 states have return successors, (32), 15 states have call predecessors, (32), 13 states have call successors, (32) [2025-02-06 14:29:46,369 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 122 states to 122 states and 150 transitions. [2025-02-06 14:29:46,369 INFO L78 Accepts]: Start accepts. Automaton has 122 states and 150 transitions. Word has length 307 [2025-02-06 14:29:46,370 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-06 14:29:46,370 INFO L471 AbstractCegarLoop]: Abstraction has 122 states and 150 transitions. [2025-02-06 14:29:46,371 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 28 states, 28 states have (on average 5.357142857142857) internal successors, (150), 28 states have internal predecessors, (150), 21 states have call successors, (25), 1 states have call predecessors, (25), 11 states have return successors, (32), 13 states have call predecessors, (32), 21 states have call successors, (32) [2025-02-06 14:29:46,371 INFO L276 IsEmpty]: Start isEmpty. Operand 122 states and 150 transitions. [2025-02-06 14:29:46,373 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 263 [2025-02-06 14:29:46,373 INFO L210 NwaCegarLoop]: Found error trace [2025-02-06 14:29:46,373 INFO L218 NwaCegarLoop]: trace histogram [27, 26, 22, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 12, 9, 5, 1, 1, 1, 1, 1] [2025-02-06 14:29:46,384 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Ended with exit code 0 [2025-02-06 14:29:46,577 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable15,13 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-06 14:29:46,577 INFO L396 AbstractCegarLoop]: === Iteration 17 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-02-06 14:29:46,577 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-06 14:29:46,577 INFO L85 PathProgramCache]: Analyzing trace with hash 336440142, now seen corresponding path program 8 times [2025-02-06 14:29:46,578 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-06 14:29:46,578 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1645828939] [2025-02-06 14:29:46,578 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-02-06 14:29:46,578 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-06 14:29:46,597 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 262 statements into 2 equivalence classes. [2025-02-06 14:29:46,616 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 262 of 262 statements. [2025-02-06 14:29:46,617 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-02-06 14:29:46,617 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 14:29:46,846 INFO L134 CoverageAnalysis]: Checked inductivity of 2363 backedges. 571 proven. 345 refuted. 0 times theorem prover too weak. 1447 trivial. 0 not checked. [2025-02-06 14:29:46,847 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-06 14:29:46,847 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1645828939] [2025-02-06 14:29:46,847 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1645828939] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-06 14:29:46,847 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [717837786] [2025-02-06 14:29:46,847 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-02-06 14:29:46,847 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-06 14:29:46,848 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 14:29:46,850 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-02-06 14:29:46,851 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2025-02-06 14:29:46,918 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 262 statements into 2 equivalence classes. [2025-02-06 14:29:46,969 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 262 of 262 statements. [2025-02-06 14:29:46,970 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-02-06 14:29:46,970 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 14:29:46,972 INFO L256 TraceCheckSpWp]: Trace formula consists of 504 conjuncts, 18 conjuncts are in the unsatisfiable core [2025-02-06 14:29:46,976 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-06 14:29:47,120 INFO L134 CoverageAnalysis]: Checked inductivity of 2363 backedges. 1197 proven. 484 refuted. 0 times theorem prover too weak. 682 trivial. 0 not checked. [2025-02-06 14:29:47,121 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-06 14:29:48,388 INFO L134 CoverageAnalysis]: Checked inductivity of 2363 backedges. 511 proven. 831 refuted. 0 times theorem prover too weak. 1021 trivial. 0 not checked. [2025-02-06 14:29:48,388 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [717837786] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-06 14:29:48,388 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-06 14:29:48,389 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 13, 19] total 25 [2025-02-06 14:29:48,389 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [731538209] [2025-02-06 14:29:48,389 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-06 14:29:48,389 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 25 states [2025-02-06 14:29:48,393 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-06 14:29:48,394 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2025-02-06 14:29:48,394 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=124, Invalid=476, Unknown=0, NotChecked=0, Total=600 [2025-02-06 14:29:48,395 INFO L87 Difference]: Start difference. First operand 122 states and 150 transitions. Second operand has 25 states, 25 states have (on average 5.76) internal successors, (144), 25 states have internal predecessors, (144), 18 states have call successors, (25), 2 states have call predecessors, (25), 10 states have return successors, (32), 12 states have call predecessors, (32), 18 states have call successors, (32) [2025-02-06 14:29:48,653 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-06 14:29:48,653 INFO L93 Difference]: Finished difference Result 235 states and 300 transitions. [2025-02-06 14:29:48,653 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2025-02-06 14:29:48,654 INFO L78 Accepts]: Start accepts. Automaton has has 25 states, 25 states have (on average 5.76) internal successors, (144), 25 states have internal predecessors, (144), 18 states have call successors, (25), 2 states have call predecessors, (25), 10 states have return successors, (32), 12 states have call predecessors, (32), 18 states have call successors, (32) Word has length 262 [2025-02-06 14:29:48,654 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-06 14:29:48,655 INFO L225 Difference]: With dead ends: 235 [2025-02-06 14:29:48,655 INFO L226 Difference]: Without dead ends: 119 [2025-02-06 14:29:48,656 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 549 GetRequests, 506 SyntacticMatches, 9 SemanticMatches, 34 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 386 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=349, Invalid=911, Unknown=0, NotChecked=0, Total=1260 [2025-02-06 14:29:48,656 INFO L435 NwaCegarLoop]: 41 mSDtfsCounter, 100 mSDsluCounter, 145 mSDsCounter, 0 mSdLazyCounter, 390 mSolverCounterSat, 52 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 100 SdHoareTripleChecker+Valid, 186 SdHoareTripleChecker+Invalid, 442 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 52 IncrementalHoareTripleChecker+Valid, 390 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-02-06 14:29:48,657 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [100 Valid, 186 Invalid, 442 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [52 Valid, 390 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-02-06 14:29:48,657 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 119 states. [2025-02-06 14:29:48,662 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 119 to 107. [2025-02-06 14:29:48,663 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 107 states, 86 states have (on average 1.0348837209302326) internal successors, (89), 84 states have internal predecessors, (89), 13 states have call successors, (13), 10 states have call predecessors, (13), 7 states have return successors, (26), 12 states have call predecessors, (26), 12 states have call successors, (26) [2025-02-06 14:29:48,664 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 107 states to 107 states and 128 transitions. [2025-02-06 14:29:48,664 INFO L78 Accepts]: Start accepts. Automaton has 107 states and 128 transitions. Word has length 262 [2025-02-06 14:29:48,664 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-06 14:29:48,664 INFO L471 AbstractCegarLoop]: Abstraction has 107 states and 128 transitions. [2025-02-06 14:29:48,665 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 25 states, 25 states have (on average 5.76) internal successors, (144), 25 states have internal predecessors, (144), 18 states have call successors, (25), 2 states have call predecessors, (25), 10 states have return successors, (32), 12 states have call predecessors, (32), 18 states have call successors, (32) [2025-02-06 14:29:48,665 INFO L276 IsEmpty]: Start isEmpty. Operand 107 states and 128 transitions. [2025-02-06 14:29:48,666 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 341 [2025-02-06 14:29:48,666 INFO L210 NwaCegarLoop]: Found error trace [2025-02-06 14:29:48,666 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, 1] [2025-02-06 14:29:48,674 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Forceful destruction successful, exit code 0 [2025-02-06 14:29:48,871 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable16 [2025-02-06 14:29:48,871 INFO L396 AbstractCegarLoop]: === Iteration 18 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-02-06 14:29:48,871 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-06 14:29:48,871 INFO L85 PathProgramCache]: Analyzing trace with hash -1953340652, now seen corresponding path program 9 times [2025-02-06 14:29:48,871 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-06 14:29:48,871 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1983895795] [2025-02-06 14:29:48,871 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-02-06 14:29:48,872 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-06 14:29:48,885 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 340 statements into 24 equivalence classes. [2025-02-06 14:29:48,905 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 15 check-sat command(s) and asserted 203 of 340 statements. [2025-02-06 14:29:48,906 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 15 check-sat command(s) [2025-02-06 14:29:48,906 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 14:29:49,133 INFO L134 CoverageAnalysis]: Checked inductivity of 4050 backedges. 1065 proven. 374 refuted. 0 times theorem prover too weak. 2611 trivial. 0 not checked. [2025-02-06 14:29:49,133 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-06 14:29:49,134 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1983895795] [2025-02-06 14:29:49,134 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1983895795] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-06 14:29:49,134 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [389446025] [2025-02-06 14:29:49,134 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-02-06 14:29:49,134 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-06 14:29:49,134 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 14:29:49,136 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-02-06 14:29:49,139 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2025-02-06 14:29:49,222 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 340 statements into 24 equivalence classes. [2025-02-06 14:29:49,274 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 15 check-sat command(s) and asserted 203 of 340 statements. [2025-02-06 14:29:49,274 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 15 check-sat command(s) [2025-02-06 14:29:49,274 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 14:29:49,276 INFO L256 TraceCheckSpWp]: Trace formula consists of 395 conjuncts, 16 conjuncts are in the unsatisfiable core [2025-02-06 14:29:49,280 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-06 14:29:49,395 INFO L134 CoverageAnalysis]: Checked inductivity of 4050 backedges. 1131 proven. 417 refuted. 0 times theorem prover too weak. 2502 trivial. 0 not checked. [2025-02-06 14:29:49,395 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-06 14:29:50,190 INFO L134 CoverageAnalysis]: Checked inductivity of 4050 backedges. 1135 proven. 447 refuted. 0 times theorem prover too weak. 2468 trivial. 0 not checked. [2025-02-06 14:29:50,190 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [389446025] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-06 14:29:50,190 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-06 14:29:50,190 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 12, 17] total 24 [2025-02-06 14:29:50,190 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1371732280] [2025-02-06 14:29:50,190 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-06 14:29:50,191 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 24 states [2025-02-06 14:29:50,191 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-06 14:29:50,192 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2025-02-06 14:29:50,192 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=114, Invalid=438, Unknown=0, NotChecked=0, Total=552 [2025-02-06 14:29:50,192 INFO L87 Difference]: Start difference. First operand 107 states and 128 transitions. Second operand has 24 states, 24 states have (on average 5.0) internal successors, (120), 24 states have internal predecessors, (120), 12 states have call successors, (20), 1 states have call predecessors, (20), 9 states have return successors, (24), 14 states have call predecessors, (24), 12 states have call successors, (24) [2025-02-06 14:29:50,461 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-06 14:29:50,461 INFO L93 Difference]: Finished difference Result 225 states and 274 transitions. [2025-02-06 14:29:50,461 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2025-02-06 14:29:50,462 INFO L78 Accepts]: Start accepts. Automaton has has 24 states, 24 states have (on average 5.0) internal successors, (120), 24 states have internal predecessors, (120), 12 states have call successors, (20), 1 states have call predecessors, (20), 9 states have return successors, (24), 14 states have call predecessors, (24), 12 states have call successors, (24) Word has length 340 [2025-02-06 14:29:50,462 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-06 14:29:50,463 INFO L225 Difference]: With dead ends: 225 [2025-02-06 14:29:50,463 INFO L226 Difference]: Without dead ends: 117 [2025-02-06 14:29:50,464 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 708 GetRequests, 666 SyntacticMatches, 8 SemanticMatches, 34 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 339 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=342, Invalid=918, Unknown=0, NotChecked=0, Total=1260 [2025-02-06 14:29:50,465 INFO L435 NwaCegarLoop]: 32 mSDtfsCounter, 107 mSDsluCounter, 126 mSDsCounter, 0 mSdLazyCounter, 296 mSolverCounterSat, 49 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 107 SdHoareTripleChecker+Valid, 158 SdHoareTripleChecker+Invalid, 345 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 49 IncrementalHoareTripleChecker+Valid, 296 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-02-06 14:29:50,465 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [107 Valid, 158 Invalid, 345 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [49 Valid, 296 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-02-06 14:29:50,465 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 117 states. [2025-02-06 14:29:50,470 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 117 to 107. [2025-02-06 14:29:50,471 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 107 states, 86 states have (on average 1.0348837209302326) internal successors, (89), 84 states have internal predecessors, (89), 13 states have call successors, (13), 10 states have call predecessors, (13), 7 states have return successors, (23), 12 states have call predecessors, (23), 12 states have call successors, (23) [2025-02-06 14:29:50,471 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 107 states to 107 states and 125 transitions. [2025-02-06 14:29:50,472 INFO L78 Accepts]: Start accepts. Automaton has 107 states and 125 transitions. Word has length 340 [2025-02-06 14:29:50,472 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-06 14:29:50,472 INFO L471 AbstractCegarLoop]: Abstraction has 107 states and 125 transitions. [2025-02-06 14:29:50,472 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 24 states, 24 states have (on average 5.0) internal successors, (120), 24 states have internal predecessors, (120), 12 states have call successors, (20), 1 states have call predecessors, (20), 9 states have return successors, (24), 14 states have call predecessors, (24), 12 states have call successors, (24) [2025-02-06 14:29:50,473 INFO L276 IsEmpty]: Start isEmpty. Operand 107 states and 125 transitions. [2025-02-06 14:29:50,475 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 650 [2025-02-06 14:29:50,476 INFO L210 NwaCegarLoop]: Found error trace [2025-02-06 14:29:50,476 INFO L218 NwaCegarLoop]: trace histogram [67, 65, 54, 33, 33, 33, 33, 33, 33, 33, 33, 33, 32, 32, 32, 31, 21, 13, 1, 1, 1, 1, 1] [2025-02-06 14:29:50,484 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-02-06 14:29:50,680 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 15 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable17 [2025-02-06 14:29:50,680 INFO L396 AbstractCegarLoop]: === Iteration 19 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-02-06 14:29:50,680 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-06 14:29:50,681 INFO L85 PathProgramCache]: Analyzing trace with hash 920328619, now seen corresponding path program 10 times [2025-02-06 14:29:50,681 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-06 14:29:50,681 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1638783852] [2025-02-06 14:29:50,681 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-02-06 14:29:50,681 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-06 14:29:50,697 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 649 statements into 2 equivalence classes. [2025-02-06 14:29:50,731 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) and asserted 385 of 649 statements. [2025-02-06 14:29:50,731 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) [2025-02-06 14:29:50,731 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 14:29:51,224 INFO L134 CoverageAnalysis]: Checked inductivity of 15197 backedges. 1156 proven. 3610 refuted. 0 times theorem prover too weak. 10431 trivial. 0 not checked. [2025-02-06 14:29:51,224 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-06 14:29:51,224 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1638783852] [2025-02-06 14:29:51,225 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1638783852] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-06 14:29:51,225 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [155275730] [2025-02-06 14:29:51,225 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-02-06 14:29:51,225 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-06 14:29:51,225 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 14:29:51,227 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-02-06 14:29:51,229 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2025-02-06 14:29:51,333 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 649 statements into 2 equivalence classes. [2025-02-06 14:29:51,409 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) and asserted 385 of 649 statements. [2025-02-06 14:29:51,409 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) [2025-02-06 14:29:51,409 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 14:29:51,419 INFO L256 TraceCheckSpWp]: Trace formula consists of 809 conjuncts, 26 conjuncts are in the unsatisfiable core [2025-02-06 14:29:51,426 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-06 14:29:51,627 INFO L134 CoverageAnalysis]: Checked inductivity of 15197 backedges. 6702 proven. 2732 refuted. 0 times theorem prover too weak. 5763 trivial. 0 not checked. [2025-02-06 14:29:51,627 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-06 14:29:53,542 INFO L134 CoverageAnalysis]: Checked inductivity of 15197 backedges. 1409 proven. 4272 refuted. 0 times theorem prover too weak. 9516 trivial. 0 not checked. [2025-02-06 14:29:53,542 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [155275730] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-06 14:29:53,542 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-06 14:29:53,543 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 17, 26] total 31 [2025-02-06 14:29:53,543 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2132173796] [2025-02-06 14:29:53,543 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-06 14:29:53,544 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 31 states [2025-02-06 14:29:53,544 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-06 14:29:53,545 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 31 interpolants. [2025-02-06 14:29:53,545 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=153, Invalid=777, Unknown=0, NotChecked=0, Total=930 [2025-02-06 14:29:53,545 INFO L87 Difference]: Start difference. First operand 107 states and 125 transitions. Second operand has 31 states, 31 states have (on average 6.032258064516129) internal successors, (187), 31 states have internal predecessors, (187), 26 states have call successors, (33), 3 states have call predecessors, (33), 13 states have return successors, (40), 15 states have call predecessors, (40), 25 states have call successors, (40) [2025-02-06 14:29:54,108 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-06 14:29:54,109 INFO L93 Difference]: Finished difference Result 256 states and 325 transitions. [2025-02-06 14:29:54,109 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 34 states. [2025-02-06 14:29:54,109 INFO L78 Accepts]: Start accepts. Automaton has has 31 states, 31 states have (on average 6.032258064516129) internal successors, (187), 31 states have internal predecessors, (187), 26 states have call successors, (33), 3 states have call predecessors, (33), 13 states have return successors, (40), 15 states have call predecessors, (40), 25 states have call successors, (40) Word has length 649 [2025-02-06 14:29:54,110 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-06 14:29:54,111 INFO L225 Difference]: With dead ends: 256 [2025-02-06 14:29:54,111 INFO L226 Difference]: Without dead ends: 155 [2025-02-06 14:29:54,113 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 1351 GetRequests, 1280 SyntacticMatches, 14 SemanticMatches, 57 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 830 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=861, Invalid=2561, Unknown=0, NotChecked=0, Total=3422 [2025-02-06 14:29:54,113 INFO L435 NwaCegarLoop]: 35 mSDtfsCounter, 346 mSDsluCounter, 136 mSDsCounter, 0 mSdLazyCounter, 340 mSolverCounterSat, 152 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 346 SdHoareTripleChecker+Valid, 171 SdHoareTripleChecker+Invalid, 492 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 152 IncrementalHoareTripleChecker+Valid, 340 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-02-06 14:29:54,114 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [346 Valid, 171 Invalid, 492 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [152 Valid, 340 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-02-06 14:29:54,114 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 155 states. [2025-02-06 14:29:54,121 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 155 to 134. [2025-02-06 14:29:54,121 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 134 states, 108 states have (on average 1.037037037037037) internal successors, (112), 106 states have internal predecessors, (112), 17 states have call successors, (17), 14 states have call predecessors, (17), 8 states have return successors, (31), 13 states have call predecessors, (31), 16 states have call successors, (31) [2025-02-06 14:29:54,122 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 134 states to 134 states and 160 transitions. [2025-02-06 14:29:54,123 INFO L78 Accepts]: Start accepts. Automaton has 134 states and 160 transitions. Word has length 649 [2025-02-06 14:29:54,123 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-06 14:29:54,123 INFO L471 AbstractCegarLoop]: Abstraction has 134 states and 160 transitions. [2025-02-06 14:29:54,124 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 31 states, 31 states have (on average 6.032258064516129) internal successors, (187), 31 states have internal predecessors, (187), 26 states have call successors, (33), 3 states have call predecessors, (33), 13 states have return successors, (40), 15 states have call predecessors, (40), 25 states have call successors, (40) [2025-02-06 14:29:54,124 INFO L276 IsEmpty]: Start isEmpty. Operand 134 states and 160 transitions. [2025-02-06 14:29:54,125 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 400 [2025-02-06 14:29:54,125 INFO L210 NwaCegarLoop]: Found error trace [2025-02-06 14:29:54,126 INFO L218 NwaCegarLoop]: trace histogram [41, 40, 33, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 19, 13, 8, 1, 1, 1, 1, 1] [2025-02-06 14:29:54,134 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Ended with exit code 0 [2025-02-06 14:29:54,326 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable18,16 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-06 14:29:54,326 INFO L396 AbstractCegarLoop]: === Iteration 20 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-02-06 14:29:54,327 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-06 14:29:54,327 INFO L85 PathProgramCache]: Analyzing trace with hash 1806187615, now seen corresponding path program 11 times [2025-02-06 14:29:54,327 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-06 14:29:54,327 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2045348587] [2025-02-06 14:29:54,327 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2025-02-06 14:29:54,327 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-06 14:29:54,337 INFO L108 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 partitioned 399 statements into 29 equivalence classes. [2025-02-06 14:29:54,371 INFO L111 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 29 check-sat command(s) and asserted 399 of 399 statements. [2025-02-06 14:29:54,373 INFO L114 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 29 check-sat command(s) [2025-02-06 14:29:54,373 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 14:29:56,646 INFO L134 CoverageAnalysis]: Checked inductivity of 5628 backedges. 936 proven. 1467 refuted. 0 times theorem prover too weak. 3225 trivial. 0 not checked. [2025-02-06 14:29:56,647 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-06 14:29:56,647 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2045348587] [2025-02-06 14:29:56,647 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2045348587] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-06 14:29:56,647 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [736818608] [2025-02-06 14:29:56,647 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2025-02-06 14:29:56,647 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-06 14:29:56,648 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 14:29:56,650 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-02-06 14:29:56,651 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2025-02-06 14:29:56,746 INFO L108 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 partitioned 399 statements into 29 equivalence classes. [2025-02-06 14:29:56,829 INFO L111 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 29 check-sat command(s) and asserted 399 of 399 statements. [2025-02-06 14:29:56,829 INFO L114 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 29 check-sat command(s) [2025-02-06 14:29:56,829 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 14:29:56,831 INFO L256 TraceCheckSpWp]: Trace formula consists of 757 conjuncts, 81 conjuncts are in the unsatisfiable core [2025-02-06 14:29:56,835 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-06 14:29:57,150 INFO L134 CoverageAnalysis]: Checked inductivity of 5628 backedges. 820 proven. 1112 refuted. 0 times theorem prover too weak. 3696 trivial. 0 not checked. [2025-02-06 14:29:57,150 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-06 14:30:02,905 INFO L134 CoverageAnalysis]: Checked inductivity of 5628 backedges. 1149 proven. 1015 refuted. 0 times theorem prover too weak. 3464 trivial. 0 not checked. [2025-02-06 14:30:02,905 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [736818608] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-06 14:30:02,905 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-06 14:30:02,905 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [24, 18, 29] total 47 [2025-02-06 14:30:02,905 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1392099480] [2025-02-06 14:30:02,906 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-06 14:30:02,906 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 48 states [2025-02-06 14:30:02,906 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-06 14:30:02,907 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 48 interpolants. [2025-02-06 14:30:02,907 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=526, Invalid=1730, Unknown=0, NotChecked=0, Total=2256 [2025-02-06 14:30:02,908 INFO L87 Difference]: Start difference. First operand 134 states and 160 transitions. Second operand has 48 states, 47 states have (on average 2.6595744680851063) internal successors, (125), 48 states have internal predecessors, (125), 12 states have call successors, (13), 1 states have call predecessors, (13), 13 states have return successors, (34), 33 states have call predecessors, (34), 12 states have call successors, (34) [2025-02-06 14:30:03,078 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-06 14:30:03,078 INFO L93 Difference]: Finished difference Result 165 states and 212 transitions. [2025-02-06 14:30:03,078 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 26 states. [2025-02-06 14:30:03,079 INFO L78 Accepts]: Start accepts. Automaton has has 48 states, 47 states have (on average 2.6595744680851063) internal successors, (125), 48 states have internal predecessors, (125), 12 states have call successors, (13), 1 states have call predecessors, (13), 13 states have return successors, (34), 33 states have call predecessors, (34), 12 states have call successors, (34) Word has length 399 [2025-02-06 14:30:03,079 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-06 14:30:03,081 INFO L225 Difference]: With dead ends: 165 [2025-02-06 14:30:03,081 INFO L226 Difference]: Without dead ends: 164 [2025-02-06 14:30:03,082 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 881 GetRequests, 776 SyntacticMatches, 55 SemanticMatches, 50 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2632 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=613, Invalid=2039, Unknown=0, NotChecked=0, Total=2652 [2025-02-06 14:30:03,082 INFO L435 NwaCegarLoop]: 20 mSDtfsCounter, 6 mSDsluCounter, 225 mSDsCounter, 0 mSdLazyCounter, 191 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 245 SdHoareTripleChecker+Invalid, 194 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 191 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-02-06 14:30:03,082 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 245 Invalid, 194 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 191 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-02-06 14:30:03,083 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 164 states. [2025-02-06 14:30:03,092 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 164 to 155. [2025-02-06 14:30:03,092 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 155 states, 125 states have (on average 1.032) internal successors, (129), 122 states have internal predecessors, (129), 19 states have call successors, (19), 14 states have call predecessors, (19), 10 states have return successors, (49), 18 states have call predecessors, (49), 18 states have call successors, (49) [2025-02-06 14:30:03,093 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 155 states to 155 states and 197 transitions. [2025-02-06 14:30:03,094 INFO L78 Accepts]: Start accepts. Automaton has 155 states and 197 transitions. Word has length 399 [2025-02-06 14:30:03,094 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-06 14:30:03,094 INFO L471 AbstractCegarLoop]: Abstraction has 155 states and 197 transitions. [2025-02-06 14:30:03,095 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 48 states, 47 states have (on average 2.6595744680851063) internal successors, (125), 48 states have internal predecessors, (125), 12 states have call successors, (13), 1 states have call predecessors, (13), 13 states have return successors, (34), 33 states have call predecessors, (34), 12 states have call successors, (34) [2025-02-06 14:30:03,095 INFO L276 IsEmpty]: Start isEmpty. Operand 155 states and 197 transitions. [2025-02-06 14:30:03,103 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1237 [2025-02-06 14:30:03,103 INFO L210 NwaCegarLoop]: Found error trace [2025-02-06 14:30:03,103 INFO L218 NwaCegarLoop]: trace histogram [128, 123, 104, 65, 65, 65, 65, 62, 62, 62, 62, 62, 61, 61, 61, 60, 39, 24, 1, 1, 1, 1, 1] [2025-02-06 14:30:03,109 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-02-06 14:30:03,303 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable19,17 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-06 14:30:03,304 INFO L396 AbstractCegarLoop]: === Iteration 21 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-02-06 14:30:03,304 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-06 14:30:03,304 INFO L85 PathProgramCache]: Analyzing trace with hash 201180579, now seen corresponding path program 12 times [2025-02-06 14:30:03,304 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-06 14:30:03,304 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [245253677] [2025-02-06 14:30:03,304 INFO L95 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2025-02-06 14:30:03,304 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-06 14:30:03,325 INFO L108 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE partitioned 1236 statements into 91 equivalence classes. [2025-02-06 14:30:03,469 INFO L111 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 62 check-sat command(s) and asserted 827 of 1236 statements. [2025-02-06 14:30:03,469 INFO L114 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 62 check-sat command(s) [2025-02-06 14:30:03,469 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 14:30:04,857 INFO L134 CoverageAnalysis]: Checked inductivity of 55912 backedges. 4137 proven. 8877 refuted. 0 times theorem prover too weak. 42898 trivial. 0 not checked. [2025-02-06 14:30:04,857 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-06 14:30:04,857 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [245253677] [2025-02-06 14:30:04,857 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [245253677] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-06 14:30:04,857 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [521273484] [2025-02-06 14:30:04,857 INFO L95 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2025-02-06 14:30:04,857 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-06 14:30:04,858 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 14:30:04,859 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-02-06 14:30:04,860 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Waiting until timeout for monitored process [2025-02-06 14:30:05,051 INFO L108 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE partitioned 1236 statements into 91 equivalence classes. [2025-02-06 14:30:05,251 INFO L111 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 62 check-sat command(s) and asserted 827 of 1236 statements. [2025-02-06 14:30:05,251 INFO L114 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 62 check-sat command(s) [2025-02-06 14:30:05,251 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 14:30:05,257 INFO L256 TraceCheckSpWp]: Trace formula consists of 1542 conjuncts, 28 conjuncts are in the unsatisfiable core [2025-02-06 14:30:05,268 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-06 14:30:05,419 INFO L134 CoverageAnalysis]: Checked inductivity of 55912 backedges. 28204 proven. 3991 refuted. 0 times theorem prover too weak. 23717 trivial. 0 not checked. [2025-02-06 14:30:05,419 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-06 14:30:07,773 INFO L134 CoverageAnalysis]: Checked inductivity of 55912 backedges. 3699 proven. 8098 refuted. 0 times theorem prover too weak. 44115 trivial. 0 not checked. [2025-02-06 14:30:07,773 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [521273484] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-06 14:30:07,773 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-06 14:30:07,773 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [25, 19, 27] total 36 [2025-02-06 14:30:07,773 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1569827701] [2025-02-06 14:30:07,773 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-06 14:30:07,775 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 36 states [2025-02-06 14:30:07,775 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-06 14:30:07,775 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 36 interpolants. [2025-02-06 14:30:07,776 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=217, Invalid=1043, Unknown=0, NotChecked=0, Total=1260 [2025-02-06 14:30:07,776 INFO L87 Difference]: Start difference. First operand 155 states and 197 transitions. Second operand has 36 states, 36 states have (on average 5.777777777777778) internal successors, (208), 35 states have internal predecessors, (208), 30 states have call successors, (37), 5 states have call predecessors, (37), 14 states have return successors, (43), 17 states have call predecessors, (43), 27 states have call successors, (43) [2025-02-06 14:30:08,510 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-06 14:30:08,510 INFO L93 Difference]: Finished difference Result 356 states and 497 transitions. [2025-02-06 14:30:08,510 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 42 states. [2025-02-06 14:30:08,511 INFO L78 Accepts]: Start accepts. Automaton has has 36 states, 36 states have (on average 5.777777777777778) internal successors, (208), 35 states have internal predecessors, (208), 30 states have call successors, (37), 5 states have call predecessors, (37), 14 states have return successors, (43), 17 states have call predecessors, (43), 27 states have call successors, (43) Word has length 1236 [2025-02-06 14:30:08,511 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-06 14:30:08,513 INFO L225 Difference]: With dead ends: 356 [2025-02-06 14:30:08,513 INFO L226 Difference]: Without dead ends: 207 [2025-02-06 14:30:08,516 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 2543 GetRequests, 2458 SyntacticMatches, 17 SemanticMatches, 68 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1512 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=1140, Invalid=3690, Unknown=0, NotChecked=0, Total=4830 [2025-02-06 14:30:08,516 INFO L435 NwaCegarLoop]: 43 mSDtfsCounter, 514 mSDsluCounter, 228 mSDsCounter, 0 mSdLazyCounter, 584 mSolverCounterSat, 211 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 514 SdHoareTripleChecker+Valid, 271 SdHoareTripleChecker+Invalid, 795 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 211 IncrementalHoareTripleChecker+Valid, 584 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2025-02-06 14:30:08,516 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [514 Valid, 271 Invalid, 795 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [211 Valid, 584 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2025-02-06 14:30:08,517 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 207 states. [2025-02-06 14:30:08,528 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 207 to 191. [2025-02-06 14:30:08,528 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 191 states, 155 states have (on average 1.038709677419355) internal successors, (161), 151 states have internal predecessors, (161), 24 states have call successors, (24), 18 states have call predecessors, (24), 11 states have return successors, (57), 21 states have call predecessors, (57), 23 states have call successors, (57) [2025-02-06 14:30:08,529 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 191 states to 191 states and 242 transitions. [2025-02-06 14:30:08,530 INFO L78 Accepts]: Start accepts. Automaton has 191 states and 242 transitions. Word has length 1236 [2025-02-06 14:30:08,530 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-06 14:30:08,530 INFO L471 AbstractCegarLoop]: Abstraction has 191 states and 242 transitions. [2025-02-06 14:30:08,531 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 36 states, 36 states have (on average 5.777777777777778) internal successors, (208), 35 states have internal predecessors, (208), 30 states have call successors, (37), 5 states have call predecessors, (37), 14 states have return successors, (43), 17 states have call predecessors, (43), 27 states have call successors, (43) [2025-02-06 14:30:08,531 INFO L276 IsEmpty]: Start isEmpty. Operand 191 states and 242 transitions. [2025-02-06 14:30:08,535 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 818 [2025-02-06 14:30:08,535 INFO L210 NwaCegarLoop]: Found error trace [2025-02-06 14:30:08,536 INFO L218 NwaCegarLoop]: trace histogram [84, 82, 68, 42, 42, 42, 42, 41, 41, 41, 41, 41, 41, 41, 41, 40, 26, 16, 1, 1, 1, 1, 1] [2025-02-06 14:30:08,545 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Ended with exit code 0 [2025-02-06 14:30:08,739 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable20,18 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-06 14:30:08,740 INFO L396 AbstractCegarLoop]: === Iteration 22 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-02-06 14:30:08,740 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-06 14:30:08,740 INFO L85 PathProgramCache]: Analyzing trace with hash 840937960, now seen corresponding path program 13 times [2025-02-06 14:30:08,740 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-06 14:30:08,740 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2104558051] [2025-02-06 14:30:08,740 INFO L95 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2025-02-06 14:30:08,741 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-06 14:30:08,753 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 817 statements into 1 equivalence classes. [2025-02-06 14:30:08,805 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 817 of 817 statements. [2025-02-06 14:30:08,805 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-06 14:30:08,805 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 14:30:09,756 INFO L134 CoverageAnalysis]: Checked inductivity of 24215 backedges. 2309 proven. 4945 refuted. 0 times theorem prover too weak. 16961 trivial. 0 not checked. [2025-02-06 14:30:09,756 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-06 14:30:09,757 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2104558051] [2025-02-06 14:30:09,757 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2104558051] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-06 14:30:09,757 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [389054567] [2025-02-06 14:30:09,757 INFO L95 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2025-02-06 14:30:09,757 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-06 14:30:09,757 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 14:30:09,759 INFO L229 MonitoredProcess]: Starting monitored process 19 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-02-06 14:30:09,761 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Waiting until timeout for monitored process [2025-02-06 14:30:09,957 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 817 statements into 1 equivalence classes. [2025-02-06 14:30:10,081 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 817 of 817 statements. [2025-02-06 14:30:10,081 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-06 14:30:10,081 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 14:30:10,087 INFO L256 TraceCheckSpWp]: Trace formula consists of 1528 conjuncts, 26 conjuncts are in the unsatisfiable core [2025-02-06 14:30:10,096 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-06 14:30:10,239 INFO L134 CoverageAnalysis]: Checked inductivity of 24215 backedges. 12370 proven. 2667 refuted. 0 times theorem prover too weak. 9178 trivial. 0 not checked. [2025-02-06 14:30:10,239 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-06 14:30:13,304 INFO L134 CoverageAnalysis]: Checked inductivity of 24215 backedges. 2300 proven. 5308 refuted. 0 times theorem prover too weak. 16607 trivial. 0 not checked. [2025-02-06 14:30:13,305 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [389054567] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-06 14:30:13,305 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-06 14:30:13,305 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 17, 27] total 32 [2025-02-06 14:30:13,305 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1187427428] [2025-02-06 14:30:13,305 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-06 14:30:13,306 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 32 states [2025-02-06 14:30:13,306 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-06 14:30:13,306 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 32 interpolants. [2025-02-06 14:30:13,307 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=179, Invalid=813, Unknown=0, NotChecked=0, Total=992 [2025-02-06 14:30:13,307 INFO L87 Difference]: Start difference. First operand 191 states and 242 transitions. Second operand has 32 states, 32 states have (on average 5.71875) internal successors, (183), 32 states have internal predecessors, (183), 26 states have call successors, (31), 2 states have call predecessors, (31), 14 states have return successors, (40), 14 states have call predecessors, (40), 26 states have call successors, (40) [2025-02-06 14:30:13,793 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-06 14:30:13,793 INFO L93 Difference]: Finished difference Result 382 states and 510 transitions. [2025-02-06 14:30:13,794 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2025-02-06 14:30:13,794 INFO L78 Accepts]: Start accepts. Automaton has has 32 states, 32 states have (on average 5.71875) internal successors, (183), 32 states have internal predecessors, (183), 26 states have call successors, (31), 2 states have call predecessors, (31), 14 states have return successors, (40), 14 states have call predecessors, (40), 26 states have call successors, (40) Word has length 817 [2025-02-06 14:30:13,795 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-06 14:30:13,796 INFO L225 Difference]: With dead ends: 382 [2025-02-06 14:30:13,797 INFO L226 Difference]: Without dead ends: 197 [2025-02-06 14:30:13,798 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 1678 GetRequests, 1617 SyntacticMatches, 13 SemanticMatches, 48 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 686 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=632, Invalid=1818, Unknown=0, NotChecked=0, Total=2450 [2025-02-06 14:30:13,800 INFO L435 NwaCegarLoop]: 56 mSDtfsCounter, 188 mSDsluCounter, 231 mSDsCounter, 0 mSdLazyCounter, 664 mSolverCounterSat, 85 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 188 SdHoareTripleChecker+Valid, 287 SdHoareTripleChecker+Invalid, 749 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 85 IncrementalHoareTripleChecker+Valid, 664 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2025-02-06 14:30:13,800 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [188 Valid, 287 Invalid, 749 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [85 Valid, 664 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2025-02-06 14:30:13,800 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 197 states. [2025-02-06 14:30:13,811 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 197 to 149. [2025-02-06 14:30:13,812 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 149 states, 120 states have (on average 1.025) internal successors, (123), 118 states have internal predecessors, (123), 19 states have call successors, (19), 14 states have call predecessors, (19), 9 states have return successors, (45), 16 states have call predecessors, (45), 18 states have call successors, (45) [2025-02-06 14:30:13,813 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 149 states to 149 states and 187 transitions. [2025-02-06 14:30:13,813 INFO L78 Accepts]: Start accepts. Automaton has 149 states and 187 transitions. Word has length 817 [2025-02-06 14:30:13,814 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-06 14:30:13,814 INFO L471 AbstractCegarLoop]: Abstraction has 149 states and 187 transitions. [2025-02-06 14:30:13,814 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 32 states, 32 states have (on average 5.71875) internal successors, (183), 32 states have internal predecessors, (183), 26 states have call successors, (31), 2 states have call predecessors, (31), 14 states have return successors, (40), 14 states have call predecessors, (40), 26 states have call successors, (40) [2025-02-06 14:30:13,814 INFO L276 IsEmpty]: Start isEmpty. Operand 149 states and 187 transitions. [2025-02-06 14:30:13,822 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1067 [2025-02-06 14:30:13,823 INFO L210 NwaCegarLoop]: Found error trace [2025-02-06 14:30:13,823 INFO L218 NwaCegarLoop]: trace histogram [109, 108, 88, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 53, 34, 21, 1, 1, 1, 1, 1] [2025-02-06 14:30:13,833 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Ended with exit code 0 [2025-02-06 14:30:14,026 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable21,19 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-06 14:30:14,027 INFO L396 AbstractCegarLoop]: === Iteration 23 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-02-06 14:30:14,027 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-06 14:30:14,027 INFO L85 PathProgramCache]: Analyzing trace with hash -1653235746, now seen corresponding path program 14 times [2025-02-06 14:30:14,027 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-06 14:30:14,028 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1913835192] [2025-02-06 14:30:14,028 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-02-06 14:30:14,028 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-06 14:30:14,044 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 1066 statements into 2 equivalence classes. [2025-02-06 14:30:14,126 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 1066 of 1066 statements. [2025-02-06 14:30:14,126 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-02-06 14:30:14,126 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 14:30:26,723 INFO L134 CoverageAnalysis]: Checked inductivity of 41466 backedges. 6794 proven. 10267 refuted. 0 times theorem prover too weak. 24405 trivial. 0 not checked. [2025-02-06 14:30:26,723 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-06 14:30:26,723 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1913835192] [2025-02-06 14:30:26,723 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1913835192] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-06 14:30:26,723 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1733762185] [2025-02-06 14:30:26,723 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-02-06 14:30:26,723 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-06 14:30:26,723 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 14:30:26,725 INFO L229 MonitoredProcess]: Starting monitored process 20 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-02-06 14:30:26,726 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Waiting until timeout for monitored process [2025-02-06 14:30:26,955 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 1066 statements into 2 equivalence classes. [2025-02-06 14:30:27,121 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 1066 of 1066 statements. [2025-02-06 14:30:27,121 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-02-06 14:30:27,121 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 14:30:27,128 INFO L256 TraceCheckSpWp]: Trace formula consists of 1989 conjuncts, 217 conjuncts are in the unsatisfiable core [2025-02-06 14:30:27,140 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-06 14:30:27,894 INFO L134 CoverageAnalysis]: Checked inductivity of 41466 backedges. 6686 proven. 7855 refuted. 0 times theorem prover too weak. 26925 trivial. 0 not checked. [2025-02-06 14:30:27,894 INFO L312 TraceCheckSpWp]: Computing backward predicates...