./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 30e01a73 Calling Ultimate with: /usr/lib/jvm/java-11-openjdk-amd64/bin/java -Dosgi.configuration.area=/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/config/TaipanReach.xml -i ../../sv-benchmarks/c/termination-numeric/Fibonacci01-2.c -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/config/svcomp-Overflow-64bit-Taipan_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire --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 Taipan --witnessprinter.graph.data.architecture 64bit --witnessprinter.graph.data.programhash 14cfbc3a2ba2bfe3a03d4d1ebff24b0baf1851f06dbbd2468b59e09322e4ce16 --- Real Ultimate output --- This is Ultimate 0.2.3-dev-30e01a7 [2023-11-23 21:09:24,417 INFO L188 SettingsManager]: Resetting all preferences to default values... [2023-11-23 21:09:24,528 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/config/svcomp-Overflow-64bit-Taipan_Default.epf [2023-11-23 21:09:24,535 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2023-11-23 21:09:24,535 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2023-11-23 21:09:24,580 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2023-11-23 21:09:24,580 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2023-11-23 21:09:24,581 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2023-11-23 21:09:24,582 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2023-11-23 21:09:24,587 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2023-11-23 21:09:24,587 INFO L153 SettingsManager]: * User list type=DISABLED [2023-11-23 21:09:24,588 INFO L151 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2023-11-23 21:09:24,589 INFO L153 SettingsManager]: * Explicit value domain=true [2023-11-23 21:09:24,590 INFO L153 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2023-11-23 21:09:24,591 INFO L153 SettingsManager]: * Octagon Domain=false [2023-11-23 21:09:24,591 INFO L153 SettingsManager]: * Abstract domain=CompoundDomain [2023-11-23 21:09:24,591 INFO L153 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2023-11-23 21:09:24,592 INFO L153 SettingsManager]: * Use the RCFG-of-the-future interface=true [2023-11-23 21:09:24,592 INFO L153 SettingsManager]: * Interval Domain=false [2023-11-23 21:09:24,593 INFO L151 SettingsManager]: Preferences of Sifa differ from their defaults: [2023-11-23 21:09:24,594 INFO L153 SettingsManager]: * Call Summarizer=TopInputCallSummarizer [2023-11-23 21:09:24,595 INFO L153 SettingsManager]: * Simplification Technique=POLY_PAC [2023-11-23 21:09:24,596 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2023-11-23 21:09:24,596 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2023-11-23 21:09:24,597 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2023-11-23 21:09:24,597 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2023-11-23 21:09:24,597 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2023-11-23 21:09:24,598 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2023-11-23 21:09:24,598 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2023-11-23 21:09:24,599 INFO L153 SettingsManager]: * Check absence of signed integer overflows=true [2023-11-23 21:09:24,600 INFO L153 SettingsManager]: * Check unreachability of reach_error function=false [2023-11-23 21:09:24,600 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2023-11-23 21:09:24,600 INFO L153 SettingsManager]: * Use constant arrays=true [2023-11-23 21:09:24,601 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2023-11-23 21:09:24,601 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2023-11-23 21:09:24,601 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2023-11-23 21:09:24,602 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-11-23 21:09:24,602 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2023-11-23 21:09:24,602 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2023-11-23 21:09:24,602 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2023-11-23 21:09:24,603 INFO L153 SettingsManager]: * Trace refinement strategy=SIFA_TAIPAN [2023-11-23 21:09:24,603 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2023-11-23 21:09:24,603 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2023-11-23 21:09:24,603 INFO L153 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2023-11-23 21:09:24,604 INFO L153 SettingsManager]: * Trace refinement exception blacklist=NONE [2023-11-23 21:09:24,604 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2023-11-23 21:09:24,604 INFO L153 SettingsManager]: * Abstract interpretation Mode=USE_PREDICATES WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/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 -> /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire 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 -> Taipan 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 [2023-11-23 21:09:24,915 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2023-11-23 21:09:24,949 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2023-11-23 21:09:24,952 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2023-11-23 21:09:24,953 INFO L270 PluginConnector]: Initializing CDTParser... [2023-11-23 21:09:24,955 INFO L274 PluginConnector]: CDTParser initialized [2023-11-23 21:09:24,956 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/../../sv-benchmarks/c/termination-numeric/Fibonacci01-2.c [2023-11-23 21:09:28,103 INFO L533 CDTParser]: Created temporary CDT project at NULL [2023-11-23 21:09:28,346 INFO L384 CDTParser]: Found 1 translation units. [2023-11-23 21:09:28,346 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/sv-benchmarks/c/termination-numeric/Fibonacci01-2.c [2023-11-23 21:09:28,355 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/data/b8d1bc9f7/9375f04a9ee742bcb3094ceb39f20762/FLAG51af0516b [2023-11-23 21:09:28,373 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/data/b8d1bc9f7/9375f04a9ee742bcb3094ceb39f20762 [2023-11-23 21:09:28,379 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2023-11-23 21:09:28,381 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2023-11-23 21:09:28,385 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2023-11-23 21:09:28,385 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2023-11-23 21:09:28,391 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2023-11-23 21:09:28,392 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 23.11 09:09:28" (1/1) ... [2023-11-23 21:09:28,393 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@20984d4a and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 09:09:28, skipping insertion in model container [2023-11-23 21:09:28,393 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 23.11 09:09:28" (1/1) ... [2023-11-23 21:09:28,418 INFO L177 MainTranslator]: Built tables and reachable declarations [2023-11-23 21:09:28,626 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-23 21:09:28,638 INFO L202 MainTranslator]: Completed pre-run [2023-11-23 21:09:28,665 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-23 21:09:28,680 INFO L206 MainTranslator]: Completed translation [2023-11-23 21:09:28,681 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 09:09:28 WrapperNode [2023-11-23 21:09:28,681 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2023-11-23 21:09:28,682 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2023-11-23 21:09:28,683 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2023-11-23 21:09:28,683 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2023-11-23 21:09:28,691 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 09:09:28" (1/1) ... [2023-11-23 21:09:28,698 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 09:09:28" (1/1) ... [2023-11-23 21:09:28,715 INFO L138 Inliner]: procedures = 13, calls = 11, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 27 [2023-11-23 21:09:28,716 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2023-11-23 21:09:28,717 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2023-11-23 21:09:28,717 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2023-11-23 21:09:28,717 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2023-11-23 21:09:28,726 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 09:09:28" (1/1) ... [2023-11-23 21:09:28,727 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 09:09:28" (1/1) ... [2023-11-23 21:09:28,728 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 09:09:28" (1/1) ... [2023-11-23 21:09:28,728 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 09:09:28" (1/1) ... [2023-11-23 21:09:28,731 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 09:09:28" (1/1) ... [2023-11-23 21:09:28,733 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 09:09:28" (1/1) ... [2023-11-23 21:09:28,734 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 09:09:28" (1/1) ... [2023-11-23 21:09:28,735 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 09:09:28" (1/1) ... [2023-11-23 21:09:28,737 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2023-11-23 21:09:28,738 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2023-11-23 21:09:28,738 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2023-11-23 21:09:28,738 INFO L274 PluginConnector]: RCFGBuilder initialized [2023-11-23 21:09:28,739 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 09:09:28" (1/1) ... [2023-11-23 21:09:28,745 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-11-23 21:09:28,756 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/z3 [2023-11-23 21:09:28,774 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2023-11-23 21:09:28,789 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2023-11-23 21:09:28,816 INFO L130 BoogieDeclarations]: Found specification of procedure fibonacci [2023-11-23 21:09:28,816 INFO L138 BoogieDeclarations]: Found implementation of procedure fibonacci [2023-11-23 21:09:28,816 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2023-11-23 21:09:28,817 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2023-11-23 21:09:28,817 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2023-11-23 21:09:28,817 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2023-11-23 21:09:28,897 INFO L241 CfgBuilder]: Building ICFG [2023-11-23 21:09:28,900 INFO L267 CfgBuilder]: Building CFG for each procedure with an implementation [2023-11-23 21:09:29,096 INFO L282 CfgBuilder]: Performing block encoding [2023-11-23 21:09:29,128 INFO L304 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2023-11-23 21:09:29,128 INFO L309 CfgBuilder]: Removed 0 assume(true) statements. [2023-11-23 21:09:29,130 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 23.11 09:09:29 BoogieIcfgContainer [2023-11-23 21:09:29,130 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2023-11-23 21:09:29,134 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2023-11-23 21:09:29,134 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2023-11-23 21:09:29,138 INFO L274 PluginConnector]: TraceAbstraction initialized [2023-11-23 21:09:29,138 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 23.11 09:09:28" (1/3) ... [2023-11-23 21:09:29,139 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@64d4e3fa and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 23.11 09:09:29, skipping insertion in model container [2023-11-23 21:09:29,139 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 09:09:28" (2/3) ... [2023-11-23 21:09:29,139 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@64d4e3fa and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 23.11 09:09:29, skipping insertion in model container [2023-11-23 21:09:29,140 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 23.11 09:09:29" (3/3) ... [2023-11-23 21:09:29,141 INFO L112 eAbstractionObserver]: Analyzing ICFG Fibonacci01-2.c [2023-11-23 21:09:29,162 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2023-11-23 21:09:29,162 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 6 error locations. [2023-11-23 21:09:29,210 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-11-23 21:09:29,217 INFO L357 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, mHoare=true, mAutomataTypeConcurrency=FINITE_AUTOMATA, 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;@1496bf07, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2023-11-23 21:09:29,217 INFO L358 AbstractCegarLoop]: Starting to check reachability of 6 error locations. [2023-11-23 21:09:29,220 INFO L276 IsEmpty]: Start isEmpty. Operand has 27 states, 16 states have (on average 1.5625) internal successors, (25), 22 states have internal predecessors, (25), 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) [2023-11-23 21:09:29,227 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 8 [2023-11-23 21:09:29,227 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 21:09:29,228 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2023-11-23 21:09:29,229 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2023-11-23 21:09:29,233 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 21:09:29,234 INFO L85 PathProgramCache]: Analyzing trace with hash -878809267, now seen corresponding path program 1 times [2023-11-23 21:09:29,242 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-23 21:09:29,242 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1260407880] [2023-11-23 21:09:29,243 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 21:09:29,243 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 21:09:29,342 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 21:09:29,485 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-23 21:09:29,486 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-23 21:09:29,487 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1260407880] [2023-11-23 21:09:29,488 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1260407880] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-23 21:09:29,488 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-23 21:09:29,488 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2023-11-23 21:09:29,490 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [51305225] [2023-11-23 21:09:29,492 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-23 21:09:29,511 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-11-23 21:09:29,512 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-23 21:09:29,567 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-11-23 21:09:29,568 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2023-11-23 21:09:29,570 INFO L87 Difference]: Start difference. First operand has 27 states, 16 states have (on average 1.5625) internal successors, (25), 22 states have internal predecessors, (25), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Second operand has 3 states, 2 states have (on average 3.0) internal successors, (6), 3 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-23 21:09:29,650 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 21:09:29,651 INFO L93 Difference]: Finished difference Result 29 states and 35 transitions. [2023-11-23 21:09:29,652 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-11-23 21:09:29,653 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 2 states have (on average 3.0) internal successors, (6), 3 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 7 [2023-11-23 21:09:29,654 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 21:09:29,661 INFO L225 Difference]: With dead ends: 29 [2023-11-23 21:09:29,661 INFO L226 Difference]: Without dead ends: 24 [2023-11-23 21:09:29,664 INFO L412 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 [2023-11-23 21:09:29,668 INFO L413 NwaCegarLoop]: 22 mSDtfsCounter, 14 mSDsluCounter, 8 mSDsCounter, 0 mSdLazyCounter, 16 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 16 SdHoareTripleChecker+Valid, 30 SdHoareTripleChecker+Invalid, 17 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 16 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-23 21:09:29,669 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [16 Valid, 30 Invalid, 17 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 16 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-23 21:09:29,687 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 24 states. [2023-11-23 21:09:29,706 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 24 to 22. [2023-11-23 21:09:29,707 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 22 states, 14 states have (on average 1.4285714285714286) internal successors, (20), 18 states have internal predecessors, (20), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2023-11-23 21:09:29,709 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 22 states to 22 states and 25 transitions. [2023-11-23 21:09:29,710 INFO L78 Accepts]: Start accepts. Automaton has 22 states and 25 transitions. Word has length 7 [2023-11-23 21:09:29,710 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 21:09:29,711 INFO L495 AbstractCegarLoop]: Abstraction has 22 states and 25 transitions. [2023-11-23 21:09:29,711 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 2 states have (on average 3.0) internal successors, (6), 3 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-23 21:09:29,711 INFO L276 IsEmpty]: Start isEmpty. Operand 22 states and 25 transitions. [2023-11-23 21:09:29,712 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 9 [2023-11-23 21:09:29,713 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 21:09:29,713 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2023-11-23 21:09:29,713 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2023-11-23 21:09:29,713 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2023-11-23 21:09:29,714 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 21:09:29,714 INFO L85 PathProgramCache]: Analyzing trace with hash -1473283459, now seen corresponding path program 1 times [2023-11-23 21:09:29,715 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-23 21:09:29,715 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1486738070] [2023-11-23 21:09:29,715 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 21:09:29,715 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 21:09:29,729 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 21:09:29,790 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-23 21:09:29,790 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-23 21:09:29,790 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1486738070] [2023-11-23 21:09:29,791 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1486738070] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-23 21:09:29,791 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-23 21:09:29,791 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2023-11-23 21:09:29,791 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1501968212] [2023-11-23 21:09:29,791 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-23 21:09:29,793 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-11-23 21:09:29,793 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-23 21:09:29,794 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-11-23 21:09:29,794 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2023-11-23 21:09:29,794 INFO L87 Difference]: Start difference. First operand 22 states and 25 transitions. Second operand has 5 states, 4 states have (on average 1.75) 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) [2023-11-23 21:09:29,871 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 21:09:29,871 INFO L93 Difference]: Finished difference Result 22 states and 25 transitions. [2023-11-23 21:09:29,872 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2023-11-23 21:09:29,872 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 1.75) 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 [2023-11-23 21:09:29,872 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 21:09:29,873 INFO L225 Difference]: With dead ends: 22 [2023-11-23 21:09:29,873 INFO L226 Difference]: Without dead ends: 20 [2023-11-23 21:09:29,874 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 0 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2023-11-23 21:09:29,875 INFO L413 NwaCegarLoop]: 10 mSDtfsCounter, 28 mSDsluCounter, 9 mSDsCounter, 0 mSdLazyCounter, 32 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 28 SdHoareTripleChecker+Valid, 19 SdHoareTripleChecker+Invalid, 39 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 32 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-11-23 21:09:29,876 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [28 Valid, 19 Invalid, 39 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 32 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-11-23 21:09:29,877 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 20 states. [2023-11-23 21:09:29,882 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 20 to 20. [2023-11-23 21:09:29,882 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 20 states, 14 states have (on average 1.2857142857142858) internal successors, (18), 16 states have internal predecessors, (18), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2023-11-23 21:09:29,884 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 20 states to 20 states and 23 transitions. [2023-11-23 21:09:29,884 INFO L78 Accepts]: Start accepts. Automaton has 20 states and 23 transitions. Word has length 8 [2023-11-23 21:09:29,884 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 21:09:29,885 INFO L495 AbstractCegarLoop]: Abstraction has 20 states and 23 transitions. [2023-11-23 21:09:29,885 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 1.75) 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) [2023-11-23 21:09:29,885 INFO L276 IsEmpty]: Start isEmpty. Operand 20 states and 23 transitions. [2023-11-23 21:09:29,886 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2023-11-23 21:09:29,886 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 21:09:29,887 INFO L195 NwaCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-23 21:09:29,887 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2023-11-23 21:09:29,887 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting fibonacciErr4ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2023-11-23 21:09:29,888 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 21:09:29,888 INFO L85 PathProgramCache]: Analyzing trace with hash -980216179, now seen corresponding path program 1 times [2023-11-23 21:09:29,889 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-23 21:09:29,889 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [996346372] [2023-11-23 21:09:29,889 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 21:09:29,889 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 21:09:29,915 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 21:09:30,097 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2023-11-23 21:09:30,098 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-23 21:09:30,098 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [996346372] [2023-11-23 21:09:30,098 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [996346372] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-23 21:09:30,098 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-23 21:09:30,098 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2023-11-23 21:09:30,099 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1694325502] [2023-11-23 21:09:30,099 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-23 21:09:30,099 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-11-23 21:09:30,100 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-23 21:09:30,101 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-11-23 21:09:30,101 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2023-11-23 21:09:30,101 INFO L87 Difference]: Start difference. First operand 20 states and 23 transitions. Second operand has 5 states, 4 states have (on average 3.5) internal successors, (14), 5 states have internal predecessors, (14), 2 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2023-11-23 21:09:30,144 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 21:09:30,144 INFO L93 Difference]: Finished difference Result 36 states and 42 transitions. [2023-11-23 21:09:30,145 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2023-11-23 21:09:30,145 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 3.5) internal successors, (14), 5 states have internal predecessors, (14), 2 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 23 [2023-11-23 21:09:30,146 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 21:09:30,147 INFO L225 Difference]: With dead ends: 36 [2023-11-23 21:09:30,147 INFO L226 Difference]: Without dead ends: 34 [2023-11-23 21:09:30,147 INFO L412 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 [2023-11-23 21:09:30,149 INFO L413 NwaCegarLoop]: 16 mSDtfsCounter, 6 mSDsluCounter, 33 mSDsCounter, 0 mSdLazyCounter, 28 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 49 SdHoareTripleChecker+Invalid, 30 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 28 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-11-23 21:09:30,149 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 49 Invalid, 30 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 28 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-11-23 21:09:30,150 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 34 states. [2023-11-23 21:09:30,157 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 34 to 29. [2023-11-23 21:09:30,158 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 29 states, 21 states have (on average 1.1904761904761905) internal successors, (25), 23 states have internal predecessors, (25), 4 states have call successors, (4), 1 states have call predecessors, (4), 2 states have return successors, (6), 4 states have call predecessors, (6), 3 states have call successors, (6) [2023-11-23 21:09:30,160 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 29 states to 29 states and 35 transitions. [2023-11-23 21:09:30,160 INFO L78 Accepts]: Start accepts. Automaton has 29 states and 35 transitions. Word has length 23 [2023-11-23 21:09:30,161 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 21:09:30,161 INFO L495 AbstractCegarLoop]: Abstraction has 29 states and 35 transitions. [2023-11-23 21:09:30,161 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 3.5) internal successors, (14), 5 states have internal predecessors, (14), 2 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2023-11-23 21:09:30,161 INFO L276 IsEmpty]: Start isEmpty. Operand 29 states and 35 transitions. [2023-11-23 21:09:30,163 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2023-11-23 21:09:30,163 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 21:09:30,163 INFO L195 NwaCegarLoop]: trace histogram [4, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-23 21:09:30,164 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2023-11-23 21:09:30,164 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting fibonacciErr4ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2023-11-23 21:09:30,165 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 21:09:30,165 INFO L85 PathProgramCache]: Analyzing trace with hash -1998791835, now seen corresponding path program 1 times [2023-11-23 21:09:30,165 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-23 21:09:30,166 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [226426658] [2023-11-23 21:09:30,166 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 21:09:30,166 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 21:09:30,186 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 21:09:30,364 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2023-11-23 21:09:30,364 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-23 21:09:30,365 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [226426658] [2023-11-23 21:09:30,365 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [226426658] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-23 21:09:30,365 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1807513348] [2023-11-23 21:09:30,365 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 21:09:30,366 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 21:09:30,366 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/z3 [2023-11-23 21:09:30,368 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-23 21:09:30,396 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2023-11-23 21:09:30,436 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 21:09:30,438 INFO L262 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 6 conjunts are in the unsatisfiable core [2023-11-23 21:09:30,450 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-23 21:09:30,597 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 6 proven. 3 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2023-11-23 21:09:30,598 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-23 21:09:30,771 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 6 proven. 3 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2023-11-23 21:09:30,773 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1807513348] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-23 21:09:30,773 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1947815916] [2023-11-23 21:09:30,801 INFO L159 IcfgInterpreter]: Started Sifa with 18 locations of interest [2023-11-23 21:09:30,802 INFO L166 IcfgInterpreter]: Building call graph [2023-11-23 21:09:30,806 FATAL L? ?]: Ignoring exception! java.lang.IllegalArgumentException: Recursive programs are not supported. at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.topsortRelevant(CallGraph.java:132) at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.(CallGraph.java:97) at de.uni_freiburg.informatik.ultimate.lib.sifa.IcfgInterpreter.(IcfgInterpreter.java:92) at de.uni_freiburg.informatik.ultimate.plugins.sifa.SifaBuilder.construct(SifaBuilder.java:96) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.SifaRunner.(SifaRunner.java:98) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleSifa.construct(IpTcStrategyModuleSifa.java:68) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getOrConstruct(IpTcStrategyModuleBase.java:101) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getInterpolantComputationStatus(IpTcStrategyModuleBase.java:77) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.tryExecuteInterpolantGenerator(AutomatonFreeRefinementEngine.java:267) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.generateProof(AutomatonFreeRefinementEngine.java:148) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.executeStrategy(AutomatonFreeRefinementEngine.java:137) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.(AutomatonFreeRefinementEngine.java:85) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.TraceAbstractionRefinementEngine.(TraceAbstractionRefinementEngine.java:82) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.BasicCegarLoop.isCounterexampleFeasible(BasicCegarLoop.java:337) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterate(AbstractCegarLoop.java:431) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.startCegar(AbstractCegarLoop.java:366) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.runCegar(AbstractCegarLoop.java:348) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.executeCegarLoop(TraceAbstractionStarter.java:415) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseProgram(TraceAbstractionStarter.java:302) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseSequentialProgram(TraceAbstractionStarter.java:262) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.runCegarLoops(TraceAbstractionStarter.java:175) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.(TraceAbstractionStarter.java:154) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver.finish(TraceAbstractionObserver.java:124) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runObserver(PluginConnector.java:167) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runTool(PluginConnector.java:150) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.run(PluginConnector.java:127) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.executePluginConnector(ToolchainWalker.java:233) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.processPlugin(ToolchainWalker.java:227) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walkUnprotected(ToolchainWalker.java:144) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walk(ToolchainWalker.java:106) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainManager$Toolchain.processToolchain(ToolchainManager.java:319) at de.uni_freiburg.informatik.ultimate.core.coreplugin.toolchain.DefaultToolchainJob.run(DefaultToolchainJob.java:145) at org.eclipse.core.internal.jobs.Worker.run(Worker.java:63) [2023-11-23 21:09:30,808 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-23 21:09:30,809 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 7, 7] total 15 [2023-11-23 21:09:30,813 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1809762970] [2023-11-23 21:09:30,813 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-23 21:09:30,815 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2023-11-23 21:09:30,816 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-23 21:09:30,819 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2023-11-23 21:09:30,821 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=35, Invalid=175, Unknown=0, NotChecked=0, Total=210 [2023-11-23 21:09:30,821 INFO L87 Difference]: Start difference. First operand 29 states and 35 transitions. Second operand has 15 states, 15 states have (on average 2.4) internal successors, (36), 15 states have internal predecessors, (36), 4 states have call successors, (5), 1 states have call predecessors, (5), 5 states have return successors, (6), 5 states have call predecessors, (6), 4 states have call successors, (6) [2023-11-23 21:09:31,160 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 21:09:31,160 INFO L93 Difference]: Finished difference Result 90 states and 128 transitions. [2023-11-23 21:09:31,161 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2023-11-23 21:09:31,161 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 15 states have (on average 2.4) internal successors, (36), 15 states have internal predecessors, (36), 4 states have call successors, (5), 1 states have call predecessors, (5), 5 states have return successors, (6), 5 states have call predecessors, (6), 4 states have call successors, (6) Word has length 30 [2023-11-23 21:09:31,162 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 21:09:31,164 INFO L225 Difference]: With dead ends: 90 [2023-11-23 21:09:31,164 INFO L226 Difference]: Without dead ends: 64 [2023-11-23 21:09:31,166 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 72 GetRequests, 50 SyntacticMatches, 1 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 39 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=126, Invalid=380, Unknown=0, NotChecked=0, Total=506 [2023-11-23 21:09:31,175 INFO L413 NwaCegarLoop]: 10 mSDtfsCounter, 121 mSDsluCounter, 57 mSDsCounter, 0 mSdLazyCounter, 157 mSolverCounterSat, 49 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 121 SdHoareTripleChecker+Valid, 67 SdHoareTripleChecker+Invalid, 206 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 49 IncrementalHoareTripleChecker+Valid, 157 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-11-23 21:09:31,176 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [121 Valid, 67 Invalid, 206 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [49 Valid, 157 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-11-23 21:09:31,177 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 64 states. [2023-11-23 21:09:31,191 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 64 to 52. [2023-11-23 21:09:31,192 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 52 states, 38 states have (on average 1.105263157894737) internal successors, (42), 41 states have internal predecessors, (42), 7 states have call successors, (7), 2 states have call predecessors, (7), 5 states have return successors, (18), 8 states have call predecessors, (18), 6 states have call successors, (18) [2023-11-23 21:09:31,194 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 52 states to 52 states and 67 transitions. [2023-11-23 21:09:31,194 INFO L78 Accepts]: Start accepts. Automaton has 52 states and 67 transitions. Word has length 30 [2023-11-23 21:09:31,195 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 21:09:31,195 INFO L495 AbstractCegarLoop]: Abstraction has 52 states and 67 transitions. [2023-11-23 21:09:31,195 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 2.4) internal successors, (36), 15 states have internal predecessors, (36), 4 states have call successors, (5), 1 states have call predecessors, (5), 5 states have return successors, (6), 5 states have call predecessors, (6), 4 states have call successors, (6) [2023-11-23 21:09:31,196 INFO L276 IsEmpty]: Start isEmpty. Operand 52 states and 67 transitions. [2023-11-23 21:09:31,197 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2023-11-23 21:09:31,197 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 21:09:31,198 INFO L195 NwaCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-23 21:09:31,228 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2023-11-23 21:09:31,408 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 21:09:31,409 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting fibonacciErr4ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2023-11-23 21:09:31,409 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 21:09:31,409 INFO L85 PathProgramCache]: Analyzing trace with hash -311801495, now seen corresponding path program 2 times [2023-11-23 21:09:31,409 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-23 21:09:31,410 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [105112379] [2023-11-23 21:09:31,410 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 21:09:31,410 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 21:09:31,421 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 21:09:31,496 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2023-11-23 21:09:31,497 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-23 21:09:31,497 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [105112379] [2023-11-23 21:09:31,497 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [105112379] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-23 21:09:31,497 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [673026878] [2023-11-23 21:09:31,498 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-11-23 21:09:31,498 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 21:09:31,498 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/z3 [2023-11-23 21:09:31,499 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-23 21:09:31,516 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2023-11-23 21:09:31,555 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 2 check-sat command(s) [2023-11-23 21:09:31,555 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-23 21:09:31,557 INFO L262 TraceCheckSpWp]: Trace formula consists of 57 conjuncts, 4 conjunts are in the unsatisfiable core [2023-11-23 21:09:31,562 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-23 21:09:31,613 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2023-11-23 21:09:31,614 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-11-23 21:09:31,614 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [673026878] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-23 21:09:31,614 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-11-23 21:09:31,614 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [5] total 8 [2023-11-23 21:09:31,615 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [691186483] [2023-11-23 21:09:31,615 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-23 21:09:31,615 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-11-23 21:09:31,616 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-23 21:09:31,616 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-11-23 21:09:31,617 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=22, Invalid=50, Unknown=0, NotChecked=0, Total=72 [2023-11-23 21:09:31,617 INFO L87 Difference]: Start difference. First operand 52 states and 67 transitions. Second operand has 5 states, 4 states have (on average 4.0) internal successors, (16), 5 states have internal predecessors, (16), 2 states have call successors, (3), 1 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2023-11-23 21:09:31,664 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 21:09:31,664 INFO L93 Difference]: Finished difference Result 60 states and 75 transitions. [2023-11-23 21:09:31,665 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2023-11-23 21:09:31,665 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 4.0) internal successors, (16), 5 states have internal predecessors, (16), 2 states have call successors, (3), 1 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 24 [2023-11-23 21:09:31,666 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 21:09:31,667 INFO L225 Difference]: With dead ends: 60 [2023-11-23 21:09:31,667 INFO L226 Difference]: Without dead ends: 59 [2023-11-23 21:09:31,668 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 28 GetRequests, 21 SyntacticMatches, 0 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=22, Invalid=50, Unknown=0, NotChecked=0, Total=72 [2023-11-23 21:09:31,669 INFO L413 NwaCegarLoop]: 16 mSDtfsCounter, 6 mSDsluCounter, 41 mSDsCounter, 0 mSdLazyCounter, 25 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 57 SdHoareTripleChecker+Invalid, 27 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 25 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-11-23 21:09:31,670 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 57 Invalid, 27 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 25 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-11-23 21:09:31,671 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 59 states. [2023-11-23 21:09:31,680 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 59 to 54. [2023-11-23 21:09:31,681 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 54 states, 40 states have (on average 1.1) internal successors, (44), 42 states have internal predecessors, (44), 7 states have call successors, (7), 2 states have call predecessors, (7), 5 states have return successors, (18), 9 states have call predecessors, (18), 6 states have call successors, (18) [2023-11-23 21:09:31,683 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 69 transitions. [2023-11-23 21:09:31,683 INFO L78 Accepts]: Start accepts. Automaton has 54 states and 69 transitions. Word has length 24 [2023-11-23 21:09:31,683 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 21:09:31,684 INFO L495 AbstractCegarLoop]: Abstraction has 54 states and 69 transitions. [2023-11-23 21:09:31,684 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 4.0) internal successors, (16), 5 states have internal predecessors, (16), 2 states have call successors, (3), 1 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2023-11-23 21:09:31,684 INFO L276 IsEmpty]: Start isEmpty. Operand 54 states and 69 transitions. [2023-11-23 21:09:31,685 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2023-11-23 21:09:31,686 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 21:09:31,686 INFO L195 NwaCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-23 21:09:31,708 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2023-11-23 21:09:31,906 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 21:09:31,907 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting fibonacciErr5ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2023-11-23 21:09:31,907 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 21:09:31,907 INFO L85 PathProgramCache]: Analyzing trace with hash -1075911699, now seen corresponding path program 1 times [2023-11-23 21:09:31,907 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-23 21:09:31,908 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1021047147] [2023-11-23 21:09:31,908 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 21:09:31,908 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 21:09:31,925 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 21:09:32,020 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2023-11-23 21:09:32,021 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-23 21:09:32,021 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1021047147] [2023-11-23 21:09:32,021 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1021047147] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-23 21:09:32,021 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1148597814] [2023-11-23 21:09:32,022 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 21:09:32,022 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 21:09:32,022 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/z3 [2023-11-23 21:09:32,023 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-23 21:09:32,044 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2023-11-23 21:09:32,071 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 21:09:32,072 INFO L262 TraceCheckSpWp]: Trace formula consists of 68 conjuncts, 5 conjunts are in the unsatisfiable core [2023-11-23 21:09:32,074 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-23 21:09:32,127 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2023-11-23 21:09:32,128 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-11-23 21:09:32,128 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1148597814] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-23 21:09:32,128 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-11-23 21:09:32,128 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [5] total 9 [2023-11-23 21:09:32,129 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [589601708] [2023-11-23 21:09:32,129 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-23 21:09:32,129 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2023-11-23 21:09:32,130 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-23 21:09:32,130 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2023-11-23 21:09:32,131 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=64, Unknown=0, NotChecked=0, Total=90 [2023-11-23 21:09:32,131 INFO L87 Difference]: Start difference. First operand 54 states and 69 transitions. Second operand has 6 states, 5 states have (on average 3.4) internal successors, (17), 6 states have internal predecessors, (17), 2 states have call successors, (3), 1 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2023-11-23 21:09:32,171 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 21:09:32,171 INFO L93 Difference]: Finished difference Result 83 states and 116 transitions. [2023-11-23 21:09:32,172 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-11-23 21:09:32,172 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 3.4) internal successors, (17), 6 states have internal predecessors, (17), 2 states have call successors, (3), 1 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 25 [2023-11-23 21:09:32,173 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 21:09:32,175 INFO L225 Difference]: With dead ends: 83 [2023-11-23 21:09:32,175 INFO L226 Difference]: Without dead ends: 82 [2023-11-23 21:09:32,176 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 29 GetRequests, 21 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 12 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=26, Invalid=64, Unknown=0, NotChecked=0, Total=90 [2023-11-23 21:09:32,177 INFO L413 NwaCegarLoop]: 16 mSDtfsCounter, 4 mSDsluCounter, 46 mSDsCounter, 0 mSdLazyCounter, 32 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 62 SdHoareTripleChecker+Invalid, 33 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 32 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-11-23 21:09:32,178 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 62 Invalid, 33 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 32 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-11-23 21:09:32,179 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 82 states. [2023-11-23 21:09:32,203 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 82 to 63. [2023-11-23 21:09:32,204 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 63 states, 47 states have (on average 1.0851063829787233) internal successors, (51), 49 states have internal predecessors, (51), 8 states have call successors, (8), 2 states have call predecessors, (8), 6 states have return successors, (27), 11 states have call predecessors, (27), 7 states have call successors, (27) [2023-11-23 21:09:32,209 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 63 states to 63 states and 86 transitions. [2023-11-23 21:09:32,209 INFO L78 Accepts]: Start accepts. Automaton has 63 states and 86 transitions. Word has length 25 [2023-11-23 21:09:32,210 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 21:09:32,210 INFO L495 AbstractCegarLoop]: Abstraction has 63 states and 86 transitions. [2023-11-23 21:09:32,210 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 3.4) internal successors, (17), 6 states have internal predecessors, (17), 2 states have call successors, (3), 1 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2023-11-23 21:09:32,210 INFO L276 IsEmpty]: Start isEmpty. Operand 63 states and 86 transitions. [2023-11-23 21:09:32,220 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 46 [2023-11-23 21:09:32,220 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 21:09:32,220 INFO L195 NwaCegarLoop]: trace histogram [5, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1] [2023-11-23 21:09:32,252 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2023-11-23 21:09:32,441 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable5 [2023-11-23 21:09:32,441 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting fibonacciErr5ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2023-11-23 21:09:32,442 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 21:09:32,442 INFO L85 PathProgramCache]: Analyzing trace with hash -155051222, now seen corresponding path program 1 times [2023-11-23 21:09:32,443 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-23 21:09:32,443 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1927248068] [2023-11-23 21:09:32,443 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 21:09:32,443 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 21:09:32,458 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 21:09:32,598 INFO L134 CoverageAnalysis]: Checked inductivity of 48 backedges. 2 proven. 15 refuted. 0 times theorem prover too weak. 31 trivial. 0 not checked. [2023-11-23 21:09:32,598 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-23 21:09:32,598 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1927248068] [2023-11-23 21:09:32,598 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1927248068] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-23 21:09:32,599 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1805173185] [2023-11-23 21:09:32,599 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 21:09:32,599 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 21:09:32,599 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/z3 [2023-11-23 21:09:32,600 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-23 21:09:32,610 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2023-11-23 21:09:32,657 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 21:09:32,658 INFO L262 TraceCheckSpWp]: Trace formula consists of 105 conjuncts, 9 conjunts are in the unsatisfiable core [2023-11-23 21:09:32,661 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-23 21:09:32,772 INFO L134 CoverageAnalysis]: Checked inductivity of 48 backedges. 2 proven. 7 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2023-11-23 21:09:32,773 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-23 21:09:33,016 INFO L134 CoverageAnalysis]: Checked inductivity of 48 backedges. 6 proven. 7 refuted. 0 times theorem prover too weak. 35 trivial. 0 not checked. [2023-11-23 21:09:33,016 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1805173185] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-23 21:09:33,017 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [198028524] [2023-11-23 21:09:33,022 INFO L159 IcfgInterpreter]: Started Sifa with 19 locations of interest [2023-11-23 21:09:33,022 INFO L166 IcfgInterpreter]: Building call graph [2023-11-23 21:09:33,023 FATAL L? ?]: Ignoring exception! java.lang.IllegalArgumentException: Recursive programs are not supported. at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.topsortRelevant(CallGraph.java:132) at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.(CallGraph.java:97) at de.uni_freiburg.informatik.ultimate.lib.sifa.IcfgInterpreter.(IcfgInterpreter.java:92) at de.uni_freiburg.informatik.ultimate.plugins.sifa.SifaBuilder.construct(SifaBuilder.java:96) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.SifaRunner.(SifaRunner.java:98) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleSifa.construct(IpTcStrategyModuleSifa.java:68) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getOrConstruct(IpTcStrategyModuleBase.java:101) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getInterpolantComputationStatus(IpTcStrategyModuleBase.java:77) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.tryExecuteInterpolantGenerator(AutomatonFreeRefinementEngine.java:267) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.generateProof(AutomatonFreeRefinementEngine.java:148) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.executeStrategy(AutomatonFreeRefinementEngine.java:137) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.(AutomatonFreeRefinementEngine.java:85) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.TraceAbstractionRefinementEngine.(TraceAbstractionRefinementEngine.java:82) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.BasicCegarLoop.isCounterexampleFeasible(BasicCegarLoop.java:337) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterate(AbstractCegarLoop.java:431) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.startCegar(AbstractCegarLoop.java:366) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.runCegar(AbstractCegarLoop.java:348) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.executeCegarLoop(TraceAbstractionStarter.java:415) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseProgram(TraceAbstractionStarter.java:302) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseSequentialProgram(TraceAbstractionStarter.java:262) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.runCegarLoops(TraceAbstractionStarter.java:175) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.(TraceAbstractionStarter.java:154) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver.finish(TraceAbstractionObserver.java:124) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runObserver(PluginConnector.java:167) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runTool(PluginConnector.java:150) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.run(PluginConnector.java:127) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.executePluginConnector(ToolchainWalker.java:233) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.processPlugin(ToolchainWalker.java:227) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walkUnprotected(ToolchainWalker.java:144) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walk(ToolchainWalker.java:106) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainManager$Toolchain.processToolchain(ToolchainManager.java:319) at de.uni_freiburg.informatik.ultimate.core.coreplugin.toolchain.DefaultToolchainJob.run(DefaultToolchainJob.java:145) at org.eclipse.core.internal.jobs.Worker.run(Worker.java:63) [2023-11-23 21:09:33,024 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-23 21:09:33,024 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 6, 7] total 15 [2023-11-23 21:09:33,025 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [282151874] [2023-11-23 21:09:33,025 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-23 21:09:33,027 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2023-11-23 21:09:33,027 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-23 21:09:33,028 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2023-11-23 21:09:33,029 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=62, Invalid=178, Unknown=0, NotChecked=0, Total=240 [2023-11-23 21:09:33,030 INFO L87 Difference]: Start difference. First operand 63 states and 86 transitions. Second operand has 16 states, 15 states have (on average 2.933333333333333) internal successors, (44), 16 states have internal predecessors, (44), 4 states have call successors, (5), 1 states have call predecessors, (5), 5 states have return successors, (9), 9 states have call predecessors, (9), 4 states have call successors, (9) [2023-11-23 21:09:33,314 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 21:09:33,314 INFO L93 Difference]: Finished difference Result 147 states and 216 transitions. [2023-11-23 21:09:33,315 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2023-11-23 21:09:33,315 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 15 states have (on average 2.933333333333333) internal successors, (44), 16 states have internal predecessors, (44), 4 states have call successors, (5), 1 states have call predecessors, (5), 5 states have return successors, (9), 9 states have call predecessors, (9), 4 states have call successors, (9) Word has length 45 [2023-11-23 21:09:33,319 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 21:09:33,326 INFO L225 Difference]: With dead ends: 147 [2023-11-23 21:09:33,327 INFO L226 Difference]: Without dead ends: 145 [2023-11-23 21:09:33,330 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 105 GetRequests, 81 SyntacticMatches, 2 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 127 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=157, Invalid=395, Unknown=0, NotChecked=0, Total=552 [2023-11-23 21:09:33,332 INFO L413 NwaCegarLoop]: 23 mSDtfsCounter, 23 mSDsluCounter, 191 mSDsCounter, 0 mSdLazyCounter, 208 mSolverCounterSat, 10 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 29 SdHoareTripleChecker+Valid, 214 SdHoareTripleChecker+Invalid, 218 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 208 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-23 21:09:33,333 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [29 Valid, 214 Invalid, 218 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 208 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-23 21:09:33,335 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 145 states. [2023-11-23 21:09:33,371 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 145 to 97. [2023-11-23 21:09:33,375 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 97 states, 75 states have (on average 1.08) internal successors, (81), 74 states have internal predecessors, (81), 11 states have call successors, (11), 2 states have call predecessors, (11), 9 states have return successors, (66), 20 states have call predecessors, (66), 10 states have call successors, (66) [2023-11-23 21:09:33,381 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 97 states to 97 states and 158 transitions. [2023-11-23 21:09:33,382 INFO L78 Accepts]: Start accepts. Automaton has 97 states and 158 transitions. Word has length 45 [2023-11-23 21:09:33,382 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 21:09:33,382 INFO L495 AbstractCegarLoop]: Abstraction has 97 states and 158 transitions. [2023-11-23 21:09:33,383 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 15 states have (on average 2.933333333333333) internal successors, (44), 16 states have internal predecessors, (44), 4 states have call successors, (5), 1 states have call predecessors, (5), 5 states have return successors, (9), 9 states have call predecessors, (9), 4 states have call successors, (9) [2023-11-23 21:09:33,383 INFO L276 IsEmpty]: Start isEmpty. Operand 97 states and 158 transitions. [2023-11-23 21:09:33,387 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 63 [2023-11-23 21:09:33,388 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 21:09:33,388 INFO L195 NwaCegarLoop]: trace histogram [7, 6, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1] [2023-11-23 21:09:33,416 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2023-11-23 21:09:33,600 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable6 [2023-11-23 21:09:33,600 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting fibonacciErr4ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2023-11-23 21:09:33,601 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 21:09:33,601 INFO L85 PathProgramCache]: Analyzing trace with hash 1083310235, now seen corresponding path program 1 times [2023-11-23 21:09:33,602 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-23 21:09:33,602 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1170426015] [2023-11-23 21:09:33,602 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 21:09:33,602 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 21:09:33,617 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 21:09:33,781 INFO L134 CoverageAnalysis]: Checked inductivity of 106 backedges. 25 proven. 46 refuted. 0 times theorem prover too weak. 35 trivial. 0 not checked. [2023-11-23 21:09:33,782 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-23 21:09:33,782 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1170426015] [2023-11-23 21:09:33,782 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1170426015] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-23 21:09:33,782 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [199073522] [2023-11-23 21:09:33,782 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 21:09:33,782 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 21:09:33,783 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/z3 [2023-11-23 21:09:33,789 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-23 21:09:33,806 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2023-11-23 21:09:33,858 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 21:09:33,860 INFO L262 TraceCheckSpWp]: Trace formula consists of 137 conjuncts, 8 conjunts are in the unsatisfiable core [2023-11-23 21:09:33,862 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-23 21:09:33,969 INFO L134 CoverageAnalysis]: Checked inductivity of 106 backedges. 4 proven. 33 refuted. 0 times theorem prover too weak. 69 trivial. 0 not checked. [2023-11-23 21:09:33,969 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-23 21:09:34,195 INFO L134 CoverageAnalysis]: Checked inductivity of 106 backedges. 2 proven. 31 refuted. 0 times theorem prover too weak. 73 trivial. 0 not checked. [2023-11-23 21:09:34,196 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [199073522] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-23 21:09:34,196 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [188820314] [2023-11-23 21:09:34,199 INFO L159 IcfgInterpreter]: Started Sifa with 19 locations of interest [2023-11-23 21:09:34,199 INFO L166 IcfgInterpreter]: Building call graph [2023-11-23 21:09:34,199 FATAL L? ?]: Ignoring exception! java.lang.IllegalArgumentException: Recursive programs are not supported. at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.topsortRelevant(CallGraph.java:132) at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.(CallGraph.java:97) at de.uni_freiburg.informatik.ultimate.lib.sifa.IcfgInterpreter.(IcfgInterpreter.java:92) at de.uni_freiburg.informatik.ultimate.plugins.sifa.SifaBuilder.construct(SifaBuilder.java:96) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.SifaRunner.(SifaRunner.java:98) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleSifa.construct(IpTcStrategyModuleSifa.java:68) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getOrConstruct(IpTcStrategyModuleBase.java:101) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getInterpolantComputationStatus(IpTcStrategyModuleBase.java:77) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.tryExecuteInterpolantGenerator(AutomatonFreeRefinementEngine.java:267) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.generateProof(AutomatonFreeRefinementEngine.java:148) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.executeStrategy(AutomatonFreeRefinementEngine.java:137) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.(AutomatonFreeRefinementEngine.java:85) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.TraceAbstractionRefinementEngine.(TraceAbstractionRefinementEngine.java:82) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.BasicCegarLoop.isCounterexampleFeasible(BasicCegarLoop.java:337) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterate(AbstractCegarLoop.java:431) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.startCegar(AbstractCegarLoop.java:366) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.runCegar(AbstractCegarLoop.java:348) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.executeCegarLoop(TraceAbstractionStarter.java:415) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseProgram(TraceAbstractionStarter.java:302) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseSequentialProgram(TraceAbstractionStarter.java:262) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.runCegarLoops(TraceAbstractionStarter.java:175) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.(TraceAbstractionStarter.java:154) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver.finish(TraceAbstractionObserver.java:124) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runObserver(PluginConnector.java:167) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runTool(PluginConnector.java:150) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.run(PluginConnector.java:127) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.executePluginConnector(ToolchainWalker.java:233) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.processPlugin(ToolchainWalker.java:227) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walkUnprotected(ToolchainWalker.java:144) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walk(ToolchainWalker.java:106) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainManager$Toolchain.processToolchain(ToolchainManager.java:319) at de.uni_freiburg.informatik.ultimate.core.coreplugin.toolchain.DefaultToolchainJob.run(DefaultToolchainJob.java:145) at org.eclipse.core.internal.jobs.Worker.run(Worker.java:63) [2023-11-23 21:09:34,200 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-23 21:09:34,200 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 6, 5] total 18 [2023-11-23 21:09:34,201 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1561425104] [2023-11-23 21:09:34,201 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-23 21:09:34,202 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2023-11-23 21:09:34,202 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-23 21:09:34,203 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2023-11-23 21:09:34,203 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=49, Invalid=257, Unknown=0, NotChecked=0, Total=306 [2023-11-23 21:09:34,203 INFO L87 Difference]: Start difference. First operand 97 states and 158 transitions. Second operand has 18 states, 18 states have (on average 3.7222222222222223) internal successors, (67), 18 states have internal predecessors, (67), 7 states have call successors, (10), 1 states have call predecessors, (10), 6 states have return successors, (14), 10 states have call predecessors, (14), 7 states have call successors, (14) [2023-11-23 21:09:34,953 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 21:09:34,953 INFO L93 Difference]: Finished difference Result 258 states and 503 transitions. [2023-11-23 21:09:34,954 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 28 states. [2023-11-23 21:09:34,954 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 18 states have (on average 3.7222222222222223) internal successors, (67), 18 states have internal predecessors, (67), 7 states have call successors, (10), 1 states have call predecessors, (10), 6 states have return successors, (14), 10 states have call predecessors, (14), 7 states have call successors, (14) Word has length 62 [2023-11-23 21:09:34,955 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 21:09:34,957 INFO L225 Difference]: With dead ends: 258 [2023-11-23 21:09:34,958 INFO L226 Difference]: Without dead ends: 164 [2023-11-23 21:09:34,961 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 163 GetRequests, 119 SyntacticMatches, 3 SemanticMatches, 41 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 374 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=409, Invalid=1397, Unknown=0, NotChecked=0, Total=1806 [2023-11-23 21:09:34,962 INFO L413 NwaCegarLoop]: 10 mSDtfsCounter, 93 mSDsluCounter, 46 mSDsCounter, 0 mSdLazyCounter, 315 mSolverCounterSat, 37 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 93 SdHoareTripleChecker+Valid, 56 SdHoareTripleChecker+Invalid, 352 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 37 IncrementalHoareTripleChecker+Valid, 315 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2023-11-23 21:09:34,962 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [93 Valid, 56 Invalid, 352 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [37 Valid, 315 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2023-11-23 21:09:34,963 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 164 states. [2023-11-23 21:09:34,988 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 164 to 102. [2023-11-23 21:09:34,989 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 102 states, 79 states have (on average 1.0506329113924051) internal successors, (83), 79 states have internal predecessors, (83), 12 states have call successors, (12), 3 states have call predecessors, (12), 10 states have return successors, (75), 19 states have call predecessors, (75), 11 states have call successors, (75) [2023-11-23 21:09:34,991 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 102 states to 102 states and 170 transitions. [2023-11-23 21:09:34,991 INFO L78 Accepts]: Start accepts. Automaton has 102 states and 170 transitions. Word has length 62 [2023-11-23 21:09:34,992 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 21:09:34,992 INFO L495 AbstractCegarLoop]: Abstraction has 102 states and 170 transitions. [2023-11-23 21:09:34,992 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 18 states, 18 states have (on average 3.7222222222222223) internal successors, (67), 18 states have internal predecessors, (67), 7 states have call successors, (10), 1 states have call predecessors, (10), 6 states have return successors, (14), 10 states have call predecessors, (14), 7 states have call successors, (14) [2023-11-23 21:09:34,992 INFO L276 IsEmpty]: Start isEmpty. Operand 102 states and 170 transitions. [2023-11-23 21:09:34,995 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 183 [2023-11-23 21:09:34,995 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 21:09:34,995 INFO L195 NwaCegarLoop]: trace histogram [20, 17, 15, 10, 10, 10, 10, 9, 9, 9, 9, 9, 8, 8, 8, 7, 5, 5, 1, 1, 1, 1] [2023-11-23 21:09:35,021 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2023-11-23 21:09:35,216 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable7 [2023-11-23 21:09:35,216 INFO L420 AbstractCegarLoop]: === Iteration 9 === Targeting fibonacciErr5ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2023-11-23 21:09:35,217 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 21:09:35,217 INFO L85 PathProgramCache]: Analyzing trace with hash 1200563879, now seen corresponding path program 2 times [2023-11-23 21:09:35,217 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-23 21:09:35,217 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1608439784] [2023-11-23 21:09:35,217 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 21:09:35,217 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 21:09:35,259 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 21:09:35,685 INFO L134 CoverageAnalysis]: Checked inductivity of 1120 backedges. 123 proven. 424 refuted. 0 times theorem prover too weak. 573 trivial. 0 not checked. [2023-11-23 21:09:35,686 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-23 21:09:35,686 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1608439784] [2023-11-23 21:09:35,686 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1608439784] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-23 21:09:35,686 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [473808130] [2023-11-23 21:09:35,686 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-11-23 21:09:35,687 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 21:09:35,687 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/z3 [2023-11-23 21:09:35,688 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-23 21:09:35,712 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2023-11-23 21:09:35,767 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2023-11-23 21:09:35,767 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-23 21:09:35,768 INFO L262 TraceCheckSpWp]: Trace formula consists of 151 conjuncts, 8 conjunts are in the unsatisfiable core [2023-11-23 21:09:35,774 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-23 21:09:35,865 INFO L134 CoverageAnalysis]: Checked inductivity of 1120 backedges. 325 proven. 21 refuted. 0 times theorem prover too weak. 774 trivial. 0 not checked. [2023-11-23 21:09:35,865 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-23 21:09:36,257 INFO L134 CoverageAnalysis]: Checked inductivity of 1120 backedges. 325 proven. 22 refuted. 0 times theorem prover too weak. 773 trivial. 0 not checked. [2023-11-23 21:09:36,257 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [473808130] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-23 21:09:36,257 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1499999883] [2023-11-23 21:09:36,260 INFO L159 IcfgInterpreter]: Started Sifa with 19 locations of interest [2023-11-23 21:09:36,260 INFO L166 IcfgInterpreter]: Building call graph [2023-11-23 21:09:36,261 FATAL L? ?]: Ignoring exception! java.lang.IllegalArgumentException: Recursive programs are not supported. at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.topsortRelevant(CallGraph.java:132) at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.(CallGraph.java:97) at de.uni_freiburg.informatik.ultimate.lib.sifa.IcfgInterpreter.(IcfgInterpreter.java:92) at de.uni_freiburg.informatik.ultimate.plugins.sifa.SifaBuilder.construct(SifaBuilder.java:96) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.SifaRunner.(SifaRunner.java:98) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleSifa.construct(IpTcStrategyModuleSifa.java:68) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getOrConstruct(IpTcStrategyModuleBase.java:101) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getInterpolantComputationStatus(IpTcStrategyModuleBase.java:77) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.tryExecuteInterpolantGenerator(AutomatonFreeRefinementEngine.java:267) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.generateProof(AutomatonFreeRefinementEngine.java:148) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.executeStrategy(AutomatonFreeRefinementEngine.java:137) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.(AutomatonFreeRefinementEngine.java:85) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.TraceAbstractionRefinementEngine.(TraceAbstractionRefinementEngine.java:82) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.BasicCegarLoop.isCounterexampleFeasible(BasicCegarLoop.java:337) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterate(AbstractCegarLoop.java:431) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.startCegar(AbstractCegarLoop.java:366) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.runCegar(AbstractCegarLoop.java:348) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.executeCegarLoop(TraceAbstractionStarter.java:415) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseProgram(TraceAbstractionStarter.java:302) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseSequentialProgram(TraceAbstractionStarter.java:262) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.runCegarLoops(TraceAbstractionStarter.java:175) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.(TraceAbstractionStarter.java:154) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver.finish(TraceAbstractionObserver.java:124) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runObserver(PluginConnector.java:167) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runTool(PluginConnector.java:150) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.run(PluginConnector.java:127) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.executePluginConnector(ToolchainWalker.java:233) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.processPlugin(ToolchainWalker.java:227) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walkUnprotected(ToolchainWalker.java:144) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walk(ToolchainWalker.java:106) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainManager$Toolchain.processToolchain(ToolchainManager.java:319) at de.uni_freiburg.informatik.ultimate.core.coreplugin.toolchain.DefaultToolchainJob.run(DefaultToolchainJob.java:145) at org.eclipse.core.internal.jobs.Worker.run(Worker.java:63) [2023-11-23 21:09:36,262 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-23 21:09:36,262 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 8, 9] total 19 [2023-11-23 21:09:36,262 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1466362651] [2023-11-23 21:09:36,263 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-23 21:09:36,264 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2023-11-23 21:09:36,264 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-23 21:09:36,265 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2023-11-23 21:09:36,265 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=64, Invalid=278, Unknown=0, NotChecked=0, Total=342 [2023-11-23 21:09:36,265 INFO L87 Difference]: Start difference. First operand 102 states and 170 transitions. Second operand has 19 states, 19 states have (on average 5.052631578947368) internal successors, (96), 19 states have internal predecessors, (96), 11 states have call successors, (16), 2 states have call predecessors, (16), 8 states have return successors, (18), 11 states have call predecessors, (18), 10 states have call successors, (18) [2023-11-23 21:09:36,555 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 21:09:36,556 INFO L93 Difference]: Finished difference Result 172 states and 293 transitions. [2023-11-23 21:09:36,556 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2023-11-23 21:09:36,557 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 19 states have (on average 5.052631578947368) internal successors, (96), 19 states have internal predecessors, (96), 11 states have call successors, (16), 2 states have call predecessors, (16), 8 states have return successors, (18), 11 states have call predecessors, (18), 10 states have call successors, (18) Word has length 182 [2023-11-23 21:09:36,560 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 21:09:36,561 INFO L225 Difference]: With dead ends: 172 [2023-11-23 21:09:36,561 INFO L226 Difference]: Without dead ends: 73 [2023-11-23 21:09:36,563 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 390 GetRequests, 358 SyntacticMatches, 4 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 165 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=219, Invalid=651, Unknown=0, NotChecked=0, Total=870 [2023-11-23 21:09:36,565 INFO L413 NwaCegarLoop]: 27 mSDtfsCounter, 146 mSDsluCounter, 74 mSDsCounter, 0 mSdLazyCounter, 237 mSolverCounterSat, 67 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 146 SdHoareTripleChecker+Valid, 101 SdHoareTripleChecker+Invalid, 304 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 67 IncrementalHoareTripleChecker+Valid, 237 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-11-23 21:09:36,566 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [146 Valid, 101 Invalid, 304 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [67 Valid, 237 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-11-23 21:09:36,567 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 73 states. [2023-11-23 21:09:36,583 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 73 to 64. [2023-11-23 21:09:36,584 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 64 states, 51 states have (on average 1.0588235294117647) internal successors, (54), 49 states have internal predecessors, (54), 7 states have call successors, (7), 6 states have call predecessors, (7), 5 states have return successors, (11), 8 states have call predecessors, (11), 6 states have call successors, (11) [2023-11-23 21:09:36,585 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 64 states to 64 states and 72 transitions. [2023-11-23 21:09:36,585 INFO L78 Accepts]: Start accepts. Automaton has 64 states and 72 transitions. Word has length 182 [2023-11-23 21:09:36,586 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 21:09:36,586 INFO L495 AbstractCegarLoop]: Abstraction has 64 states and 72 transitions. [2023-11-23 21:09:36,586 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 19 states have (on average 5.052631578947368) internal successors, (96), 19 states have internal predecessors, (96), 11 states have call successors, (16), 2 states have call predecessors, (16), 8 states have return successors, (18), 11 states have call predecessors, (18), 10 states have call successors, (18) [2023-11-23 21:09:36,587 INFO L276 IsEmpty]: Start isEmpty. Operand 64 states and 72 transitions. [2023-11-23 21:09:36,591 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 237 [2023-11-23 21:09:36,592 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 21:09:36,592 INFO L195 NwaCegarLoop]: trace histogram [25, 23, 20, 12, 12, 12, 12, 12, 12, 12, 12, 12, 11, 11, 11, 10, 8, 5, 1, 1, 1, 1] [2023-11-23 21:09:36,625 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2023-11-23 21:09:36,811 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,7 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 21:09:36,812 INFO L420 AbstractCegarLoop]: === Iteration 10 === Targeting fibonacciErr5ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2023-11-23 21:09:36,812 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 21:09:36,812 INFO L85 PathProgramCache]: Analyzing trace with hash 343358896, now seen corresponding path program 3 times [2023-11-23 21:09:36,813 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-23 21:09:36,813 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1605939086] [2023-11-23 21:09:36,813 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 21:09:36,813 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 21:09:36,855 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 21:09:37,358 INFO L134 CoverageAnalysis]: Checked inductivity of 1923 backedges. 242 proven. 648 refuted. 0 times theorem prover too weak. 1033 trivial. 0 not checked. [2023-11-23 21:09:37,358 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-23 21:09:37,358 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1605939086] [2023-11-23 21:09:37,359 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1605939086] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-23 21:09:37,359 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [25036764] [2023-11-23 21:09:37,359 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2023-11-23 21:09:37,365 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 21:09:37,365 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/z3 [2023-11-23 21:09:37,366 INFO L229 MonitoredProcess]: Starting monitored process 8 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-23 21:09:37,373 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2023-11-23 21:09:37,479 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2023-11-23 21:09:37,479 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-23 21:09:37,481 INFO L262 TraceCheckSpWp]: Trace formula consists of 301 conjuncts, 18 conjunts are in the unsatisfiable core [2023-11-23 21:09:37,495 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-23 21:09:37,708 INFO L134 CoverageAnalysis]: Checked inductivity of 1923 backedges. 901 proven. 533 refuted. 0 times theorem prover too weak. 489 trivial. 0 not checked. [2023-11-23 21:09:37,709 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-23 21:09:38,792 INFO L134 CoverageAnalysis]: Checked inductivity of 1923 backedges. 283 proven. 850 refuted. 0 times theorem prover too weak. 790 trivial. 0 not checked. [2023-11-23 21:09:38,793 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [25036764] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-23 21:09:38,793 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [804428099] [2023-11-23 21:09:38,797 INFO L159 IcfgInterpreter]: Started Sifa with 19 locations of interest [2023-11-23 21:09:38,797 INFO L166 IcfgInterpreter]: Building call graph [2023-11-23 21:09:38,797 FATAL L? ?]: Ignoring exception! java.lang.IllegalArgumentException: Recursive programs are not supported. at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.topsortRelevant(CallGraph.java:132) at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.(CallGraph.java:97) at de.uni_freiburg.informatik.ultimate.lib.sifa.IcfgInterpreter.(IcfgInterpreter.java:92) at de.uni_freiburg.informatik.ultimate.plugins.sifa.SifaBuilder.construct(SifaBuilder.java:96) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.SifaRunner.(SifaRunner.java:98) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleSifa.construct(IpTcStrategyModuleSifa.java:68) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getOrConstruct(IpTcStrategyModuleBase.java:101) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getInterpolantComputationStatus(IpTcStrategyModuleBase.java:77) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.tryExecuteInterpolantGenerator(AutomatonFreeRefinementEngine.java:267) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.generateProof(AutomatonFreeRefinementEngine.java:148) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.executeStrategy(AutomatonFreeRefinementEngine.java:137) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.(AutomatonFreeRefinementEngine.java:85) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.TraceAbstractionRefinementEngine.(TraceAbstractionRefinementEngine.java:82) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.BasicCegarLoop.isCounterexampleFeasible(BasicCegarLoop.java:337) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterate(AbstractCegarLoop.java:431) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.startCegar(AbstractCegarLoop.java:366) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.runCegar(AbstractCegarLoop.java:348) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.executeCegarLoop(TraceAbstractionStarter.java:415) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseProgram(TraceAbstractionStarter.java:302) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseSequentialProgram(TraceAbstractionStarter.java:262) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.runCegarLoops(TraceAbstractionStarter.java:175) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.(TraceAbstractionStarter.java:154) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver.finish(TraceAbstractionObserver.java:124) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runObserver(PluginConnector.java:167) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runTool(PluginConnector.java:150) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.run(PluginConnector.java:127) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.executePluginConnector(ToolchainWalker.java:233) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.processPlugin(ToolchainWalker.java:227) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walkUnprotected(ToolchainWalker.java:144) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walk(ToolchainWalker.java:106) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainManager$Toolchain.processToolchain(ToolchainManager.java:319) at de.uni_freiburg.informatik.ultimate.core.coreplugin.toolchain.DefaultToolchainJob.run(DefaultToolchainJob.java:145) at org.eclipse.core.internal.jobs.Worker.run(Worker.java:63) [2023-11-23 21:09:38,798 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-23 21:09:38,799 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13, 18] total 23 [2023-11-23 21:09:38,801 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1954110711] [2023-11-23 21:09:38,801 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-23 21:09:38,802 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2023-11-23 21:09:38,803 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-23 21:09:38,804 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2023-11-23 21:09:38,805 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=91, Invalid=415, Unknown=0, NotChecked=0, Total=506 [2023-11-23 21:09:38,805 INFO L87 Difference]: Start difference. First operand 64 states and 72 transitions. Second operand has 23 states, 23 states have (on average 6.0) internal successors, (138), 23 states have internal predecessors, (138), 18 states have call successors, (25), 3 states have call predecessors, (25), 9 states have return successors, (28), 11 states have call predecessors, (28), 17 states have call successors, (28) [2023-11-23 21:09:39,253 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 21:09:39,253 INFO L93 Difference]: Finished difference Result 154 states and 186 transitions. [2023-11-23 21:09:39,254 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2023-11-23 21:09:39,254 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 23 states have (on average 6.0) internal successors, (138), 23 states have internal predecessors, (138), 18 states have call successors, (25), 3 states have call predecessors, (25), 9 states have return successors, (28), 11 states have call predecessors, (28), 17 states have call successors, (28) Word has length 236 [2023-11-23 21:09:39,255 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 21:09:39,256 INFO L225 Difference]: With dead ends: 154 [2023-11-23 21:09:39,256 INFO L226 Difference]: Without dead ends: 95 [2023-11-23 21:09:39,258 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 506 GetRequests, 459 SyntacticMatches, 10 SemanticMatches, 37 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 306 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=411, Invalid=1071, Unknown=0, NotChecked=0, Total=1482 [2023-11-23 21:09:39,258 INFO L413 NwaCegarLoop]: 20 mSDtfsCounter, 150 mSDsluCounter, 65 mSDsCounter, 0 mSdLazyCounter, 208 mSolverCounterSat, 71 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 150 SdHoareTripleChecker+Valid, 85 SdHoareTripleChecker+Invalid, 279 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 71 IncrementalHoareTripleChecker+Valid, 208 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-11-23 21:09:39,259 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [150 Valid, 85 Invalid, 279 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [71 Valid, 208 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-11-23 21:09:39,260 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 95 states. [2023-11-23 21:09:39,267 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 95 to 82. [2023-11-23 21:09:39,268 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 82 states, 66 states have (on average 1.0757575757575757) internal successors, (71), 63 states have internal predecessors, (71), 9 states have call successors, (9), 8 states have call predecessors, (9), 6 states have return successors, (17), 10 states have call predecessors, (17), 8 states have call successors, (17) [2023-11-23 21:09:39,269 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 82 states to 82 states and 97 transitions. [2023-11-23 21:09:39,269 INFO L78 Accepts]: Start accepts. Automaton has 82 states and 97 transitions. Word has length 236 [2023-11-23 21:09:39,269 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 21:09:39,270 INFO L495 AbstractCegarLoop]: Abstraction has 82 states and 97 transitions. [2023-11-23 21:09:39,270 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 23 states have (on average 6.0) internal successors, (138), 23 states have internal predecessors, (138), 18 states have call successors, (25), 3 states have call predecessors, (25), 9 states have return successors, (28), 11 states have call predecessors, (28), 17 states have call successors, (28) [2023-11-23 21:09:39,270 INFO L276 IsEmpty]: Start isEmpty. Operand 82 states and 97 transitions. [2023-11-23 21:09:39,272 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 130 [2023-11-23 21:09:39,272 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 21:09:39,272 INFO L195 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] [2023-11-23 21:09:39,306 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2023-11-23 21:09:39,496 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,8 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 21:09:39,497 INFO L420 AbstractCegarLoop]: === Iteration 11 === Targeting fibonacciErr5ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2023-11-23 21:09:39,497 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 21:09:39,497 INFO L85 PathProgramCache]: Analyzing trace with hash 299428584, now seen corresponding path program 4 times [2023-11-23 21:09:39,497 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-23 21:09:39,497 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1923943679] [2023-11-23 21:09:39,498 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 21:09:39,498 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 21:09:39,531 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 21:09:39,867 INFO L134 CoverageAnalysis]: Checked inductivity of 537 backedges. 169 proven. 168 refuted. 0 times theorem prover too weak. 200 trivial. 0 not checked. [2023-11-23 21:09:39,867 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-23 21:09:39,867 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1923943679] [2023-11-23 21:09:39,867 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1923943679] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-23 21:09:39,867 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1372018784] [2023-11-23 21:09:39,868 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2023-11-23 21:09:39,868 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 21:09:39,868 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/z3 [2023-11-23 21:09:39,869 INFO L229 MonitoredProcess]: Starting monitored process 9 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-23 21:09:39,892 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2023-11-23 21:09:39,959 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 21:09:39,960 INFO L262 TraceCheckSpWp]: Trace formula consists of 259 conjuncts, 14 conjunts are in the unsatisfiable core [2023-11-23 21:09:39,963 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-23 21:09:40,067 INFO L134 CoverageAnalysis]: Checked inductivity of 537 backedges. 167 proven. 182 refuted. 0 times theorem prover too weak. 188 trivial. 0 not checked. [2023-11-23 21:09:40,068 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-23 21:09:40,760 INFO L134 CoverageAnalysis]: Checked inductivity of 537 backedges. 167 proven. 202 refuted. 0 times theorem prover too weak. 168 trivial. 0 not checked. [2023-11-23 21:09:40,761 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1372018784] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-23 21:09:40,761 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1489163450] [2023-11-23 21:09:40,768 INFO L159 IcfgInterpreter]: Started Sifa with 19 locations of interest [2023-11-23 21:09:40,769 INFO L166 IcfgInterpreter]: Building call graph [2023-11-23 21:09:40,769 FATAL L? ?]: Ignoring exception! java.lang.IllegalArgumentException: Recursive programs are not supported. at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.topsortRelevant(CallGraph.java:132) at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.(CallGraph.java:97) at de.uni_freiburg.informatik.ultimate.lib.sifa.IcfgInterpreter.(IcfgInterpreter.java:92) at de.uni_freiburg.informatik.ultimate.plugins.sifa.SifaBuilder.construct(SifaBuilder.java:96) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.SifaRunner.(SifaRunner.java:98) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleSifa.construct(IpTcStrategyModuleSifa.java:68) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getOrConstruct(IpTcStrategyModuleBase.java:101) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getInterpolantComputationStatus(IpTcStrategyModuleBase.java:77) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.tryExecuteInterpolantGenerator(AutomatonFreeRefinementEngine.java:267) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.generateProof(AutomatonFreeRefinementEngine.java:148) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.executeStrategy(AutomatonFreeRefinementEngine.java:137) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.(AutomatonFreeRefinementEngine.java:85) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.TraceAbstractionRefinementEngine.(TraceAbstractionRefinementEngine.java:82) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.BasicCegarLoop.isCounterexampleFeasible(BasicCegarLoop.java:337) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterate(AbstractCegarLoop.java:431) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.startCegar(AbstractCegarLoop.java:366) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.runCegar(AbstractCegarLoop.java:348) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.executeCegarLoop(TraceAbstractionStarter.java:415) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseProgram(TraceAbstractionStarter.java:302) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseSequentialProgram(TraceAbstractionStarter.java:262) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.runCegarLoops(TraceAbstractionStarter.java:175) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.(TraceAbstractionStarter.java:154) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver.finish(TraceAbstractionObserver.java:124) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runObserver(PluginConnector.java:167) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runTool(PluginConnector.java:150) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.run(PluginConnector.java:127) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.executePluginConnector(ToolchainWalker.java:233) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.processPlugin(ToolchainWalker.java:227) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walkUnprotected(ToolchainWalker.java:144) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walk(ToolchainWalker.java:106) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainManager$Toolchain.processToolchain(ToolchainManager.java:319) at de.uni_freiburg.informatik.ultimate.core.coreplugin.toolchain.DefaultToolchainJob.run(DefaultToolchainJob.java:145) at org.eclipse.core.internal.jobs.Worker.run(Worker.java:63) [2023-11-23 21:09:40,770 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-23 21:09:40,770 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 11, 15] total 20 [2023-11-23 21:09:40,771 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1752978334] [2023-11-23 21:09:40,771 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-23 21:09:40,773 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2023-11-23 21:09:40,773 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-23 21:09:40,774 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2023-11-23 21:09:40,774 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=83, Invalid=297, Unknown=0, NotChecked=0, Total=380 [2023-11-23 21:09:40,775 INFO L87 Difference]: Start difference. First operand 82 states and 97 transitions. Second operand has 20 states, 20 states have (on average 4.9) internal successors, (98), 20 states have internal predecessors, (98), 13 states have call successors, (16), 1 states have call predecessors, (16), 7 states have return successors, (18), 8 states have call predecessors, (18), 13 states have call successors, (18) [2023-11-23 21:09:41,048 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 21:09:41,048 INFO L93 Difference]: Finished difference Result 162 states and 202 transitions. [2023-11-23 21:09:41,048 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2023-11-23 21:09:41,049 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 20 states have (on average 4.9) internal successors, (98), 20 states have internal predecessors, (98), 13 states have call successors, (16), 1 states have call predecessors, (16), 7 states have return successors, (18), 8 states have call predecessors, (18), 13 states have call successors, (18) Word has length 129 [2023-11-23 21:09:41,049 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 21:09:41,050 INFO L225 Difference]: With dead ends: 162 [2023-11-23 21:09:41,050 INFO L226 Difference]: Without dead ends: 85 [2023-11-23 21:09:41,051 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 281 GetRequests, 247 SyntacticMatches, 7 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 192 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=239, Invalid=573, Unknown=0, NotChecked=0, Total=812 [2023-11-23 21:09:41,052 INFO L413 NwaCegarLoop]: 32 mSDtfsCounter, 64 mSDsluCounter, 87 mSDsCounter, 0 mSdLazyCounter, 270 mSolverCounterSat, 34 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 64 SdHoareTripleChecker+Valid, 119 SdHoareTripleChecker+Invalid, 304 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 34 IncrementalHoareTripleChecker+Valid, 270 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-11-23 21:09:41,053 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [64 Valid, 119 Invalid, 304 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [34 Valid, 270 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-11-23 21:09:41,053 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 85 states. [2023-11-23 21:09:41,060 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 85 to 82. [2023-11-23 21:09:41,061 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 82 states, 65 states have (on average 1.0461538461538462) internal successors, (68), 64 states have internal predecessors, (68), 10 states have call successors, (10), 8 states have call predecessors, (10), 6 states have return successors, (18), 9 states have call predecessors, (18), 9 states have call successors, (18) [2023-11-23 21:09:41,062 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 82 states to 82 states and 96 transitions. [2023-11-23 21:09:41,062 INFO L78 Accepts]: Start accepts. Automaton has 82 states and 96 transitions. Word has length 129 [2023-11-23 21:09:41,063 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 21:09:41,063 INFO L495 AbstractCegarLoop]: Abstraction has 82 states and 96 transitions. [2023-11-23 21:09:41,063 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 20 states have (on average 4.9) internal successors, (98), 20 states have internal predecessors, (98), 13 states have call successors, (16), 1 states have call predecessors, (16), 7 states have return successors, (18), 8 states have call predecessors, (18), 13 states have call successors, (18) [2023-11-23 21:09:41,063 INFO L276 IsEmpty]: Start isEmpty. Operand 82 states and 96 transitions. [2023-11-23 21:09:41,065 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 150 [2023-11-23 21:09:41,065 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 21:09:41,065 INFO L195 NwaCegarLoop]: trace histogram [16, 14, 13, 8, 8, 8, 8, 7, 7, 7, 7, 7, 7, 7, 7, 6, 5, 3, 1, 1, 1, 1] [2023-11-23 21:09:41,086 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2023-11-23 21:09:41,285 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2023-11-23 21:09:41,286 INFO L420 AbstractCegarLoop]: === Iteration 12 === Targeting fibonacciErr5ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2023-11-23 21:09:41,286 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 21:09:41,286 INFO L85 PathProgramCache]: Analyzing trace with hash 71861835, now seen corresponding path program 5 times [2023-11-23 21:09:41,286 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-23 21:09:41,287 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [144206798] [2023-11-23 21:09:41,287 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 21:09:41,287 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 21:09:41,307 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 21:09:41,881 INFO L134 CoverageAnalysis]: Checked inductivity of 731 backedges. 78 proven. 189 refuted. 0 times theorem prover too weak. 464 trivial. 0 not checked. [2023-11-23 21:09:41,881 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-23 21:09:41,881 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [144206798] [2023-11-23 21:09:41,882 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [144206798] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-23 21:09:41,882 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [91540871] [2023-11-23 21:09:41,882 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-11-23 21:09:41,882 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 21:09:41,882 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/z3 [2023-11-23 21:09:41,883 INFO L229 MonitoredProcess]: Starting monitored process 10 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-23 21:09:41,912 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2023-11-23 21:09:41,994 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 11 check-sat command(s) [2023-11-23 21:09:41,994 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-23 21:09:41,998 INFO L262 TraceCheckSpWp]: Trace formula consists of 276 conjuncts, 29 conjunts are in the unsatisfiable core [2023-11-23 21:09:42,002 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-23 21:09:42,230 INFO L134 CoverageAnalysis]: Checked inductivity of 731 backedges. 78 proven. 135 refuted. 0 times theorem prover too weak. 518 trivial. 0 not checked. [2023-11-23 21:09:42,230 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-23 21:09:43,661 INFO L134 CoverageAnalysis]: Checked inductivity of 731 backedges. 144 proven. 128 refuted. 0 times theorem prover too weak. 459 trivial. 0 not checked. [2023-11-23 21:09:43,661 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [91540871] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-23 21:09:43,661 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1801674816] [2023-11-23 21:09:43,664 INFO L159 IcfgInterpreter]: Started Sifa with 19 locations of interest [2023-11-23 21:09:43,664 INFO L166 IcfgInterpreter]: Building call graph [2023-11-23 21:09:43,664 FATAL L? ?]: Ignoring exception! java.lang.IllegalArgumentException: Recursive programs are not supported. at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.topsortRelevant(CallGraph.java:132) at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.(CallGraph.java:97) at de.uni_freiburg.informatik.ultimate.lib.sifa.IcfgInterpreter.(IcfgInterpreter.java:92) at de.uni_freiburg.informatik.ultimate.plugins.sifa.SifaBuilder.construct(SifaBuilder.java:96) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.SifaRunner.(SifaRunner.java:98) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleSifa.construct(IpTcStrategyModuleSifa.java:68) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getOrConstruct(IpTcStrategyModuleBase.java:101) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getInterpolantComputationStatus(IpTcStrategyModuleBase.java:77) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.tryExecuteInterpolantGenerator(AutomatonFreeRefinementEngine.java:267) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.generateProof(AutomatonFreeRefinementEngine.java:148) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.executeStrategy(AutomatonFreeRefinementEngine.java:137) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.(AutomatonFreeRefinementEngine.java:85) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.TraceAbstractionRefinementEngine.(TraceAbstractionRefinementEngine.java:82) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.BasicCegarLoop.isCounterexampleFeasible(BasicCegarLoop.java:337) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterate(AbstractCegarLoop.java:431) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.startCegar(AbstractCegarLoop.java:366) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.runCegar(AbstractCegarLoop.java:348) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.executeCegarLoop(TraceAbstractionStarter.java:415) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseProgram(TraceAbstractionStarter.java:302) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseSequentialProgram(TraceAbstractionStarter.java:262) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.runCegarLoops(TraceAbstractionStarter.java:175) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.(TraceAbstractionStarter.java:154) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver.finish(TraceAbstractionObserver.java:124) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runObserver(PluginConnector.java:167) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runTool(PluginConnector.java:150) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.run(PluginConnector.java:127) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.executePluginConnector(ToolchainWalker.java:233) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.processPlugin(ToolchainWalker.java:227) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walkUnprotected(ToolchainWalker.java:144) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walk(ToolchainWalker.java:106) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainManager$Toolchain.processToolchain(ToolchainManager.java:319) at de.uni_freiburg.informatik.ultimate.core.coreplugin.toolchain.DefaultToolchainJob.run(DefaultToolchainJob.java:145) at org.eclipse.core.internal.jobs.Worker.run(Worker.java:63) [2023-11-23 21:09:43,665 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-23 21:09:43,666 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 12, 17] total 31 [2023-11-23 21:09:43,666 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1046336573] [2023-11-23 21:09:43,666 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-23 21:09:43,667 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 32 states [2023-11-23 21:09:43,667 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-23 21:09:43,668 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 32 interpolants. [2023-11-23 21:09:43,669 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=232, Invalid=760, Unknown=0, NotChecked=0, Total=992 [2023-11-23 21:09:43,669 INFO L87 Difference]: Start difference. First operand 82 states and 96 transitions. Second operand has 32 states, 31 states have (on average 2.7096774193548385) internal successors, (84), 32 states have internal predecessors, (84), 8 states have call successors, (9), 1 states have call predecessors, (9), 9 states have return successors, (21), 21 states have call predecessors, (21), 8 states have call successors, (21) [2023-11-23 21:09:43,865 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 21:09:43,865 INFO L93 Difference]: Finished difference Result 115 states and 146 transitions. [2023-11-23 21:09:43,866 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2023-11-23 21:09:43,867 INFO L78 Accepts]: Start accepts. Automaton has has 32 states, 31 states have (on average 2.7096774193548385) internal successors, (84), 32 states have internal predecessors, (84), 8 states have call successors, (9), 1 states have call predecessors, (9), 9 states have return successors, (21), 21 states have call predecessors, (21), 8 states have call successors, (21) Word has length 149 [2023-11-23 21:09:43,867 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 21:09:43,869 INFO L225 Difference]: With dead ends: 115 [2023-11-23 21:09:43,870 INFO L226 Difference]: Without dead ends: 114 [2023-11-23 21:09:43,871 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 329 GetRequests, 282 SyntacticMatches, 13 SemanticMatches, 34 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 723 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=293, Invalid=967, Unknown=0, NotChecked=0, Total=1260 [2023-11-23 21:09:43,872 INFO L413 NwaCegarLoop]: 18 mSDtfsCounter, 15 mSDsluCounter, 128 mSDsCounter, 0 mSdLazyCounter, 138 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 20 SdHoareTripleChecker+Valid, 146 SdHoareTripleChecker+Invalid, 144 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 138 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-23 21:09:43,872 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [20 Valid, 146 Invalid, 144 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 138 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-23 21:09:43,873 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 114 states. [2023-11-23 21:09:43,883 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 114 to 103. [2023-11-23 21:09:43,884 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 103 states, 82 states have (on average 1.0365853658536586) internal successors, (85), 80 states have internal predecessors, (85), 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) [2023-11-23 21:09:43,885 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 103 states to 103 states and 131 transitions. [2023-11-23 21:09:43,885 INFO L78 Accepts]: Start accepts. Automaton has 103 states and 131 transitions. Word has length 149 [2023-11-23 21:09:43,886 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 21:09:43,887 INFO L495 AbstractCegarLoop]: Abstraction has 103 states and 131 transitions. [2023-11-23 21:09:43,887 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 32 states, 31 states have (on average 2.7096774193548385) internal successors, (84), 32 states have internal predecessors, (84), 8 states have call successors, (9), 1 states have call predecessors, (9), 9 states have return successors, (21), 21 states have call predecessors, (21), 8 states have call successors, (21) [2023-11-23 21:09:43,887 INFO L276 IsEmpty]: Start isEmpty. Operand 103 states and 131 transitions. [2023-11-23 21:09:43,891 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 307 [2023-11-23 21:09:43,891 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 21:09:43,891 INFO L195 NwaCegarLoop]: trace histogram [32, 30, 26, 16, 16, 16, 16, 15, 15, 15, 15, 15, 15, 15, 15, 14, 10, 6, 1, 1, 1, 1] [2023-11-23 21:09:43,918 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2023-11-23 21:09:44,092 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable11 [2023-11-23 21:09:44,092 INFO L420 AbstractCegarLoop]: === Iteration 13 === Targeting fibonacciErr5ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2023-11-23 21:09:44,092 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 21:09:44,093 INFO L85 PathProgramCache]: Analyzing trace with hash -881563023, now seen corresponding path program 6 times [2023-11-23 21:09:44,093 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-23 21:09:44,093 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [918403358] [2023-11-23 21:09:44,093 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 21:09:44,093 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 21:09:44,133 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 21:09:44,753 INFO L134 CoverageAnalysis]: Checked inductivity of 3282 backedges. 521 proven. 1076 refuted. 0 times theorem prover too weak. 1685 trivial. 0 not checked. [2023-11-23 21:09:44,754 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-23 21:09:44,754 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [918403358] [2023-11-23 21:09:44,754 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [918403358] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-23 21:09:44,754 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1998254518] [2023-11-23 21:09:44,754 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2023-11-23 21:09:44,754 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 21:09:44,755 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/z3 [2023-11-23 21:09:44,756 INFO L229 MonitoredProcess]: Starting monitored process 11 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-23 21:09:44,784 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2023-11-23 21:09:44,915 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2023-11-23 21:09:44,916 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-23 21:09:44,918 INFO L262 TraceCheckSpWp]: Trace formula consists of 385 conjuncts, 22 conjunts are in the unsatisfiable core [2023-11-23 21:09:44,924 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-23 21:09:45,125 INFO L134 CoverageAnalysis]: Checked inductivity of 3282 backedges. 613 proven. 1181 refuted. 0 times theorem prover too weak. 1488 trivial. 0 not checked. [2023-11-23 21:09:45,126 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-23 21:09:47,200 INFO L134 CoverageAnalysis]: Checked inductivity of 3282 backedges. 613 proven. 1253 refuted. 0 times theorem prover too weak. 1416 trivial. 0 not checked. [2023-11-23 21:09:47,201 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1998254518] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-23 21:09:47,201 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [274398297] [2023-11-23 21:09:47,203 INFO L159 IcfgInterpreter]: Started Sifa with 19 locations of interest [2023-11-23 21:09:47,204 INFO L166 IcfgInterpreter]: Building call graph [2023-11-23 21:09:47,204 FATAL L? ?]: Ignoring exception! java.lang.IllegalArgumentException: Recursive programs are not supported. at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.topsortRelevant(CallGraph.java:132) at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.(CallGraph.java:97) at de.uni_freiburg.informatik.ultimate.lib.sifa.IcfgInterpreter.(IcfgInterpreter.java:92) at de.uni_freiburg.informatik.ultimate.plugins.sifa.SifaBuilder.construct(SifaBuilder.java:96) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.SifaRunner.(SifaRunner.java:98) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleSifa.construct(IpTcStrategyModuleSifa.java:68) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getOrConstruct(IpTcStrategyModuleBase.java:101) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getInterpolantComputationStatus(IpTcStrategyModuleBase.java:77) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.tryExecuteInterpolantGenerator(AutomatonFreeRefinementEngine.java:267) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.generateProof(AutomatonFreeRefinementEngine.java:148) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.executeStrategy(AutomatonFreeRefinementEngine.java:137) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.(AutomatonFreeRefinementEngine.java:85) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.TraceAbstractionRefinementEngine.(TraceAbstractionRefinementEngine.java:82) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.BasicCegarLoop.isCounterexampleFeasible(BasicCegarLoop.java:337) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterate(AbstractCegarLoop.java:431) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.startCegar(AbstractCegarLoop.java:366) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.runCegar(AbstractCegarLoop.java:348) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.executeCegarLoop(TraceAbstractionStarter.java:415) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseProgram(TraceAbstractionStarter.java:302) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseSequentialProgram(TraceAbstractionStarter.java:262) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.runCegarLoops(TraceAbstractionStarter.java:175) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.(TraceAbstractionStarter.java:154) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver.finish(TraceAbstractionObserver.java:124) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runObserver(PluginConnector.java:167) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runTool(PluginConnector.java:150) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.run(PluginConnector.java:127) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.executePluginConnector(ToolchainWalker.java:233) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.processPlugin(ToolchainWalker.java:227) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walkUnprotected(ToolchainWalker.java:144) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walk(ToolchainWalker.java:106) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainManager$Toolchain.processToolchain(ToolchainManager.java:319) at de.uni_freiburg.informatik.ultimate.core.coreplugin.toolchain.DefaultToolchainJob.run(DefaultToolchainJob.java:145) at org.eclipse.core.internal.jobs.Worker.run(Worker.java:63) [2023-11-23 21:09:47,205 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-23 21:09:47,206 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 15, 23] total 28 [2023-11-23 21:09:47,206 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1366035714] [2023-11-23 21:09:47,206 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-23 21:09:47,207 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 28 states [2023-11-23 21:09:47,208 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-23 21:09:47,209 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 28 interpolants. [2023-11-23 21:09:47,209 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=134, Invalid=622, Unknown=0, NotChecked=0, Total=756 [2023-11-23 21:09:47,210 INFO L87 Difference]: Start difference. First operand 103 states and 131 transitions. Second operand has 28 states, 28 states have (on average 5.321428571428571) internal successors, (149), 28 states have internal predecessors, (149), 21 states have call successors, (25), 1 states have call predecessors, (25), 11 states have return successors, (32), 13 states have call predecessors, (32), 21 states have call successors, (32) [2023-11-23 21:09:47,731 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 21:09:47,732 INFO L93 Difference]: Finished difference Result 241 states and 330 transitions. [2023-11-23 21:09:47,732 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2023-11-23 21:09:47,733 INFO L78 Accepts]: Start accepts. Automaton has has 28 states, 28 states have (on average 5.321428571428571) internal successors, (149), 28 states have internal predecessors, (149), 21 states have call successors, (25), 1 states have call predecessors, (25), 11 states have return successors, (32), 13 states have call predecessors, (32), 21 states have call successors, (32) Word has length 306 [2023-11-23 21:09:47,733 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 21:09:47,735 INFO L225 Difference]: With dead ends: 241 [2023-11-23 21:09:47,735 INFO L226 Difference]: Without dead ends: 143 [2023-11-23 21:09:47,737 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 655 GetRequests, 597 SyntacticMatches, 11 SemanticMatches, 47 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 544 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=604, Invalid=1748, Unknown=0, NotChecked=0, Total=2352 [2023-11-23 21:09:47,738 INFO L413 NwaCegarLoop]: 34 mSDtfsCounter, 357 mSDsluCounter, 76 mSDsCounter, 0 mSdLazyCounter, 281 mSolverCounterSat, 167 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 357 SdHoareTripleChecker+Valid, 110 SdHoareTripleChecker+Invalid, 448 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 167 IncrementalHoareTripleChecker+Valid, 281 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2023-11-23 21:09:47,738 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [357 Valid, 110 Invalid, 448 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [167 Valid, 281 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2023-11-23 21:09:47,739 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 143 states. [2023-11-23 21:09:47,750 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 143 to 130. [2023-11-23 21:09:47,750 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 130 states, 105 states have (on average 1.0476190476190477) internal successors, (110), 101 states have internal predecessors, (110), 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) [2023-11-23 21:09:47,752 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 130 states to 130 states and 162 transitions. [2023-11-23 21:09:47,752 INFO L78 Accepts]: Start accepts. Automaton has 130 states and 162 transitions. Word has length 306 [2023-11-23 21:09:47,753 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 21:09:47,753 INFO L495 AbstractCegarLoop]: Abstraction has 130 states and 162 transitions. [2023-11-23 21:09:47,754 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 28 states, 28 states have (on average 5.321428571428571) internal successors, (149), 28 states have internal predecessors, (149), 21 states have call successors, (25), 1 states have call predecessors, (25), 11 states have return successors, (32), 13 states have call predecessors, (32), 21 states have call successors, (32) [2023-11-23 21:09:47,754 INFO L276 IsEmpty]: Start isEmpty. Operand 130 states and 162 transitions. [2023-11-23 21:09:47,758 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 307 [2023-11-23 21:09:47,759 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 21:09:47,759 INFO L195 NwaCegarLoop]: trace histogram [32, 30, 26, 16, 16, 16, 16, 15, 15, 15, 15, 15, 15, 15, 15, 14, 10, 6, 1, 1, 1, 1] [2023-11-23 21:09:47,781 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2023-11-23 21:09:47,981 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2023-11-23 21:09:47,982 INFO L420 AbstractCegarLoop]: === Iteration 14 === Targeting fibonacciErr5ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2023-11-23 21:09:47,982 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 21:09:47,982 INFO L85 PathProgramCache]: Analyzing trace with hash -1702912443, now seen corresponding path program 7 times [2023-11-23 21:09:47,982 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-23 21:09:47,982 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [66553908] [2023-11-23 21:09:47,982 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 21:09:47,983 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 21:09:48,027 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 21:09:48,528 INFO L134 CoverageAnalysis]: Checked inductivity of 3282 backedges. 554 proven. 990 refuted. 0 times theorem prover too weak. 1738 trivial. 0 not checked. [2023-11-23 21:09:48,529 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-23 21:09:48,529 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [66553908] [2023-11-23 21:09:48,529 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [66553908] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-23 21:09:48,529 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1757925715] [2023-11-23 21:09:48,530 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2023-11-23 21:09:48,530 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 21:09:48,530 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/z3 [2023-11-23 21:09:48,531 INFO L229 MonitoredProcess]: Starting monitored process 12 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-23 21:09:48,537 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2023-11-23 21:09:48,697 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 21:09:48,700 INFO L262 TraceCheckSpWp]: Trace formula consists of 586 conjuncts, 18 conjunts are in the unsatisfiable core [2023-11-23 21:09:48,706 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-23 21:09:48,861 INFO L134 CoverageAnalysis]: Checked inductivity of 3282 backedges. 1858 proven. 484 refuted. 0 times theorem prover too weak. 940 trivial. 0 not checked. [2023-11-23 21:09:48,861 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-23 21:09:50,711 INFO L134 CoverageAnalysis]: Checked inductivity of 3282 backedges. 551 proven. 1101 refuted. 0 times theorem prover too weak. 1630 trivial. 0 not checked. [2023-11-23 21:09:50,711 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1757925715] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-23 21:09:50,711 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [536901631] [2023-11-23 21:09:50,714 INFO L159 IcfgInterpreter]: Started Sifa with 19 locations of interest [2023-11-23 21:09:50,714 INFO L166 IcfgInterpreter]: Building call graph [2023-11-23 21:09:50,714 FATAL L? ?]: Ignoring exception! java.lang.IllegalArgumentException: Recursive programs are not supported. at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.topsortRelevant(CallGraph.java:132) at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.(CallGraph.java:97) at de.uni_freiburg.informatik.ultimate.lib.sifa.IcfgInterpreter.(IcfgInterpreter.java:92) at de.uni_freiburg.informatik.ultimate.plugins.sifa.SifaBuilder.construct(SifaBuilder.java:96) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.SifaRunner.(SifaRunner.java:98) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleSifa.construct(IpTcStrategyModuleSifa.java:68) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getOrConstruct(IpTcStrategyModuleBase.java:101) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getInterpolantComputationStatus(IpTcStrategyModuleBase.java:77) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.tryExecuteInterpolantGenerator(AutomatonFreeRefinementEngine.java:267) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.generateProof(AutomatonFreeRefinementEngine.java:148) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.executeStrategy(AutomatonFreeRefinementEngine.java:137) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.(AutomatonFreeRefinementEngine.java:85) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.TraceAbstractionRefinementEngine.(TraceAbstractionRefinementEngine.java:82) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.BasicCegarLoop.isCounterexampleFeasible(BasicCegarLoop.java:337) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterate(AbstractCegarLoop.java:431) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.startCegar(AbstractCegarLoop.java:366) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.runCegar(AbstractCegarLoop.java:348) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.executeCegarLoop(TraceAbstractionStarter.java:415) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseProgram(TraceAbstractionStarter.java:302) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseSequentialProgram(TraceAbstractionStarter.java:262) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.runCegarLoops(TraceAbstractionStarter.java:175) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.(TraceAbstractionStarter.java:154) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver.finish(TraceAbstractionObserver.java:124) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runObserver(PluginConnector.java:167) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runTool(PluginConnector.java:150) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.run(PluginConnector.java:127) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.executePluginConnector(ToolchainWalker.java:233) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.processPlugin(ToolchainWalker.java:227) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walkUnprotected(ToolchainWalker.java:144) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walk(ToolchainWalker.java:106) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainManager$Toolchain.processToolchain(ToolchainManager.java:319) at de.uni_freiburg.informatik.ultimate.core.coreplugin.toolchain.DefaultToolchainJob.run(DefaultToolchainJob.java:145) at org.eclipse.core.internal.jobs.Worker.run(Worker.java:63) [2023-11-23 21:09:50,715 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-23 21:09:50,716 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 13, 19] total 24 [2023-11-23 21:09:50,716 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1545614040] [2023-11-23 21:09:50,716 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-23 21:09:50,717 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 24 states [2023-11-23 21:09:50,718 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-23 21:09:50,719 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2023-11-23 21:09:50,719 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=111, Invalid=441, Unknown=0, NotChecked=0, Total=552 [2023-11-23 21:09:50,720 INFO L87 Difference]: Start difference. First operand 130 states and 162 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), 2 states have call predecessors, (23), 10 states have return successors, (28), 10 states have call predecessors, (28), 18 states have call successors, (28) [2023-11-23 21:09:51,124 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 21:09:51,125 INFO L93 Difference]: Finished difference Result 243 states and 316 transitions. [2023-11-23 21:09:51,125 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2023-11-23 21:09:51,126 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), 2 states have call predecessors, (23), 10 states have return successors, (28), 10 states have call predecessors, (28), 18 states have call successors, (28) Word has length 306 [2023-11-23 21:09:51,126 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 21:09:51,128 INFO L225 Difference]: With dead ends: 243 [2023-11-23 21:09:51,128 INFO L226 Difference]: Without dead ends: 118 [2023-11-23 21:09:51,134 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 642 GetRequests, 599 SyntacticMatches, 9 SemanticMatches, 34 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 326 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=349, Invalid=911, Unknown=0, NotChecked=0, Total=1260 [2023-11-23 21:09:51,139 INFO L413 NwaCegarLoop]: 39 mSDtfsCounter, 111 mSDsluCounter, 124 mSDsCounter, 0 mSdLazyCounter, 395 mSolverCounterSat, 44 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 111 SdHoareTripleChecker+Valid, 163 SdHoareTripleChecker+Invalid, 439 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 44 IncrementalHoareTripleChecker+Valid, 395 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-11-23 21:09:51,140 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [111 Valid, 163 Invalid, 439 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [44 Valid, 395 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-11-23 21:09:51,141 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 118 states. [2023-11-23 21:09:51,150 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 118 to 106. [2023-11-23 21:09:51,151 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 106 states, 85 states have (on average 1.035294117647059) internal successors, (88), 83 states have internal predecessors, (88), 13 states have call successors, (13), 10 states have call predecessors, (13), 7 states have return successors, (26), 12 states have call predecessors, (26), 12 states have call successors, (26) [2023-11-23 21:09:51,152 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 106 states to 106 states and 127 transitions. [2023-11-23 21:09:51,152 INFO L78 Accepts]: Start accepts. Automaton has 106 states and 127 transitions. Word has length 306 [2023-11-23 21:09:51,153 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 21:09:51,153 INFO L495 AbstractCegarLoop]: Abstraction has 106 states and 127 transitions. [2023-11-23 21:09:51,154 INFO L496 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), 2 states have call predecessors, (23), 10 states have return successors, (28), 10 states have call predecessors, (28), 18 states have call successors, (28) [2023-11-23 21:09:51,154 INFO L276 IsEmpty]: Start isEmpty. Operand 106 states and 127 transitions. [2023-11-23 21:09:51,174 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 497 [2023-11-23 21:09:51,175 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 21:09:51,175 INFO L195 NwaCegarLoop]: trace histogram [51, 50, 41, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 24, 16, 10, 1, 1, 1, 1] [2023-11-23 21:09:51,204 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2023-11-23 21:09:51,389 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2023-11-23 21:09:51,390 INFO L420 AbstractCegarLoop]: === Iteration 15 === Targeting fibonacciErr5ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2023-11-23 21:09:51,390 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 21:09:51,390 INFO L85 PathProgramCache]: Analyzing trace with hash 1673614201, now seen corresponding path program 8 times [2023-11-23 21:09:51,390 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-23 21:09:51,391 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [115403025] [2023-11-23 21:09:51,391 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 21:09:51,391 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 21:09:51,531 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 21:09:52,534 INFO L134 CoverageAnalysis]: Checked inductivity of 8820 backedges. 1078 proven. 2452 refuted. 0 times theorem prover too weak. 5290 trivial. 0 not checked. [2023-11-23 21:09:52,534 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-23 21:09:52,534 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [115403025] [2023-11-23 21:09:52,534 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [115403025] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-23 21:09:52,535 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1236298265] [2023-11-23 21:09:52,535 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-11-23 21:09:52,535 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 21:09:52,535 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/z3 [2023-11-23 21:09:52,536 INFO L229 MonitoredProcess]: Starting monitored process 13 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-23 21:09:52,558 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2023-11-23 21:09:52,794 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 27 check-sat command(s) [2023-11-23 21:09:52,794 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-23 21:09:52,797 INFO L262 TraceCheckSpWp]: Trace formula consists of 705 conjuncts, 18 conjunts are in the unsatisfiable core [2023-11-23 21:09:52,807 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-23 21:09:52,964 INFO L134 CoverageAnalysis]: Checked inductivity of 8820 backedges. 1737 proven. 1024 refuted. 0 times theorem prover too weak. 6059 trivial. 0 not checked. [2023-11-23 21:09:52,965 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-23 21:09:54,506 INFO L134 CoverageAnalysis]: Checked inductivity of 8820 backedges. 1745 proven. 1063 refuted. 0 times theorem prover too weak. 6012 trivial. 0 not checked. [2023-11-23 21:09:54,506 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1236298265] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-23 21:09:54,507 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [702562325] [2023-11-23 21:09:54,509 INFO L159 IcfgInterpreter]: Started Sifa with 19 locations of interest [2023-11-23 21:09:54,509 INFO L166 IcfgInterpreter]: Building call graph [2023-11-23 21:09:54,509 FATAL L? ?]: Ignoring exception! java.lang.IllegalArgumentException: Recursive programs are not supported. at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.topsortRelevant(CallGraph.java:132) at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.(CallGraph.java:97) at de.uni_freiburg.informatik.ultimate.lib.sifa.IcfgInterpreter.(IcfgInterpreter.java:92) at de.uni_freiburg.informatik.ultimate.plugins.sifa.SifaBuilder.construct(SifaBuilder.java:96) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.SifaRunner.(SifaRunner.java:98) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleSifa.construct(IpTcStrategyModuleSifa.java:68) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getOrConstruct(IpTcStrategyModuleBase.java:101) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getInterpolantComputationStatus(IpTcStrategyModuleBase.java:77) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.tryExecuteInterpolantGenerator(AutomatonFreeRefinementEngine.java:267) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.generateProof(AutomatonFreeRefinementEngine.java:148) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.executeStrategy(AutomatonFreeRefinementEngine.java:137) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.(AutomatonFreeRefinementEngine.java:85) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.TraceAbstractionRefinementEngine.(TraceAbstractionRefinementEngine.java:82) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.BasicCegarLoop.isCounterexampleFeasible(BasicCegarLoop.java:337) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterate(AbstractCegarLoop.java:431) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.startCegar(AbstractCegarLoop.java:366) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.runCegar(AbstractCegarLoop.java:348) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.executeCegarLoop(TraceAbstractionStarter.java:415) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseProgram(TraceAbstractionStarter.java:302) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseSequentialProgram(TraceAbstractionStarter.java:262) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.runCegarLoops(TraceAbstractionStarter.java:175) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.(TraceAbstractionStarter.java:154) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver.finish(TraceAbstractionObserver.java:124) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runObserver(PluginConnector.java:167) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runTool(PluginConnector.java:150) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.run(PluginConnector.java:127) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.executePluginConnector(ToolchainWalker.java:233) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.processPlugin(ToolchainWalker.java:227) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walkUnprotected(ToolchainWalker.java:144) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walk(ToolchainWalker.java:106) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainManager$Toolchain.processToolchain(ToolchainManager.java:319) at de.uni_freiburg.informatik.ultimate.core.coreplugin.toolchain.DefaultToolchainJob.run(DefaultToolchainJob.java:145) at org.eclipse.core.internal.jobs.Worker.run(Worker.java:63) [2023-11-23 21:09:54,510 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-23 21:09:54,511 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 13, 19] total 27 [2023-11-23 21:09:54,511 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [492959298] [2023-11-23 21:09:54,511 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-23 21:09:54,513 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 27 states [2023-11-23 21:09:54,513 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-23 21:09:54,514 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 27 interpolants. [2023-11-23 21:09:54,514 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=128, Invalid=574, Unknown=0, NotChecked=0, Total=702 [2023-11-23 21:09:54,515 INFO L87 Difference]: Start difference. First operand 106 states and 127 transitions. Second operand has 27 states, 27 states have (on average 5.851851851851852) internal successors, (158), 27 states have internal predecessors, (158), 19 states have call successors, (28), 1 states have call predecessors, (28), 12 states have return successors, (38), 19 states have call predecessors, (38), 19 states have call successors, (38) [2023-11-23 21:09:55,164 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 21:09:55,164 INFO L93 Difference]: Finished difference Result 261 states and 339 transitions. [2023-11-23 21:09:55,165 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 33 states. [2023-11-23 21:09:55,165 INFO L78 Accepts]: Start accepts. Automaton has has 27 states, 27 states have (on average 5.851851851851852) internal successors, (158), 27 states have internal predecessors, (158), 19 states have call successors, (28), 1 states have call predecessors, (28), 12 states have return successors, (38), 19 states have call predecessors, (38), 19 states have call successors, (38) Word has length 496 [2023-11-23 21:09:55,166 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 21:09:55,169 INFO L225 Difference]: With dead ends: 261 [2023-11-23 21:09:55,170 INFO L226 Difference]: Without dead ends: 160 [2023-11-23 21:09:55,172 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 1044 GetRequests, 984 SyntacticMatches, 9 SemanticMatches, 51 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 631 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=682, Invalid=2074, Unknown=0, NotChecked=0, Total=2756 [2023-11-23 21:09:55,173 INFO L413 NwaCegarLoop]: 33 mSDtfsCounter, 305 mSDsluCounter, 101 mSDsCounter, 0 mSdLazyCounter, 391 mSolverCounterSat, 146 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 305 SdHoareTripleChecker+Valid, 134 SdHoareTripleChecker+Invalid, 537 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 146 IncrementalHoareTripleChecker+Valid, 391 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2023-11-23 21:09:55,174 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [305 Valid, 134 Invalid, 537 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [146 Valid, 391 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2023-11-23 21:09:55,174 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 160 states. [2023-11-23 21:09:55,185 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 160 to 136. [2023-11-23 21:09:55,186 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 136 states, 110 states have (on average 1.0454545454545454) internal successors, (115), 107 states have internal predecessors, (115), 17 states have call successors, (17), 14 states have call predecessors, (17), 8 states have return successors, (38), 14 states have call predecessors, (38), 16 states have call successors, (38) [2023-11-23 21:09:55,188 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 136 states to 136 states and 170 transitions. [2023-11-23 21:09:55,188 INFO L78 Accepts]: Start accepts. Automaton has 136 states and 170 transitions. Word has length 496 [2023-11-23 21:09:55,189 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 21:09:55,189 INFO L495 AbstractCegarLoop]: Abstraction has 136 states and 170 transitions. [2023-11-23 21:09:55,190 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 27 states, 27 states have (on average 5.851851851851852) internal successors, (158), 27 states have internal predecessors, (158), 19 states have call successors, (28), 1 states have call predecessors, (28), 12 states have return successors, (38), 19 states have call predecessors, (38), 19 states have call successors, (38) [2023-11-23 21:09:55,190 INFO L276 IsEmpty]: Start isEmpty. Operand 136 states and 170 transitions. [2023-11-23 21:09:55,192 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 340 [2023-11-23 21:09:55,193 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 21:09:55,193 INFO L195 NwaCegarLoop]: trace histogram [35, 34, 28, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 16, 11, 7, 1, 1, 1, 1] [2023-11-23 21:09:55,217 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Forceful destruction successful, exit code 0 [2023-11-23 21:09:55,404 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2023-11-23 21:09:55,404 INFO L420 AbstractCegarLoop]: === Iteration 16 === Targeting fibonacciErr5ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2023-11-23 21:09:55,405 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 21:09:55,405 INFO L85 PathProgramCache]: Analyzing trace with hash -332352317, now seen corresponding path program 9 times [2023-11-23 21:09:55,405 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-23 21:09:55,405 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1612390996] [2023-11-23 21:09:55,405 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 21:09:55,405 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 21:09:55,463 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 21:09:56,084 INFO L134 CoverageAnalysis]: Checked inductivity of 4050 backedges. 743 proven. 1095 refuted. 0 times theorem prover too weak. 2212 trivial. 0 not checked. [2023-11-23 21:09:56,085 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-23 21:09:56,085 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1612390996] [2023-11-23 21:09:56,085 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1612390996] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-23 21:09:56,085 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [947333966] [2023-11-23 21:09:56,086 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2023-11-23 21:09:56,086 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 21:09:56,086 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/z3 [2023-11-23 21:09:56,087 INFO L229 MonitoredProcess]: Starting monitored process 14 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-23 21:09:56,116 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2023-11-23 21:09:56,281 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2023-11-23 21:09:56,281 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-23 21:09:56,283 INFO L262 TraceCheckSpWp]: Trace formula consists of 425 conjuncts, 22 conjunts are in the unsatisfiable core [2023-11-23 21:09:56,295 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-23 21:09:56,481 INFO L134 CoverageAnalysis]: Checked inductivity of 4050 backedges. 856 proven. 1214 refuted. 0 times theorem prover too weak. 1980 trivial. 0 not checked. [2023-11-23 21:09:56,481 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-23 21:09:58,508 INFO L134 CoverageAnalysis]: Checked inductivity of 4050 backedges. 856 proven. 1290 refuted. 0 times theorem prover too weak. 1904 trivial. 0 not checked. [2023-11-23 21:09:58,509 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [947333966] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-23 21:09:58,509 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1673434146] [2023-11-23 21:09:58,511 INFO L159 IcfgInterpreter]: Started Sifa with 19 locations of interest [2023-11-23 21:09:58,511 INFO L166 IcfgInterpreter]: Building call graph [2023-11-23 21:09:58,511 FATAL L? ?]: Ignoring exception! java.lang.IllegalArgumentException: Recursive programs are not supported. at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.topsortRelevant(CallGraph.java:132) at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.(CallGraph.java:97) at de.uni_freiburg.informatik.ultimate.lib.sifa.IcfgInterpreter.(IcfgInterpreter.java:92) at de.uni_freiburg.informatik.ultimate.plugins.sifa.SifaBuilder.construct(SifaBuilder.java:96) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.SifaRunner.(SifaRunner.java:98) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleSifa.construct(IpTcStrategyModuleSifa.java:68) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getOrConstruct(IpTcStrategyModuleBase.java:101) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getInterpolantComputationStatus(IpTcStrategyModuleBase.java:77) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.tryExecuteInterpolantGenerator(AutomatonFreeRefinementEngine.java:267) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.generateProof(AutomatonFreeRefinementEngine.java:148) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.executeStrategy(AutomatonFreeRefinementEngine.java:137) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.(AutomatonFreeRefinementEngine.java:85) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.TraceAbstractionRefinementEngine.(TraceAbstractionRefinementEngine.java:82) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.BasicCegarLoop.isCounterexampleFeasible(BasicCegarLoop.java:337) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterate(AbstractCegarLoop.java:431) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.startCegar(AbstractCegarLoop.java:366) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.runCegar(AbstractCegarLoop.java:348) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.executeCegarLoop(TraceAbstractionStarter.java:415) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseProgram(TraceAbstractionStarter.java:302) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseSequentialProgram(TraceAbstractionStarter.java:262) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.runCegarLoops(TraceAbstractionStarter.java:175) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.(TraceAbstractionStarter.java:154) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver.finish(TraceAbstractionObserver.java:124) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runObserver(PluginConnector.java:167) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runTool(PluginConnector.java:150) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.run(PluginConnector.java:127) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.executePluginConnector(ToolchainWalker.java:233) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.processPlugin(ToolchainWalker.java:227) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walkUnprotected(ToolchainWalker.java:144) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walk(ToolchainWalker.java:106) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainManager$Toolchain.processToolchain(ToolchainManager.java:319) at de.uni_freiburg.informatik.ultimate.core.coreplugin.toolchain.DefaultToolchainJob.run(DefaultToolchainJob.java:145) at org.eclipse.core.internal.jobs.Worker.run(Worker.java:63) [2023-11-23 21:09:58,512 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-23 21:09:58,513 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 15, 23] total 28 [2023-11-23 21:09:58,513 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [463927004] [2023-11-23 21:09:58,513 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-23 21:09:58,514 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 28 states [2023-11-23 21:09:58,514 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-23 21:09:58,515 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 28 interpolants. [2023-11-23 21:09:58,516 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=143, Invalid=613, Unknown=0, NotChecked=0, Total=756 [2023-11-23 21:09:58,516 INFO L87 Difference]: Start difference. First operand 136 states and 170 transitions. Second operand has 28 states, 28 states have (on average 5.321428571428571) internal successors, (149), 28 states have internal predecessors, (149), 21 states have call successors, (25), 1 states have call predecessors, (25), 11 states have return successors, (32), 13 states have call predecessors, (32), 21 states have call successors, (32) [2023-11-23 21:09:58,970 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 21:09:58,970 INFO L93 Difference]: Finished difference Result 279 states and 364 transitions. [2023-11-23 21:09:58,970 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2023-11-23 21:09:58,971 INFO L78 Accepts]: Start accepts. Automaton has has 28 states, 28 states have (on average 5.321428571428571) internal successors, (149), 28 states have internal predecessors, (149), 21 states have call successors, (25), 1 states have call predecessors, (25), 11 states have return successors, (32), 13 states have call predecessors, (32), 21 states have call successors, (32) Word has length 339 [2023-11-23 21:09:58,972 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 21:09:58,973 INFO L225 Difference]: With dead ends: 279 [2023-11-23 21:09:58,973 INFO L226 Difference]: Without dead ends: 148 [2023-11-23 21:09:58,976 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 713 GetRequests, 661 SyntacticMatches, 11 SemanticMatches, 41 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 516 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=480, Invalid=1326, Unknown=0, NotChecked=0, Total=1806 [2023-11-23 21:09:58,976 INFO L413 NwaCegarLoop]: 47 mSDtfsCounter, 193 mSDsluCounter, 109 mSDsCounter, 0 mSdLazyCounter, 404 mSolverCounterSat, 82 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 193 SdHoareTripleChecker+Valid, 156 SdHoareTripleChecker+Invalid, 486 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 82 IncrementalHoareTripleChecker+Valid, 404 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2023-11-23 21:09:58,977 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [193 Valid, 156 Invalid, 486 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [82 Valid, 404 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2023-11-23 21:09:58,977 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 148 states. [2023-11-23 21:09:58,987 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 148 to 124. [2023-11-23 21:09:58,987 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 124 states, 99 states have (on average 1.0303030303030303) internal successors, (102), 98 states have internal predecessors, (102), 16 states have call successors, (16), 12 states have call predecessors, (16), 8 states have return successors, (35), 13 states have call predecessors, (35), 15 states have call successors, (35) [2023-11-23 21:09:58,989 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 124 states to 124 states and 153 transitions. [2023-11-23 21:09:58,990 INFO L78 Accepts]: Start accepts. Automaton has 124 states and 153 transitions. Word has length 339 [2023-11-23 21:09:58,991 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 21:09:58,991 INFO L495 AbstractCegarLoop]: Abstraction has 124 states and 153 transitions. [2023-11-23 21:09:58,991 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 28 states, 28 states have (on average 5.321428571428571) internal successors, (149), 28 states have internal predecessors, (149), 21 states have call successors, (25), 1 states have call predecessors, (25), 11 states have return successors, (32), 13 states have call predecessors, (32), 21 states have call successors, (32) [2023-11-23 21:09:58,991 INFO L276 IsEmpty]: Start isEmpty. Operand 124 states and 153 transitions. [2023-11-23 21:09:58,994 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 399 [2023-11-23 21:09:58,994 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 21:09:58,994 INFO L195 NwaCegarLoop]: trace histogram [41, 40, 33, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 19, 13, 8, 1, 1, 1, 1] [2023-11-23 21:09:59,020 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Forceful destruction successful, exit code 0 [2023-11-23 21:09:59,220 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable15 [2023-11-23 21:09:59,221 INFO L420 AbstractCegarLoop]: === Iteration 17 === Targeting fibonacciErr5ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2023-11-23 21:09:59,221 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 21:09:59,221 INFO L85 PathProgramCache]: Analyzing trace with hash -1078591254, now seen corresponding path program 10 times [2023-11-23 21:09:59,222 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-23 21:09:59,222 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [175402166] [2023-11-23 21:09:59,222 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 21:09:59,222 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 21:09:59,306 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 21:10:02,451 INFO L134 CoverageAnalysis]: Checked inductivity of 5628 backedges. 830 proven. 1470 refuted. 0 times theorem prover too weak. 3328 trivial. 0 not checked. [2023-11-23 21:10:02,452 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-23 21:10:02,452 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [175402166] [2023-11-23 21:10:02,452 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [175402166] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-23 21:10:02,452 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [655142618] [2023-11-23 21:10:02,453 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2023-11-23 21:10:02,453 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 21:10:02,453 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/z3 [2023-11-23 21:10:02,457 INFO L229 MonitoredProcess]: Starting monitored process 15 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-23 21:10:02,468 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2023-11-23 21:10:02,703 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 21:10:02,708 INFO L262 TraceCheckSpWp]: Trace formula consists of 757 conjuncts, 81 conjunts are in the unsatisfiable core [2023-11-23 21:10:02,717 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-23 21:10:03,264 INFO L134 CoverageAnalysis]: Checked inductivity of 5628 backedges. 820 proven. 1112 refuted. 0 times theorem prover too weak. 3696 trivial. 0 not checked. [2023-11-23 21:10:03,264 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-23 21:10:12,486 INFO L134 CoverageAnalysis]: Checked inductivity of 5628 backedges. 1149 proven. 1015 refuted. 0 times theorem prover too weak. 3464 trivial. 0 not checked. [2023-11-23 21:10:12,486 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [655142618] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-23 21:10:12,487 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1808835718] [2023-11-23 21:10:12,489 INFO L159 IcfgInterpreter]: Started Sifa with 19 locations of interest [2023-11-23 21:10:12,489 INFO L166 IcfgInterpreter]: Building call graph [2023-11-23 21:10:12,489 FATAL L? ?]: Ignoring exception! java.lang.IllegalArgumentException: Recursive programs are not supported. at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.topsortRelevant(CallGraph.java:132) at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.(CallGraph.java:97) at de.uni_freiburg.informatik.ultimate.lib.sifa.IcfgInterpreter.(IcfgInterpreter.java:92) at de.uni_freiburg.informatik.ultimate.plugins.sifa.SifaBuilder.construct(SifaBuilder.java:96) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.SifaRunner.(SifaRunner.java:98) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleSifa.construct(IpTcStrategyModuleSifa.java:68) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getOrConstruct(IpTcStrategyModuleBase.java:101) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getInterpolantComputationStatus(IpTcStrategyModuleBase.java:77) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.tryExecuteInterpolantGenerator(AutomatonFreeRefinementEngine.java:267) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.generateProof(AutomatonFreeRefinementEngine.java:148) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.executeStrategy(AutomatonFreeRefinementEngine.java:137) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.(AutomatonFreeRefinementEngine.java:85) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.TraceAbstractionRefinementEngine.(TraceAbstractionRefinementEngine.java:82) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.BasicCegarLoop.isCounterexampleFeasible(BasicCegarLoop.java:337) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterate(AbstractCegarLoop.java:431) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.startCegar(AbstractCegarLoop.java:366) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.runCegar(AbstractCegarLoop.java:348) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.executeCegarLoop(TraceAbstractionStarter.java:415) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseProgram(TraceAbstractionStarter.java:302) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseSequentialProgram(TraceAbstractionStarter.java:262) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.runCegarLoops(TraceAbstractionStarter.java:175) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.(TraceAbstractionStarter.java:154) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver.finish(TraceAbstractionObserver.java:124) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runObserver(PluginConnector.java:167) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runTool(PluginConnector.java:150) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.run(PluginConnector.java:127) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.executePluginConnector(ToolchainWalker.java:233) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.processPlugin(ToolchainWalker.java:227) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walkUnprotected(ToolchainWalker.java:144) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walk(ToolchainWalker.java:106) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainManager$Toolchain.processToolchain(ToolchainManager.java:319) at de.uni_freiburg.informatik.ultimate.core.coreplugin.toolchain.DefaultToolchainJob.run(DefaultToolchainJob.java:145) at org.eclipse.core.internal.jobs.Worker.run(Worker.java:63) [2023-11-23 21:10:12,489 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-23 21:10:12,490 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 18, 29] total 45 [2023-11-23 21:10:12,490 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1733505755] [2023-11-23 21:10:12,490 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-23 21:10:12,491 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 46 states [2023-11-23 21:10:12,491 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-23 21:10:12,493 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 46 interpolants. [2023-11-23 21:10:12,494 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=463, Invalid=1607, Unknown=0, NotChecked=0, Total=2070 [2023-11-23 21:10:12,495 INFO L87 Difference]: Start difference. First operand 124 states and 153 transitions. Second operand has 46 states, 45 states have (on average 2.6222222222222222) internal successors, (118), 46 states have internal predecessors, (118), 12 states have call successors, (13), 1 states have call predecessors, (13), 13 states have return successors, (31), 31 states have call predecessors, (31), 12 states have call successors, (31) [2023-11-23 21:10:12,777 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 21:10:12,777 INFO L93 Difference]: Finished difference Result 157 states and 207 transitions. [2023-11-23 21:10:12,777 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 26 states. [2023-11-23 21:10:12,778 INFO L78 Accepts]: Start accepts. Automaton has has 46 states, 45 states have (on average 2.6222222222222222) internal successors, (118), 46 states have internal predecessors, (118), 12 states have call successors, (13), 1 states have call predecessors, (13), 13 states have return successors, (31), 31 states have call predecessors, (31), 12 states have call successors, (31) Word has length 398 [2023-11-23 21:10:12,779 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 21:10:12,781 INFO L225 Difference]: With dead ends: 157 [2023-11-23 21:10:12,781 INFO L226 Difference]: Without dead ends: 156 [2023-11-23 21:10:12,782 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 879 GetRequests, 780 SyntacticMatches, 51 SemanticMatches, 48 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2454 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=544, Invalid=1906, Unknown=0, NotChecked=0, Total=2450 [2023-11-23 21:10:12,783 INFO L413 NwaCegarLoop]: 18 mSDtfsCounter, 22 mSDsluCounter, 227 mSDsCounter, 0 mSdLazyCounter, 179 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 30 SdHoareTripleChecker+Valid, 245 SdHoareTripleChecker+Invalid, 188 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 179 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-23 21:10:12,783 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [30 Valid, 245 Invalid, 188 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 179 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-23 21:10:12,784 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 156 states. [2023-11-23 21:10:12,796 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 156 to 145. [2023-11-23 21:10:12,797 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 145 states, 116 states have (on average 1.0258620689655173) internal successors, (119), 114 states have internal predecessors, (119), 18 states have call successors, (18), 12 states have call predecessors, (18), 10 states have return successors, (55), 18 states have call predecessors, (55), 17 states have call successors, (55) [2023-11-23 21:10:12,799 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 145 states to 145 states and 192 transitions. [2023-11-23 21:10:12,799 INFO L78 Accepts]: Start accepts. Automaton has 145 states and 192 transitions. Word has length 398 [2023-11-23 21:10:12,800 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 21:10:12,800 INFO L495 AbstractCegarLoop]: Abstraction has 145 states and 192 transitions. [2023-11-23 21:10:12,801 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 46 states, 45 states have (on average 2.6222222222222222) internal successors, (118), 46 states have internal predecessors, (118), 12 states have call successors, (13), 1 states have call predecessors, (13), 13 states have return successors, (31), 31 states have call predecessors, (31), 12 states have call successors, (31) [2023-11-23 21:10:12,801 INFO L276 IsEmpty]: Start isEmpty. Operand 145 states and 192 transitions. [2023-11-23 21:10:12,815 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1230 [2023-11-23 21:10:12,816 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 21:10:12,816 INFO L195 NwaCegarLoop]: trace histogram [127, 123, 103, 64, 64, 64, 64, 62, 62, 62, 62, 62, 61, 61, 61, 60, 39, 24, 1, 1, 1, 1] [2023-11-23 21:10:12,836 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Forceful destruction successful, exit code 0 [2023-11-23 21:10:13,017 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 15 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_40517f19-d8de-45f8-ac32-60e559f16578/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable16 [2023-11-23 21:10:13,017 INFO L420 AbstractCegarLoop]: === Iteration 18 === Targeting fibonacciErr5ASSERT_VIOLATIONINTEGER_OVERFLOW === [fibonacciErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, fibonacciErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2023-11-23 21:10:13,017 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 21:10:13,018 INFO L85 PathProgramCache]: Analyzing trace with hash -150804752, now seen corresponding path program 11 times [2023-11-23 21:10:13,018 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-23 21:10:13,018 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2029470044] [2023-11-23 21:10:13,018 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 21:10:13,019 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 21:10:13,199 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat