./Ultimate.py --spec ../sv-benchmarks/c/properties/no-overflow.prp --file ../sv-benchmarks/c/termination-numeric/Fibonacci01-2-overflow.c --full-output --architecture 64bit -------------------------------------------------------------------------------- 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/termination-numeric/Fibonacci01-2-overflow.c -s /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/config/svcomp-Overflow-64bit-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 64bit --witnessprinter.graph.data.programhash 694713b32fd9c1719d4a8995f33c66cfa1f4ebdac7358c65fcc55ce37970cfaf --- Real Ultimate output --- This is Ultimate 0.3.0-?-c00e63d-m [2025-02-06 13:29:58,689 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-02-06 13:29:58,760 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/config/svcomp-Overflow-64bit-Automizer_Default.epf [2025-02-06 13:29:58,769 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-02-06 13:29:58,770 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-02-06 13:29:58,795 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-02-06 13:29:58,796 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-02-06 13:29:58,796 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-02-06 13:29:58,796 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-02-06 13:29:58,797 INFO L153 SettingsManager]: * Use memory slicer=true [2025-02-06 13:29:58,797 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2025-02-06 13:29:58,797 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2025-02-06 13:29:58,797 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-02-06 13:29:58,797 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-02-06 13:29:58,797 INFO L153 SettingsManager]: * Use SBE=true [2025-02-06 13:29:58,798 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-02-06 13:29:58,798 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2025-02-06 13:29:58,800 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2025-02-06 13:29:58,802 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-02-06 13:29:58,802 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2025-02-06 13:29:58,802 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2025-02-06 13:29:58,802 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2025-02-06 13:29:58,802 INFO L153 SettingsManager]: * Check absence of signed integer overflows=ASSERTandASSUME [2025-02-06 13:29:58,802 INFO L153 SettingsManager]: * Check unreachability of reach_error function=false [2025-02-06 13:29:58,802 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-02-06 13:29:58,802 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-02-06 13:29:58,802 INFO L153 SettingsManager]: * Use constant arrays=true [2025-02-06 13:29:58,803 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-02-06 13:29:58,803 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-02-06 13:29:58,803 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-02-06 13:29:58,803 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-02-06 13:29:58,803 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-02-06 13:29:58,803 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-02-06 13:29:58,803 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2025-02-06 13:29:58,804 INFO L153 SettingsManager]: * Compute procedure contracts=false [2025-02-06 13:29:58,804 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2025-02-06 13:29:58,804 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2025-02-06 13:29:58,804 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2025-02-06 13:29:58,804 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2025-02-06 13:29:58,804 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2025-02-06 13:29:58,804 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2025-02-06 13:29:58,805 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2025-02-06 13:29:58,805 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 -> 64bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> 694713b32fd9c1719d4a8995f33c66cfa1f4ebdac7358c65fcc55ce37970cfaf [2025-02-06 13:29:59,100 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-02-06 13:29:59,107 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-02-06 13:29:59,111 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-02-06 13:29:59,112 INFO L270 PluginConnector]: Initializing CDTParser... [2025-02-06 13:29:59,112 INFO L274 PluginConnector]: CDTParser initialized [2025-02-06 13:29:59,114 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/termination-numeric/Fibonacci01-2-overflow.c [2025-02-06 13:30:00,518 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/a559b61e6/e54144e5adb746249d86b23106e951dc/FLAGe30950662 [2025-02-06 13:30:00,802 INFO L384 CDTParser]: Found 1 translation units. [2025-02-06 13:30:00,803 INFO L180 CDTParser]: Scanning /storage/repos/ultimate-jdk21/releaseScripts/default/sv-benchmarks/c/termination-numeric/Fibonacci01-2-overflow.c [2025-02-06 13:30:00,811 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/a559b61e6/e54144e5adb746249d86b23106e951dc/FLAGe30950662 [2025-02-06 13:30:00,834 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/a559b61e6/e54144e5adb746249d86b23106e951dc [2025-02-06 13:30:00,837 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-02-06 13:30:00,838 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-02-06 13:30:00,841 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-02-06 13:30:00,841 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-02-06 13:30:00,845 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-02-06 13:30:00,846 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 06.02 01:30:00" (1/1) ... [2025-02-06 13:30:00,846 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@6a48ab1d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.02 01:30:00, skipping insertion in model container [2025-02-06 13:30:00,847 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 06.02 01:30:00" (1/1) ... [2025-02-06 13:30:00,859 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-02-06 13:30:00,992 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-02-06 13:30:01,000 INFO L200 MainTranslator]: Completed pre-run [2025-02-06 13:30:01,010 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-02-06 13:30:01,025 INFO L204 MainTranslator]: Completed translation [2025-02-06 13:30:01,025 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.02 01:30:01 WrapperNode [2025-02-06 13:30:01,026 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-02-06 13:30:01,026 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-02-06 13:30:01,027 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-02-06 13:30:01,027 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-02-06 13:30:01,032 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.02 01:30:01" (1/1) ... [2025-02-06 13:30:01,037 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.02 01:30:01" (1/1) ... [2025-02-06 13:30:01,050 INFO L138 Inliner]: procedures = 13, calls = 11, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 27 [2025-02-06 13:30:01,051 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-02-06 13:30:01,052 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-02-06 13:30:01,052 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-02-06 13:30:01,052 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-02-06 13:30:01,058 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.02 01:30:01" (1/1) ... [2025-02-06 13:30:01,058 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.02 01:30:01" (1/1) ... [2025-02-06 13:30:01,059 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.02 01:30:01" (1/1) ... [2025-02-06 13:30:01,070 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 13:30:01,071 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.02 01:30:01" (1/1) ... [2025-02-06 13:30:01,071 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.02 01:30:01" (1/1) ... [2025-02-06 13:30:01,073 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.02 01:30:01" (1/1) ... [2025-02-06 13:30:01,075 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.02 01:30:01" (1/1) ... [2025-02-06 13:30:01,076 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.02 01:30:01" (1/1) ... [2025-02-06 13:30:01,077 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.02 01:30:01" (1/1) ... [2025-02-06 13:30:01,078 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-02-06 13:30:01,082 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2025-02-06 13:30:01,082 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2025-02-06 13:30:01,082 INFO L274 PluginConnector]: IcfgBuilder initialized [2025-02-06 13:30:01,083 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.02 01:30:01" (1/1) ... [2025-02-06 13:30:01,090 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-02-06 13:30:01,102 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 13:30:01,116 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 13:30:01,125 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 13:30:01,145 INFO L130 BoogieDeclarations]: Found specification of procedure fibonacci [2025-02-06 13:30:01,146 INFO L138 BoogieDeclarations]: Found implementation of procedure fibonacci [2025-02-06 13:30:01,146 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2025-02-06 13:30:01,146 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-02-06 13:30:01,146 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-02-06 13:30:01,146 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2025-02-06 13:30:01,195 INFO L257 CfgBuilder]: Building ICFG [2025-02-06 13:30:01,197 INFO L287 CfgBuilder]: Building CFG for each procedure with an implementation [2025-02-06 13:30:01,286 INFO L1309 $ProcedureCfgBuilder]: dead code at ProgramPoint L22: havoc #t~ret4;havoc #t~ret5; [2025-02-06 13:30:01,341 INFO L? ?]: Removed 15 outVars from TransFormulas that were not future-live. [2025-02-06 13:30:01,341 INFO L308 CfgBuilder]: Performing block encoding [2025-02-06 13:30:01,353 INFO L332 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-02-06 13:30:01,354 INFO L337 CfgBuilder]: Removed 0 assume(true) statements. [2025-02-06 13:30:01,354 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 06.02 01:30:01 BoogieIcfgContainer [2025-02-06 13:30:01,355 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2025-02-06 13:30:01,357 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2025-02-06 13:30:01,357 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2025-02-06 13:30:01,361 INFO L274 PluginConnector]: TraceAbstraction initialized [2025-02-06 13:30:01,361 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 06.02 01:30:00" (1/3) ... [2025-02-06 13:30:01,362 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6e61a433 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 06.02 01:30:01, skipping insertion in model container [2025-02-06 13:30:01,362 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.02 01:30:01" (2/3) ... [2025-02-06 13:30:01,363 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6e61a433 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 06.02 01:30:01, skipping insertion in model container [2025-02-06 13:30:01,363 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 06.02 01:30:01" (3/3) ... [2025-02-06 13:30:01,364 INFO L128 eAbstractionObserver]: Analyzing ICFG Fibonacci01-2-overflow.c [2025-02-06 13:30:01,379 INFO L216 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2025-02-06 13:30:01,380 INFO L151 ceAbstractionStarter]: Applying trace abstraction to ICFG Fibonacci01-2-overflow.c that has 2 procedures, 32 locations, 1 initial locations, 0 loop locations, and 6 error locations. [2025-02-06 13:30:01,435 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2025-02-06 13:30:01,447 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;@7099a77b, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2025-02-06 13:30:01,448 INFO L334 AbstractCegarLoop]: Starting to check reachability of 6 error locations. [2025-02-06 13:30:01,452 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 13:30:01,457 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 9 [2025-02-06 13:30:01,457 INFO L210 NwaCegarLoop]: Found error trace [2025-02-06 13:30:01,458 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2025-02-06 13:30:01,458 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting fibonacciErr5ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-02-06 13:30:01,466 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-06 13:30:01,466 INFO L85 PathProgramCache]: Analyzing trace with hash 154990982, now seen corresponding path program 1 times [2025-02-06 13:30:01,473 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-06 13:30:01,474 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1051279816] [2025-02-06 13:30:01,474 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-06 13:30:01,476 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-06 13:30:01,538 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 8 statements into 1 equivalence classes. [2025-02-06 13:30:01,559 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 8 of 8 statements. [2025-02-06 13:30:01,560 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-06 13:30:01,560 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 13:30:01,635 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 13:30:01,636 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-06 13:30:01,636 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1051279816] [2025-02-06 13:30:01,637 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1051279816] provided 1 perfect and 0 imperfect interpolant sequences [2025-02-06 13:30:01,639 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-02-06 13:30:01,639 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2025-02-06 13:30:01,641 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [845245675] [2025-02-06 13:30:01,642 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-02-06 13:30:01,645 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2025-02-06 13:30:01,645 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-06 13:30:01,660 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2025-02-06 13:30:01,661 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2025-02-06 13:30:01,662 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 13:30:01,701 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-06 13:30:01,701 INFO L93 Difference]: Finished difference Result 37 states and 43 transitions. [2025-02-06 13:30:01,702 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2025-02-06 13:30:01,704 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 13:30:01,704 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-06 13:30:01,709 INFO L225 Difference]: With dead ends: 37 [2025-02-06 13:30:01,710 INFO L226 Difference]: Without dead ends: 25 [2025-02-06 13:30:01,712 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 13:30:01,715 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 13:30:01,715 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 13:30:01,725 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 25 states. [2025-02-06 13:30:01,740 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 25 to 23. [2025-02-06 13:30:01,741 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 13:30:01,747 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 23 states to 23 states and 26 transitions. [2025-02-06 13:30:01,751 INFO L78 Accepts]: Start accepts. Automaton has 23 states and 26 transitions. Word has length 8 [2025-02-06 13:30:01,751 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-06 13:30:01,751 INFO L471 AbstractCegarLoop]: Abstraction has 23 states and 26 transitions. [2025-02-06 13:30:01,751 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 13:30:01,752 INFO L276 IsEmpty]: Start isEmpty. Operand 23 states and 26 transitions. [2025-02-06 13:30:01,752 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 10 [2025-02-06 13:30:01,752 INFO L210 NwaCegarLoop]: Found error trace [2025-02-06 13:30:01,752 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-02-06 13:30:01,753 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2025-02-06 13:30:01,753 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting fibonacciErr4ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-02-06 13:30:01,753 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-06 13:30:01,753 INFO L85 PathProgramCache]: Analyzing trace with hash 509753131, now seen corresponding path program 1 times [2025-02-06 13:30:01,753 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-06 13:30:01,753 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [423381756] [2025-02-06 13:30:01,755 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-06 13:30:01,756 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-06 13:30:01,762 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 9 statements into 1 equivalence classes. [2025-02-06 13:30:01,770 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 9 of 9 statements. [2025-02-06 13:30:01,770 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-06 13:30:01,771 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 13:30:01,833 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 13:30:01,834 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-06 13:30:01,834 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [423381756] [2025-02-06 13:30:01,834 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [423381756] provided 1 perfect and 0 imperfect interpolant sequences [2025-02-06 13:30:01,834 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-02-06 13:30:01,834 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2025-02-06 13:30:01,834 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1360942739] [2025-02-06 13:30:01,834 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-02-06 13:30:01,835 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-02-06 13:30:01,836 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-06 13:30:01,836 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-02-06 13:30:01,836 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-02-06 13:30:01,836 INFO L87 Difference]: Start difference. First operand 23 states and 26 transitions. Second operand has 5 states, 4 states have (on average 2.0) 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 13:30:01,921 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-06 13:30:01,923 INFO L93 Difference]: Finished difference Result 25 states and 29 transitions. [2025-02-06 13:30:01,923 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-02-06 13:30:01,923 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 2.0) 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 13:30:01,924 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-06 13:30:01,924 INFO L225 Difference]: With dead ends: 25 [2025-02-06 13:30:01,924 INFO L226 Difference]: Without dead ends: 23 [2025-02-06 13:30:01,925 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 13:30:01,927 INFO L435 NwaCegarLoop]: 13 mSDtfsCounter, 26 mSDsluCounter, 16 mSDsCounter, 0 mSdLazyCounter, 35 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 26 SdHoareTripleChecker+Valid, 29 SdHoareTripleChecker+Invalid, 42 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 35 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-02-06 13:30:01,927 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [26 Valid, 29 Invalid, 42 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 35 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-02-06 13:30:01,928 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 23 states. [2025-02-06 13:30:01,932 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 23 to 21. [2025-02-06 13:30:01,933 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 13:30:01,934 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 21 states to 21 states and 24 transitions. [2025-02-06 13:30:01,934 INFO L78 Accepts]: Start accepts. Automaton has 21 states and 24 transitions. Word has length 9 [2025-02-06 13:30:01,934 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-06 13:30:01,934 INFO L471 AbstractCegarLoop]: Abstraction has 21 states and 24 transitions. [2025-02-06 13:30:01,935 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 2.0) 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 13:30:01,935 INFO L276 IsEmpty]: Start isEmpty. Operand 21 states and 24 transitions. [2025-02-06 13:30:01,936 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2025-02-06 13:30:01,936 INFO L210 NwaCegarLoop]: Found error trace [2025-02-06 13:30:01,936 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 13:30:01,936 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2025-02-06 13:30:01,936 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-02-06 13:30:01,937 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-06 13:30:01,937 INFO L85 PathProgramCache]: Analyzing trace with hash -984405394, now seen corresponding path program 1 times [2025-02-06 13:30:01,937 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-06 13:30:01,937 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1120422014] [2025-02-06 13:30:01,937 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-06 13:30:01,937 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-06 13:30:01,948 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 24 statements into 1 equivalence classes. [2025-02-06 13:30:01,967 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 24 of 24 statements. [2025-02-06 13:30:01,967 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-06 13:30:01,967 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 13:30:02,142 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 13:30:02,143 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-06 13:30:02,143 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1120422014] [2025-02-06 13:30:02,143 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1120422014] provided 1 perfect and 0 imperfect interpolant sequences [2025-02-06 13:30:02,143 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-02-06 13:30:02,143 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2025-02-06 13:30:02,143 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [565111713] [2025-02-06 13:30:02,143 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-02-06 13:30:02,143 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-02-06 13:30:02,143 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-06 13:30:02,144 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-02-06 13:30:02,144 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2025-02-06 13:30:02,145 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 13:30:02,190 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-06 13:30:02,190 INFO L93 Difference]: Finished difference Result 35 states and 43 transitions. [2025-02-06 13:30:02,190 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-02-06 13:30:02,191 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 13:30:02,191 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-06 13:30:02,191 INFO L225 Difference]: With dead ends: 35 [2025-02-06 13:30:02,192 INFO L226 Difference]: Without dead ends: 33 [2025-02-06 13:30:02,192 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 13:30:02,193 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 13:30:02,193 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 13:30:02,193 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 33 states. [2025-02-06 13:30:02,198 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 33 to 30. [2025-02-06 13:30:02,199 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 13:30:02,200 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 30 states to 30 states and 36 transitions. [2025-02-06 13:30:02,200 INFO L78 Accepts]: Start accepts. Automaton has 30 states and 36 transitions. Word has length 24 [2025-02-06 13:30:02,200 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-06 13:30:02,200 INFO L471 AbstractCegarLoop]: Abstraction has 30 states and 36 transitions. [2025-02-06 13:30:02,200 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 13:30:02,200 INFO L276 IsEmpty]: Start isEmpty. Operand 30 states and 36 transitions. [2025-02-06 13:30:02,201 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2025-02-06 13:30:02,201 INFO L210 NwaCegarLoop]: Found error trace [2025-02-06 13:30:02,201 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 13:30:02,201 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2025-02-06 13:30:02,202 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-02-06 13:30:02,202 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-06 13:30:02,202 INFO L85 PathProgramCache]: Analyzing trace with hash -119709208, now seen corresponding path program 1 times [2025-02-06 13:30:02,202 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-06 13:30:02,202 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [522590954] [2025-02-06 13:30:02,202 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-06 13:30:02,202 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-06 13:30:02,212 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 31 statements into 1 equivalence classes. [2025-02-06 13:30:02,227 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 31 of 31 statements. [2025-02-06 13:30:02,230 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-06 13:30:02,230 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 13:30:02,361 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 13:30:02,362 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-06 13:30:02,362 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [522590954] [2025-02-06 13:30:02,362 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [522590954] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-06 13:30:02,362 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2010379070] [2025-02-06 13:30:02,362 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-06 13:30:02,362 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-06 13:30:02,362 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 13:30:02,366 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 13:30:02,368 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 13:30:02,405 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 31 statements into 1 equivalence classes. [2025-02-06 13:30:02,423 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 31 of 31 statements. [2025-02-06 13:30:02,423 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-06 13:30:02,423 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 13:30:02,429 INFO L256 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 6 conjuncts are in the unsatisfiable core [2025-02-06 13:30:02,433 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-06 13:30:02,545 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 13:30:02,545 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-06 13:30:02,704 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 13:30:02,704 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2010379070] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-06 13:30:02,704 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-06 13:30:02,704 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 7, 7] total 15 [2025-02-06 13:30:02,704 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1447955361] [2025-02-06 13:30:02,704 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-06 13:30:02,705 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2025-02-06 13:30:02,705 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-06 13:30:02,706 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2025-02-06 13:30:02,706 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=35, Invalid=175, Unknown=0, NotChecked=0, Total=210 [2025-02-06 13:30:02,706 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 13:30:02,989 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-06 13:30:02,989 INFO L93 Difference]: Finished difference Result 91 states and 129 transitions. [2025-02-06 13:30:02,989 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2025-02-06 13:30:02,990 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 13:30:02,990 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-06 13:30:02,991 INFO L225 Difference]: With dead ends: 91 [2025-02-06 13:30:02,991 INFO L226 Difference]: Without dead ends: 65 [2025-02-06 13:30:02,992 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 74 GetRequests, 52 SyntacticMatches, 1 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 42 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=111, Invalid=395, Unknown=0, NotChecked=0, Total=506 [2025-02-06 13:30:02,993 INFO L435 NwaCegarLoop]: 13 mSDtfsCounter, 134 mSDsluCounter, 79 mSDsCounter, 0 mSdLazyCounter, 168 mSolverCounterSat, 60 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 134 SdHoareTripleChecker+Valid, 92 SdHoareTripleChecker+Invalid, 228 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 60 IncrementalHoareTripleChecker+Valid, 168 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-02-06 13:30:02,993 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [134 Valid, 92 Invalid, 228 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [60 Valid, 168 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-02-06 13:30:02,993 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 65 states. [2025-02-06 13:30:03,004 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 65 to 53. [2025-02-06 13:30:03,007 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 13:30:03,010 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 53 states to 53 states and 68 transitions. [2025-02-06 13:30:03,010 INFO L78 Accepts]: Start accepts. Automaton has 53 states and 68 transitions. Word has length 31 [2025-02-06 13:30:03,011 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-06 13:30:03,011 INFO L471 AbstractCegarLoop]: Abstraction has 53 states and 68 transitions. [2025-02-06 13:30:03,012 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 13:30:03,013 INFO L276 IsEmpty]: Start isEmpty. Operand 53 states and 68 transitions. [2025-02-06 13:30:03,013 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2025-02-06 13:30:03,013 INFO L210 NwaCegarLoop]: Found error trace [2025-02-06 13:30:03,014 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 13:30:03,022 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 13:30:03,214 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 13:30:03,214 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-02-06 13:30:03,215 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-06 13:30:03,215 INFO L85 PathProgramCache]: Analyzing trace with hash 1220480843, now seen corresponding path program 2 times [2025-02-06 13:30:03,215 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-06 13:30:03,215 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1174502703] [2025-02-06 13:30:03,215 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-02-06 13:30:03,215 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-06 13:30:03,224 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 25 statements into 2 equivalence classes. [2025-02-06 13:30:03,233 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 25 of 25 statements. [2025-02-06 13:30:03,236 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-02-06 13:30:03,236 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 13:30:03,332 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 13:30:03,332 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-06 13:30:03,333 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1174502703] [2025-02-06 13:30:03,333 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1174502703] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-06 13:30:03,333 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [406956806] [2025-02-06 13:30:03,333 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-02-06 13:30:03,333 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-06 13:30:03,333 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 13:30:03,336 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 13:30:03,338 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 13:30:03,365 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 25 statements into 2 equivalence classes. [2025-02-06 13:30:03,377 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 25 of 25 statements. [2025-02-06 13:30:03,378 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-02-06 13:30:03,378 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 13:30:03,379 INFO L256 TraceCheckSpWp]: Trace formula consists of 67 conjuncts, 4 conjuncts are in the unsatisfiable core [2025-02-06 13:30:03,380 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-06 13:30:03,440 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 13:30:03,441 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-02-06 13:30:03,441 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [406956806] provided 1 perfect and 0 imperfect interpolant sequences [2025-02-06 13:30:03,441 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-02-06 13:30:03,441 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [5] total 7 [2025-02-06 13:30:03,442 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1960583188] [2025-02-06 13:30:03,442 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-02-06 13:30:03,442 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-02-06 13:30:03,442 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-06 13:30:03,443 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-02-06 13:30:03,443 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=38, Unknown=0, NotChecked=0, Total=56 [2025-02-06 13:30:03,443 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 13:30:03,476 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-06 13:30:03,476 INFO L93 Difference]: Finished difference Result 60 states and 76 transitions. [2025-02-06 13:30:03,476 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-02-06 13:30:03,477 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 13:30:03,477 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-06 13:30:03,478 INFO L225 Difference]: With dead ends: 60 [2025-02-06 13:30:03,478 INFO L226 Difference]: Without dead ends: 59 [2025-02-06 13:30:03,478 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 13:30:03,479 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 13:30:03,479 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 13:30:03,480 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 59 states. [2025-02-06 13:30:03,488 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 59 to 55. [2025-02-06 13:30:03,489 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 13:30:03,490 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 55 states to 55 states and 70 transitions. [2025-02-06 13:30:03,490 INFO L78 Accepts]: Start accepts. Automaton has 55 states and 70 transitions. Word has length 25 [2025-02-06 13:30:03,490 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-06 13:30:03,490 INFO L471 AbstractCegarLoop]: Abstraction has 55 states and 70 transitions. [2025-02-06 13:30:03,490 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 13:30:03,491 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 70 transitions. [2025-02-06 13:30:03,491 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2025-02-06 13:30:03,491 INFO L210 NwaCegarLoop]: Found error trace [2025-02-06 13:30:03,492 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 13:30:03,499 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2025-02-06 13:30:03,696 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 13:30:03,696 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-02-06 13:30:03,697 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-06 13:30:03,697 INFO L85 PathProgramCache]: Analyzing trace with hash 929820207, now seen corresponding path program 1 times [2025-02-06 13:30:03,697 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-06 13:30:03,697 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [764439950] [2025-02-06 13:30:03,697 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-06 13:30:03,697 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-06 13:30:03,702 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 32 statements into 1 equivalence classes. [2025-02-06 13:30:03,706 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 32 of 32 statements. [2025-02-06 13:30:03,706 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-06 13:30:03,706 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 13:30:03,775 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 13:30:03,775 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-06 13:30:03,775 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [764439950] [2025-02-06 13:30:03,776 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [764439950] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-06 13:30:03,776 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [976869287] [2025-02-06 13:30:03,776 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-06 13:30:03,776 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-06 13:30:03,776 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 13:30:03,778 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 13:30:03,780 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 13:30:03,806 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 32 statements into 1 equivalence classes. [2025-02-06 13:30:03,817 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 32 of 32 statements. [2025-02-06 13:30:03,818 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-06 13:30:03,818 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 13:30:03,818 INFO L256 TraceCheckSpWp]: Trace formula consists of 78 conjuncts, 5 conjuncts are in the unsatisfiable core [2025-02-06 13:30:03,819 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-06 13:30:03,882 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 13:30:03,883 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-02-06 13:30:03,883 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [976869287] provided 1 perfect and 0 imperfect interpolant sequences [2025-02-06 13:30:03,883 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-02-06 13:30:03,883 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [5] total 9 [2025-02-06 13:30:03,883 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1014122407] [2025-02-06 13:30:03,883 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-02-06 13:30:03,883 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2025-02-06 13:30:03,883 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-06 13:30:03,884 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2025-02-06 13:30:03,884 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=64, Unknown=0, NotChecked=0, Total=90 [2025-02-06 13:30:03,884 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 13:30:03,922 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-06 13:30:03,923 INFO L93 Difference]: Finished difference Result 82 states and 117 transitions. [2025-02-06 13:30:03,923 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2025-02-06 13:30:03,924 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 13:30:03,924 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-06 13:30:03,925 INFO L225 Difference]: With dead ends: 82 [2025-02-06 13:30:03,925 INFO L226 Difference]: Without dead ends: 81 [2025-02-06 13:30:03,925 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 13:30:03,926 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 13:30:03,926 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 13:30:03,929 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 81 states. [2025-02-06 13:30:03,943 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 81 to 64. [2025-02-06 13:30:03,944 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 13:30:03,946 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 64 states to 64 states and 87 transitions. [2025-02-06 13:30:03,946 INFO L78 Accepts]: Start accepts. Automaton has 64 states and 87 transitions. Word has length 32 [2025-02-06 13:30:03,946 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-06 13:30:03,947 INFO L471 AbstractCegarLoop]: Abstraction has 64 states and 87 transitions. [2025-02-06 13:30:03,947 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 13:30:03,947 INFO L276 IsEmpty]: Start isEmpty. Operand 64 states and 87 transitions. [2025-02-06 13:30:03,948 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 47 [2025-02-06 13:30:03,948 INFO L210 NwaCegarLoop]: Found error trace [2025-02-06 13:30:03,948 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 13:30:03,955 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 13:30:04,148 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 13:30:04,149 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-02-06 13:30:04,149 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-06 13:30:04,149 INFO L85 PathProgramCache]: Analyzing trace with hash -1465088786, now seen corresponding path program 1 times [2025-02-06 13:30:04,149 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-06 13:30:04,149 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1118448512] [2025-02-06 13:30:04,149 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-06 13:30:04,149 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-06 13:30:04,160 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 46 statements into 1 equivalence classes. [2025-02-06 13:30:04,168 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 46 of 46 statements. [2025-02-06 13:30:04,168 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-06 13:30:04,168 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 13:30:04,285 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 13:30:04,285 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-06 13:30:04,286 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1118448512] [2025-02-06 13:30:04,286 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1118448512] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-06 13:30:04,286 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [970838938] [2025-02-06 13:30:04,286 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-06 13:30:04,286 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-06 13:30:04,286 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 13:30:04,288 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 13:30:04,289 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 13:30:04,321 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 46 statements into 1 equivalence classes. [2025-02-06 13:30:04,334 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 46 of 46 statements. [2025-02-06 13:30:04,335 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-06 13:30:04,335 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 13:30:04,336 INFO L256 TraceCheckSpWp]: Trace formula consists of 105 conjuncts, 9 conjuncts are in the unsatisfiable core [2025-02-06 13:30:04,337 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-06 13:30:04,444 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 13:30:04,444 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-06 13:30:04,693 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 13:30:04,693 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [970838938] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-06 13:30:04,693 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-06 13:30:04,693 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 6, 7] total 15 [2025-02-06 13:30:04,693 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [959088809] [2025-02-06 13:30:04,693 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-06 13:30:04,694 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2025-02-06 13:30:04,694 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-06 13:30:04,694 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2025-02-06 13:30:04,694 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=62, Invalid=178, Unknown=0, NotChecked=0, Total=240 [2025-02-06 13:30:04,695 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 13:30:04,908 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-06 13:30:04,908 INFO L93 Difference]: Finished difference Result 141 states and 217 transitions. [2025-02-06 13:30:04,908 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2025-02-06 13:30:04,909 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 13:30:04,909 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-06 13:30:04,912 INFO L225 Difference]: With dead ends: 141 [2025-02-06 13:30:04,913 INFO L226 Difference]: Without dead ends: 139 [2025-02-06 13:30:04,913 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 13:30:04,914 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 13:30:04,914 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 13:30:04,915 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 139 states. [2025-02-06 13:30:04,940 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 139 to 98. [2025-02-06 13:30:04,940 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 13:30:04,942 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 98 states to 98 states and 159 transitions. [2025-02-06 13:30:04,942 INFO L78 Accepts]: Start accepts. Automaton has 98 states and 159 transitions. Word has length 46 [2025-02-06 13:30:04,942 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-06 13:30:04,942 INFO L471 AbstractCegarLoop]: Abstraction has 98 states and 159 transitions. [2025-02-06 13:30:04,943 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 13:30:04,943 INFO L276 IsEmpty]: Start isEmpty. Operand 98 states and 159 transitions. [2025-02-06 13:30:04,946 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 123 [2025-02-06 13:30:04,946 INFO L210 NwaCegarLoop]: Found error trace [2025-02-06 13:30:04,946 INFO L218 NwaCegarLoop]: trace histogram [14, 11, 9, 7, 7, 7, 7, 6, 6, 6, 6, 6, 5, 5, 5, 4, 4, 2, 1, 1, 1, 1, 1] [2025-02-06 13:30:04,954 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2025-02-06 13:30:05,146 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 13:30:05,147 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-02-06 13:30:05,147 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-06 13:30:05,147 INFO L85 PathProgramCache]: Analyzing trace with hash -187782971, now seen corresponding path program 1 times [2025-02-06 13:30:05,147 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-06 13:30:05,147 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1911505891] [2025-02-06 13:30:05,147 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-06 13:30:05,147 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-06 13:30:05,162 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 122 statements into 1 equivalence classes. [2025-02-06 13:30:05,175 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 122 of 122 statements. [2025-02-06 13:30:05,176 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-06 13:30:05,176 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 13:30:05,365 INFO L134 CoverageAnalysis]: Checked inductivity of 477 backedges. 55 proven. 149 refuted. 0 times theorem prover too weak. 273 trivial. 0 not checked. [2025-02-06 13:30:05,366 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-06 13:30:05,366 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1911505891] [2025-02-06 13:30:05,366 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1911505891] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-06 13:30:05,366 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [887146011] [2025-02-06 13:30:05,366 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-06 13:30:05,366 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-06 13:30:05,366 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 13:30:05,368 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 13:30:05,371 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 13:30:05,403 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 122 statements into 1 equivalence classes. [2025-02-06 13:30:05,438 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 122 of 122 statements. [2025-02-06 13:30:05,438 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-06 13:30:05,438 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 13:30:05,439 INFO L256 TraceCheckSpWp]: Trace formula consists of 245 conjuncts, 10 conjuncts are in the unsatisfiable core [2025-02-06 13:30:05,444 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-06 13:30:05,529 INFO L134 CoverageAnalysis]: Checked inductivity of 477 backedges. 295 proven. 67 refuted. 0 times theorem prover too weak. 115 trivial. 0 not checked. [2025-02-06 13:30:05,529 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-06 13:30:05,871 INFO L134 CoverageAnalysis]: Checked inductivity of 477 backedges. 69 proven. 194 refuted. 0 times theorem prover too weak. 214 trivial. 0 not checked. [2025-02-06 13:30:05,871 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [887146011] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-06 13:30:05,871 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-06 13:30:05,871 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 9, 10] total 13 [2025-02-06 13:30:05,871 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1941287486] [2025-02-06 13:30:05,872 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-06 13:30:05,872 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2025-02-06 13:30:05,872 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-06 13:30:05,875 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2025-02-06 13:30:05,875 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=34, Invalid=122, Unknown=0, NotChecked=0, Total=156 [2025-02-06 13:30:05,876 INFO L87 Difference]: Start difference. First operand 98 states and 159 transitions. Second operand has 13 states, 13 states have (on average 5.923076923076923) internal successors, (77), 13 states have internal predecessors, (77), 8 states have call successors, (14), 3 states have call predecessors, (14), 5 states have return successors, (13), 5 states have call predecessors, (13), 7 states have call successors, (13) [2025-02-06 13:30:06,031 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-06 13:30:06,032 INFO L93 Difference]: Finished difference Result 224 states and 401 transitions. [2025-02-06 13:30:06,032 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2025-02-06 13:30:06,033 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 5.923076923076923) internal successors, (77), 13 states have internal predecessors, (77), 8 states have call successors, (14), 3 states have call predecessors, (14), 5 states have return successors, (13), 5 states have call predecessors, (13), 7 states have call successors, (13) Word has length 122 [2025-02-06 13:30:06,033 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-06 13:30:06,038 INFO L225 Difference]: With dead ends: 224 [2025-02-06 13:30:06,038 INFO L226 Difference]: Without dead ends: 130 [2025-02-06 13:30:06,041 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 262 GetRequests, 238 SyntacticMatches, 6 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 49 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=113, Invalid=267, Unknown=0, NotChecked=0, Total=380 [2025-02-06 13:30:06,045 INFO L435 NwaCegarLoop]: 16 mSDtfsCounter, 108 mSDsluCounter, 56 mSDsCounter, 0 mSdLazyCounter, 101 mSolverCounterSat, 40 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 108 SdHoareTripleChecker+Valid, 72 SdHoareTripleChecker+Invalid, 141 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 40 IncrementalHoareTripleChecker+Valid, 101 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-02-06 13:30:06,045 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [108 Valid, 72 Invalid, 141 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [40 Valid, 101 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-02-06 13:30:06,046 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 130 states. [2025-02-06 13:30:06,069 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 130 to 110. [2025-02-06 13:30:06,071 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 110 states, 86 states have (on average 1.0813953488372092) internal successors, (93), 84 states have internal predecessors, (93), 12 states have call successors, (12), 3 states have call predecessors, (12), 10 states have return successors, (75), 22 states have call predecessors, (75), 11 states have call successors, (75) [2025-02-06 13:30:06,077 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 110 states to 110 states and 180 transitions. [2025-02-06 13:30:06,077 INFO L78 Accepts]: Start accepts. Automaton has 110 states and 180 transitions. Word has length 122 [2025-02-06 13:30:06,078 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-06 13:30:06,078 INFO L471 AbstractCegarLoop]: Abstraction has 110 states and 180 transitions. [2025-02-06 13:30:06,078 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 5.923076923076923) internal successors, (77), 13 states have internal predecessors, (77), 8 states have call successors, (14), 3 states have call predecessors, (14), 5 states have return successors, (13), 5 states have call predecessors, (13), 7 states have call successors, (13) [2025-02-06 13:30:06,078 INFO L276 IsEmpty]: Start isEmpty. Operand 110 states and 180 transitions. [2025-02-06 13:30:06,080 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 109 [2025-02-06 13:30:06,084 INFO L210 NwaCegarLoop]: Found error trace [2025-02-06 13:30:06,084 INFO L218 NwaCegarLoop]: trace histogram [12, 10, 8, 6, 6, 6, 6, 5, 5, 5, 5, 5, 5, 5, 4, 4, 4, 2, 1, 1, 1, 1, 1] [2025-02-06 13:30:06,092 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 13:30:06,284 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 13:30:06,285 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-02-06 13:30:06,285 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-06 13:30:06,285 INFO L85 PathProgramCache]: Analyzing trace with hash 1316310439, now seen corresponding path program 2 times [2025-02-06 13:30:06,285 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-06 13:30:06,285 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1643980422] [2025-02-06 13:30:06,285 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-02-06 13:30:06,285 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-06 13:30:06,293 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 108 statements into 2 equivalence classes. [2025-02-06 13:30:06,305 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 108 of 108 statements. [2025-02-06 13:30:06,306 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-02-06 13:30:06,306 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 13:30:06,404 INFO L134 CoverageAnalysis]: Checked inductivity of 361 backedges. 30 proven. 89 refuted. 0 times theorem prover too weak. 242 trivial. 0 not checked. [2025-02-06 13:30:06,404 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-06 13:30:06,404 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1643980422] [2025-02-06 13:30:06,404 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1643980422] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-06 13:30:06,405 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [880820717] [2025-02-06 13:30:06,405 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-02-06 13:30:06,405 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-06 13:30:06,405 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 13:30:06,407 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 13:30:06,409 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 13:30:06,438 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 108 statements into 2 equivalence classes. [2025-02-06 13:30:06,469 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 108 of 108 statements. [2025-02-06 13:30:06,469 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-02-06 13:30:06,469 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 13:30:06,471 INFO L256 TraceCheckSpWp]: Trace formula consists of 219 conjuncts, 12 conjuncts are in the unsatisfiable core [2025-02-06 13:30:06,473 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-06 13:30:06,586 INFO L134 CoverageAnalysis]: Checked inductivity of 361 backedges. 4 proven. 90 refuted. 0 times theorem prover too weak. 267 trivial. 0 not checked. [2025-02-06 13:30:06,586 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-06 13:30:06,989 INFO L134 CoverageAnalysis]: Checked inductivity of 361 backedges. 4 proven. 90 refuted. 0 times theorem prover too weak. 267 trivial. 0 not checked. [2025-02-06 13:30:06,989 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [880820717] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-06 13:30:06,989 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-06 13:30:06,989 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 5, 5] total 12 [2025-02-06 13:30:06,989 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [528498373] [2025-02-06 13:30:06,989 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-06 13:30:06,990 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2025-02-06 13:30:06,990 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-06 13:30:06,990 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2025-02-06 13:30:06,992 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=29, Invalid=103, Unknown=0, NotChecked=0, Total=132 [2025-02-06 13:30:06,992 INFO L87 Difference]: Start difference. First operand 110 states and 180 transitions. Second operand has 12 states, 12 states have (on average 3.9166666666666665) internal successors, (47), 12 states have internal predecessors, (47), 4 states have call successors, (6), 1 states have call predecessors, (6), 4 states have return successors, (9), 5 states have call predecessors, (9), 4 states have call successors, (9) [2025-02-06 13:30:07,124 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-06 13:30:07,125 INFO L93 Difference]: Finished difference Result 173 states and 293 transitions. [2025-02-06 13:30:07,125 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2025-02-06 13:30:07,125 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 3.9166666666666665) internal successors, (47), 12 states have internal predecessors, (47), 4 states have call successors, (6), 1 states have call predecessors, (6), 4 states have return successors, (9), 5 states have call predecessors, (9), 4 states have call successors, (9) Word has length 108 [2025-02-06 13:30:07,125 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-06 13:30:07,127 INFO L225 Difference]: With dead ends: 173 [2025-02-06 13:30:07,128 INFO L226 Difference]: Without dead ends: 67 [2025-02-06 13:30:07,130 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 228 GetRequests, 204 SyntacticMatches, 8 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 48 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=72, Invalid=234, Unknown=0, NotChecked=0, Total=306 [2025-02-06 13:30:07,130 INFO L435 NwaCegarLoop]: 10 mSDtfsCounter, 28 mSDsluCounter, 41 mSDsCounter, 0 mSdLazyCounter, 102 mSolverCounterSat, 10 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 28 SdHoareTripleChecker+Valid, 51 SdHoareTripleChecker+Invalid, 112 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 102 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-02-06 13:30:07,131 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [28 Valid, 51 Invalid, 112 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 102 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-02-06 13:30:07,132 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 67 states. [2025-02-06 13:30:07,146 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 67 to 63. [2025-02-06 13:30:07,147 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 63 states, 49 states have (on average 1.0816326530612246) internal successors, (53), 49 states have internal predecessors, (53), 7 states have call successors, (7), 3 states have call predecessors, (7), 6 states have return successors, (26), 10 states have call predecessors, (26), 6 states have call successors, (26) [2025-02-06 13:30:07,148 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 63 states to 63 states and 86 transitions. [2025-02-06 13:30:07,151 INFO L78 Accepts]: Start accepts. Automaton has 63 states and 86 transitions. Word has length 108 [2025-02-06 13:30:07,151 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-06 13:30:07,151 INFO L471 AbstractCegarLoop]: Abstraction has 63 states and 86 transitions. [2025-02-06 13:30:07,151 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 3.9166666666666665) internal successors, (47), 12 states have internal predecessors, (47), 4 states have call successors, (6), 1 states have call predecessors, (6), 4 states have return successors, (9), 5 states have call predecessors, (9), 4 states have call successors, (9) [2025-02-06 13:30:07,151 INFO L276 IsEmpty]: Start isEmpty. Operand 63 states and 86 transitions. [2025-02-06 13:30:07,153 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 125 [2025-02-06 13:30:07,153 INFO L210 NwaCegarLoop]: Found error trace [2025-02-06 13:30:07,153 INFO L218 NwaCegarLoop]: trace histogram [13, 12, 10, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 5, 4, 3, 1, 1, 1, 1, 1] [2025-02-06 13:30:07,162 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2025-02-06 13:30:07,354 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 13:30:07,354 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-02-06 13:30:07,354 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-06 13:30:07,354 INFO L85 PathProgramCache]: Analyzing trace with hash 1677445974, now seen corresponding path program 2 times [2025-02-06 13:30:07,355 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-06 13:30:07,355 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [309303934] [2025-02-06 13:30:07,355 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-02-06 13:30:07,355 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-06 13:30:07,361 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 124 statements into 2 equivalence classes. [2025-02-06 13:30:07,381 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 124 of 124 statements. [2025-02-06 13:30:07,381 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-02-06 13:30:07,381 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 13:30:07,539 INFO L134 CoverageAnalysis]: Checked inductivity of 483 backedges. 53 proven. 135 refuted. 0 times theorem prover too weak. 295 trivial. 0 not checked. [2025-02-06 13:30:07,539 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-06 13:30:07,539 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [309303934] [2025-02-06 13:30:07,539 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [309303934] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-06 13:30:07,539 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [287737614] [2025-02-06 13:30:07,539 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-02-06 13:30:07,539 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-06 13:30:07,539 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 13:30:07,541 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 13:30:07,543 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 13:30:07,575 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 124 statements into 2 equivalence classes. [2025-02-06 13:30:07,601 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 124 of 124 statements. [2025-02-06 13:30:07,601 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-02-06 13:30:07,601 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 13:30:07,602 INFO L256 TraceCheckSpWp]: Trace formula consists of 249 conjuncts, 8 conjuncts are in the unsatisfiable core [2025-02-06 13:30:07,607 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-06 13:30:07,660 INFO L134 CoverageAnalysis]: Checked inductivity of 483 backedges. 269 proven. 15 refuted. 0 times theorem prover too weak. 199 trivial. 0 not checked. [2025-02-06 13:30:07,661 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-06 13:30:07,984 INFO L134 CoverageAnalysis]: Checked inductivity of 483 backedges. 54 proven. 168 refuted. 0 times theorem prover too weak. 261 trivial. 0 not checked. [2025-02-06 13:30:07,984 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [287737614] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-06 13:30:07,984 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-06 13:30:07,985 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 8, 9] total 14 [2025-02-06 13:30:07,986 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [745972382] [2025-02-06 13:30:07,986 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-06 13:30:07,987 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2025-02-06 13:30:07,987 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-06 13:30:07,988 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2025-02-06 13:30:07,988 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=47, Invalid=135, Unknown=0, NotChecked=0, Total=182 [2025-02-06 13:30:07,988 INFO L87 Difference]: Start difference. First operand 63 states and 86 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 13:30:08,087 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-06 13:30:08,088 INFO L93 Difference]: Finished difference Result 115 states and 163 transitions. [2025-02-06 13:30:08,088 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2025-02-06 13:30:08,088 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 124 [2025-02-06 13:30:08,088 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-06 13:30:08,089 INFO L225 Difference]: With dead ends: 115 [2025-02-06 13:30:08,089 INFO L226 Difference]: Without dead ends: 56 [2025-02-06 13:30:08,090 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 260 GetRequests, 240 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 13:30:08,090 INFO L435 NwaCegarLoop]: 21 mSDtfsCounter, 36 mSDsluCounter, 35 mSDsCounter, 0 mSdLazyCounter, 73 mSolverCounterSat, 16 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 36 SdHoareTripleChecker+Valid, 56 SdHoareTripleChecker+Invalid, 89 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 16 IncrementalHoareTripleChecker+Valid, 73 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-02-06 13:30:08,092 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [36 Valid, 56 Invalid, 89 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [16 Valid, 73 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-02-06 13:30:08,093 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 56 states. [2025-02-06 13:30:08,100 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 56 to 56. [2025-02-06 13:30:08,100 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 56 states, 44 states have (on average 1.0681818181818181) internal successors, (47), 43 states have internal predecessors, (47), 6 states have call successors, (6), 4 states have call predecessors, (6), 5 states have return successors, (14), 8 states have call predecessors, (14), 5 states have call successors, (14) [2025-02-06 13:30:08,101 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 56 states to 56 states and 67 transitions. [2025-02-06 13:30:08,101 INFO L78 Accepts]: Start accepts. Automaton has 56 states and 67 transitions. Word has length 124 [2025-02-06 13:30:08,101 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-06 13:30:08,101 INFO L471 AbstractCegarLoop]: Abstraction has 56 states and 67 transitions. [2025-02-06 13:30:08,101 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 13:30:08,101 INFO L276 IsEmpty]: Start isEmpty. Operand 56 states and 67 transitions. [2025-02-06 13:30:08,104 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 180 [2025-02-06 13:30:08,104 INFO L210 NwaCegarLoop]: Found error trace [2025-02-06 13:30:08,105 INFO L218 NwaCegarLoop]: trace histogram [19, 17, 16, 9, 9, 9, 9, 9, 9, 9, 9, 9, 8, 8, 8, 7, 7, 3, 1, 1, 1, 1, 1] [2025-02-06 13:30:08,114 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 13:30:08,306 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 13:30:08,306 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-02-06 13:30:08,307 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-06 13:30:08,307 INFO L85 PathProgramCache]: Analyzing trace with hash 44298057, now seen corresponding path program 3 times [2025-02-06 13:30:08,307 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-06 13:30:08,307 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [708272398] [2025-02-06 13:30:08,307 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-02-06 13:30:08,308 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-06 13:30:08,316 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 179 statements into 17 equivalence classes. [2025-02-06 13:30:08,327 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) and asserted 71 of 179 statements. [2025-02-06 13:30:08,327 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2025-02-06 13:30:08,327 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 13:30:08,426 INFO L134 CoverageAnalysis]: Checked inductivity of 1070 backedges. 325 proven. 18 refuted. 0 times theorem prover too weak. 727 trivial. 0 not checked. [2025-02-06 13:30:08,427 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-06 13:30:08,427 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [708272398] [2025-02-06 13:30:08,427 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [708272398] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-06 13:30:08,427 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1540512326] [2025-02-06 13:30:08,427 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-02-06 13:30:08,427 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-06 13:30:08,427 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 13:30:08,429 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 13:30:08,431 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 13:30:08,471 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 179 statements into 17 equivalence classes. [2025-02-06 13:30:08,489 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) and asserted 71 of 179 statements. [2025-02-06 13:30:08,489 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2025-02-06 13:30:08,489 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 13:30:08,491 INFO L256 TraceCheckSpWp]: Trace formula consists of 151 conjuncts, 8 conjuncts are in the unsatisfiable core [2025-02-06 13:30:08,493 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-06 13:30:08,551 INFO L134 CoverageAnalysis]: Checked inductivity of 1070 backedges. 322 proven. 21 refuted. 0 times theorem prover too weak. 727 trivial. 0 not checked. [2025-02-06 13:30:08,552 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-06 13:30:08,887 INFO L134 CoverageAnalysis]: Checked inductivity of 1070 backedges. 322 proven. 22 refuted. 0 times theorem prover too weak. 726 trivial. 0 not checked. [2025-02-06 13:30:08,887 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1540512326] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-06 13:30:08,887 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-06 13:30:08,888 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 9] total 12 [2025-02-06 13:30:08,888 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1668899185] [2025-02-06 13:30:08,889 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-06 13:30:08,889 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2025-02-06 13:30:08,889 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-06 13:30:08,890 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2025-02-06 13:30:08,890 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=35, Invalid=97, Unknown=0, NotChecked=0, Total=132 [2025-02-06 13:30:08,890 INFO L87 Difference]: Start difference. First operand 56 states and 67 transitions. Second operand has 12 states, 12 states have (on average 5.0) internal successors, (60), 12 states have internal predecessors, (60), 4 states have call successors, (8), 1 states have call predecessors, (8), 5 states have return successors, (9), 6 states have call predecessors, (9), 4 states have call successors, (9) [2025-02-06 13:30:08,993 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-06 13:30:08,994 INFO L93 Difference]: Finished difference Result 108 states and 132 transitions. [2025-02-06 13:30:08,994 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2025-02-06 13:30:08,994 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 5.0) internal successors, (60), 12 states have internal predecessors, (60), 4 states have call successors, (8), 1 states have call predecessors, (8), 5 states have return successors, (9), 6 states have call predecessors, (9), 4 states have call successors, (9) Word has length 179 [2025-02-06 13:30:08,995 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-06 13:30:08,995 INFO L225 Difference]: With dead ends: 108 [2025-02-06 13:30:08,995 INFO L226 Difference]: Without dead ends: 58 [2025-02-06 13:30:08,996 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 370 GetRequests, 352 SyntacticMatches, 4 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 30 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=74, Invalid=166, Unknown=0, NotChecked=0, Total=240 [2025-02-06 13:30:08,996 INFO L435 NwaCegarLoop]: 25 mSDtfsCounter, 36 mSDsluCounter, 61 mSDsCounter, 0 mSdLazyCounter, 101 mSolverCounterSat, 17 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 36 SdHoareTripleChecker+Valid, 86 SdHoareTripleChecker+Invalid, 118 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 17 IncrementalHoareTripleChecker+Valid, 101 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-02-06 13:30:08,998 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [36 Valid, 86 Invalid, 118 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [17 Valid, 101 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-02-06 13:30:08,999 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 58 states. [2025-02-06 13:30:09,007 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 58 to 56. [2025-02-06 13:30:09,008 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 56 states, 44 states have (on average 1.0681818181818181) internal successors, (47), 43 states have internal predecessors, (47), 6 states have call successors, (6), 4 states have call predecessors, (6), 5 states have return successors, (12), 8 states have call predecessors, (12), 5 states have call successors, (12) [2025-02-06 13:30:09,009 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 56 states to 56 states and 65 transitions. [2025-02-06 13:30:09,009 INFO L78 Accepts]: Start accepts. Automaton has 56 states and 65 transitions. Word has length 179 [2025-02-06 13:30:09,010 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-06 13:30:09,010 INFO L471 AbstractCegarLoop]: Abstraction has 56 states and 65 transitions. [2025-02-06 13:30:09,010 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 5.0) internal successors, (60), 12 states have internal predecessors, (60), 4 states have call successors, (8), 1 states have call predecessors, (8), 5 states have return successors, (9), 6 states have call predecessors, (9), 4 states have call successors, (9) [2025-02-06 13:30:09,012 INFO L276 IsEmpty]: Start isEmpty. Operand 56 states and 65 transitions. [2025-02-06 13:30:09,013 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 160 [2025-02-06 13:30:09,013 INFO L210 NwaCegarLoop]: Found error trace [2025-02-06 13:30:09,013 INFO L218 NwaCegarLoop]: trace histogram [17, 15, 14, 8, 8, 8, 8, 8, 8, 8, 8, 8, 7, 7, 7, 6, 6, 3, 1, 1, 1, 1, 1] [2025-02-06 13:30:09,022 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 13:30:09,214 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,9 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-06 13:30:09,214 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-02-06 13:30:09,214 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-06 13:30:09,214 INFO L85 PathProgramCache]: Analyzing trace with hash 81726525, now seen corresponding path program 4 times [2025-02-06 13:30:09,215 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-06 13:30:09,215 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1688257377] [2025-02-06 13:30:09,215 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-02-06 13:30:09,215 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-06 13:30:09,222 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 159 statements into 2 equivalence classes. [2025-02-06 13:30:09,229 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) and asserted 96 of 159 statements. [2025-02-06 13:30:09,229 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) [2025-02-06 13:30:09,229 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 13:30:09,433 INFO L134 CoverageAnalysis]: Checked inductivity of 832 backedges. 97 proven. 355 refuted. 0 times theorem prover too weak. 380 trivial. 0 not checked. [2025-02-06 13:30:09,433 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-06 13:30:09,433 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1688257377] [2025-02-06 13:30:09,433 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1688257377] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-06 13:30:09,433 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1555016139] [2025-02-06 13:30:09,433 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-02-06 13:30:09,433 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-06 13:30:09,434 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 13:30:09,436 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 13:30:09,438 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 13:30:09,480 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 159 statements into 2 equivalence classes. [2025-02-06 13:30:09,502 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) and asserted 96 of 159 statements. [2025-02-06 13:30:09,502 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) [2025-02-06 13:30:09,502 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 13:30:09,503 INFO L256 TraceCheckSpWp]: Trace formula consists of 205 conjuncts, 14 conjuncts are in the unsatisfiable core [2025-02-06 13:30:09,506 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-06 13:30:09,617 INFO L134 CoverageAnalysis]: Checked inductivity of 832 backedges. 467 proven. 189 refuted. 0 times theorem prover too weak. 176 trivial. 0 not checked. [2025-02-06 13:30:09,617 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-06 13:30:10,126 INFO L134 CoverageAnalysis]: Checked inductivity of 832 backedges. 113 proven. 410 refuted. 0 times theorem prover too weak. 309 trivial. 0 not checked. [2025-02-06 13:30:10,126 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1555016139] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-06 13:30:10,126 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-06 13:30:10,126 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 11, 14] total 19 [2025-02-06 13:30:10,126 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1093283481] [2025-02-06 13:30:10,126 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-06 13:30:10,127 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2025-02-06 13:30:10,127 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-06 13:30:10,128 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2025-02-06 13:30:10,128 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=66, Invalid=276, Unknown=0, NotChecked=0, Total=342 [2025-02-06 13:30:10,128 INFO L87 Difference]: Start difference. First operand 56 states and 65 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 13:30:10,356 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-06 13:30:10,356 INFO L93 Difference]: Finished difference Result 123 states and 149 transitions. [2025-02-06 13:30:10,357 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2025-02-06 13:30:10,357 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 159 [2025-02-06 13:30:10,357 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-06 13:30:10,358 INFO L225 Difference]: With dead ends: 123 [2025-02-06 13:30:10,358 INFO L226 Difference]: Without dead ends: 73 [2025-02-06 13:30:10,359 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 344 GetRequests, 308 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 13:30:10,359 INFO L435 NwaCegarLoop]: 17 mSDtfsCounter, 112 mSDsluCounter, 79 mSDsCounter, 0 mSdLazyCounter, 166 mSolverCounterSat, 42 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 112 SdHoareTripleChecker+Valid, 96 SdHoareTripleChecker+Invalid, 208 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 42 IncrementalHoareTripleChecker+Valid, 166 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-02-06 13:30:10,360 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [112 Valid, 96 Invalid, 208 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [42 Valid, 166 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-02-06 13:30:10,360 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 73 states. [2025-02-06 13:30:10,366 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 73 to 62. [2025-02-06 13:30:10,366 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 62 states, 49 states have (on average 1.0816326530612246) internal successors, (53), 48 states have internal predecessors, (53), 7 states have call successors, (7), 5 states have call predecessors, (7), 5 states have return successors, (11), 8 states have call predecessors, (11), 6 states have call successors, (11) [2025-02-06 13:30:10,367 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 62 states to 62 states and 71 transitions. [2025-02-06 13:30:10,367 INFO L78 Accepts]: Start accepts. Automaton has 62 states and 71 transitions. Word has length 159 [2025-02-06 13:30:10,367 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-06 13:30:10,367 INFO L471 AbstractCegarLoop]: Abstraction has 62 states and 71 transitions. [2025-02-06 13:30:10,367 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 13:30:10,367 INFO L276 IsEmpty]: Start isEmpty. Operand 62 states and 71 transitions. [2025-02-06 13:30:10,370 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 218 [2025-02-06 13:30:10,370 INFO L210 NwaCegarLoop]: Found error trace [2025-02-06 13:30:10,370 INFO L218 NwaCegarLoop]: trace histogram [23, 21, 18, 11, 11, 11, 11, 11, 11, 11, 11, 11, 10, 10, 10, 9, 7, 5, 1, 1, 1, 1, 1] [2025-02-06 13:30:10,378 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 13:30:10,573 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11,10 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-06 13:30:10,574 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-02-06 13:30:10,574 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-06 13:30:10,574 INFO L85 PathProgramCache]: Analyzing trace with hash -639135331, now seen corresponding path program 5 times [2025-02-06 13:30:10,574 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-06 13:30:10,574 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1773745518] [2025-02-06 13:30:10,574 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2025-02-06 13:30:10,574 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-06 13:30:10,593 INFO L108 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 partitioned 217 statements into 15 equivalence classes. [2025-02-06 13:30:10,603 INFO L111 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 9 check-sat command(s) and asserted 137 of 217 statements. [2025-02-06 13:30:10,603 INFO L114 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 9 check-sat command(s) [2025-02-06 13:30:10,603 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 13:30:10,822 INFO L134 CoverageAnalysis]: Checked inductivity of 1599 backedges. 301 proven. 501 refuted. 0 times theorem prover too weak. 797 trivial. 0 not checked. [2025-02-06 13:30:10,823 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-06 13:30:10,823 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1773745518] [2025-02-06 13:30:10,823 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1773745518] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-06 13:30:10,823 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1633672696] [2025-02-06 13:30:10,823 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2025-02-06 13:30:10,823 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-06 13:30:10,823 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 13:30:10,825 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 13:30:10,828 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 13:30:10,877 INFO L108 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 partitioned 217 statements into 15 equivalence classes. [2025-02-06 13:30:10,908 INFO L111 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 9 check-sat command(s) and asserted 137 of 217 statements. [2025-02-06 13:30:10,908 INFO L114 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 9 check-sat command(s) [2025-02-06 13:30:10,909 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 13:30:10,910 INFO L256 TraceCheckSpWp]: Trace formula consists of 255 conjuncts, 15 conjuncts are in the unsatisfiable core [2025-02-06 13:30:10,913 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-06 13:30:11,033 INFO L134 CoverageAnalysis]: Checked inductivity of 1599 backedges. 650 proven. 384 refuted. 0 times theorem prover too weak. 565 trivial. 0 not checked. [2025-02-06 13:30:11,033 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-06 13:30:11,652 INFO L134 CoverageAnalysis]: Checked inductivity of 1599 backedges. 302 proven. 509 refuted. 0 times theorem prover too weak. 788 trivial. 0 not checked. [2025-02-06 13:30:11,652 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1633672696] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-06 13:30:11,652 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-06 13:30:11,652 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 12, 15] total 21 [2025-02-06 13:30:11,652 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1916438003] [2025-02-06 13:30:11,652 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-06 13:30:11,653 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2025-02-06 13:30:11,653 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-06 13:30:11,654 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2025-02-06 13:30:11,654 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=83, Invalid=337, Unknown=0, NotChecked=0, Total=420 [2025-02-06 13:30:11,655 INFO L87 Difference]: Start difference. First operand 62 states and 71 transitions. Second operand has 21 states, 21 states have (on average 5.523809523809524) internal successors, (116), 21 states have internal predecessors, (116), 13 states have call successors, (21), 3 states have call predecessors, (21), 7 states have return successors, (21), 10 states have call predecessors, (21), 12 states have call successors, (21) [2025-02-06 13:30:11,923 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-06 13:30:11,923 INFO L93 Difference]: Finished difference Result 143 states and 173 transitions. [2025-02-06 13:30:11,923 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2025-02-06 13:30:11,923 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 21 states have (on average 5.523809523809524) internal successors, (116), 21 states have internal predecessors, (116), 13 states have call successors, (21), 3 states have call predecessors, (21), 7 states have return successors, (21), 10 states have call predecessors, (21), 12 states have call successors, (21) Word has length 217 [2025-02-06 13:30:11,924 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-06 13:30:11,925 INFO L225 Difference]: With dead ends: 143 [2025-02-06 13:30:11,925 INFO L226 Difference]: Without dead ends: 87 [2025-02-06 13:30:11,925 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 463 GetRequests, 424 SyntacticMatches, 8 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 194 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=315, Invalid=741, Unknown=0, NotChecked=0, Total=1056 [2025-02-06 13:30:11,926 INFO L435 NwaCegarLoop]: 23 mSDtfsCounter, 111 mSDsluCounter, 84 mSDsCounter, 0 mSdLazyCounter, 213 mSolverCounterSat, 47 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 111 SdHoareTripleChecker+Valid, 107 SdHoareTripleChecker+Invalid, 260 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 47 IncrementalHoareTripleChecker+Valid, 213 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-02-06 13:30:11,926 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [111 Valid, 107 Invalid, 260 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [47 Valid, 213 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-02-06 13:30:11,928 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 87 states. [2025-02-06 13:30:11,936 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 87 to 74. [2025-02-06 13:30:11,937 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 74 states, 58 states have (on average 1.0862068965517242) internal successors, (63), 58 states have internal predecessors, (63), 9 states have call successors, (9), 6 states have call predecessors, (9), 6 states have return successors, (17), 9 states have call predecessors, (17), 8 states have call successors, (17) [2025-02-06 13:30:11,937 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 74 states to 74 states and 89 transitions. [2025-02-06 13:30:11,937 INFO L78 Accepts]: Start accepts. Automaton has 74 states and 89 transitions. Word has length 217 [2025-02-06 13:30:11,938 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-06 13:30:11,938 INFO L471 AbstractCegarLoop]: Abstraction has 74 states and 89 transitions. [2025-02-06 13:30:11,938 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 21 states have (on average 5.523809523809524) internal successors, (116), 21 states have internal predecessors, (116), 13 states have call successors, (21), 3 states have call predecessors, (21), 7 states have return successors, (21), 10 states have call predecessors, (21), 12 states have call successors, (21) [2025-02-06 13:30:11,938 INFO L276 IsEmpty]: Start isEmpty. Operand 74 states and 89 transitions. [2025-02-06 13:30:11,939 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 131 [2025-02-06 13:30:11,939 INFO L210 NwaCegarLoop]: Found error trace [2025-02-06 13:30:11,939 INFO L218 NwaCegarLoop]: trace histogram [14, 12, 11, 7, 7, 7, 7, 6, 6, 6, 6, 6, 6, 6, 6, 5, 4, 3, 1, 1, 1, 1, 1] [2025-02-06 13:30:11,947 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 13:30:12,140 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2025-02-06 13:30:12,140 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-02-06 13:30:12,141 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-06 13:30:12,141 INFO L85 PathProgramCache]: Analyzing trace with hash 1715536077, now seen corresponding path program 6 times [2025-02-06 13:30:12,141 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-06 13:30:12,141 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1859564457] [2025-02-06 13:30:12,141 INFO L95 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2025-02-06 13:30:12,141 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-06 13:30:12,147 INFO L108 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE partitioned 130 statements into 9 equivalence classes. [2025-02-06 13:30:12,163 INFO L111 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 9 check-sat command(s) and asserted 130 of 130 statements. [2025-02-06 13:30:12,163 INFO L114 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 9 check-sat command(s) [2025-02-06 13:30:12,163 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 13:30:12,315 INFO L134 CoverageAnalysis]: Checked inductivity of 537 backedges. 183 proven. 132 refuted. 0 times theorem prover too weak. 222 trivial. 0 not checked. [2025-02-06 13:30:12,315 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-06 13:30:12,315 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1859564457] [2025-02-06 13:30:12,315 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1859564457] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-06 13:30:12,316 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1891745004] [2025-02-06 13:30:12,316 INFO L95 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2025-02-06 13:30:12,316 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-06 13:30:12,316 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 13:30:12,319 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 13:30:12,320 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 13:30:12,360 INFO L108 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE partitioned 130 statements into 9 equivalence classes. [2025-02-06 13:30:12,389 INFO L111 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 9 check-sat command(s) and asserted 130 of 130 statements. [2025-02-06 13:30:12,389 INFO L114 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 9 check-sat command(s) [2025-02-06 13:30:12,389 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 13:30:12,390 INFO L256 TraceCheckSpWp]: Trace formula consists of 259 conjuncts, 25 conjuncts are in the unsatisfiable core [2025-02-06 13:30:12,393 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-06 13:30:12,618 INFO L134 CoverageAnalysis]: Checked inductivity of 537 backedges. 61 proven. 95 refuted. 0 times theorem prover too weak. 381 trivial. 0 not checked. [2025-02-06 13:30:12,618 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-06 13:30:13,610 INFO L134 CoverageAnalysis]: Checked inductivity of 537 backedges. 103 proven. 95 refuted. 0 times theorem prover too weak. 339 trivial. 0 not checked. [2025-02-06 13:30:13,610 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1891745004] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-06 13:30:13,610 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-06 13:30:13,610 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 12, 15] total 33 [2025-02-06 13:30:13,610 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2030960321] [2025-02-06 13:30:13,610 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-06 13:30:13,611 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 33 states [2025-02-06 13:30:13,611 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-06 13:30:13,611 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 33 interpolants. [2025-02-06 13:30:13,612 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=159, Invalid=897, Unknown=0, NotChecked=0, Total=1056 [2025-02-06 13:30:13,612 INFO L87 Difference]: Start difference. First operand 74 states and 89 transitions. Second operand has 33 states, 33 states have (on average 3.484848484848485) internal successors, (115), 33 states have internal predecessors, (115), 11 states have call successors, (15), 1 states have call predecessors, (15), 13 states have return successors, (25), 23 states have call predecessors, (25), 11 states have call successors, (25) [2025-02-06 13:30:14,215 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-06 13:30:14,215 INFO L93 Difference]: Finished difference Result 197 states and 263 transitions. [2025-02-06 13:30:14,215 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2025-02-06 13:30:14,215 INFO L78 Accepts]: Start accepts. Automaton has has 33 states, 33 states have (on average 3.484848484848485) internal successors, (115), 33 states have internal predecessors, (115), 11 states have call successors, (15), 1 states have call predecessors, (15), 13 states have return successors, (25), 23 states have call predecessors, (25), 11 states have call successors, (25) Word has length 130 [2025-02-06 13:30:14,216 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-06 13:30:14,217 INFO L225 Difference]: With dead ends: 197 [2025-02-06 13:30:14,217 INFO L226 Difference]: Without dead ends: 123 [2025-02-06 13:30:14,218 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 294 GetRequests, 231 SyntacticMatches, 10 SemanticMatches, 53 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 842 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=501, Invalid=2469, Unknown=0, NotChecked=0, Total=2970 [2025-02-06 13:30:14,219 INFO L435 NwaCegarLoop]: 17 mSDtfsCounter, 145 mSDsluCounter, 121 mSDsCounter, 0 mSdLazyCounter, 663 mSolverCounterSat, 78 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 145 SdHoareTripleChecker+Valid, 138 SdHoareTripleChecker+Invalid, 741 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 78 IncrementalHoareTripleChecker+Valid, 663 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2025-02-06 13:30:14,219 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [145 Valid, 138 Invalid, 741 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [78 Valid, 663 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2025-02-06 13:30:14,219 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 123 states. [2025-02-06 13:30:14,228 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 123 to 98. [2025-02-06 13:30:14,228 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 98 states, 78 states have (on average 1.064102564102564) internal successors, (83), 77 states have internal predecessors, (83), 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 13:30:14,231 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 98 states to 98 states and 121 transitions. [2025-02-06 13:30:14,231 INFO L78 Accepts]: Start accepts. Automaton has 98 states and 121 transitions. Word has length 130 [2025-02-06 13:30:14,231 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-06 13:30:14,231 INFO L471 AbstractCegarLoop]: Abstraction has 98 states and 121 transitions. [2025-02-06 13:30:14,231 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 33 states, 33 states have (on average 3.484848484848485) internal successors, (115), 33 states have internal predecessors, (115), 11 states have call successors, (15), 1 states have call predecessors, (15), 13 states have return successors, (25), 23 states have call predecessors, (25), 11 states have call successors, (25) [2025-02-06 13:30:14,231 INFO L276 IsEmpty]: Start isEmpty. Operand 98 states and 121 transitions. [2025-02-06 13:30:14,238 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 454 [2025-02-06 13:30:14,238 INFO L210 NwaCegarLoop]: Found error trace [2025-02-06 13:30:14,238 INFO L218 NwaCegarLoop]: trace histogram [47, 45, 38, 23, 23, 23, 23, 23, 23, 23, 23, 23, 22, 22, 22, 21, 15, 9, 1, 1, 1, 1, 1] [2025-02-06 13:30:14,245 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 13:30:14,438 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2025-02-06 13:30:14,439 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-02-06 13:30:14,439 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-06 13:30:14,439 INFO L85 PathProgramCache]: Analyzing trace with hash 1857142939, now seen corresponding path program 7 times [2025-02-06 13:30:14,439 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-06 13:30:14,439 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1204864504] [2025-02-06 13:30:14,439 INFO L95 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2025-02-06 13:30:14,439 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-06 13:30:14,452 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 453 statements into 1 equivalence classes. [2025-02-06 13:30:14,482 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 453 of 453 statements. [2025-02-06 13:30:14,482 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-06 13:30:14,482 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 13:30:15,112 INFO L134 CoverageAnalysis]: Checked inductivity of 7309 backedges. 558 proven. 2001 refuted. 0 times theorem prover too weak. 4750 trivial. 0 not checked. [2025-02-06 13:30:15,112 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-06 13:30:15,112 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1204864504] [2025-02-06 13:30:15,112 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1204864504] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-06 13:30:15,112 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [555013787] [2025-02-06 13:30:15,112 INFO L95 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2025-02-06 13:30:15,112 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-06 13:30:15,112 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 13:30:15,115 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 13:30:15,117 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 13:30:15,184 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 453 statements into 1 equivalence classes. [2025-02-06 13:30:15,260 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 453 of 453 statements. [2025-02-06 13:30:15,260 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-06 13:30:15,260 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 13:30:15,264 INFO L256 TraceCheckSpWp]: Trace formula consists of 857 conjuncts, 22 conjuncts are in the unsatisfiable core [2025-02-06 13:30:15,269 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-06 13:30:15,435 INFO L134 CoverageAnalysis]: Checked inductivity of 7309 backedges. 3859 proven. 1245 refuted. 0 times theorem prover too weak. 2205 trivial. 0 not checked. [2025-02-06 13:30:15,435 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-06 13:30:16,721 INFO L134 CoverageAnalysis]: Checked inductivity of 7309 backedges. 658 proven. 2493 refuted. 0 times theorem prover too weak. 4158 trivial. 0 not checked. [2025-02-06 13:30:16,721 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [555013787] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-06 13:30:16,721 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-06 13:30:16,721 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 15, 22] total 27 [2025-02-06 13:30:16,721 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [79504321] [2025-02-06 13:30:16,721 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-06 13:30:16,723 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 27 states [2025-02-06 13:30:16,723 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-06 13:30:16,724 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 27 interpolants. [2025-02-06 13:30:16,724 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=120, Invalid=582, Unknown=0, NotChecked=0, Total=702 [2025-02-06 13:30:16,725 INFO L87 Difference]: Start difference. First operand 98 states and 121 transitions. Second operand has 27 states, 27 states have (on average 6.037037037037037) internal successors, (163), 27 states have internal predecessors, (163), 22 states have call successors, (29), 3 states have call predecessors, (29), 11 states have return successors, (34), 13 states have call predecessors, (34), 21 states have call successors, (34) [2025-02-06 13:30:17,073 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-06 13:30:17,074 INFO L93 Difference]: Finished difference Result 233 states and 310 transitions. [2025-02-06 13:30:17,074 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 26 states. [2025-02-06 13:30:17,074 INFO L78 Accepts]: Start accepts. Automaton has has 27 states, 27 states have (on average 6.037037037037037) internal successors, (163), 27 states have internal predecessors, (163), 22 states have call successors, (29), 3 states have call predecessors, (29), 11 states have return successors, (34), 13 states have call predecessors, (34), 21 states have call successors, (34) Word has length 453 [2025-02-06 13:30:17,075 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-06 13:30:17,076 INFO L225 Difference]: With dead ends: 233 [2025-02-06 13:30:17,076 INFO L226 Difference]: Without dead ends: 141 [2025-02-06 13:30:17,077 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 949 GetRequests, 891 SyntacticMatches, 12 SemanticMatches, 46 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 510 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=589, Invalid=1667, Unknown=0, NotChecked=0, Total=2256 [2025-02-06 13:30:17,078 INFO L435 NwaCegarLoop]: 29 mSDtfsCounter, 283 mSDsluCounter, 119 mSDsCounter, 0 mSdLazyCounter, 269 mSolverCounterSat, 128 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 283 SdHoareTripleChecker+Valid, 148 SdHoareTripleChecker+Invalid, 397 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 128 IncrementalHoareTripleChecker+Valid, 269 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-02-06 13:30:17,078 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [283 Valid, 148 Invalid, 397 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [128 Valid, 269 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-02-06 13:30:17,079 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 141 states. [2025-02-06 13:30:17,089 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 141 to 119. [2025-02-06 13:30:17,089 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 119 states, 96 states have (on average 1.0625) internal successors, (102), 93 states have internal predecessors, (102), 14 states have call successors, (14), 10 states have call predecessors, (14), 8 states have return successors, (32), 15 states have call predecessors, (32), 13 states have call successors, (32) [2025-02-06 13:30:17,091 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 119 states to 119 states and 148 transitions. [2025-02-06 13:30:17,092 INFO L78 Accepts]: Start accepts. Automaton has 119 states and 148 transitions. Word has length 453 [2025-02-06 13:30:17,092 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-06 13:30:17,092 INFO L471 AbstractCegarLoop]: Abstraction has 119 states and 148 transitions. [2025-02-06 13:30:17,092 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 27 states, 27 states have (on average 6.037037037037037) internal successors, (163), 27 states have internal predecessors, (163), 22 states have call successors, (29), 3 states have call predecessors, (29), 11 states have return successors, (34), 13 states have call predecessors, (34), 21 states have call successors, (34) [2025-02-06 13:30:17,092 INFO L276 IsEmpty]: Start isEmpty. Operand 119 states and 148 transitions. [2025-02-06 13:30:17,096 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 308 [2025-02-06 13:30:17,096 INFO L210 NwaCegarLoop]: Found error trace [2025-02-06 13:30:17,096 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 13:30:17,104 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Forceful destruction successful, exit code 0 [2025-02-06 13:30:17,296 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable14,13 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-06 13:30:17,297 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-02-06 13:30:17,297 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-06 13:30:17,297 INFO L85 PathProgramCache]: Analyzing trace with hash -449393690, now seen corresponding path program 8 times [2025-02-06 13:30:17,297 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-06 13:30:17,298 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1382484640] [2025-02-06 13:30:17,298 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-02-06 13:30:17,298 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-06 13:30:17,310 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 307 statements into 2 equivalence classes. [2025-02-06 13:30:17,336 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 307 of 307 statements. [2025-02-06 13:30:17,336 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-02-06 13:30:17,336 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 13:30:17,752 INFO L134 CoverageAnalysis]: Checked inductivity of 3282 backedges. 554 proven. 990 refuted. 0 times theorem prover too weak. 1738 trivial. 0 not checked. [2025-02-06 13:30:17,752 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-06 13:30:17,752 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1382484640] [2025-02-06 13:30:17,752 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1382484640] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-06 13:30:17,753 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1440179898] [2025-02-06 13:30:17,753 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-02-06 13:30:17,753 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-06 13:30:17,753 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 13:30:17,755 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 13:30:17,757 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 13:30:17,825 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 307 statements into 2 equivalence classes. [2025-02-06 13:30:17,883 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 307 of 307 statements. [2025-02-06 13:30:17,883 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-02-06 13:30:17,883 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 13:30:17,885 INFO L256 TraceCheckSpWp]: Trace formula consists of 586 conjuncts, 18 conjuncts are in the unsatisfiable core [2025-02-06 13:30:17,889 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-06 13:30:18,024 INFO L134 CoverageAnalysis]: Checked inductivity of 3282 backedges. 1858 proven. 484 refuted. 0 times theorem prover too weak. 940 trivial. 0 not checked. [2025-02-06 13:30:18,025 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-06 13:30:19,319 INFO L134 CoverageAnalysis]: Checked inductivity of 3282 backedges. 551 proven. 1101 refuted. 0 times theorem prover too weak. 1630 trivial. 0 not checked. [2025-02-06 13:30:19,319 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1440179898] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-06 13:30:19,319 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-06 13:30:19,319 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 13, 19] total 24 [2025-02-06 13:30:19,319 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1222836644] [2025-02-06 13:30:19,319 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-06 13:30:19,320 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 24 states [2025-02-06 13:30:19,320 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-06 13:30:19,321 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2025-02-06 13:30:19,321 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=111, Invalid=441, Unknown=0, NotChecked=0, Total=552 [2025-02-06 13:30:19,321 INFO L87 Difference]: Start difference. First operand 119 states and 148 transitions. Second operand has 24 states, 24 states have (on average 5.625) internal successors, (135), 24 states have internal predecessors, (135), 18 states have call successors, (23), 2 states have call predecessors, (23), 10 states have return successors, (28), 10 states have call predecessors, (28), 18 states have call successors, (28) [2025-02-06 13:30:19,604 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-06 13:30:19,604 INFO L93 Difference]: Finished difference Result 232 states and 300 transitions. [2025-02-06 13:30:19,605 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2025-02-06 13:30:19,605 INFO L78 Accepts]: Start accepts. Automaton has has 24 states, 24 states have (on average 5.625) internal successors, (135), 24 states have internal predecessors, (135), 18 states have call successors, (23), 2 states have call predecessors, (23), 10 states have return successors, (28), 10 states have call predecessors, (28), 18 states have call successors, (28) Word has length 307 [2025-02-06 13:30:19,605 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-06 13:30:19,606 INFO L225 Difference]: With dead ends: 232 [2025-02-06 13:30:19,606 INFO L226 Difference]: Without dead ends: 119 [2025-02-06 13:30:19,607 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 644 GetRequests, 601 SyntacticMatches, 9 SemanticMatches, 34 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 325 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=349, Invalid=911, Unknown=0, NotChecked=0, Total=1260 [2025-02-06 13:30:19,608 INFO L435 NwaCegarLoop]: 41 mSDtfsCounter, 72 mSDsluCounter, 137 mSDsCounter, 0 mSdLazyCounter, 363 mSolverCounterSat, 49 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 72 SdHoareTripleChecker+Valid, 178 SdHoareTripleChecker+Invalid, 412 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 49 IncrementalHoareTripleChecker+Valid, 363 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-02-06 13:30:19,608 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [72 Valid, 178 Invalid, 412 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [49 Valid, 363 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-02-06 13:30:19,608 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 119 states. [2025-02-06 13:30:19,614 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 119 to 107. [2025-02-06 13:30:19,615 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 13:30:19,615 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 107 states to 107 states and 128 transitions. [2025-02-06 13:30:19,616 INFO L78 Accepts]: Start accepts. Automaton has 107 states and 128 transitions. Word has length 307 [2025-02-06 13:30:19,616 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-06 13:30:19,616 INFO L471 AbstractCegarLoop]: Abstraction has 107 states and 128 transitions. [2025-02-06 13:30:19,616 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 24 states, 24 states have (on average 5.625) internal successors, (135), 24 states have internal predecessors, (135), 18 states have call successors, (23), 2 states have call predecessors, (23), 10 states have return successors, (28), 10 states have call predecessors, (28), 18 states have call successors, (28) [2025-02-06 13:30:19,616 INFO L276 IsEmpty]: Start isEmpty. Operand 107 states and 128 transitions. [2025-02-06 13:30:19,618 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 341 [2025-02-06 13:30:19,618 INFO L210 NwaCegarLoop]: Found error trace [2025-02-06 13:30:19,618 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 13:30:19,626 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Ended with exit code 0 [2025-02-06 13:30:19,822 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable15,14 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-06 13:30:19,822 INFO L396 AbstractCegarLoop]: === Iteration 17 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-02-06 13:30:19,822 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-06 13:30:19,822 INFO L85 PathProgramCache]: Analyzing trace with hash -1953340652, now seen corresponding path program 9 times [2025-02-06 13:30:19,822 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-06 13:30:19,822 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [644464633] [2025-02-06 13:30:19,822 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-02-06 13:30:19,823 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-06 13:30:19,833 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 340 statements into 24 equivalence classes. [2025-02-06 13:30:19,857 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 15 check-sat command(s) and asserted 203 of 340 statements. [2025-02-06 13:30:19,857 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 15 check-sat command(s) [2025-02-06 13:30:19,857 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 13:30:20,081 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 13:30:20,081 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-06 13:30:20,081 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [644464633] [2025-02-06 13:30:20,081 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [644464633] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-06 13:30:20,081 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [288334547] [2025-02-06 13:30:20,082 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-02-06 13:30:20,082 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-06 13:30:20,082 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 13:30:20,084 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 13:30:20,087 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 13:30:20,173 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 340 statements into 24 equivalence classes. [2025-02-06 13:30:20,222 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 15 check-sat command(s) and asserted 203 of 340 statements. [2025-02-06 13:30:20,222 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 15 check-sat command(s) [2025-02-06 13:30:20,222 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 13:30:20,224 INFO L256 TraceCheckSpWp]: Trace formula consists of 395 conjuncts, 16 conjuncts are in the unsatisfiable core [2025-02-06 13:30:20,231 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-06 13:30:20,353 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 13:30:20,353 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-06 13:30:21,235 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 13:30:21,235 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [288334547] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-06 13:30:21,235 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-06 13:30:21,235 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 12, 17] total 24 [2025-02-06 13:30:21,235 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1939174388] [2025-02-06 13:30:21,235 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-06 13:30:21,236 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 24 states [2025-02-06 13:30:21,236 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-06 13:30:21,236 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2025-02-06 13:30:21,237 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=114, Invalid=438, Unknown=0, NotChecked=0, Total=552 [2025-02-06 13:30:21,237 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 13:30:21,490 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-06 13:30:21,490 INFO L93 Difference]: Finished difference Result 225 states and 274 transitions. [2025-02-06 13:30:21,491 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2025-02-06 13:30:21,491 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 13:30:21,491 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-06 13:30:21,494 INFO L225 Difference]: With dead ends: 225 [2025-02-06 13:30:21,495 INFO L226 Difference]: Without dead ends: 117 [2025-02-06 13:30:21,496 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 13:30:21,496 INFO L435 NwaCegarLoop]: 32 mSDtfsCounter, 93 mSDsluCounter, 122 mSDsCounter, 0 mSdLazyCounter, 300 mSolverCounterSat, 48 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 93 SdHoareTripleChecker+Valid, 154 SdHoareTripleChecker+Invalid, 348 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 48 IncrementalHoareTripleChecker+Valid, 300 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-02-06 13:30:21,496 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [93 Valid, 154 Invalid, 348 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [48 Valid, 300 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-02-06 13:30:21,497 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 117 states. [2025-02-06 13:30:21,505 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 117 to 107. [2025-02-06 13:30:21,506 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 13:30:21,506 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 107 states to 107 states and 125 transitions. [2025-02-06 13:30:21,507 INFO L78 Accepts]: Start accepts. Automaton has 107 states and 125 transitions. Word has length 340 [2025-02-06 13:30:21,508 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-06 13:30:21,508 INFO L471 AbstractCegarLoop]: Abstraction has 107 states and 125 transitions. [2025-02-06 13:30:21,508 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 13:30:21,509 INFO L276 IsEmpty]: Start isEmpty. Operand 107 states and 125 transitions. [2025-02-06 13:30:21,513 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 662 [2025-02-06 13:30:21,513 INFO L210 NwaCegarLoop]: Found error trace [2025-02-06 13:30:21,513 INFO L218 NwaCegarLoop]: trace histogram [69, 65, 56, 35, 35, 35, 35, 33, 33, 33, 33, 33, 32, 32, 32, 31, 21, 13, 1, 1, 1, 1, 1] [2025-02-06 13:30:21,522 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Forceful destruction successful, exit code 0 [2025-02-06 13:30:21,717 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 15 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable16 [2025-02-06 13:30:21,717 INFO L396 AbstractCegarLoop]: === Iteration 18 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-02-06 13:30:21,717 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-06 13:30:21,717 INFO L85 PathProgramCache]: Analyzing trace with hash -1172881087, now seen corresponding path program 10 times [2025-02-06 13:30:21,718 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-06 13:30:21,718 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [577972470] [2025-02-06 13:30:21,718 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-02-06 13:30:21,718 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-06 13:30:21,735 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 661 statements into 2 equivalence classes. [2025-02-06 13:30:21,772 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) and asserted 394 of 661 statements. [2025-02-06 13:30:21,773 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) [2025-02-06 13:30:21,773 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 13:30:22,236 INFO L134 CoverageAnalysis]: Checked inductivity of 15777 backedges. 1047 proven. 3398 refuted. 0 times theorem prover too weak. 11332 trivial. 0 not checked. [2025-02-06 13:30:22,236 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-06 13:30:22,236 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [577972470] [2025-02-06 13:30:22,236 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [577972470] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-06 13:30:22,236 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1307857909] [2025-02-06 13:30:22,237 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-02-06 13:30:22,237 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-06 13:30:22,237 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 13:30:22,239 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 13:30:22,242 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 13:30:22,350 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 661 statements into 2 equivalence classes. [2025-02-06 13:30:22,428 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) and asserted 394 of 661 statements. [2025-02-06 13:30:22,428 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) [2025-02-06 13:30:22,428 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 13:30:22,432 INFO L256 TraceCheckSpWp]: Trace formula consists of 826 conjuncts, 26 conjuncts are in the unsatisfiable core [2025-02-06 13:30:22,439 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-06 13:30:22,617 INFO L134 CoverageAnalysis]: Checked inductivity of 15777 backedges. 6705 proven. 2740 refuted. 0 times theorem prover too weak. 6332 trivial. 0 not checked. [2025-02-06 13:30:22,618 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-06 13:30:24,186 INFO L134 CoverageAnalysis]: Checked inductivity of 15777 backedges. 1286 proven. 4125 refuted. 0 times theorem prover too weak. 10366 trivial. 0 not checked. [2025-02-06 13:30:24,187 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1307857909] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-06 13:30:24,187 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-06 13:30:24,187 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 17, 24] total 29 [2025-02-06 13:30:24,187 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1837282461] [2025-02-06 13:30:24,187 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-06 13:30:24,188 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 29 states [2025-02-06 13:30:24,188 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-06 13:30:24,189 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 29 interpolants. [2025-02-06 13:30:24,189 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=130, Invalid=682, Unknown=0, NotChecked=0, Total=812 [2025-02-06 13:30:24,189 INFO L87 Difference]: Start difference. First operand 107 states and 125 transitions. Second operand has 29 states, 29 states have (on average 5.9655172413793105) internal successors, (173), 29 states have internal predecessors, (173), 24 states have call successors, (31), 5 states have call predecessors, (31), 11 states have return successors, (34), 13 states have call predecessors, (34), 21 states have call successors, (34) [2025-02-06 13:30:24,601 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-06 13:30:24,602 INFO L93 Difference]: Finished difference Result 247 states and 315 transitions. [2025-02-06 13:30:24,602 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 28 states. [2025-02-06 13:30:24,602 INFO L78 Accepts]: Start accepts. Automaton has has 29 states, 29 states have (on average 5.9655172413793105) internal successors, (173), 29 states have internal predecessors, (173), 24 states have call successors, (31), 5 states have call predecessors, (31), 11 states have return successors, (34), 13 states have call predecessors, (34), 21 states have call successors, (34) Word has length 661 [2025-02-06 13:30:24,603 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-06 13:30:24,604 INFO L225 Difference]: With dead ends: 247 [2025-02-06 13:30:24,604 INFO L226 Difference]: Without dead ends: 146 [2025-02-06 13:30:24,606 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 1371 GetRequests, 1304 SyntacticMatches, 16 SemanticMatches, 51 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 658 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=752, Invalid=2004, Unknown=0, NotChecked=0, Total=2756 [2025-02-06 13:30:24,607 INFO L435 NwaCegarLoop]: 22 mSDtfsCounter, 316 mSDsluCounter, 113 mSDsCounter, 0 mSdLazyCounter, 252 mSolverCounterSat, 120 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 316 SdHoareTripleChecker+Valid, 135 SdHoareTripleChecker+Invalid, 372 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 120 IncrementalHoareTripleChecker+Valid, 252 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-02-06 13:30:24,607 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [316 Valid, 135 Invalid, 372 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [120 Valid, 252 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-02-06 13:30:24,607 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 146 states. [2025-02-06 13:30:24,616 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 146 to 134. [2025-02-06 13:30:24,616 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 13:30:24,617 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 134 states to 134 states and 160 transitions. [2025-02-06 13:30:24,617 INFO L78 Accepts]: Start accepts. Automaton has 134 states and 160 transitions. Word has length 661 [2025-02-06 13:30:24,619 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-06 13:30:24,619 INFO L471 AbstractCegarLoop]: Abstraction has 134 states and 160 transitions. [2025-02-06 13:30:24,620 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 29 states, 29 states have (on average 5.9655172413793105) internal successors, (173), 29 states have internal predecessors, (173), 24 states have call successors, (31), 5 states have call predecessors, (31), 11 states have return successors, (34), 13 states have call predecessors, (34), 21 states have call successors, (34) [2025-02-06 13:30:24,620 INFO L276 IsEmpty]: Start isEmpty. Operand 134 states and 160 transitions. [2025-02-06 13:30:24,621 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 400 [2025-02-06 13:30:24,621 INFO L210 NwaCegarLoop]: Found error trace [2025-02-06 13:30:24,622 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 13:30:24,630 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 13:30:24,822 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 16 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable17 [2025-02-06 13:30:24,822 INFO L396 AbstractCegarLoop]: === Iteration 19 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-02-06 13:30:24,823 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-06 13:30:24,823 INFO L85 PathProgramCache]: Analyzing trace with hash 1806187615, now seen corresponding path program 11 times [2025-02-06 13:30:24,823 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-06 13:30:24,823 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [514703554] [2025-02-06 13:30:24,823 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2025-02-06 13:30:24,823 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-06 13:30:24,834 INFO L108 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 partitioned 399 statements into 29 equivalence classes. [2025-02-06 13:30:24,862 INFO L111 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 29 check-sat command(s) and asserted 399 of 399 statements. [2025-02-06 13:30:24,862 INFO L114 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 29 check-sat command(s) [2025-02-06 13:30:24,862 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 13:30:27,848 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 13:30:27,849 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-06 13:30:27,849 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [514703554] [2025-02-06 13:30:27,849 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [514703554] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-06 13:30:27,849 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2032616648] [2025-02-06 13:30:27,849 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2025-02-06 13:30:27,849 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-06 13:30:27,849 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 13:30:27,852 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 13:30:27,854 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 13:30:27,952 INFO L108 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 partitioned 399 statements into 29 equivalence classes. [2025-02-06 13:30:28,065 INFO L111 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 29 check-sat command(s) and asserted 399 of 399 statements. [2025-02-06 13:30:28,065 INFO L114 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 29 check-sat command(s) [2025-02-06 13:30:28,065 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 13:30:28,068 INFO L256 TraceCheckSpWp]: Trace formula consists of 757 conjuncts, 81 conjuncts are in the unsatisfiable core [2025-02-06 13:30:28,073 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-06 13:30:28,445 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 13:30:28,446 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-06 13:30:34,465 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 13:30:34,465 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2032616648] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-06 13:30:34,465 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-06 13:30:34,466 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [24, 18, 29] total 47 [2025-02-06 13:30:34,466 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [35802505] [2025-02-06 13:30:34,466 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-06 13:30:34,467 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 48 states [2025-02-06 13:30:34,467 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-06 13:30:34,468 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 48 interpolants. [2025-02-06 13:30:34,468 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=526, Invalid=1730, Unknown=0, NotChecked=0, Total=2256 [2025-02-06 13:30:34,469 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 13:30:34,682 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-06 13:30:34,682 INFO L93 Difference]: Finished difference Result 165 states and 212 transitions. [2025-02-06 13:30:34,682 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 26 states. [2025-02-06 13:30:34,682 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 13:30:34,683 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-06 13:30:34,688 INFO L225 Difference]: With dead ends: 165 [2025-02-06 13:30:34,688 INFO L226 Difference]: Without dead ends: 164 [2025-02-06 13:30:34,689 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 881 GetRequests, 776 SyntacticMatches, 55 SemanticMatches, 50 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2632 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=613, Invalid=2039, Unknown=0, NotChecked=0, Total=2652 [2025-02-06 13:30:34,690 INFO L435 NwaCegarLoop]: 20 mSDtfsCounter, 12 mSDsluCounter, 185 mSDsCounter, 0 mSdLazyCounter, 180 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 19 SdHoareTripleChecker+Valid, 205 SdHoareTripleChecker+Invalid, 189 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 180 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-02-06 13:30:34,690 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [19 Valid, 205 Invalid, 189 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 180 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-02-06 13:30:34,690 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 164 states. [2025-02-06 13:30:34,707 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 164 to 155. [2025-02-06 13:30:34,708 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 13:30:34,709 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 155 states to 155 states and 197 transitions. [2025-02-06 13:30:34,710 INFO L78 Accepts]: Start accepts. Automaton has 155 states and 197 transitions. Word has length 399 [2025-02-06 13:30:34,711 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-06 13:30:34,711 INFO L471 AbstractCegarLoop]: Abstraction has 155 states and 197 transitions. [2025-02-06 13:30:34,712 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 13:30:34,712 INFO L276 IsEmpty]: Start isEmpty. Operand 155 states and 197 transitions. [2025-02-06 13:30:34,729 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1225 [2025-02-06 13:30:34,730 INFO L210 NwaCegarLoop]: Found error trace [2025-02-06 13:30:34,730 INFO L218 NwaCegarLoop]: trace histogram [126, 123, 102, 63, 63, 63, 63, 62, 62, 62, 62, 62, 61, 61, 61, 60, 39, 24, 1, 1, 1, 1, 1] [2025-02-06 13:30:34,739 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Forceful destruction successful, exit code 0 [2025-02-06 13:30:34,930 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable18,17 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-06 13:30:34,931 INFO L396 AbstractCegarLoop]: === Iteration 20 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-02-06 13:30:34,931 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-06 13:30:34,931 INFO L85 PathProgramCache]: Analyzing trace with hash 336610573, now seen corresponding path program 12 times [2025-02-06 13:30:34,931 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-06 13:30:34,932 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [197837962] [2025-02-06 13:30:34,932 INFO L95 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2025-02-06 13:30:34,932 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-06 13:30:34,960 INFO L108 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE partitioned 1224 statements into 91 equivalence classes. [2025-02-06 13:30:35,111 INFO L111 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 62 check-sat command(s) and asserted 815 of 1224 statements. [2025-02-06 13:30:35,111 INFO L114 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 62 check-sat command(s) [2025-02-06 13:30:35,111 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 13:30:36,502 INFO L134 CoverageAnalysis]: Checked inductivity of 54820 backedges. 3817 proven. 8116 refuted. 0 times theorem prover too weak. 42887 trivial. 0 not checked. [2025-02-06 13:30:36,503 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-06 13:30:36,503 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [197837962] [2025-02-06 13:30:36,503 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [197837962] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-06 13:30:36,503 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1344354447] [2025-02-06 13:30:36,503 INFO L95 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2025-02-06 13:30:36,503 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-06 13:30:36,503 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 13:30:36,505 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 13:30:36,506 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 13:30:36,713 INFO L108 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE partitioned 1224 statements into 91 equivalence classes. [2025-02-06 13:30:36,964 INFO L111 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 62 check-sat command(s) and asserted 815 of 1224 statements. [2025-02-06 13:30:36,964 INFO L114 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 62 check-sat command(s) [2025-02-06 13:30:36,964 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 13:30:36,968 INFO L256 TraceCheckSpWp]: Trace formula consists of 1522 conjuncts, 28 conjuncts are in the unsatisfiable core [2025-02-06 13:30:36,979 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-06 13:30:37,138 INFO L134 CoverageAnalysis]: Checked inductivity of 54820 backedges. 28119 proven. 4089 refuted. 0 times theorem prover too weak. 22612 trivial. 0 not checked. [2025-02-06 13:30:37,138 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-06 13:30:39,977 INFO L134 CoverageAnalysis]: Checked inductivity of 54820 backedges. 3964 proven. 8595 refuted. 0 times theorem prover too weak. 42261 trivial. 0 not checked. [2025-02-06 13:30:39,977 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1344354447] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-06 13:30:39,977 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-06 13:30:39,978 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [23, 19, 29] total 36 [2025-02-06 13:30:39,978 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [58260138] [2025-02-06 13:30:39,978 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-06 13:30:39,979 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 36 states [2025-02-06 13:30:39,979 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-06 13:30:39,980 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 36 interpolants. [2025-02-06 13:30:39,980 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=225, Invalid=1035, Unknown=0, NotChecked=0, Total=1260 [2025-02-06 13:30:39,980 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), 3 states have call predecessors, (37), 14 states have return successors, (45), 17 states have call predecessors, (45), 29 states have call successors, (45) [2025-02-06 13:30:40,607 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-06 13:30:40,607 INFO L93 Difference]: Finished difference Result 356 states and 497 transitions. [2025-02-06 13:30:40,608 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 42 states. [2025-02-06 13:30:40,608 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), 3 states have call predecessors, (37), 14 states have return successors, (45), 17 states have call predecessors, (45), 29 states have call successors, (45) Word has length 1224 [2025-02-06 13:30:40,609 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-06 13:30:40,611 INFO L225 Difference]: With dead ends: 356 [2025-02-06 13:30:40,611 INFO L226 Difference]: Without dead ends: 207 [2025-02-06 13:30:40,613 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 2515 GetRequests, 2432 SyntacticMatches, 15 SemanticMatches, 68 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1441 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=1169, Invalid=3661, Unknown=0, NotChecked=0, Total=4830 [2025-02-06 13:30:40,614 INFO L435 NwaCegarLoop]: 43 mSDtfsCounter, 457 mSDsluCounter, 182 mSDsCounter, 0 mSdLazyCounter, 510 mSolverCounterSat, 202 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 457 SdHoareTripleChecker+Valid, 225 SdHoareTripleChecker+Invalid, 712 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 202 IncrementalHoareTripleChecker+Valid, 510 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2025-02-06 13:30:40,614 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [457 Valid, 225 Invalid, 712 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [202 Valid, 510 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2025-02-06 13:30:40,614 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 207 states. [2025-02-06 13:30:40,625 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 207 to 191. [2025-02-06 13:30:40,626 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 13:30:40,627 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 191 states to 191 states and 242 transitions. [2025-02-06 13:30:40,627 INFO L78 Accepts]: Start accepts. Automaton has 191 states and 242 transitions. Word has length 1224 [2025-02-06 13:30:40,628 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-06 13:30:40,628 INFO L471 AbstractCegarLoop]: Abstraction has 191 states and 242 transitions. [2025-02-06 13:30:40,628 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), 3 states have call predecessors, (37), 14 states have return successors, (45), 17 states have call predecessors, (45), 29 states have call successors, (45) [2025-02-06 13:30:40,628 INFO L276 IsEmpty]: Start isEmpty. Operand 191 states and 242 transitions. [2025-02-06 13:30:40,633 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 818 [2025-02-06 13:30:40,633 INFO L210 NwaCegarLoop]: Found error trace [2025-02-06 13:30:40,633 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 13:30:40,644 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 13:30:40,834 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable19,18 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-06 13:30:40,834 INFO L396 AbstractCegarLoop]: === Iteration 21 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-02-06 13:30:40,835 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-06 13:30:40,835 INFO L85 PathProgramCache]: Analyzing trace with hash 840937960, now seen corresponding path program 13 times [2025-02-06 13:30:40,835 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-06 13:30:40,835 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [758433101] [2025-02-06 13:30:40,835 INFO L95 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2025-02-06 13:30:40,835 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-06 13:30:40,848 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 817 statements into 1 equivalence classes. [2025-02-06 13:30:40,907 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 817 of 817 statements. [2025-02-06 13:30:40,907 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-06 13:30:40,907 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 13:30:42,034 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 13:30:42,034 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-06 13:30:42,034 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [758433101] [2025-02-06 13:30:42,034 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [758433101] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-06 13:30:42,034 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [261359508] [2025-02-06 13:30:42,035 INFO L95 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2025-02-06 13:30:42,035 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-06 13:30:42,035 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 13:30:42,037 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 13:30:42,039 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 13:30:42,224 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 817 statements into 1 equivalence classes. [2025-02-06 13:30:42,346 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 817 of 817 statements. [2025-02-06 13:30:42,346 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-06 13:30:42,346 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 13:30:42,350 INFO L256 TraceCheckSpWp]: Trace formula consists of 1528 conjuncts, 26 conjuncts are in the unsatisfiable core [2025-02-06 13:30:42,358 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-06 13:30:42,504 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 13:30:42,504 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-06 13:30:45,614 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 13:30:45,614 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [261359508] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-06 13:30:45,614 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-06 13:30:45,614 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 17, 27] total 32 [2025-02-06 13:30:45,614 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [802212665] [2025-02-06 13:30:45,614 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-06 13:30:45,616 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 32 states [2025-02-06 13:30:45,616 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-06 13:30:45,616 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 32 interpolants. [2025-02-06 13:30:45,617 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=179, Invalid=813, Unknown=0, NotChecked=0, Total=992 [2025-02-06 13:30:45,617 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 13:30:46,084 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-06 13:30:46,084 INFO L93 Difference]: Finished difference Result 382 states and 510 transitions. [2025-02-06 13:30:46,085 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2025-02-06 13:30:46,085 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 13:30:46,086 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-06 13:30:46,088 INFO L225 Difference]: With dead ends: 382 [2025-02-06 13:30:46,088 INFO L226 Difference]: Without dead ends: 197 [2025-02-06 13:30:46,090 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 13:30:46,091 INFO L435 NwaCegarLoop]: 56 mSDtfsCounter, 173 mSDsluCounter, 227 mSDsCounter, 0 mSdLazyCounter, 651 mSolverCounterSat, 92 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 173 SdHoareTripleChecker+Valid, 283 SdHoareTripleChecker+Invalid, 743 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 92 IncrementalHoareTripleChecker+Valid, 651 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2025-02-06 13:30:46,091 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [173 Valid, 283 Invalid, 743 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [92 Valid, 651 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2025-02-06 13:30:46,091 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 197 states. [2025-02-06 13:30:46,106 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 197 to 149. [2025-02-06 13:30:46,106 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 13:30:46,108 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 149 states to 149 states and 187 transitions. [2025-02-06 13:30:46,108 INFO L78 Accepts]: Start accepts. Automaton has 149 states and 187 transitions. Word has length 817 [2025-02-06 13:30:46,109 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-06 13:30:46,109 INFO L471 AbstractCegarLoop]: Abstraction has 149 states and 187 transitions. [2025-02-06 13:30:46,109 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 13:30:46,109 INFO L276 IsEmpty]: Start isEmpty. Operand 149 states and 187 transitions. [2025-02-06 13:30:46,130 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1590 [2025-02-06 13:30:46,130 INFO L210 NwaCegarLoop]: Found error trace [2025-02-06 13:30:46,131 INFO L218 NwaCegarLoop]: trace histogram [164, 159, 133, 83, 83, 83, 83, 80, 80, 80, 80, 80, 79, 79, 79, 78, 50, 31, 1, 1, 1, 1, 1] [2025-02-06 13:30:46,141 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 13:30:46,331 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable20,19 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-06 13:30:46,331 INFO L396 AbstractCegarLoop]: === Iteration 22 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-02-06 13:30:46,332 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-06 13:30:46,332 INFO L85 PathProgramCache]: Analyzing trace with hash -297827312, now seen corresponding path program 14 times [2025-02-06 13:30:46,332 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-06 13:30:46,332 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [782830100] [2025-02-06 13:30:46,332 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-02-06 13:30:46,332 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-06 13:30:46,354 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 1589 statements into 2 equivalence classes. [2025-02-06 13:30:46,457 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 1589 of 1589 statements. [2025-02-06 13:30:46,458 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-02-06 13:30:46,458 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 13:30:49,556 INFO L134 CoverageAnalysis]: Checked inductivity of 92724 backedges. 4248 proven. 12329 refuted. 0 times theorem prover too weak. 76147 trivial. 0 not checked. [2025-02-06 13:30:49,557 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-06 13:30:49,557 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [782830100] [2025-02-06 13:30:49,557 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [782830100] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-06 13:30:49,557 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1349917472] [2025-02-06 13:30:49,557 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-02-06 13:30:49,557 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-06 13:30:49,557 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 13:30:49,559 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 13:30:49,561 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 13:30:49,817 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 1589 statements into 2 equivalence classes. [2025-02-06 13:30:50,073 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 1589 of 1589 statements. [2025-02-06 13:30:50,073 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-02-06 13:30:50,073 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 13:30:50,084 INFO L256 TraceCheckSpWp]: Trace formula consists of 2952 conjuncts, 34 conjuncts are in the unsatisfiable core [2025-02-06 13:30:50,100 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-06 13:30:50,388 INFO L134 CoverageAnalysis]: Checked inductivity of 92724 backedges. 29181 proven. 10760 refuted. 0 times theorem prover too weak. 52783 trivial. 0 not checked. [2025-02-06 13:30:50,388 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-06 13:30:54,407 INFO L134 CoverageAnalysis]: Checked inductivity of 92724 backedges. 5159 proven. 14002 refuted. 0 times theorem prover too weak. 73563 trivial. 0 not checked. [2025-02-06 13:30:54,407 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1349917472] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-06 13:30:54,407 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-06 13:30:54,407 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 21, 32] total 37 [2025-02-06 13:30:54,407 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1818076845] [2025-02-06 13:30:54,408 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-06 13:30:54,409 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 37 states [2025-02-06 13:30:54,409 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-06 13:30:54,409 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 37 interpolants. [2025-02-06 13:30:54,410 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=200, Invalid=1132, Unknown=0, NotChecked=0, Total=1332 [2025-02-06 13:30:54,410 INFO L87 Difference]: Start difference. First operand 149 states and 187 transitions. Second operand has 37 states, 37 states have (on average 5.972972972972973) internal successors, (221), 37 states have internal predecessors, (221), 32 states have call successors, (39), 5 states have call predecessors, (39), 15 states have return successors, (46), 17 states have call predecessors, (46), 29 states have call successors, (46) [2025-02-06 13:30:55,126 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-06 13:30:55,126 INFO L93 Difference]: Finished difference Result 374 states and 511 transitions. [2025-02-06 13:30:55,130 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 48 states. [2025-02-06 13:30:55,131 INFO L78 Accepts]: Start accepts. Automaton has has 37 states, 37 states have (on average 5.972972972972973) internal successors, (221), 37 states have internal predecessors, (221), 32 states have call successors, (39), 5 states have call predecessors, (39), 15 states have return successors, (46), 17 states have call predecessors, (46), 29 states have call successors, (46) Word has length 1589 [2025-02-06 13:30:55,131 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-06 13:30:55,133 INFO L225 Difference]: With dead ends: 374 [2025-02-06 13:30:55,134 INFO L226 Difference]: Without dead ends: 231 [2025-02-06 13:30:55,136 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 3254 GetRequests, 3157 SyntacticMatches, 20 SemanticMatches, 77 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1630 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=1530, Invalid=4632, Unknown=0, NotChecked=0, Total=6162 [2025-02-06 13:30:55,138 INFO L435 NwaCegarLoop]: 35 mSDtfsCounter, 457 mSDsluCounter, 194 mSDsCounter, 0 mSdLazyCounter, 458 mSolverCounterSat, 188 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 457 SdHoareTripleChecker+Valid, 229 SdHoareTripleChecker+Invalid, 646 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 188 IncrementalHoareTripleChecker+Valid, 458 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2025-02-06 13:30:55,138 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [457 Valid, 229 Invalid, 646 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [188 Valid, 458 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2025-02-06 13:30:55,139 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 231 states. [2025-02-06 13:30:55,155 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 231 to 191. [2025-02-06 13:30:55,155 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 191 states, 155 states have (on average 1.032258064516129) internal successors, (160), 152 states have internal predecessors, (160), 25 states have call successors, (25), 20 states have call predecessors, (25), 10 states have return successors, (63), 18 states have call predecessors, (63), 24 states have call successors, (63) [2025-02-06 13:30:55,157 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 191 states to 191 states and 248 transitions. [2025-02-06 13:30:55,157 INFO L78 Accepts]: Start accepts. Automaton has 191 states and 248 transitions. Word has length 1589 [2025-02-06 13:30:55,158 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-06 13:30:55,158 INFO L471 AbstractCegarLoop]: Abstraction has 191 states and 248 transitions. [2025-02-06 13:30:55,158 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 37 states, 37 states have (on average 5.972972972972973) internal successors, (221), 37 states have internal predecessors, (221), 32 states have call successors, (39), 5 states have call predecessors, (39), 15 states have return successors, (46), 17 states have call predecessors, (46), 29 states have call successors, (46) [2025-02-06 13:30:55,158 INFO L276 IsEmpty]: Start isEmpty. Operand 191 states and 248 transitions. [2025-02-06 13:30:55,164 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 910 [2025-02-06 13:30:55,164 INFO L210 NwaCegarLoop]: Found error trace [2025-02-06 13:30:55,164 INFO L218 NwaCegarLoop]: trace histogram [93, 92, 75, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 45, 29, 18, 1, 1, 1, 1, 1] [2025-02-06 13:30:55,177 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Ended with exit code 0 [2025-02-06 13:30:55,368 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable21,20 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-06 13:30:55,369 INFO L396 AbstractCegarLoop]: === Iteration 23 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-02-06 13:30:55,369 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-06 13:30:55,369 INFO L85 PathProgramCache]: Analyzing trace with hash -1979856459, now seen corresponding path program 15 times [2025-02-06 13:30:55,369 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-06 13:30:55,369 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1303510969] [2025-02-06 13:30:55,369 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-02-06 13:30:55,369 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-06 13:30:55,383 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 909 statements into 66 equivalence classes. [2025-02-06 13:30:55,421 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 41 check-sat command(s) and asserted 553 of 909 statements. [2025-02-06 13:30:55,421 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 41 check-sat command(s) [2025-02-06 13:30:55,421 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 13:30:56,000 INFO L134 CoverageAnalysis]: Checked inductivity of 30053 backedges. 4444 proven. 1382 refuted. 0 times theorem prover too weak. 24227 trivial. 0 not checked. [2025-02-06 13:30:56,001 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-06 13:30:56,001 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1303510969] [2025-02-06 13:30:56,001 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1303510969] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-06 13:30:56,001 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1210867733] [2025-02-06 13:30:56,001 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-02-06 13:30:56,001 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-06 13:30:56,001 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 13:30:56,003 INFO L229 MonitoredProcess]: Starting monitored process 21 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-02-06 13:30:56,003 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Waiting until timeout for monitored process [2025-02-06 13:30:56,252 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 909 statements into 66 equivalence classes. [2025-02-06 13:30:56,374 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 41 check-sat command(s) and asserted 553 of 909 statements. [2025-02-06 13:30:56,374 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 41 check-sat command(s) [2025-02-06 13:30:56,374 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 13:30:56,377 INFO L256 TraceCheckSpWp]: Trace formula consists of 1035 conjuncts, 20 conjuncts are in the unsatisfiable core [2025-02-06 13:30:56,386 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-06 13:30:56,522 INFO L134 CoverageAnalysis]: Checked inductivity of 30053 backedges. 4641 proven. 1482 refuted. 0 times theorem prover too weak. 23930 trivial. 0 not checked. [2025-02-06 13:30:56,523 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-06 13:30:58,282 INFO L134 CoverageAnalysis]: Checked inductivity of 30053 backedges. 4649 proven. 1545 refuted. 0 times theorem prover too weak. 23859 trivial. 0 not checked. [2025-02-06 13:30:58,282 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1210867733] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-06 13:30:58,282 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-06 13:30:58,283 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 14, 21] total 26 [2025-02-06 13:30:58,283 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1082419653] [2025-02-06 13:30:58,283 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-06 13:30:58,285 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 26 states [2025-02-06 13:30:58,286 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-06 13:30:58,286 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2025-02-06 13:30:58,287 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=124, Invalid=526, Unknown=0, NotChecked=0, Total=650 [2025-02-06 13:30:58,287 INFO L87 Difference]: Start difference. First operand 191 states and 248 transitions. Second operand has 26 states, 26 states have (on average 5.423076923076923) internal successors, (141), 26 states have internal predecessors, (141), 14 states have call successors, (24), 1 states have call predecessors, (24), 10 states have return successors, (29), 18 states have call predecessors, (29), 14 states have call successors, (29) [2025-02-06 13:30:58,698 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-06 13:30:58,699 INFO L93 Difference]: Finished difference Result 422 states and 552 transitions. [2025-02-06 13:30:58,699 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 30 states. [2025-02-06 13:30:58,699 INFO L78 Accepts]: Start accepts. Automaton has has 26 states, 26 states have (on average 5.423076923076923) internal successors, (141), 26 states have internal predecessors, (141), 14 states have call successors, (24), 1 states have call predecessors, (24), 10 states have return successors, (29), 18 states have call predecessors, (29), 14 states have call successors, (29) Word has length 909 [2025-02-06 13:30:58,700 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-06 13:30:58,702 INFO L225 Difference]: With dead ends: 422 [2025-02-06 13:30:58,703 INFO L226 Difference]: Without dead ends: 217 [2025-02-06 13:30:58,705 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 1859 GetRequests, 1804 SyntacticMatches, 10 SemanticMatches, 45 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 521 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=578, Invalid=1584, Unknown=0, NotChecked=0, Total=2162 [2025-02-06 13:30:58,706 INFO L435 NwaCegarLoop]: 40 mSDtfsCounter, 171 mSDsluCounter, 165 mSDsCounter, 0 mSdLazyCounter, 464 mSolverCounterSat, 82 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 171 SdHoareTripleChecker+Valid, 205 SdHoareTripleChecker+Invalid, 546 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 82 IncrementalHoareTripleChecker+Valid, 464 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-02-06 13:30:58,706 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [171 Valid, 205 Invalid, 546 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [82 Valid, 464 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-02-06 13:30:58,706 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 217 states. [2025-02-06 13:30:58,721 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 217 to 188. [2025-02-06 13:30:58,722 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 188 states, 152 states have (on average 1.0263157894736843) internal successors, (156), 150 states have internal predecessors, (156), 25 states have call successors, (25), 20 states have call predecessors, (25), 10 states have return successors, (52), 17 states have call predecessors, (52), 24 states have call successors, (52) [2025-02-06 13:30:58,723 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 188 states to 188 states and 233 transitions. [2025-02-06 13:30:58,724 INFO L78 Accepts]: Start accepts. Automaton has 188 states and 233 transitions. Word has length 909 [2025-02-06 13:30:58,724 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-06 13:30:58,724 INFO L471 AbstractCegarLoop]: Abstraction has 188 states and 233 transitions. [2025-02-06 13:30:58,725 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 26 states, 26 states have (on average 5.423076923076923) internal successors, (141), 26 states have internal predecessors, (141), 14 states have call successors, (24), 1 states have call predecessors, (24), 10 states have return successors, (29), 18 states have call predecessors, (29), 14 states have call successors, (29) [2025-02-06 13:30:58,725 INFO L276 IsEmpty]: Start isEmpty. Operand 188 states and 233 transitions. [2025-02-06 13:30:58,732 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1073 [2025-02-06 13:30:58,732 INFO L210 NwaCegarLoop]: Found error trace [2025-02-06 13:30:58,732 INFO L218 NwaCegarLoop]: trace histogram [110, 108, 89, 55, 55, 55, 55, 54, 54, 54, 54, 54, 54, 54, 54, 53, 34, 21, 1, 1, 1, 1, 1] [2025-02-06 13:30:58,743 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Forceful destruction successful, exit code 0 [2025-02-06 13:30:58,933 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable22,21 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-06 13:30:58,933 INFO L396 AbstractCegarLoop]: === Iteration 24 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2025-02-06 13:30:58,934 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-06 13:30:58,934 INFO L85 PathProgramCache]: Analyzing trace with hash 2004822547, now seen corresponding path program 16 times [2025-02-06 13:30:58,934 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-06 13:30:58,934 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1450319220] [2025-02-06 13:30:58,934 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-02-06 13:30:58,934 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-06 13:30:58,951 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 1072 statements into 2 equivalence classes. [2025-02-06 13:30:59,020 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) and asserted 1072 of 1072 statements. [2025-02-06 13:30:59,020 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) [2025-02-06 13:30:59,020 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 13:31:15,199 INFO L134 CoverageAnalysis]: Checked inductivity of 41934 backedges. 6686 proven. 7855 refuted. 0 times theorem prover too weak. 27393 trivial. 0 not checked. [2025-02-06 13:31:15,199 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-06 13:31:15,199 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1450319220] [2025-02-06 13:31:15,199 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1450319220] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-06 13:31:15,199 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [204374482] [2025-02-06 13:31:15,199 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-02-06 13:31:15,199 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-06 13:31:15,199 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 13:31:15,201 INFO L229 MonitoredProcess]: Starting monitored process 22 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 13:31:15,202 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (22)] Waiting until timeout for monitored process [2025-02-06 13:31:15,464 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 1072 statements into 2 equivalence classes. [2025-02-06 13:31:15,621 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) and asserted 1072 of 1072 statements. [2025-02-06 13:31:15,621 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) [2025-02-06 13:31:15,621 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 13:31:15,628 INFO L256 TraceCheckSpWp]: Trace formula consists of 1999 conjuncts, 217 conjuncts are in the unsatisfiable core [2025-02-06 13:31:15,640 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-06 13:31:16,398 INFO L134 CoverageAnalysis]: Checked inductivity of 41934 backedges. 6686 proven. 7855 refuted. 0 times theorem prover too weak. 27393 trivial. 0 not checked. [2025-02-06 13:31:16,398 INFO L312 TraceCheckSpWp]: Computing backward predicates...