./Ultimate.py --spec ../sv-benchmarks/c/properties/no-overflow.prp --file ../sv-benchmarks/c/termination-numeric/Fibonacci01-2.c --full-output --architecture 64bit -------------------------------------------------------------------------------- Checking for overflows Using default analysis Version 3061b6dc Calling Ultimate with: /root/.sdkman/candidates/java/11.0.12-open/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/termination-numeric/Fibonacci01-2.c -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Overflow-64bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate/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 14cfbc3a2ba2bfe3a03d4d1ebff24b0baf1851f06dbbd2468b59e09322e4ce16 --- Real Ultimate output --- This is Ultimate 0.2.5-tmp.dk.eval-assert-order-craig-3061b6d-m [2024-11-19 10:11:32,460 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-19 10:11:32,538 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Overflow-64bit-Automizer_Default.epf [2024-11-19 10:11:32,543 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-19 10:11:32,545 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-19 10:11:32,578 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-19 10:11:32,580 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-19 10:11:32,580 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-19 10:11:32,581 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-19 10:11:32,583 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-19 10:11:32,583 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-19 10:11:32,583 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-19 10:11:32,584 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-19 10:11:32,584 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-19 10:11:32,586 INFO L153 SettingsManager]: * Use SBE=true [2024-11-19 10:11:32,586 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-19 10:11:32,587 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-19 10:11:32,587 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-19 10:11:32,587 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-19 10:11:32,590 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-19 10:11:32,590 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-19 10:11:32,591 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-19 10:11:32,591 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-19 10:11:32,591 INFO L153 SettingsManager]: * Check absence of signed integer overflows=ASSERTandASSUME [2024-11-19 10:11:32,591 INFO L153 SettingsManager]: * Check unreachability of reach_error function=false [2024-11-19 10:11:32,592 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-19 10:11:32,592 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-19 10:11:32,592 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-19 10:11:32,593 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-19 10:11:32,593 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-19 10:11:32,593 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-19 10:11:32,593 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-19 10:11:32,594 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-19 10:11:32,594 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-19 10:11:32,594 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-19 10:11:32,595 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-19 10:11:32,595 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-19 10:11:32,596 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-19 10:11:32,596 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-19 10:11:32,597 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-19 10:11:32,597 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-19 10:11:32,598 INFO L153 SettingsManager]: * Looper check in Petri net analysis=SEMANTIC WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release 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/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 -> 14cfbc3a2ba2bfe3a03d4d1ebff24b0baf1851f06dbbd2468b59e09322e4ce16 [2024-11-19 10:11:32,859 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-19 10:11:32,884 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-19 10:11:32,887 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-19 10:11:32,888 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-19 10:11:32,889 INFO L274 PluginConnector]: CDTParser initialized [2024-11-19 10:11:32,890 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/termination-numeric/Fibonacci01-2.c [2024-11-19 10:11:34,304 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-19 10:11:34,519 INFO L384 CDTParser]: Found 1 translation units. [2024-11-19 10:11:34,519 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/termination-numeric/Fibonacci01-2.c [2024-11-19 10:11:34,528 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/7c4bdddf7/ff891aeeb90a41e1b1731f1030d36419/FLAG45cd07c9e [2024-11-19 10:11:34,916 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/7c4bdddf7/ff891aeeb90a41e1b1731f1030d36419 [2024-11-19 10:11:34,918 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-19 10:11:34,920 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-19 10:11:34,921 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-19 10:11:34,921 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-19 10:11:34,927 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-19 10:11:34,928 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 19.11 10:11:34" (1/1) ... [2024-11-19 10:11:34,929 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@65a40cf0 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 10:11:34, skipping insertion in model container [2024-11-19 10:11:34,929 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 19.11 10:11:34" (1/1) ... [2024-11-19 10:11:34,949 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-19 10:11:35,130 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-19 10:11:35,143 INFO L200 MainTranslator]: Completed pre-run [2024-11-19 10:11:35,155 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-19 10:11:35,167 INFO L204 MainTranslator]: Completed translation [2024-11-19 10:11:35,167 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 10:11:35 WrapperNode [2024-11-19 10:11:35,168 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-19 10:11:35,168 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-19 10:11:35,168 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-19 10:11:35,169 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-19 10:11:35,174 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 10:11:35" (1/1) ... [2024-11-19 10:11:35,179 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 10:11:35" (1/1) ... [2024-11-19 10:11:35,193 INFO L138 Inliner]: procedures = 13, calls = 11, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 27 [2024-11-19 10:11:35,194 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-19 10:11:35,194 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-19 10:11:35,194 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-19 10:11:35,194 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-19 10:11:35,202 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 10:11:35" (1/1) ... [2024-11-19 10:11:35,203 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 10:11:35" (1/1) ... [2024-11-19 10:11:35,204 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 10:11:35" (1/1) ... [2024-11-19 10:11:35,214 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]. [2024-11-19 10:11:35,215 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 10:11:35" (1/1) ... [2024-11-19 10:11:35,215 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 10:11:35" (1/1) ... [2024-11-19 10:11:35,217 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 10:11:35" (1/1) ... [2024-11-19 10:11:35,219 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 10:11:35" (1/1) ... [2024-11-19 10:11:35,219 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 10:11:35" (1/1) ... [2024-11-19 10:11:35,220 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 10:11:35" (1/1) ... [2024-11-19 10:11:35,221 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-19 10:11:35,222 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-19 10:11:35,222 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-19 10:11:35,223 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-19 10:11:35,223 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 10:11:35" (1/1) ... [2024-11-19 10:11:35,228 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-19 10:11:35,237 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 10:11:35,253 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2024-11-19 10:11:35,263 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2024-11-19 10:11:35,309 INFO L130 BoogieDeclarations]: Found specification of procedure fibonacci [2024-11-19 10:11:35,310 INFO L138 BoogieDeclarations]: Found implementation of procedure fibonacci [2024-11-19 10:11:35,310 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-19 10:11:35,310 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-19 10:11:35,311 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-19 10:11:35,311 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-19 10:11:35,373 INFO L238 CfgBuilder]: Building ICFG [2024-11-19 10:11:35,375 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-19 10:11:35,536 INFO L? ?]: Removed 15 outVars from TransFormulas that were not future-live. [2024-11-19 10:11:35,536 INFO L287 CfgBuilder]: Performing block encoding [2024-11-19 10:11:35,549 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-19 10:11:35,549 INFO L316 CfgBuilder]: Removed 0 assume(true) statements. [2024-11-19 10:11:35,550 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 19.11 10:11:35 BoogieIcfgContainer [2024-11-19 10:11:35,550 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-19 10:11:35,552 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-19 10:11:35,553 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-19 10:11:35,556 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-19 10:11:35,556 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 19.11 10:11:34" (1/3) ... [2024-11-19 10:11:35,557 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@447b8bb3 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 19.11 10:11:35, skipping insertion in model container [2024-11-19 10:11:35,557 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 10:11:35" (2/3) ... [2024-11-19 10:11:35,557 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@447b8bb3 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 19.11 10:11:35, skipping insertion in model container [2024-11-19 10:11:35,557 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 19.11 10:11:35" (3/3) ... [2024-11-19 10:11:35,558 INFO L112 eAbstractionObserver]: Analyzing ICFG Fibonacci01-2.c [2024-11-19 10:11:35,575 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-19 10:11:35,575 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 6 error locations. [2024-11-19 10:11:35,632 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-19 10:11:35,638 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;@77e19305, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-19 10:11:35,638 INFO L334 AbstractCegarLoop]: Starting to check reachability of 6 error locations. [2024-11-19 10:11:35,642 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) [2024-11-19 10:11:35,648 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 9 [2024-11-19 10:11:35,648 INFO L207 NwaCegarLoop]: Found error trace [2024-11-19 10:11:35,649 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 10:11:35,649 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2024-11-19 10:11:35,654 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 10:11:35,654 INFO L85 PathProgramCache]: Analyzing trace with hash 629029755, now seen corresponding path program 1 times [2024-11-19 10:11:35,661 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 10:11:35,661 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1907012170] [2024-11-19 10:11:35,662 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 10:11:35,662 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 10:11:35,745 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 10:11:35,809 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-19 10:11:35,810 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 10:11:35,810 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1907012170] [2024-11-19 10:11:35,811 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1907012170] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-19 10:11:35,811 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-19 10:11:35,811 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-11-19 10:11:35,812 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1369640036] [2024-11-19 10:11:35,813 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-19 10:11:35,817 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2024-11-19 10:11:35,817 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 10:11:35,845 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2024-11-19 10:11:35,846 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-11-19 10:11:35,848 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) [2024-11-19 10:11:35,890 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 10:11:35,890 INFO L93 Difference]: Finished difference Result 37 states and 43 transitions. [2024-11-19 10:11:35,892 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2024-11-19 10:11:35,914 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 [2024-11-19 10:11:35,915 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-19 10:11:35,921 INFO L225 Difference]: With dead ends: 37 [2024-11-19 10:11:35,921 INFO L226 Difference]: Without dead ends: 25 [2024-11-19 10:11:35,924 INFO L431 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 [2024-11-19 10:11:35,927 INFO L432 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 [2024-11-19 10:11:35,928 INFO L433 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] [2024-11-19 10:11:35,953 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 25 states. [2024-11-19 10:11:35,969 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 25 to 23. [2024-11-19 10:11:35,970 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) [2024-11-19 10:11:35,972 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 23 states to 23 states and 26 transitions. [2024-11-19 10:11:35,974 INFO L78 Accepts]: Start accepts. Automaton has 23 states and 26 transitions. Word has length 8 [2024-11-19 10:11:35,975 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-19 10:11:35,975 INFO L471 AbstractCegarLoop]: Abstraction has 23 states and 26 transitions. [2024-11-19 10:11:35,975 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) [2024-11-19 10:11:35,976 INFO L276 IsEmpty]: Start isEmpty. Operand 23 states and 26 transitions. [2024-11-19 10:11:35,977 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 10 [2024-11-19 10:11:35,977 INFO L207 NwaCegarLoop]: Found error trace [2024-11-19 10:11:35,977 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 10:11:35,977 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-19 10:11:35,979 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2024-11-19 10:11:35,980 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 10:11:35,980 INFO L85 PathProgramCache]: Analyzing trace with hash -1974914033, now seen corresponding path program 1 times [2024-11-19 10:11:35,980 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 10:11:35,980 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [970077581] [2024-11-19 10:11:35,980 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 10:11:35,981 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 10:11:35,996 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 10:11:36,062 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-19 10:11:36,062 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 10:11:36,062 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [970077581] [2024-11-19 10:11:36,063 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [970077581] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-19 10:11:36,063 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-19 10:11:36,063 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2024-11-19 10:11:36,064 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2121501886] [2024-11-19 10:11:36,064 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-19 10:11:36,067 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-19 10:11:36,068 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 10:11:36,068 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-19 10:11:36,068 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-19 10:11:36,069 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) [2024-11-19 10:11:36,152 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 10:11:36,152 INFO L93 Difference]: Finished difference Result 25 states and 29 transitions. [2024-11-19 10:11:36,153 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-19 10:11:36,153 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 [2024-11-19 10:11:36,153 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-19 10:11:36,154 INFO L225 Difference]: With dead ends: 25 [2024-11-19 10:11:36,154 INFO L226 Difference]: Without dead ends: 23 [2024-11-19 10:11:36,155 INFO L431 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 [2024-11-19 10:11:36,156 INFO L432 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 [2024-11-19 10:11:36,158 INFO L433 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] [2024-11-19 10:11:36,160 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 23 states. [2024-11-19 10:11:36,167 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 23 to 21. [2024-11-19 10:11:36,168 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) [2024-11-19 10:11:36,169 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 21 states to 21 states and 24 transitions. [2024-11-19 10:11:36,170 INFO L78 Accepts]: Start accepts. Automaton has 21 states and 24 transitions. Word has length 9 [2024-11-19 10:11:36,171 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-19 10:11:36,171 INFO L471 AbstractCegarLoop]: Abstraction has 21 states and 24 transitions. [2024-11-19 10:11:36,171 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) [2024-11-19 10:11:36,171 INFO L276 IsEmpty]: Start isEmpty. Operand 21 states and 24 transitions. [2024-11-19 10:11:36,172 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2024-11-19 10:11:36,173 INFO L207 NwaCegarLoop]: Found error trace [2024-11-19 10:11:36,173 INFO L215 NwaCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 10:11:36,173 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-11-19 10:11:36,174 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting fibonacciErr4ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2024-11-19 10:11:36,174 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 10:11:36,176 INFO L85 PathProgramCache]: Analyzing trace with hash 1558234811, now seen corresponding path program 1 times [2024-11-19 10:11:36,176 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 10:11:36,176 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1533637284] [2024-11-19 10:11:36,177 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 10:11:36,177 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 10:11:36,206 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 10:11:36,355 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2024-11-19 10:11:36,355 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 10:11:36,356 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1533637284] [2024-11-19 10:11:36,356 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1533637284] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-19 10:11:36,356 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-19 10:11:36,356 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2024-11-19 10:11:36,356 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1605305391] [2024-11-19 10:11:36,356 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-19 10:11:36,357 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-19 10:11:36,357 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 10:11:36,358 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-19 10:11:36,360 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2024-11-19 10:11:36,360 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) [2024-11-19 10:11:36,409 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 10:11:36,409 INFO L93 Difference]: Finished difference Result 35 states and 43 transitions. [2024-11-19 10:11:36,411 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-19 10:11:36,411 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 [2024-11-19 10:11:36,411 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-19 10:11:36,412 INFO L225 Difference]: With dead ends: 35 [2024-11-19 10:11:36,412 INFO L226 Difference]: Without dead ends: 33 [2024-11-19 10:11:36,413 INFO L431 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 [2024-11-19 10:11:36,414 INFO L432 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 [2024-11-19 10:11:36,415 INFO L433 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] [2024-11-19 10:11:36,416 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 33 states. [2024-11-19 10:11:36,421 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 33 to 30. [2024-11-19 10:11:36,421 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) [2024-11-19 10:11:36,423 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 30 states to 30 states and 36 transitions. [2024-11-19 10:11:36,423 INFO L78 Accepts]: Start accepts. Automaton has 30 states and 36 transitions. Word has length 24 [2024-11-19 10:11:36,424 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-19 10:11:36,424 INFO L471 AbstractCegarLoop]: Abstraction has 30 states and 36 transitions. [2024-11-19 10:11:36,424 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) [2024-11-19 10:11:36,424 INFO L276 IsEmpty]: Start isEmpty. Operand 30 states and 36 transitions. [2024-11-19 10:11:36,425 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2024-11-19 10:11:36,426 INFO L207 NwaCegarLoop]: Found error trace [2024-11-19 10:11:36,426 INFO L215 NwaCegarLoop]: trace histogram [4, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 10:11:36,426 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2024-11-19 10:11:36,427 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting fibonacciErr4ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2024-11-19 10:11:36,430 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 10:11:36,430 INFO L85 PathProgramCache]: Analyzing trace with hash 171916151, now seen corresponding path program 1 times [2024-11-19 10:11:36,430 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 10:11:36,430 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [644866037] [2024-11-19 10:11:36,431 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 10:11:36,431 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 10:11:36,460 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 10:11:36,611 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2024-11-19 10:11:36,611 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 10:11:36,611 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [644866037] [2024-11-19 10:11:36,611 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [644866037] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-19 10:11:36,611 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [294137059] [2024-11-19 10:11:36,612 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 10:11:36,612 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 10:11:36,612 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 10:11:36,615 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-19 10:11:36,617 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-11-19 10:11:36,668 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 10:11:36,670 INFO L255 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-11-19 10:11:36,675 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 10:11:36,795 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 6 proven. 3 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2024-11-19 10:11:36,798 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-19 10:11:36,977 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 6 proven. 3 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2024-11-19 10:11:36,980 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [294137059] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-19 10:11:36,980 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-19 10:11:36,980 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 7, 7] total 15 [2024-11-19 10:11:36,981 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [70714879] [2024-11-19 10:11:36,981 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-19 10:11:36,981 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2024-11-19 10:11:36,981 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 10:11:36,985 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2024-11-19 10:11:36,986 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=35, Invalid=175, Unknown=0, NotChecked=0, Total=210 [2024-11-19 10:11:36,986 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) [2024-11-19 10:11:37,257 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 10:11:37,258 INFO L93 Difference]: Finished difference Result 91 states and 129 transitions. [2024-11-19 10:11:37,258 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2024-11-19 10:11:37,258 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 [2024-11-19 10:11:37,259 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-19 10:11:37,260 INFO L225 Difference]: With dead ends: 91 [2024-11-19 10:11:37,260 INFO L226 Difference]: Without dead ends: 65 [2024-11-19 10:11:37,261 INFO L431 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 [2024-11-19 10:11:37,263 INFO L432 NwaCegarLoop]: 13 mSDtfsCounter, 134 mSDsluCounter, 79 mSDsCounter, 0 mSdLazyCounter, 161 mSolverCounterSat, 64 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 134 SdHoareTripleChecker+Valid, 92 SdHoareTripleChecker+Invalid, 225 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 64 IncrementalHoareTripleChecker+Valid, 161 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-19 10:11:37,263 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [134 Valid, 92 Invalid, 225 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [64 Valid, 161 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-19 10:11:37,264 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 65 states. [2024-11-19 10:11:37,278 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 65 to 53. [2024-11-19 10:11:37,278 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) [2024-11-19 10:11:37,280 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 53 states to 53 states and 68 transitions. [2024-11-19 10:11:37,280 INFO L78 Accepts]: Start accepts. Automaton has 53 states and 68 transitions. Word has length 31 [2024-11-19 10:11:37,281 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-19 10:11:37,281 INFO L471 AbstractCegarLoop]: Abstraction has 53 states and 68 transitions. [2024-11-19 10:11:37,281 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) [2024-11-19 10:11:37,281 INFO L276 IsEmpty]: Start isEmpty. Operand 53 states and 68 transitions. [2024-11-19 10:11:37,284 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2024-11-19 10:11:37,284 INFO L207 NwaCegarLoop]: Found error trace [2024-11-19 10:11:37,284 INFO L215 NwaCegarLoop]: trace histogram [4, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 10:11:37,303 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2024-11-19 10:11:37,485 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 10:11:37,486 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting fibonacciErr4ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2024-11-19 10:11:37,486 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 10:11:37,486 INFO L85 PathProgramCache]: Analyzing trace with hash 170784145, now seen corresponding path program 2 times [2024-11-19 10:11:37,486 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 10:11:37,487 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [722072925] [2024-11-19 10:11:37,487 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-19 10:11:37,487 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 10:11:37,501 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-19 10:11:37,501 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-19 10:11:37,613 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2024-11-19 10:11:37,614 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 10:11:37,614 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [722072925] [2024-11-19 10:11:37,614 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [722072925] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-19 10:11:37,614 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1864517494] [2024-11-19 10:11:37,615 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-19 10:11:37,615 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 10:11:37,615 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 10:11:37,617 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-19 10:11:37,621 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-11-19 10:11:37,658 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-19 10:11:37,658 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-19 10:11:37,660 INFO L255 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 4 conjuncts are in the unsatisfiable core [2024-11-19 10:11:37,662 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 10:11:37,700 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2024-11-19 10:11:37,700 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-19 10:11:37,700 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1864517494] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-19 10:11:37,701 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-19 10:11:37,701 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [5] total 7 [2024-11-19 10:11:37,701 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [69897845] [2024-11-19 10:11:37,702 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-19 10:11:37,703 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-19 10:11:37,703 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 10:11:37,703 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-19 10:11:37,704 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=38, Unknown=0, NotChecked=0, Total=56 [2024-11-19 10:11:37,704 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) [2024-11-19 10:11:37,733 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 10:11:37,734 INFO L93 Difference]: Finished difference Result 60 states and 76 transitions. [2024-11-19 10:11:37,734 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-19 10:11:37,734 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 31 [2024-11-19 10:11:37,735 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-19 10:11:37,736 INFO L225 Difference]: With dead ends: 60 [2024-11-19 10:11:37,737 INFO L226 Difference]: Without dead ends: 59 [2024-11-19 10:11:37,737 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 35 GetRequests, 28 SyntacticMatches, 1 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=18, Invalid=38, Unknown=0, NotChecked=0, Total=56 [2024-11-19 10:11:37,738 INFO L432 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 [2024-11-19 10:11:37,738 INFO L433 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] [2024-11-19 10:11:37,739 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 59 states. [2024-11-19 10:11:37,756 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 59 to 55. [2024-11-19 10:11:37,756 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) [2024-11-19 10:11:37,757 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 55 states to 55 states and 70 transitions. [2024-11-19 10:11:37,758 INFO L78 Accepts]: Start accepts. Automaton has 55 states and 70 transitions. Word has length 31 [2024-11-19 10:11:37,758 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-19 10:11:37,758 INFO L471 AbstractCegarLoop]: Abstraction has 55 states and 70 transitions. [2024-11-19 10:11:37,761 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) [2024-11-19 10:11:37,761 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 70 transitions. [2024-11-19 10:11:37,762 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2024-11-19 10:11:37,762 INFO L207 NwaCegarLoop]: Found error trace [2024-11-19 10:11:37,762 INFO L215 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] [2024-11-19 10:11:37,777 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2024-11-19 10:11:37,963 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 10:11:37,963 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting fibonacciErr5ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2024-11-19 10:11:37,964 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 10:11:37,964 INFO L85 PathProgramCache]: Analyzing trace with hash 999341253, now seen corresponding path program 1 times [2024-11-19 10:11:37,964 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 10:11:37,964 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1002100213] [2024-11-19 10:11:37,964 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 10:11:37,965 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 10:11:37,973 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 10:11:38,038 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2024-11-19 10:11:38,039 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 10:11:38,039 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1002100213] [2024-11-19 10:11:38,039 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1002100213] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-19 10:11:38,039 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1280615059] [2024-11-19 10:11:38,039 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 10:11:38,039 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 10:11:38,039 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 10:11:38,041 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-19 10:11:38,042 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-11-19 10:11:38,080 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 10:11:38,081 INFO L255 TraceCheckSpWp]: Trace formula consists of 78 conjuncts, 5 conjuncts are in the unsatisfiable core [2024-11-19 10:11:38,082 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 10:11:38,148 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2024-11-19 10:11:38,148 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-19 10:11:38,148 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1280615059] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-19 10:11:38,148 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-19 10:11:38,148 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [5] total 9 [2024-11-19 10:11:38,148 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [504181327] [2024-11-19 10:11:38,149 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-19 10:11:38,149 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-19 10:11:38,150 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 10:11:38,150 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-19 10:11:38,150 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=64, Unknown=0, NotChecked=0, Total=90 [2024-11-19 10:11:38,150 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) [2024-11-19 10:11:38,191 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 10:11:38,191 INFO L93 Difference]: Finished difference Result 82 states and 117 transitions. [2024-11-19 10:11:38,193 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-19 10:11:38,194 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 [2024-11-19 10:11:38,194 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-19 10:11:38,195 INFO L225 Difference]: With dead ends: 82 [2024-11-19 10:11:38,195 INFO L226 Difference]: Without dead ends: 81 [2024-11-19 10:11:38,196 INFO L431 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 [2024-11-19 10:11:38,197 INFO L432 NwaCegarLoop]: 18 mSDtfsCounter, 2 mSDsluCounter, 52 mSDsCounter, 0 mSdLazyCounter, 28 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 70 SdHoareTripleChecker+Invalid, 29 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 28 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-19 10:11:38,199 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 70 Invalid, 29 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 28 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-19 10:11:38,200 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 81 states. [2024-11-19 10:11:38,221 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 81 to 64. [2024-11-19 10:11:38,221 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) [2024-11-19 10:11:38,223 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 64 states to 64 states and 87 transitions. [2024-11-19 10:11:38,223 INFO L78 Accepts]: Start accepts. Automaton has 64 states and 87 transitions. Word has length 32 [2024-11-19 10:11:38,223 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-19 10:11:38,223 INFO L471 AbstractCegarLoop]: Abstraction has 64 states and 87 transitions. [2024-11-19 10:11:38,223 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) [2024-11-19 10:11:38,223 INFO L276 IsEmpty]: Start isEmpty. Operand 64 states and 87 transitions. [2024-11-19 10:11:38,225 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 53 [2024-11-19 10:11:38,225 INFO L207 NwaCegarLoop]: Found error trace [2024-11-19 10:11:38,225 INFO L215 NwaCegarLoop]: trace histogram [6, 5, 4, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 10:11:38,242 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2024-11-19 10:11:38,429 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 10:11:38,430 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting fibonacciErr5ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2024-11-19 10:11:38,430 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 10:11:38,431 INFO L85 PathProgramCache]: Analyzing trace with hash 1613174786, now seen corresponding path program 1 times [2024-11-19 10:11:38,431 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 10:11:38,431 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2117969711] [2024-11-19 10:11:38,431 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 10:11:38,431 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 10:11:38,452 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 10:11:38,635 INFO L134 CoverageAnalysis]: Checked inductivity of 68 backedges. 2 proven. 15 refuted. 0 times theorem prover too weak. 51 trivial. 0 not checked. [2024-11-19 10:11:38,635 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 10:11:38,635 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2117969711] [2024-11-19 10:11:38,635 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2117969711] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-19 10:11:38,635 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1183739943] [2024-11-19 10:11:38,635 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 10:11:38,635 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 10:11:38,636 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 10:11:38,639 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-19 10:11:38,641 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-11-19 10:11:38,685 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 10:11:38,686 INFO L255 TraceCheckSpWp]: Trace formula consists of 115 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-11-19 10:11:38,688 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 10:11:38,784 INFO L134 CoverageAnalysis]: Checked inductivity of 68 backedges. 2 proven. 7 refuted. 0 times theorem prover too weak. 59 trivial. 0 not checked. [2024-11-19 10:11:38,785 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-19 10:11:38,965 INFO L134 CoverageAnalysis]: Checked inductivity of 68 backedges. 6 proven. 7 refuted. 0 times theorem prover too weak. 55 trivial. 0 not checked. [2024-11-19 10:11:38,966 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1183739943] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-19 10:11:38,966 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-19 10:11:38,966 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 6, 7] total 15 [2024-11-19 10:11:38,966 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [72824342] [2024-11-19 10:11:38,967 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-19 10:11:38,967 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2024-11-19 10:11:38,967 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 10:11:38,968 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2024-11-19 10:11:38,968 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=62, Invalid=178, Unknown=0, NotChecked=0, Total=240 [2024-11-19 10:11:38,968 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) [2024-11-19 10:11:39,175 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 10:11:39,175 INFO L93 Difference]: Finished difference Result 141 states and 217 transitions. [2024-11-19 10:11:39,175 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2024-11-19 10:11:39,176 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 52 [2024-11-19 10:11:39,176 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-19 10:11:39,178 INFO L225 Difference]: With dead ends: 141 [2024-11-19 10:11:39,179 INFO L226 Difference]: Without dead ends: 139 [2024-11-19 10:11:39,179 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 117 GetRequests, 95 SyntacticMatches, 2 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 110 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=126, Invalid=336, Unknown=0, NotChecked=0, Total=462 [2024-11-19 10:11:39,180 INFO L432 NwaCegarLoop]: 25 mSDtfsCounter, 14 mSDsluCounter, 112 mSDsCounter, 0 mSdLazyCounter, 121 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 20 SdHoareTripleChecker+Valid, 137 SdHoareTripleChecker+Invalid, 126 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 121 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-19 10:11:39,180 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [20 Valid, 137 Invalid, 126 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 121 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-19 10:11:39,181 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 139 states. [2024-11-19 10:11:39,196 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 139 to 98. [2024-11-19 10:11:39,197 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) [2024-11-19 10:11:39,201 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 98 states to 98 states and 159 transitions. [2024-11-19 10:11:39,201 INFO L78 Accepts]: Start accepts. Automaton has 98 states and 159 transitions. Word has length 52 [2024-11-19 10:11:39,201 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-19 10:11:39,202 INFO L471 AbstractCegarLoop]: Abstraction has 98 states and 159 transitions. [2024-11-19 10:11:39,202 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) [2024-11-19 10:11:39,202 INFO L276 IsEmpty]: Start isEmpty. Operand 98 states and 159 transitions. [2024-11-19 10:11:39,207 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 83 [2024-11-19 10:11:39,207 INFO L207 NwaCegarLoop]: Found error trace [2024-11-19 10:11:39,208 INFO L215 NwaCegarLoop]: trace histogram [9, 8, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 1, 1, 1, 1, 1, 1] [2024-11-19 10:11:39,223 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2024-11-19 10:11:39,408 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 10:11:39,408 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting fibonacciErr4ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2024-11-19 10:11:39,409 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 10:11:39,409 INFO L85 PathProgramCache]: Analyzing trace with hash -1355362734, now seen corresponding path program 1 times [2024-11-19 10:11:39,409 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 10:11:39,409 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1277506437] [2024-11-19 10:11:39,409 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 10:11:39,409 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 10:11:39,432 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 10:11:39,632 INFO L134 CoverageAnalysis]: Checked inductivity of 195 backedges. 38 proven. 80 refuted. 0 times theorem prover too weak. 77 trivial. 0 not checked. [2024-11-19 10:11:39,633 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 10:11:39,633 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1277506437] [2024-11-19 10:11:39,634 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1277506437] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-19 10:11:39,636 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [947098395] [2024-11-19 10:11:39,637 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 10:11:39,637 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 10:11:39,637 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 10:11:39,639 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-19 10:11:39,645 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2024-11-19 10:11:39,699 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 10:11:39,700 INFO L255 TraceCheckSpWp]: Trace formula consists of 172 conjuncts, 10 conjuncts are in the unsatisfiable core [2024-11-19 10:11:39,702 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 10:11:39,798 INFO L134 CoverageAnalysis]: Checked inductivity of 195 backedges. 50 proven. 84 refuted. 0 times theorem prover too weak. 61 trivial. 0 not checked. [2024-11-19 10:11:39,799 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-19 10:11:40,152 INFO L134 CoverageAnalysis]: Checked inductivity of 195 backedges. 50 proven. 87 refuted. 0 times theorem prover too weak. 58 trivial. 0 not checked. [2024-11-19 10:11:40,152 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [947098395] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-19 10:11:40,153 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-19 10:11:40,153 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 9, 11] total 16 [2024-11-19 10:11:40,153 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [127365347] [2024-11-19 10:11:40,153 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-19 10:11:40,154 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2024-11-19 10:11:40,154 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 10:11:40,155 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2024-11-19 10:11:40,155 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=53, Invalid=187, Unknown=0, NotChecked=0, Total=240 [2024-11-19 10:11:40,155 INFO L87 Difference]: Start difference. First operand 98 states and 159 transitions. Second operand has 16 states, 16 states have (on average 5.0625) internal successors, (81), 16 states have internal predecessors, (81), 10 states have call successors, (14), 1 states have call predecessors, (14), 5 states have return successors, (14), 7 states have call predecessors, (14), 10 states have call successors, (14) [2024-11-19 10:11:40,331 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 10:11:40,331 INFO L93 Difference]: Finished difference Result 174 states and 299 transitions. [2024-11-19 10:11:40,332 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2024-11-19 10:11:40,332 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 16 states have (on average 5.0625) internal successors, (81), 16 states have internal predecessors, (81), 10 states have call successors, (14), 1 states have call predecessors, (14), 5 states have return successors, (14), 7 states have call predecessors, (14), 10 states have call successors, (14) Word has length 82 [2024-11-19 10:11:40,333 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-19 10:11:40,334 INFO L225 Difference]: With dead ends: 174 [2024-11-19 10:11:40,334 INFO L226 Difference]: Without dead ends: 80 [2024-11-19 10:11:40,337 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 184 GetRequests, 157 SyntacticMatches, 5 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 73 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=164, Invalid=388, Unknown=0, NotChecked=0, Total=552 [2024-11-19 10:11:40,337 INFO L432 NwaCegarLoop]: 16 mSDtfsCounter, 103 mSDsluCounter, 59 mSDsCounter, 0 mSdLazyCounter, 120 mSolverCounterSat, 50 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 103 SdHoareTripleChecker+Valid, 75 SdHoareTripleChecker+Invalid, 170 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 50 IncrementalHoareTripleChecker+Valid, 120 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-19 10:11:40,338 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [103 Valid, 75 Invalid, 170 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [50 Valid, 120 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-19 10:11:40,338 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 80 states. [2024-11-19 10:11:40,345 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 80 to 70. [2024-11-19 10:11:40,345 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 70 states, 55 states have (on average 1.1090909090909091) internal successors, (61), 53 states have internal predecessors, (61), 7 states have call successors, (7), 4 states have call predecessors, (7), 6 states have return successors, (26), 12 states have call predecessors, (26), 6 states have call successors, (26) [2024-11-19 10:11:40,346 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 70 states to 70 states and 94 transitions. [2024-11-19 10:11:40,346 INFO L78 Accepts]: Start accepts. Automaton has 70 states and 94 transitions. Word has length 82 [2024-11-19 10:11:40,347 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-19 10:11:40,347 INFO L471 AbstractCegarLoop]: Abstraction has 70 states and 94 transitions. [2024-11-19 10:11:40,347 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 16 states have (on average 5.0625) internal successors, (81), 16 states have internal predecessors, (81), 10 states have call successors, (14), 1 states have call predecessors, (14), 5 states have return successors, (14), 7 states have call predecessors, (14), 10 states have call successors, (14) [2024-11-19 10:11:40,347 INFO L276 IsEmpty]: Start isEmpty. Operand 70 states and 94 transitions. [2024-11-19 10:11:40,349 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 129 [2024-11-19 10:11:40,349 INFO L207 NwaCegarLoop]: Found error trace [2024-11-19 10:11:40,349 INFO L215 NwaCegarLoop]: trace histogram [14, 12, 10, 7, 7, 7, 7, 6, 6, 6, 6, 6, 6, 6, 5, 5, 4, 3, 1, 1, 1, 1, 1] [2024-11-19 10:11:40,365 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2024-11-19 10:11:40,552 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 10:11:40,553 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting fibonacciErr4ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2024-11-19 10:11:40,553 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 10:11:40,553 INFO L85 PathProgramCache]: Analyzing trace with hash -195722252, now seen corresponding path program 2 times [2024-11-19 10:11:40,554 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 10:11:40,554 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1355851914] [2024-11-19 10:11:40,554 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-19 10:11:40,554 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 10:11:40,580 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-19 10:11:40,580 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-19 10:11:40,723 INFO L134 CoverageAnalysis]: Checked inductivity of 522 backedges. 55 proven. 134 refuted. 0 times theorem prover too weak. 333 trivial. 0 not checked. [2024-11-19 10:11:40,723 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 10:11:40,723 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1355851914] [2024-11-19 10:11:40,724 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1355851914] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-19 10:11:40,724 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [833006560] [2024-11-19 10:11:40,724 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-19 10:11:40,724 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 10:11:40,724 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 10:11:40,726 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-19 10:11:40,728 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2024-11-19 10:11:40,795 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-19 10:11:40,796 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-19 10:11:40,797 INFO L255 TraceCheckSpWp]: Trace formula consists of 256 conjuncts, 8 conjuncts are in the unsatisfiable core [2024-11-19 10:11:40,800 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 10:11:40,871 INFO L134 CoverageAnalysis]: Checked inductivity of 522 backedges. 300 proven. 15 refuted. 0 times theorem prover too weak. 207 trivial. 0 not checked. [2024-11-19 10:11:40,872 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-19 10:11:41,202 INFO L134 CoverageAnalysis]: Checked inductivity of 522 backedges. 58 proven. 166 refuted. 0 times theorem prover too weak. 298 trivial. 0 not checked. [2024-11-19 10:11:41,203 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [833006560] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-19 10:11:41,203 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-19 10:11:41,204 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 8, 9] total 14 [2024-11-19 10:11:41,204 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2045754380] [2024-11-19 10:11:41,204 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-19 10:11:41,204 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2024-11-19 10:11:41,205 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 10:11:41,205 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2024-11-19 10:11:41,206 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=47, Invalid=135, Unknown=0, NotChecked=0, Total=182 [2024-11-19 10:11:41,206 INFO L87 Difference]: Start difference. First operand 70 states and 94 transitions. Second operand has 14 states, 14 states have (on average 5.0) internal successors, (70), 14 states have internal predecessors, (70), 7 states have call successors, (12), 2 states have call predecessors, (12), 5 states have return successors, (13), 5 states have call predecessors, (13), 7 states have call successors, (13) [2024-11-19 10:11:41,310 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 10:11:41,310 INFO L93 Difference]: Finished difference Result 129 states and 179 transitions. [2024-11-19 10:11:41,311 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2024-11-19 10:11:41,311 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 128 [2024-11-19 10:11:41,311 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-19 10:11:41,312 INFO L225 Difference]: With dead ends: 129 [2024-11-19 10:11:41,313 INFO L226 Difference]: Without dead ends: 63 [2024-11-19 10:11:41,314 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 268 GetRequests, 248 SyntacticMatches, 4 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 55 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=96, Invalid=210, Unknown=0, NotChecked=0, Total=306 [2024-11-19 10:11:41,314 INFO L432 NwaCegarLoop]: 22 mSDtfsCounter, 32 mSDsluCounter, 50 mSDsCounter, 0 mSdLazyCounter, 90 mSolverCounterSat, 12 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 32 SdHoareTripleChecker+Valid, 72 SdHoareTripleChecker+Invalid, 102 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 90 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-19 10:11:41,315 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [32 Valid, 72 Invalid, 102 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 90 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-19 10:11:41,316 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 63 states. [2024-11-19 10:11:41,324 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 63 to 61. [2024-11-19 10:11:41,327 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 61 states, 48 states have (on average 1.1041666666666667) internal successors, (53), 46 states have internal predecessors, (53), 6 states have call successors, (6), 4 states have call predecessors, (6), 5 states have return successors, (14), 10 states have call predecessors, (14), 5 states have call successors, (14) [2024-11-19 10:11:41,328 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 61 states to 61 states and 73 transitions. [2024-11-19 10:11:41,328 INFO L78 Accepts]: Start accepts. Automaton has 61 states and 73 transitions. Word has length 128 [2024-11-19 10:11:41,329 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-19 10:11:41,329 INFO L471 AbstractCegarLoop]: Abstraction has 61 states and 73 transitions. [2024-11-19 10:11:41,329 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) [2024-11-19 10:11:41,329 INFO L276 IsEmpty]: Start isEmpty. Operand 61 states and 73 transitions. [2024-11-19 10:11:41,330 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 131 [2024-11-19 10:11:41,332 INFO L207 NwaCegarLoop]: Found error trace [2024-11-19 10:11:41,332 INFO L215 NwaCegarLoop]: trace histogram [14, 12, 12, 7, 7, 7, 7, 6, 6, 6, 6, 6, 6, 6, 5, 5, 5, 2, 1, 1, 1, 1, 1] [2024-11-19 10:11:41,349 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2024-11-19 10:11:41,533 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 10:11:41,533 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting fibonacciErr4ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2024-11-19 10:11:41,534 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 10:11:41,534 INFO L85 PathProgramCache]: Analyzing trace with hash 1731852194, now seen corresponding path program 3 times [2024-11-19 10:11:41,534 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 10:11:41,534 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1044500331] [2024-11-19 10:11:41,534 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-19 10:11:41,534 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 10:11:41,552 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2024-11-19 10:11:41,552 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-19 10:11:41,661 INFO L134 CoverageAnalysis]: Checked inductivity of 543 backedges. 206 proven. 18 refuted. 0 times theorem prover too weak. 319 trivial. 0 not checked. [2024-11-19 10:11:41,661 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 10:11:41,661 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1044500331] [2024-11-19 10:11:41,662 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1044500331] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-19 10:11:41,662 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [785428298] [2024-11-19 10:11:41,662 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-19 10:11:41,662 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 10:11:41,662 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 10:11:41,664 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-19 10:11:41,665 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2024-11-19 10:11:41,718 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2024-11-19 10:11:41,719 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-19 10:11:41,720 INFO L255 TraceCheckSpWp]: Trace formula consists of 150 conjuncts, 8 conjuncts are in the unsatisfiable core [2024-11-19 10:11:41,723 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 10:11:41,776 INFO L134 CoverageAnalysis]: Checked inductivity of 543 backedges. 203 proven. 21 refuted. 0 times theorem prover too weak. 319 trivial. 0 not checked. [2024-11-19 10:11:41,776 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-19 10:11:42,083 INFO L134 CoverageAnalysis]: Checked inductivity of 543 backedges. 203 proven. 22 refuted. 0 times theorem prover too weak. 318 trivial. 0 not checked. [2024-11-19 10:11:42,083 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [785428298] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-19 10:11:42,083 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-19 10:11:42,083 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 9] total 12 [2024-11-19 10:11:42,084 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [856977730] [2024-11-19 10:11:42,084 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-19 10:11:42,084 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2024-11-19 10:11:42,084 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 10:11:42,085 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2024-11-19 10:11:42,085 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=35, Invalid=97, Unknown=0, NotChecked=0, Total=132 [2024-11-19 10:11:42,090 INFO L87 Difference]: Start difference. First operand 61 states and 73 transitions. Second operand has 12 states, 12 states have (on average 5.0) internal successors, (60), 12 states have internal predecessors, (60), 4 states have call successors, (8), 1 states have call predecessors, (8), 5 states have return successors, (9), 6 states have call predecessors, (9), 4 states have call successors, (9) [2024-11-19 10:11:42,195 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 10:11:42,196 INFO L93 Difference]: Finished difference Result 114 states and 140 transitions. [2024-11-19 10:11:42,200 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-19 10:11:42,200 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 5.0) internal successors, (60), 12 states have internal predecessors, (60), 4 states have call successors, (8), 1 states have call predecessors, (8), 5 states have return successors, (9), 6 states have call predecessors, (9), 4 states have call successors, (9) Word has length 130 [2024-11-19 10:11:42,201 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-19 10:11:42,203 INFO L225 Difference]: With dead ends: 114 [2024-11-19 10:11:42,203 INFO L226 Difference]: Without dead ends: 59 [2024-11-19 10:11:42,204 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 272 GetRequests, 254 SyntacticMatches, 4 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 30 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=74, Invalid=166, Unknown=0, NotChecked=0, Total=240 [2024-11-19 10:11:42,204 INFO L432 NwaCegarLoop]: 26 mSDtfsCounter, 35 mSDsluCounter, 59 mSDsCounter, 0 mSdLazyCounter, 95 mSolverCounterSat, 12 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 35 SdHoareTripleChecker+Valid, 85 SdHoareTripleChecker+Invalid, 107 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 95 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-19 10:11:42,207 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [35 Valid, 85 Invalid, 107 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 95 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-19 10:11:42,208 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 59 states. [2024-11-19 10:11:42,214 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 59 to 57. [2024-11-19 10:11:42,214 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 57 states, 44 states have (on average 1.1136363636363635) internal successors, (49), 44 states have internal predecessors, (49), 6 states have call successors, (6), 4 states have call predecessors, (6), 5 states have return successors, (12), 8 states have call predecessors, (12), 5 states have call successors, (12) [2024-11-19 10:11:42,215 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 57 states to 57 states and 67 transitions. [2024-11-19 10:11:42,215 INFO L78 Accepts]: Start accepts. Automaton has 57 states and 67 transitions. Word has length 130 [2024-11-19 10:11:42,216 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-19 10:11:42,216 INFO L471 AbstractCegarLoop]: Abstraction has 57 states and 67 transitions. [2024-11-19 10:11:42,216 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) [2024-11-19 10:11:42,216 INFO L276 IsEmpty]: Start isEmpty. Operand 57 states and 67 transitions. [2024-11-19 10:11:42,218 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 139 [2024-11-19 10:11:42,218 INFO L207 NwaCegarLoop]: Found error trace [2024-11-19 10:11:42,218 INFO L215 NwaCegarLoop]: trace histogram [15, 13, 12, 7, 7, 7, 7, 7, 7, 7, 7, 7, 6, 6, 5, 5, 5, 3, 1, 1, 1, 1, 1] [2024-11-19 10:11:42,235 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2024-11-19 10:11:42,422 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 10:11:42,423 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting fibonacciErr4ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2024-11-19 10:11:42,423 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 10:11:42,423 INFO L85 PathProgramCache]: Analyzing trace with hash 293946725, now seen corresponding path program 4 times [2024-11-19 10:11:42,423 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 10:11:42,423 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1181803623] [2024-11-19 10:11:42,423 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-19 10:11:42,424 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 10:11:42,441 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-19 10:11:42,444 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-19 10:11:42,594 INFO L134 CoverageAnalysis]: Checked inductivity of 619 backedges. 89 proven. 276 refuted. 0 times theorem prover too weak. 254 trivial. 0 not checked. [2024-11-19 10:11:42,594 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 10:11:42,595 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1181803623] [2024-11-19 10:11:42,595 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1181803623] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-19 10:11:42,595 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1217327144] [2024-11-19 10:11:42,595 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-19 10:11:42,595 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 10:11:42,595 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 10:11:42,597 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-19 10:11:42,598 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2024-11-19 10:11:42,656 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-19 10:11:42,657 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-19 10:11:42,658 INFO L255 TraceCheckSpWp]: Trace formula consists of 180 conjuncts, 14 conjuncts are in the unsatisfiable core [2024-11-19 10:11:42,661 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 10:11:42,771 INFO L134 CoverageAnalysis]: Checked inductivity of 619 backedges. 305 proven. 189 refuted. 0 times theorem prover too weak. 125 trivial. 0 not checked. [2024-11-19 10:11:42,771 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-19 10:11:43,253 INFO L134 CoverageAnalysis]: Checked inductivity of 619 backedges. 105 proven. 313 refuted. 0 times theorem prover too weak. 201 trivial. 0 not checked. [2024-11-19 10:11:43,253 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1217327144] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-19 10:11:43,253 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-19 10:11:43,253 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 11, 14] total 19 [2024-11-19 10:11:43,253 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1238449039] [2024-11-19 10:11:43,254 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-19 10:11:43,254 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2024-11-19 10:11:43,254 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 10:11:43,255 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2024-11-19 10:11:43,255 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=66, Invalid=276, Unknown=0, NotChecked=0, Total=342 [2024-11-19 10:11:43,256 INFO L87 Difference]: Start difference. First operand 57 states and 67 transitions. Second operand has 19 states, 19 states have (on average 5.894736842105263) internal successors, (112), 19 states have internal predecessors, (112), 14 states have call successors, (20), 3 states have call predecessors, (20), 7 states have return successors, (20), 8 states have call predecessors, (20), 13 states have call successors, (20) [2024-11-19 10:11:43,510 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 10:11:43,510 INFO L93 Difference]: Finished difference Result 126 states and 154 transitions. [2024-11-19 10:11:43,511 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2024-11-19 10:11:43,511 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 138 [2024-11-19 10:11:43,511 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-19 10:11:43,512 INFO L225 Difference]: With dead ends: 126 [2024-11-19 10:11:43,512 INFO L226 Difference]: Without dead ends: 75 [2024-11-19 10:11:43,513 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 302 GetRequests, 266 SyntacticMatches, 8 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 147 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=252, Invalid=618, Unknown=0, NotChecked=0, Total=870 [2024-11-19 10:11:43,514 INFO L432 NwaCegarLoop]: 18 mSDtfsCounter, 123 mSDsluCounter, 81 mSDsCounter, 0 mSdLazyCounter, 159 mSolverCounterSat, 41 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 123 SdHoareTripleChecker+Valid, 99 SdHoareTripleChecker+Invalid, 200 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 41 IncrementalHoareTripleChecker+Valid, 159 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-19 10:11:43,514 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [123 Valid, 99 Invalid, 200 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [41 Valid, 159 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-19 10:11:43,515 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 75 states. [2024-11-19 10:11:43,521 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 75 to 63. [2024-11-19 10:11:43,521 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 63 states, 49 states have (on average 1.1224489795918366) internal successors, (55), 49 states have internal predecessors, (55), 7 states have call successors, (7), 5 states have call predecessors, (7), 5 states have return successors, (11), 8 states have call predecessors, (11), 6 states have call successors, (11) [2024-11-19 10:11:43,522 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 63 states to 63 states and 73 transitions. [2024-11-19 10:11:43,522 INFO L78 Accepts]: Start accepts. Automaton has 63 states and 73 transitions. Word has length 138 [2024-11-19 10:11:43,523 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-19 10:11:43,523 INFO L471 AbstractCegarLoop]: Abstraction has 63 states and 73 transitions. [2024-11-19 10:11:43,523 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) [2024-11-19 10:11:43,523 INFO L276 IsEmpty]: Start isEmpty. Operand 63 states and 73 transitions. [2024-11-19 10:11:43,524 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 91 [2024-11-19 10:11:43,524 INFO L207 NwaCegarLoop]: Found error trace [2024-11-19 10:11:43,524 INFO L215 NwaCegarLoop]: trace histogram [10, 8, 8, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 2, 1, 1, 1, 1, 1] [2024-11-19 10:11:43,541 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2024-11-19 10:11:43,728 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2024-11-19 10:11:43,729 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting fibonacciErr4ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2024-11-19 10:11:43,729 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 10:11:43,730 INFO L85 PathProgramCache]: Analyzing trace with hash -1765439256, now seen corresponding path program 5 times [2024-11-19 10:11:43,730 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 10:11:43,730 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [391741451] [2024-11-19 10:11:43,730 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2024-11-19 10:11:43,730 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 10:11:43,745 INFO L227 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 8 check-sat command(s) [2024-11-19 10:11:43,746 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-19 10:11:43,942 INFO L134 CoverageAnalysis]: Checked inductivity of 243 backedges. 16 proven. 71 refuted. 0 times theorem prover too weak. 156 trivial. 0 not checked. [2024-11-19 10:11:43,942 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 10:11:43,942 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [391741451] [2024-11-19 10:11:43,943 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [391741451] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-19 10:11:43,943 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1929122410] [2024-11-19 10:11:43,943 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2024-11-19 10:11:43,943 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 10:11:43,943 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 10:11:43,945 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-19 10:11:43,946 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2024-11-19 10:11:44,007 INFO L227 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 8 check-sat command(s) [2024-11-19 10:11:44,007 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-19 10:11:44,008 INFO L255 TraceCheckSpWp]: Trace formula consists of 186 conjuncts, 16 conjuncts are in the unsatisfiable core [2024-11-19 10:11:44,010 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 10:11:44,127 INFO L134 CoverageAnalysis]: Checked inductivity of 243 backedges. 29 proven. 42 refuted. 0 times theorem prover too weak. 172 trivial. 0 not checked. [2024-11-19 10:11:44,127 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-19 10:11:44,568 INFO L134 CoverageAnalysis]: Checked inductivity of 243 backedges. 45 proven. 42 refuted. 0 times theorem prover too weak. 156 trivial. 0 not checked. [2024-11-19 10:11:44,569 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1929122410] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-19 10:11:44,569 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-19 10:11:44,569 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11, 13] total 24 [2024-11-19 10:11:44,569 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [866958069] [2024-11-19 10:11:44,569 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-19 10:11:44,570 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 25 states [2024-11-19 10:11:44,570 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 10:11:44,571 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2024-11-19 10:11:44,571 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=135, Invalid=465, Unknown=0, NotChecked=0, Total=600 [2024-11-19 10:11:44,571 INFO L87 Difference]: Start difference. First operand 63 states and 73 transitions. Second operand has 25 states, 24 states have (on average 3.0416666666666665) internal successors, (73), 25 states have internal predecessors, (73), 6 states have call successors, (8), 1 states have call predecessors, (8), 8 states have return successors, (17), 14 states have call predecessors, (17), 6 states have call successors, (17) [2024-11-19 10:11:44,645 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 10:11:44,645 INFO L93 Difference]: Finished difference Result 63 states and 73 transitions. [2024-11-19 10:11:44,646 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2024-11-19 10:11:44,646 INFO L78 Accepts]: Start accepts. Automaton has has 25 states, 24 states have (on average 3.0416666666666665) internal successors, (73), 25 states have internal predecessors, (73), 6 states have call successors, (8), 1 states have call predecessors, (8), 8 states have return successors, (17), 14 states have call predecessors, (17), 6 states have call successors, (17) Word has length 90 [2024-11-19 10:11:44,646 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-19 10:11:44,647 INFO L225 Difference]: With dead ends: 63 [2024-11-19 10:11:44,647 INFO L226 Difference]: Without dead ends: 62 [2024-11-19 10:11:44,648 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 191 GetRequests, 162 SyntacticMatches, 5 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 305 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=151, Invalid=499, Unknown=0, NotChecked=0, Total=650 [2024-11-19 10:11:44,648 INFO L432 NwaCegarLoop]: 27 mSDtfsCounter, 2 mSDsluCounter, 164 mSDsCounter, 0 mSdLazyCounter, 90 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 191 SdHoareTripleChecker+Invalid, 90 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 90 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-19 10:11:44,649 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [2 Valid, 191 Invalid, 90 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 90 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-19 10:11:44,649 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 62 states. [2024-11-19 10:11:44,655 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 62 to 62. [2024-11-19 10:11:44,658 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) [2024-11-19 10:11:44,659 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 62 states to 62 states and 71 transitions. [2024-11-19 10:11:44,659 INFO L78 Accepts]: Start accepts. Automaton has 62 states and 71 transitions. Word has length 90 [2024-11-19 10:11:44,659 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-19 10:11:44,661 INFO L471 AbstractCegarLoop]: Abstraction has 62 states and 71 transitions. [2024-11-19 10:11:44,661 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 25 states, 24 states have (on average 3.0416666666666665) internal successors, (73), 25 states have internal predecessors, (73), 6 states have call successors, (8), 1 states have call predecessors, (8), 8 states have return successors, (17), 14 states have call predecessors, (17), 6 states have call successors, (17) [2024-11-19 10:11:44,661 INFO L276 IsEmpty]: Start isEmpty. Operand 62 states and 71 transitions. [2024-11-19 10:11:44,662 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 131 [2024-11-19 10:11:44,662 INFO L207 NwaCegarLoop]: Found error trace [2024-11-19 10:11:44,662 INFO L215 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] [2024-11-19 10:11:44,679 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2024-11-19 10:11:44,866 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11,10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 10:11:44,867 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting fibonacciErr5ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2024-11-19 10:11:44,867 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 10:11:44,867 INFO L85 PathProgramCache]: Analyzing trace with hash 1463816598, now seen corresponding path program 2 times [2024-11-19 10:11:44,867 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 10:11:44,868 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [62177273] [2024-11-19 10:11:44,868 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-19 10:11:44,868 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 10:11:44,891 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-19 10:11:44,891 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-19 10:11:45,277 INFO L134 CoverageAnalysis]: Checked inductivity of 537 backedges. 55 proven. 137 refuted. 0 times theorem prover too weak. 345 trivial. 0 not checked. [2024-11-19 10:11:45,277 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 10:11:45,278 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [62177273] [2024-11-19 10:11:45,278 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [62177273] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-19 10:11:45,278 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [773745447] [2024-11-19 10:11:45,278 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-19 10:11:45,278 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 10:11:45,278 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 10:11:45,280 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-19 10:11:45,281 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2024-11-19 10:11:45,361 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-19 10:11:45,361 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-19 10:11:45,362 INFO L255 TraceCheckSpWp]: Trace formula consists of 259 conjuncts, 14 conjuncts are in the unsatisfiable core [2024-11-19 10:11:45,364 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 10:11:45,555 INFO L134 CoverageAnalysis]: Checked inductivity of 537 backedges. 167 proven. 182 refuted. 0 times theorem prover too weak. 188 trivial. 0 not checked. [2024-11-19 10:11:45,555 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-19 10:11:46,253 INFO L134 CoverageAnalysis]: Checked inductivity of 537 backedges. 167 proven. 202 refuted. 0 times theorem prover too weak. 168 trivial. 0 not checked. [2024-11-19 10:11:46,254 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [773745447] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-19 10:11:46,254 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-19 10:11:46,254 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 11, 15] total 30 [2024-11-19 10:11:46,254 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2015183746] [2024-11-19 10:11:46,254 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-19 10:11:46,255 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 30 states [2024-11-19 10:11:46,255 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 10:11:46,256 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 30 interpolants. [2024-11-19 10:11:46,256 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=112, Invalid=758, Unknown=0, NotChecked=0, Total=870 [2024-11-19 10:11:46,257 INFO L87 Difference]: Start difference. First operand 62 states and 71 transitions. Second operand has 30 states, 30 states have (on average 4.066666666666666) internal successors, (122), 30 states have internal predecessors, (122), 16 states have call successors, (18), 1 states have call predecessors, (18), 12 states have return successors, (24), 15 states have call predecessors, (24), 16 states have call successors, (24) [2024-11-19 10:11:46,784 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 10:11:46,784 INFO L93 Difference]: Finished difference Result 136 states and 170 transitions. [2024-11-19 10:11:46,784 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2024-11-19 10:11:46,785 INFO L78 Accepts]: Start accepts. Automaton has has 30 states, 30 states have (on average 4.066666666666666) internal successors, (122), 30 states have internal predecessors, (122), 16 states have call successors, (18), 1 states have call predecessors, (18), 12 states have return successors, (24), 15 states have call predecessors, (24), 16 states have call successors, (24) Word has length 130 [2024-11-19 10:11:46,785 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-19 10:11:46,787 INFO L225 Difference]: With dead ends: 136 [2024-11-19 10:11:46,787 INFO L226 Difference]: Without dead ends: 80 [2024-11-19 10:11:46,788 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 302 GetRequests, 249 SyntacticMatches, 7 SemanticMatches, 46 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 491 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=430, Invalid=1826, Unknown=0, NotChecked=0, Total=2256 [2024-11-19 10:11:46,789 INFO L432 NwaCegarLoop]: 18 mSDtfsCounter, 130 mSDsluCounter, 99 mSDsCounter, 0 mSdLazyCounter, 498 mSolverCounterSat, 71 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 130 SdHoareTripleChecker+Valid, 117 SdHoareTripleChecker+Invalid, 569 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 71 IncrementalHoareTripleChecker+Valid, 498 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-11-19 10:11:46,789 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [130 Valid, 117 Invalid, 569 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [71 Valid, 498 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-11-19 10:11:46,789 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 80 states. [2024-11-19 10:11:46,797 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 80 to 71. [2024-11-19 10:11:46,798 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 71 states, 57 states have (on average 1.0526315789473684) internal successors, (60), 55 states have internal predecessors, (60), 8 states have call successors, (8), 7 states have call predecessors, (8), 5 states have return successors, (13), 8 states have call predecessors, (13), 7 states have call successors, (13) [2024-11-19 10:11:46,798 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 71 states to 71 states and 81 transitions. [2024-11-19 10:11:46,798 INFO L78 Accepts]: Start accepts. Automaton has 71 states and 81 transitions. Word has length 130 [2024-11-19 10:11:46,799 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-19 10:11:46,799 INFO L471 AbstractCegarLoop]: Abstraction has 71 states and 81 transitions. [2024-11-19 10:11:46,799 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 30 states, 30 states have (on average 4.066666666666666) internal successors, (122), 30 states have internal predecessors, (122), 16 states have call successors, (18), 1 states have call predecessors, (18), 12 states have return successors, (24), 15 states have call predecessors, (24), 16 states have call successors, (24) [2024-11-19 10:11:46,799 INFO L276 IsEmpty]: Start isEmpty. Operand 71 states and 81 transitions. [2024-11-19 10:11:46,802 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 244 [2024-11-19 10:11:46,802 INFO L207 NwaCegarLoop]: Found error trace [2024-11-19 10:11:46,802 INFO L215 NwaCegarLoop]: trace histogram [26, 23, 21, 13, 13, 13, 13, 12, 12, 12, 12, 12, 11, 11, 11, 10, 8, 5, 1, 1, 1, 1, 1] [2024-11-19 10:11:46,819 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Ended with exit code 0 [2024-11-19 10:11:47,002 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2024-11-19 10:11:47,003 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting fibonacciErr5ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2024-11-19 10:11:47,004 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 10:11:47,004 INFO L85 PathProgramCache]: Analyzing trace with hash -1852602920, now seen corresponding path program 3 times [2024-11-19 10:11:47,004 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 10:11:47,004 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [501583617] [2024-11-19 10:11:47,004 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-19 10:11:47,004 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 10:11:47,051 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 11 check-sat command(s) [2024-11-19 10:11:47,051 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-19 10:11:47,587 INFO L134 CoverageAnalysis]: Checked inductivity of 2029 backedges. 554 proven. 189 refuted. 0 times theorem prover too weak. 1286 trivial. 0 not checked. [2024-11-19 10:11:47,588 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 10:11:47,588 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [501583617] [2024-11-19 10:11:47,588 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [501583617] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-19 10:11:47,588 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1530672687] [2024-11-19 10:11:47,588 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-19 10:11:47,589 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 10:11:47,589 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 10:11:47,590 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-19 10:11:47,592 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2024-11-19 10:11:47,679 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 11 check-sat command(s) [2024-11-19 10:11:47,679 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-19 10:11:47,682 INFO L255 TraceCheckSpWp]: Trace formula consists of 276 conjuncts, 29 conjuncts are in the unsatisfiable core [2024-11-19 10:11:47,685 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 10:11:47,855 INFO L134 CoverageAnalysis]: Checked inductivity of 2029 backedges. 554 proven. 135 refuted. 0 times theorem prover too weak. 1340 trivial. 0 not checked. [2024-11-19 10:11:47,855 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-19 10:11:49,082 INFO L134 CoverageAnalysis]: Checked inductivity of 2029 backedges. 620 proven. 128 refuted. 0 times theorem prover too weak. 1281 trivial. 0 not checked. [2024-11-19 10:11:49,083 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1530672687] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-19 10:11:49,083 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-19 10:11:49,083 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 12, 17] total 31 [2024-11-19 10:11:49,083 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1589121535] [2024-11-19 10:11:49,083 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-19 10:11:49,084 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 32 states [2024-11-19 10:11:49,084 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 10:11:49,086 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 32 interpolants. [2024-11-19 10:11:49,087 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=232, Invalid=760, Unknown=0, NotChecked=0, Total=992 [2024-11-19 10:11:49,087 INFO L87 Difference]: Start difference. First operand 71 states and 81 transitions. Second operand has 32 states, 31 states have (on average 3.032258064516129) internal successors, (94), 32 states have internal predecessors, (94), 8 states have call successors, (10), 1 states have call predecessors, (10), 10 states have return successors, (23), 22 states have call predecessors, (23), 8 states have call successors, (23) [2024-11-19 10:11:49,289 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 10:11:49,290 INFO L93 Difference]: Finished difference Result 117 states and 156 transitions. [2024-11-19 10:11:49,290 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2024-11-19 10:11:49,290 INFO L78 Accepts]: Start accepts. Automaton has has 32 states, 31 states have (on average 3.032258064516129) internal successors, (94), 32 states have internal predecessors, (94), 8 states have call successors, (10), 1 states have call predecessors, (10), 10 states have return successors, (23), 22 states have call predecessors, (23), 8 states have call successors, (23) Word has length 243 [2024-11-19 10:11:49,291 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-19 10:11:49,292 INFO L225 Difference]: With dead ends: 117 [2024-11-19 10:11:49,292 INFO L226 Difference]: Without dead ends: 116 [2024-11-19 10:11:49,293 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 519 GetRequests, 470 SyntacticMatches, 13 SemanticMatches, 36 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 759 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=330, Invalid=1076, Unknown=0, NotChecked=0, Total=1406 [2024-11-19 10:11:49,293 INFO L432 NwaCegarLoop]: 20 mSDtfsCounter, 16 mSDsluCounter, 163 mSDsCounter, 0 mSdLazyCounter, 144 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 24 SdHoareTripleChecker+Valid, 183 SdHoareTripleChecker+Invalid, 152 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 144 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-19 10:11:49,293 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [24 Valid, 183 Invalid, 152 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 144 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-19 10:11:49,294 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 116 states. [2024-11-19 10:11:49,304 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 116 to 98. [2024-11-19 10:11:49,304 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 98 states, 78 states have (on average 1.0384615384615385) internal successors, (81), 76 states have internal predecessors, (81), 11 states have call successors, (11), 7 states have call predecessors, (11), 8 states have return successors, (37), 14 states have call predecessors, (37), 10 states have call successors, (37) [2024-11-19 10:11:49,306 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 98 states to 98 states and 129 transitions. [2024-11-19 10:11:49,308 INFO L78 Accepts]: Start accepts. Automaton has 98 states and 129 transitions. Word has length 243 [2024-11-19 10:11:49,309 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-19 10:11:49,309 INFO L471 AbstractCegarLoop]: Abstraction has 98 states and 129 transitions. [2024-11-19 10:11:49,309 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 32 states, 31 states have (on average 3.032258064516129) internal successors, (94), 32 states have internal predecessors, (94), 8 states have call successors, (10), 1 states have call predecessors, (10), 10 states have return successors, (23), 22 states have call predecessors, (23), 8 states have call successors, (23) [2024-11-19 10:11:49,310 INFO L276 IsEmpty]: Start isEmpty. Operand 98 states and 129 transitions. [2024-11-19 10:11:49,314 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 380 [2024-11-19 10:11:49,314 INFO L207 NwaCegarLoop]: Found error trace [2024-11-19 10:11:49,315 INFO L215 NwaCegarLoop]: trace histogram [39, 38, 31, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 18, 12, 8, 1, 1, 1, 1, 1] [2024-11-19 10:11:49,333 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Ended with exit code 0 [2024-11-19 10:11:49,518 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2024-11-19 10:11:49,519 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting fibonacciErr5ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2024-11-19 10:11:49,519 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 10:11:49,519 INFO L85 PathProgramCache]: Analyzing trace with hash -1326333035, now seen corresponding path program 4 times [2024-11-19 10:11:49,519 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 10:11:49,519 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [88951851] [2024-11-19 10:11:49,520 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-19 10:11:49,520 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 10:11:49,544 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-19 10:11:49,544 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-19 10:11:49,804 INFO L134 CoverageAnalysis]: Checked inductivity of 5063 backedges. 428 proven. 1234 refuted. 0 times theorem prover too weak. 3401 trivial. 0 not checked. [2024-11-19 10:11:49,804 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 10:11:49,804 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [88951851] [2024-11-19 10:11:49,805 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [88951851] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-19 10:11:49,805 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1076324417] [2024-11-19 10:11:49,805 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-19 10:11:49,805 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 10:11:49,805 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 10:11:49,807 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-19 10:11:49,808 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2024-11-19 10:11:49,928 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-19 10:11:49,928 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-19 10:11:49,930 INFO L255 TraceCheckSpWp]: Trace formula consists of 473 conjuncts, 18 conjuncts are in the unsatisfiable core [2024-11-19 10:11:49,935 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 10:11:50,088 INFO L134 CoverageAnalysis]: Checked inductivity of 5063 backedges. 389 proven. 1723 refuted. 0 times theorem prover too weak. 2951 trivial. 0 not checked. [2024-11-19 10:11:50,088 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-19 10:11:51,161 INFO L134 CoverageAnalysis]: Checked inductivity of 5063 backedges. 389 proven. 1762 refuted. 0 times theorem prover too weak. 2912 trivial. 0 not checked. [2024-11-19 10:11:51,162 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1076324417] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-19 10:11:51,162 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-19 10:11:51,162 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 13, 19] total 24 [2024-11-19 10:11:51,162 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1577536176] [2024-11-19 10:11:51,162 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-19 10:11:51,163 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 24 states [2024-11-19 10:11:51,163 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 10:11:51,164 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2024-11-19 10:11:51,164 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=103, Invalid=449, Unknown=0, NotChecked=0, Total=552 [2024-11-19 10:11:51,165 INFO L87 Difference]: Start difference. First operand 98 states and 129 transitions. Second operand has 24 states, 24 states have (on average 5.583333333333333) internal successors, (134), 24 states have internal predecessors, (134), 18 states have call successors, (23), 1 states have call predecessors, (23), 9 states have return successors, (28), 12 states have call predecessors, (28), 18 states have call successors, (28) [2024-11-19 10:11:51,468 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 10:11:51,469 INFO L93 Difference]: Finished difference Result 214 states and 308 transitions. [2024-11-19 10:11:51,469 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2024-11-19 10:11:51,469 INFO L78 Accepts]: Start accepts. Automaton has has 24 states, 24 states have (on average 5.583333333333333) internal successors, (134), 24 states have internal predecessors, (134), 18 states have call successors, (23), 1 states have call predecessors, (23), 9 states have return successors, (28), 12 states have call predecessors, (28), 18 states have call successors, (28) Word has length 379 [2024-11-19 10:11:51,470 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-19 10:11:51,471 INFO L225 Difference]: With dead ends: 214 [2024-11-19 10:11:51,471 INFO L226 Difference]: Without dead ends: 122 [2024-11-19 10:11:51,472 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 791 GetRequests, 744 SyntacticMatches, 9 SemanticMatches, 38 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 328 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=416, Invalid=1144, Unknown=0, NotChecked=0, Total=1560 [2024-11-19 10:11:51,473 INFO L432 NwaCegarLoop]: 29 mSDtfsCounter, 182 mSDsluCounter, 95 mSDsCounter, 0 mSdLazyCounter, 227 mSolverCounterSat, 99 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 182 SdHoareTripleChecker+Valid, 124 SdHoareTripleChecker+Invalid, 326 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 99 IncrementalHoareTripleChecker+Valid, 227 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-19 10:11:51,473 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [182 Valid, 124 Invalid, 326 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [99 Valid, 227 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-19 10:11:51,473 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 122 states. [2024-11-19 10:11:51,498 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 122 to 104. [2024-11-19 10:11:51,499 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 104 states, 83 states have (on average 1.036144578313253) internal successors, (86), 81 states have internal predecessors, (86), 12 states have call successors, (12), 8 states have call predecessors, (12), 8 states have return successors, (34), 14 states have call predecessors, (34), 11 states have call successors, (34) [2024-11-19 10:11:51,501 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 104 states to 104 states and 132 transitions. [2024-11-19 10:11:51,501 INFO L78 Accepts]: Start accepts. Automaton has 104 states and 132 transitions. Word has length 379 [2024-11-19 10:11:51,502 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-19 10:11:51,502 INFO L471 AbstractCegarLoop]: Abstraction has 104 states and 132 transitions. [2024-11-19 10:11:51,502 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 24 states, 24 states have (on average 5.583333333333333) internal successors, (134), 24 states have internal predecessors, (134), 18 states have call successors, (23), 1 states have call predecessors, (23), 9 states have return successors, (28), 12 states have call predecessors, (28), 18 states have call successors, (28) [2024-11-19 10:11:51,502 INFO L276 IsEmpty]: Start isEmpty. Operand 104 states and 132 transitions. [2024-11-19 10:11:51,506 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 302 [2024-11-19 10:11:51,507 INFO L207 NwaCegarLoop]: Found error trace [2024-11-19 10:11:51,507 INFO L215 NwaCegarLoop]: trace histogram [31, 30, 25, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 14, 10, 6, 1, 1, 1, 1, 1] [2024-11-19 10:11:51,523 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Ended with exit code 0 [2024-11-19 10:11:51,711 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2024-11-19 10:11:51,712 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting fibonacciErr5ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2024-11-19 10:11:51,712 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 10:11:51,712 INFO L85 PathProgramCache]: Analyzing trace with hash 2085379565, now seen corresponding path program 5 times [2024-11-19 10:11:51,712 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 10:11:51,712 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [803368743] [2024-11-19 10:11:51,712 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2024-11-19 10:11:51,713 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 10:11:51,739 INFO L227 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 17 check-sat command(s) [2024-11-19 10:11:51,739 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-19 10:11:52,111 INFO L134 CoverageAnalysis]: Checked inductivity of 3150 backedges. 767 proven. 782 refuted. 0 times theorem prover too weak. 1601 trivial. 0 not checked. [2024-11-19 10:11:52,112 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 10:11:52,112 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [803368743] [2024-11-19 10:11:52,112 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [803368743] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-19 10:11:52,112 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [733696688] [2024-11-19 10:11:52,112 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2024-11-19 10:11:52,112 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 10:11:52,113 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 10:11:52,114 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-19 10:11:52,116 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2024-11-19 10:11:52,255 INFO L227 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 17 check-sat command(s) [2024-11-19 10:11:52,255 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-19 10:11:52,258 INFO L255 TraceCheckSpWp]: Trace formula consists of 445 conjuncts, 20 conjuncts are in the unsatisfiable core [2024-11-19 10:11:52,263 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 10:11:52,418 INFO L134 CoverageAnalysis]: Checked inductivity of 3150 backedges. 814 proven. 814 refuted. 0 times theorem prover too weak. 1522 trivial. 0 not checked. [2024-11-19 10:11:52,418 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-19 10:11:53,608 INFO L134 CoverageAnalysis]: Checked inductivity of 3150 backedges. 822 proven. 861 refuted. 0 times theorem prover too weak. 1467 trivial. 0 not checked. [2024-11-19 10:11:53,608 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [733696688] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-19 10:11:53,608 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-19 10:11:53,608 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 14, 21] total 27 [2024-11-19 10:11:53,608 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1528257387] [2024-11-19 10:11:53,608 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-19 10:11:53,609 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 27 states [2024-11-19 10:11:53,609 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 10:11:53,610 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 27 interpolants. [2024-11-19 10:11:53,610 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=130, Invalid=572, Unknown=0, NotChecked=0, Total=702 [2024-11-19 10:11:53,610 INFO L87 Difference]: Start difference. First operand 104 states and 132 transitions. Second operand has 27 states, 27 states have (on average 5.185185185185185) internal successors, (140), 27 states have internal predecessors, (140), 18 states have call successors, (23), 1 states have call predecessors, (23), 11 states have return successors, (29), 13 states have call predecessors, (29), 18 states have call successors, (29) [2024-11-19 10:11:54,073 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 10:11:54,074 INFO L93 Difference]: Finished difference Result 264 states and 349 transitions. [2024-11-19 10:11:54,074 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 31 states. [2024-11-19 10:11:54,074 INFO L78 Accepts]: Start accepts. Automaton has has 27 states, 27 states have (on average 5.185185185185185) internal successors, (140), 27 states have internal predecessors, (140), 18 states have call successors, (23), 1 states have call predecessors, (23), 11 states have return successors, (29), 13 states have call predecessors, (29), 18 states have call successors, (29) Word has length 301 [2024-11-19 10:11:54,075 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-19 10:11:54,076 INFO L225 Difference]: With dead ends: 264 [2024-11-19 10:11:54,076 INFO L226 Difference]: Without dead ends: 150 [2024-11-19 10:11:54,078 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 649 GetRequests, 589 SyntacticMatches, 10 SemanticMatches, 50 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 666 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=668, Invalid=1984, Unknown=0, NotChecked=0, Total=2652 [2024-11-19 10:11:54,078 INFO L432 NwaCegarLoop]: 40 mSDtfsCounter, 212 mSDsluCounter, 121 mSDsCounter, 0 mSdLazyCounter, 387 mSolverCounterSat, 104 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 212 SdHoareTripleChecker+Valid, 161 SdHoareTripleChecker+Invalid, 491 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 104 IncrementalHoareTripleChecker+Valid, 387 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-19 10:11:54,079 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [212 Valid, 161 Invalid, 491 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [104 Valid, 387 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-19 10:11:54,079 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 150 states. [2024-11-19 10:11:54,088 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 150 to 131. [2024-11-19 10:11:54,088 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 131 states, 106 states have (on average 1.0471698113207548) internal successors, (111), 102 states have internal predecessors, (111), 15 states have call successors, (15), 11 states have call predecessors, (15), 9 states have return successors, (37), 17 states have call predecessors, (37), 14 states have call successors, (37) [2024-11-19 10:11:54,089 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 131 states to 131 states and 163 transitions. [2024-11-19 10:11:54,089 INFO L78 Accepts]: Start accepts. Automaton has 131 states and 163 transitions. Word has length 301 [2024-11-19 10:11:54,090 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-19 10:11:54,090 INFO L471 AbstractCegarLoop]: Abstraction has 131 states and 163 transitions. [2024-11-19 10:11:54,090 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 27 states, 27 states have (on average 5.185185185185185) internal successors, (140), 27 states have internal predecessors, (140), 18 states have call successors, (23), 1 states have call predecessors, (23), 11 states have return successors, (29), 13 states have call predecessors, (29), 18 states have call successors, (29) [2024-11-19 10:11:54,090 INFO L276 IsEmpty]: Start isEmpty. Operand 131 states and 163 transitions. [2024-11-19 10:11:54,091 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 302 [2024-11-19 10:11:54,091 INFO L207 NwaCegarLoop]: Found error trace [2024-11-19 10:11:54,092 INFO L215 NwaCegarLoop]: trace histogram [31, 30, 25, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 14, 10, 6, 1, 1, 1, 1, 1] [2024-11-19 10:11:54,109 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Ended with exit code 0 [2024-11-19 10:11:54,295 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable15 [2024-11-19 10:11:54,296 INFO L396 AbstractCegarLoop]: === Iteration 17 === Targeting fibonacciErr5ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2024-11-19 10:11:54,296 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 10:11:54,296 INFO L85 PathProgramCache]: Analyzing trace with hash 1264030145, now seen corresponding path program 6 times [2024-11-19 10:11:54,296 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 10:11:54,296 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [7047603] [2024-11-19 10:11:54,296 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2024-11-19 10:11:54,296 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 10:11:54,334 INFO L227 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 18 check-sat command(s) [2024-11-19 10:11:54,334 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-19 10:11:54,729 INFO L134 CoverageAnalysis]: Checked inductivity of 3150 backedges. 688 proven. 794 refuted. 0 times theorem prover too weak. 1668 trivial. 0 not checked. [2024-11-19 10:11:54,730 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 10:11:54,730 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [7047603] [2024-11-19 10:11:54,730 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [7047603] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-19 10:11:54,730 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [591254039] [2024-11-19 10:11:54,730 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2024-11-19 10:11:54,730 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 10:11:54,731 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 10:11:54,732 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-19 10:11:54,733 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2024-11-19 10:11:54,882 INFO L227 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 18 check-sat command(s) [2024-11-19 10:11:54,883 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-19 10:11:54,885 INFO L255 TraceCheckSpWp]: Trace formula consists of 512 conjuncts, 18 conjuncts are in the unsatisfiable core [2024-11-19 10:11:54,888 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 10:11:55,008 INFO L134 CoverageAnalysis]: Checked inductivity of 3150 backedges. 690 proven. 793 refuted. 0 times theorem prover too weak. 1667 trivial. 0 not checked. [2024-11-19 10:11:55,009 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-19 10:11:56,141 INFO L134 CoverageAnalysis]: Checked inductivity of 3150 backedges. 706 proven. 824 refuted. 0 times theorem prover too weak. 1620 trivial. 0 not checked. [2024-11-19 10:11:56,142 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [591254039] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-19 10:11:56,142 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-19 10:11:56,142 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 13, 19] total 24 [2024-11-19 10:11:56,142 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1937233733] [2024-11-19 10:11:56,142 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-19 10:11:56,143 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 24 states [2024-11-19 10:11:56,143 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 10:11:56,144 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2024-11-19 10:11:56,144 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=120, Invalid=432, Unknown=0, NotChecked=0, Total=552 [2024-11-19 10:11:56,144 INFO L87 Difference]: Start difference. First operand 131 states and 163 transitions. Second operand has 24 states, 24 states have (on average 5.458333333333333) internal successors, (131), 24 states have internal predecessors, (131), 16 states have call successors, (22), 1 states have call predecessors, (22), 10 states have return successors, (27), 14 states have call predecessors, (27), 16 states have call successors, (27) [2024-11-19 10:11:56,449 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 10:11:56,450 INFO L93 Difference]: Finished difference Result 262 states and 351 transitions. [2024-11-19 10:11:56,450 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2024-11-19 10:11:56,451 INFO L78 Accepts]: Start accepts. Automaton has has 24 states, 24 states have (on average 5.458333333333333) internal successors, (131), 24 states have internal predecessors, (131), 16 states have call successors, (22), 1 states have call predecessors, (22), 10 states have return successors, (27), 14 states have call predecessors, (27), 16 states have call successors, (27) Word has length 301 [2024-11-19 10:11:56,451 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-19 10:11:56,452 INFO L225 Difference]: With dead ends: 262 [2024-11-19 10:11:56,453 INFO L226 Difference]: Without dead ends: 137 [2024-11-19 10:11:56,454 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 634 GetRequests, 590 SyntacticMatches, 9 SemanticMatches, 35 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 380 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=347, Invalid=985, Unknown=0, NotChecked=0, Total=1332 [2024-11-19 10:11:56,454 INFO L432 NwaCegarLoop]: 48 mSDtfsCounter, 99 mSDsluCounter, 188 mSDsCounter, 0 mSdLazyCounter, 515 mSolverCounterSat, 43 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 100 SdHoareTripleChecker+Valid, 236 SdHoareTripleChecker+Invalid, 558 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 43 IncrementalHoareTripleChecker+Valid, 515 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-19 10:11:56,455 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [100 Valid, 236 Invalid, 558 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [43 Valid, 515 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-19 10:11:56,455 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 137 states. [2024-11-19 10:11:56,462 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 137 to 122. [2024-11-19 10:11:56,462 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 122 states, 98 states have (on average 1.0408163265306123) internal successors, (102), 97 states have internal predecessors, (102), 16 states have call successors, (16), 12 states have call predecessors, (16), 7 states have return successors, (30), 12 states have call predecessors, (30), 15 states have call successors, (30) [2024-11-19 10:11:56,463 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 122 states to 122 states and 148 transitions. [2024-11-19 10:11:56,463 INFO L78 Accepts]: Start accepts. Automaton has 122 states and 148 transitions. Word has length 301 [2024-11-19 10:11:56,464 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-19 10:11:56,464 INFO L471 AbstractCegarLoop]: Abstraction has 122 states and 148 transitions. [2024-11-19 10:11:56,464 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 24 states, 24 states have (on average 5.458333333333333) internal successors, (131), 24 states have internal predecessors, (131), 16 states have call successors, (22), 1 states have call predecessors, (22), 10 states have return successors, (27), 14 states have call predecessors, (27), 16 states have call successors, (27) [2024-11-19 10:11:56,464 INFO L276 IsEmpty]: Start isEmpty. Operand 122 states and 148 transitions. [2024-11-19 10:11:56,466 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 406 [2024-11-19 10:11:56,466 INFO L207 NwaCegarLoop]: Found error trace [2024-11-19 10:11:56,466 INFO L215 NwaCegarLoop]: trace histogram [42, 40, 34, 21, 21, 21, 21, 20, 20, 20, 20, 20, 20, 20, 20, 19, 13, 8, 1, 1, 1, 1, 1] [2024-11-19 10:11:56,483 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Ended with exit code 0 [2024-11-19 10:11:56,667 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable16,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 10:11:56,667 INFO L396 AbstractCegarLoop]: === Iteration 18 === Targeting fibonacciErr5ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2024-11-19 10:11:56,668 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 10:11:56,668 INFO L85 PathProgramCache]: Analyzing trace with hash 1368637202, now seen corresponding path program 7 times [2024-11-19 10:11:56,668 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 10:11:56,668 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [568671999] [2024-11-19 10:11:56,668 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2024-11-19 10:11:56,668 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 10:11:56,721 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 10:11:58,937 INFO L134 CoverageAnalysis]: Checked inductivity of 5803 backedges. 830 proven. 1470 refuted. 0 times theorem prover too weak. 3503 trivial. 0 not checked. [2024-11-19 10:11:58,938 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 10:11:58,938 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [568671999] [2024-11-19 10:11:58,938 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [568671999] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-19 10:11:58,938 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [663464723] [2024-11-19 10:11:58,938 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2024-11-19 10:11:58,939 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 10:11:58,939 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 10:11:58,940 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-19 10:11:58,942 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2024-11-19 10:11:59,102 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 10:11:59,104 INFO L255 TraceCheckSpWp]: Trace formula consists of 767 conjuncts, 81 conjuncts are in the unsatisfiable core [2024-11-19 10:11:59,110 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 10:11:59,479 INFO L134 CoverageAnalysis]: Checked inductivity of 5803 backedges. 820 proven. 1112 refuted. 0 times theorem prover too weak. 3871 trivial. 0 not checked. [2024-11-19 10:11:59,480 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-19 10:12:05,865 INFO L134 CoverageAnalysis]: Checked inductivity of 5803 backedges. 1149 proven. 1015 refuted. 0 times theorem prover too weak. 3639 trivial. 0 not checked. [2024-11-19 10:12:05,866 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [663464723] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-19 10:12:05,866 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-19 10:12:05,866 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 18, 29] total 45 [2024-11-19 10:12:05,867 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1626595745] [2024-11-19 10:12:05,867 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-19 10:12:05,867 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 46 states [2024-11-19 10:12:05,868 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 10:12:05,868 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 46 interpolants. [2024-11-19 10:12:05,869 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=463, Invalid=1607, Unknown=0, NotChecked=0, Total=2070 [2024-11-19 10:12:05,869 INFO L87 Difference]: Start difference. First operand 122 states and 148 transitions. Second operand has 46 states, 45 states have (on average 2.6444444444444444) internal successors, (119), 46 states have internal predecessors, (119), 12 states have call successors, (13), 1 states have call predecessors, (13), 13 states have return successors, (31), 31 states have call predecessors, (31), 12 states have call successors, (31) [2024-11-19 10:12:06,098 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 10:12:06,098 INFO L93 Difference]: Finished difference Result 168 states and 229 transitions. [2024-11-19 10:12:06,098 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 28 states. [2024-11-19 10:12:06,099 INFO L78 Accepts]: Start accepts. Automaton has has 46 states, 45 states have (on average 2.6444444444444444) internal successors, (119), 46 states have internal predecessors, (119), 12 states have call successors, (13), 1 states have call predecessors, (13), 13 states have return successors, (31), 31 states have call predecessors, (31), 12 states have call successors, (31) Word has length 405 [2024-11-19 10:12:06,099 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-19 10:12:06,101 INFO L225 Difference]: With dead ends: 168 [2024-11-19 10:12:06,101 INFO L226 Difference]: Without dead ends: 167 [2024-11-19 10:12:06,102 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 895 GetRequests, 794 SyntacticMatches, 51 SemanticMatches, 50 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2499 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=591, Invalid=2061, Unknown=0, NotChecked=0, Total=2652 [2024-11-19 10:12:06,103 INFO L432 NwaCegarLoop]: 20 mSDtfsCounter, 34 mSDsluCounter, 206 mSDsCounter, 0 mSdLazyCounter, 190 mSolverCounterSat, 17 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 41 SdHoareTripleChecker+Valid, 226 SdHoareTripleChecker+Invalid, 207 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 17 IncrementalHoareTripleChecker+Valid, 190 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-19 10:12:06,103 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [41 Valid, 226 Invalid, 207 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [17 Valid, 190 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-19 10:12:06,103 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 167 states. [2024-11-19 10:12:06,115 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 167 to 149. [2024-11-19 10:12:06,115 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 149 states, 119 states have (on average 1.0336134453781514) internal successors, (123), 118 states have internal predecessors, (123), 19 states have call successors, (19), 12 states have call predecessors, (19), 10 states have return successors, (60), 18 states have call predecessors, (60), 18 states have call successors, (60) [2024-11-19 10:12:06,116 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 149 states to 149 states and 202 transitions. [2024-11-19 10:12:06,117 INFO L78 Accepts]: Start accepts. Automaton has 149 states and 202 transitions. Word has length 405 [2024-11-19 10:12:06,117 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-19 10:12:06,117 INFO L471 AbstractCegarLoop]: Abstraction has 149 states and 202 transitions. [2024-11-19 10:12:06,118 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 46 states, 45 states have (on average 2.6444444444444444) internal successors, (119), 46 states have internal predecessors, (119), 12 states have call successors, (13), 1 states have call predecessors, (13), 13 states have return successors, (31), 31 states have call predecessors, (31), 12 states have call successors, (31) [2024-11-19 10:12:06,118 INFO L276 IsEmpty]: Start isEmpty. Operand 149 states and 202 transitions. [2024-11-19 10:12:06,124 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 910 [2024-11-19 10:12:06,124 INFO L207 NwaCegarLoop]: Found error trace [2024-11-19 10:12:06,125 INFO L215 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] [2024-11-19 10:12:06,139 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Ended with exit code 0 [2024-11-19 10:12:06,325 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 16 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable17 [2024-11-19 10:12:06,325 INFO L396 AbstractCegarLoop]: === Iteration 19 === Targeting fibonacciErr5ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2024-11-19 10:12:06,326 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 10:12:06,326 INFO L85 PathProgramCache]: Analyzing trace with hash -1447574050, now seen corresponding path program 8 times [2024-11-19 10:12:06,326 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 10:12:06,326 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1538323596] [2024-11-19 10:12:06,326 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-19 10:12:06,326 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 10:12:06,432 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-19 10:12:06,433 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-19 10:12:07,577 INFO L134 CoverageAnalysis]: Checked inductivity of 30053 backedges. 1430 proven. 5737 refuted. 0 times theorem prover too weak. 22886 trivial. 0 not checked. [2024-11-19 10:12:07,578 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 10:12:07,578 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1538323596] [2024-11-19 10:12:07,578 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1538323596] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-19 10:12:07,579 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1736403687] [2024-11-19 10:12:07,579 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-19 10:12:07,579 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 10:12:07,579 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 10:12:07,581 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-19 10:12:07,583 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2024-11-19 10:12:07,956 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-19 10:12:07,956 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-19 10:12:07,960 INFO L255 TraceCheckSpWp]: Trace formula consists of 1699 conjuncts, 26 conjuncts are in the unsatisfiable core [2024-11-19 10:12:07,968 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 10:12:08,172 INFO L134 CoverageAnalysis]: Checked inductivity of 30053 backedges. 1688 proven. 6747 refuted. 0 times theorem prover too weak. 21618 trivial. 0 not checked. [2024-11-19 10:12:08,172 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-19 10:12:10,972 INFO L134 CoverageAnalysis]: Checked inductivity of 30053 backedges. 1688 proven. 6862 refuted. 0 times theorem prover too weak. 21503 trivial. 0 not checked. [2024-11-19 10:12:10,972 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1736403687] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-19 10:12:10,972 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-19 10:12:10,973 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 17, 27] total 32 [2024-11-19 10:12:10,973 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1776317859] [2024-11-19 10:12:10,973 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-19 10:12:10,974 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 32 states [2024-11-19 10:12:10,974 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 10:12:10,975 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 32 interpolants. [2024-11-19 10:12:10,976 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=169, Invalid=823, Unknown=0, NotChecked=0, Total=992 [2024-11-19 10:12:10,976 INFO L87 Difference]: Start difference. First operand 149 states and 202 transitions. Second operand has 32 states, 32 states have (on average 5.6875) internal successors, (182), 32 states have internal predecessors, (182), 26 states have call successors, (31), 1 states have call predecessors, (31), 13 states have return successors, (40), 16 states have call predecessors, (40), 26 states have call successors, (40) [2024-11-19 10:12:11,463 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 10:12:11,464 INFO L93 Difference]: Finished difference Result 331 states and 496 transitions. [2024-11-19 10:12:11,464 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 33 states. [2024-11-19 10:12:11,465 INFO L78 Accepts]: Start accepts. Automaton has has 32 states, 32 states have (on average 5.6875) internal successors, (182), 32 states have internal predecessors, (182), 26 states have call successors, (31), 1 states have call predecessors, (31), 13 states have return successors, (40), 16 states have call predecessors, (40), 26 states have call successors, (40) Word has length 909 [2024-11-19 10:12:11,465 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-19 10:12:11,467 INFO L225 Difference]: With dead ends: 331 [2024-11-19 10:12:11,467 INFO L226 Difference]: Without dead ends: 188 [2024-11-19 10:12:11,469 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 1869 GetRequests, 1800 SyntacticMatches, 13 SemanticMatches, 56 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 810 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=824, Invalid=2482, Unknown=0, NotChecked=0, Total=3306 [2024-11-19 10:12:11,470 INFO L432 NwaCegarLoop]: 43 mSDtfsCounter, 260 mSDsluCounter, 155 mSDsCounter, 0 mSdLazyCounter, 412 mSolverCounterSat, 124 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 260 SdHoareTripleChecker+Valid, 198 SdHoareTripleChecker+Invalid, 536 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 124 IncrementalHoareTripleChecker+Valid, 412 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-19 10:12:11,470 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [260 Valid, 198 Invalid, 536 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [124 Valid, 412 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-19 10:12:11,471 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 188 states. [2024-11-19 10:12:11,481 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 188 to 158. [2024-11-19 10:12:11,481 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 158 states, 127 states have (on average 1.031496062992126) internal successors, (131), 125 states have internal predecessors, (131), 20 states have call successors, (20), 14 states have call predecessors, (20), 10 states have return successors, (57), 18 states have call predecessors, (57), 19 states have call successors, (57) [2024-11-19 10:12:11,482 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 158 states to 158 states and 208 transitions. [2024-11-19 10:12:11,483 INFO L78 Accepts]: Start accepts. Automaton has 158 states and 208 transitions. Word has length 909 [2024-11-19 10:12:11,483 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-19 10:12:11,483 INFO L471 AbstractCegarLoop]: Abstraction has 158 states and 208 transitions. [2024-11-19 10:12:11,484 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 32 states, 32 states have (on average 5.6875) internal successors, (182), 32 states have internal predecessors, (182), 26 states have call successors, (31), 1 states have call predecessors, (31), 13 states have return successors, (40), 16 states have call predecessors, (40), 26 states have call successors, (40) [2024-11-19 10:12:11,484 INFO L276 IsEmpty]: Start isEmpty. Operand 158 states and 208 transitions. [2024-11-19 10:12:11,493 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1243 [2024-11-19 10:12:11,493 INFO L207 NwaCegarLoop]: Found error trace [2024-11-19 10:12:11,494 INFO L215 NwaCegarLoop]: trace histogram [129, 123, 105, 66, 66, 66, 66, 62, 62, 62, 62, 62, 61, 61, 61, 60, 39, 24, 1, 1, 1, 1, 1] [2024-11-19 10:12:11,512 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Forceful destruction successful, exit code 0 [2024-11-19 10:12:11,694 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable18,17 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 10:12:11,694 INFO L396 AbstractCegarLoop]: === Iteration 20 === Targeting fibonacciErr5ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2024-11-19 10:12:11,695 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 10:12:11,695 INFO L85 PathProgramCache]: Analyzing trace with hash 700024010, now seen corresponding path program 9 times [2024-11-19 10:12:11,695 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 10:12:11,695 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1755570174] [2024-11-19 10:12:11,695 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-19 10:12:11,695 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 10:12:11,878 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 61 check-sat command(s) [2024-11-19 10:12:11,880 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-19 10:12:20,165 INFO L134 CoverageAnalysis]: Checked inductivity of 56467 backedges. 16280 proven. 6125 refuted. 0 times theorem prover too weak. 34062 trivial. 0 not checked. [2024-11-19 10:12:20,165 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 10:12:20,166 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1755570174] [2024-11-19 10:12:20,166 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1755570174] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-19 10:12:20,166 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1469281649] [2024-11-19 10:12:20,166 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-19 10:12:20,166 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 10:12:20,167 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 10:12:20,168 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-19 10:12:20,169 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Waiting until timeout for monitored process [2024-11-19 10:12:20,593 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 61 check-sat command(s) [2024-11-19 10:12:20,593 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-19 10:12:20,599 INFO L255 TraceCheckSpWp]: Trace formula consists of 1562 conjuncts, 165 conjuncts are in the unsatisfiable core [2024-11-19 10:12:20,621 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 10:12:21,242 INFO L134 CoverageAnalysis]: Checked inductivity of 56467 backedges. 16360 proven. 4596 refuted. 0 times theorem prover too weak. 35511 trivial. 0 not checked. [2024-11-19 10:12:21,242 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-19 10:12:43,840 INFO L134 CoverageAnalysis]: Checked inductivity of 56467 backedges. 17227 proven. 4261 refuted. 0 times theorem prover too weak. 34979 trivial. 0 not checked. [2024-11-19 10:12:43,840 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1469281649] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-19 10:12:43,840 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-19 10:12:43,840 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [24, 21, 38] total 53 [2024-11-19 10:12:43,840 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [431627477] [2024-11-19 10:12:43,841 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-19 10:12:43,842 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 54 states [2024-11-19 10:12:43,842 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 10:12:43,843 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 54 interpolants. [2024-11-19 10:12:43,844 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=642, Invalid=2220, Unknown=0, NotChecked=0, Total=2862 [2024-11-19 10:12:43,844 INFO L87 Difference]: Start difference. First operand 158 states and 208 transitions. Second operand has 54 states, 53 states have (on average 2.811320754716981) internal successors, (149), 54 states have internal predecessors, (149), 14 states have call successors, (16), 1 states have call predecessors, (16), 16 states have return successors, (39), 38 states have call predecessors, (39), 14 states have call successors, (39) [2024-11-19 10:12:44,071 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 10:12:44,071 INFO L93 Difference]: Finished difference Result 216 states and 319 transitions. [2024-11-19 10:12:44,072 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 35 states. [2024-11-19 10:12:44,072 INFO L78 Accepts]: Start accepts. Automaton has has 54 states, 53 states have (on average 2.811320754716981) internal successors, (149), 54 states have internal predecessors, (149), 14 states have call successors, (16), 1 states have call predecessors, (16), 16 states have return successors, (39), 38 states have call predecessors, (39), 14 states have call successors, (39) Word has length 1242 [2024-11-19 10:12:44,074 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-19 10:12:44,075 INFO L225 Difference]: With dead ends: 216 [2024-11-19 10:12:44,076 INFO L226 Difference]: Without dead ends: 215 [2024-11-19 10:12:44,077 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 2654 GetRequests, 2476 SyntacticMatches, 119 SemanticMatches, 59 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6499 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=784, Invalid=2876, Unknown=0, NotChecked=0, Total=3660 [2024-11-19 10:12:44,078 INFO L432 NwaCegarLoop]: 20 mSDtfsCounter, 26 mSDsluCounter, 170 mSDsCounter, 0 mSdLazyCounter, 181 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 40 SdHoareTripleChecker+Valid, 190 SdHoareTripleChecker+Invalid, 192 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 181 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-19 10:12:44,078 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [40 Valid, 190 Invalid, 192 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 181 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-19 10:12:44,080 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 215 states. [2024-11-19 10:12:44,094 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 215 to 176. [2024-11-19 10:12:44,094 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 176 states, 141 states have (on average 1.0283687943262412) internal successors, (145), 139 states have internal predecessors, (145), 22 states have call successors, (22), 14 states have call predecessors, (22), 12 states have return successors, (85), 22 states have call predecessors, (85), 21 states have call successors, (85) [2024-11-19 10:12:44,096 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 176 states to 176 states and 252 transitions. [2024-11-19 10:12:44,096 INFO L78 Accepts]: Start accepts. Automaton has 176 states and 252 transitions. Word has length 1242 [2024-11-19 10:12:44,098 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-19 10:12:44,098 INFO L471 AbstractCegarLoop]: Abstraction has 176 states and 252 transitions. [2024-11-19 10:12:44,098 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 54 states, 53 states have (on average 2.811320754716981) internal successors, (149), 54 states have internal predecessors, (149), 14 states have call successors, (16), 1 states have call predecessors, (16), 16 states have return successors, (39), 38 states have call predecessors, (39), 14 states have call successors, (39) [2024-11-19 10:12:44,098 INFO L276 IsEmpty]: Start isEmpty. Operand 176 states and 252 transitions. [2024-11-19 10:12:44,118 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1898 [2024-11-19 10:12:44,118 INFO L207 NwaCegarLoop]: Found error trace [2024-11-19 10:12:44,119 INFO L215 NwaCegarLoop]: trace histogram [195, 191, 158, 98, 98, 98, 98, 96, 96, 96, 96, 96, 95, 95, 95, 94, 60, 37, 1, 1, 1, 1, 1] [2024-11-19 10:12:44,139 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Forceful destruction successful, exit code 0 [2024-11-19 10:12:44,319 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable19,18 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 10:12:44,320 INFO L396 AbstractCegarLoop]: === Iteration 21 === Targeting fibonacciErr5ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2024-11-19 10:12:44,320 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 10:12:44,321 INFO L85 PathProgramCache]: Analyzing trace with hash -7426598, now seen corresponding path program 10 times [2024-11-19 10:12:44,321 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 10:12:44,321 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1880936843] [2024-11-19 10:12:44,321 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-19 10:12:44,321 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 10:12:44,477 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-19 10:12:44,477 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-19 10:12:45,758 INFO L134 CoverageAnalysis]: Checked inductivity of 132417 backedges. 2433 proven. 15333 refuted. 0 times theorem prover too weak. 114651 trivial. 0 not checked. [2024-11-19 10:12:45,758 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 10:12:45,758 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1880936843] [2024-11-19 10:12:45,758 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1880936843] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-19 10:12:45,758 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1117532103] [2024-11-19 10:12:45,758 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-19 10:12:45,759 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 10:12:45,759 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 10:12:45,761 INFO L229 MonitoredProcess]: Starting monitored process 19 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-19 10:12:45,762 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Waiting until timeout for monitored process [2024-11-19 10:12:46,445 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-19 10:12:46,445 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-19 10:12:46,454 INFO L255 TraceCheckSpWp]: Trace formula consists of 2353 conjuncts, 30 conjuncts are in the unsatisfiable core [2024-11-19 10:12:46,472 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 10:12:46,658 INFO L134 CoverageAnalysis]: Checked inductivity of 132417 backedges. 68023 proven. 5564 refuted. 0 times theorem prover too weak. 58830 trivial. 0 not checked. [2024-11-19 10:12:46,659 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-19 10:12:50,574 INFO L134 CoverageAnalysis]: Checked inductivity of 132417 backedges. 2937 proven. 17973 refuted. 0 times theorem prover too weak. 111507 trivial. 0 not checked. [2024-11-19 10:12:50,574 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1117532103] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-19 10:12:50,574 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-19 10:12:50,575 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 19, 29] total 34 [2024-11-19 10:12:50,575 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [387341967] [2024-11-19 10:12:50,575 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-19 10:12:50,576 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 34 states [2024-11-19 10:12:50,576 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 10:12:50,577 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 34 interpolants. [2024-11-19 10:12:50,577 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=175, Invalid=947, Unknown=0, NotChecked=0, Total=1122 [2024-11-19 10:12:50,577 INFO L87 Difference]: Start difference. First operand 176 states and 252 transitions. Second operand has 34 states, 34 states have (on average 6.0) internal successors, (204), 34 states have internal predecessors, (204), 29 states have call successors, (36), 4 states have call predecessors, (36), 14 states have return successors, (43), 16 states have call predecessors, (43), 27 states have call successors, (43) [2024-11-19 10:12:51,157 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 10:12:51,157 INFO L93 Difference]: Finished difference Result 428 states and 705 transitions. [2024-11-19 10:12:51,158 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 41 states. [2024-11-19 10:12:51,158 INFO L78 Accepts]: Start accepts. Automaton has has 34 states, 34 states have (on average 6.0) internal successors, (204), 34 states have internal predecessors, (204), 29 states have call successors, (36), 4 states have call predecessors, (36), 14 states have return successors, (43), 16 states have call predecessors, (43), 27 states have call successors, (43) Word has length 1897 [2024-11-19 10:12:51,159 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-19 10:12:51,161 INFO L225 Difference]: With dead ends: 428 [2024-11-19 10:12:51,161 INFO L226 Difference]: Without dead ends: 258 [2024-11-19 10:12:51,165 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 3859 GetRequests, 3775 SyntacticMatches, 17 SemanticMatches, 67 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1192 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=1170, Invalid=3522, Unknown=0, NotChecked=0, Total=4692 [2024-11-19 10:12:51,166 INFO L432 NwaCegarLoop]: 36 mSDtfsCounter, 608 mSDsluCounter, 158 mSDsCounter, 0 mSdLazyCounter, 375 mSolverCounterSat, 214 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 608 SdHoareTripleChecker+Valid, 194 SdHoareTripleChecker+Invalid, 589 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 214 IncrementalHoareTripleChecker+Valid, 375 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-19 10:12:51,166 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [608 Valid, 194 Invalid, 589 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [214 Valid, 375 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-19 10:12:51,167 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 258 states. [2024-11-19 10:12:51,183 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 258 to 230. [2024-11-19 10:12:51,184 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 230 states, 185 states have (on average 1.0324324324324323) internal successors, (191), 182 states have internal predecessors, (191), 29 states have call successors, (29), 18 states have call predecessors, (29), 15 states have return successors, (110), 29 states have call predecessors, (110), 28 states have call successors, (110) [2024-11-19 10:12:51,186 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 230 states to 230 states and 330 transitions. [2024-11-19 10:12:51,186 INFO L78 Accepts]: Start accepts. Automaton has 230 states and 330 transitions. Word has length 1897 [2024-11-19 10:12:51,187 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-19 10:12:51,187 INFO L471 AbstractCegarLoop]: Abstraction has 230 states and 330 transitions. [2024-11-19 10:12:51,187 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 34 states, 34 states have (on average 6.0) internal successors, (204), 34 states have internal predecessors, (204), 29 states have call successors, (36), 4 states have call predecessors, (36), 14 states have return successors, (43), 16 states have call predecessors, (43), 27 states have call successors, (43) [2024-11-19 10:12:51,187 INFO L276 IsEmpty]: Start isEmpty. Operand 230 states and 330 transitions. [2024-11-19 10:12:51,241 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1642 [2024-11-19 10:12:51,241 INFO L207 NwaCegarLoop]: Found error trace [2024-11-19 10:12:51,242 INFO L215 NwaCegarLoop]: trace histogram [168, 166, 136, 84, 84, 84, 84, 83, 83, 83, 83, 83, 83, 83, 83, 82, 52, 32, 1, 1, 1, 1, 1] [2024-11-19 10:12:51,264 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Forceful destruction successful, exit code 0 [2024-11-19 10:12:51,442 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable20,19 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 10:12:51,442 INFO L396 AbstractCegarLoop]: === Iteration 22 === Targeting fibonacciErr5ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2024-11-19 10:12:51,443 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 10:12:51,443 INFO L85 PathProgramCache]: Analyzing trace with hash 231613447, now seen corresponding path program 11 times [2024-11-19 10:12:51,443 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 10:12:51,443 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1903112763] [2024-11-19 10:12:51,444 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2024-11-19 10:12:51,444 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 10:12:51,642 INFO L227 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 92 check-sat command(s) [2024-11-19 10:12:51,642 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat