./Ultimate.py --spec ../../sv-benchmarks/c/properties/unreach-call.prp --file ../../sv-benchmarks/c/recursive/Fibonacci05.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 53f42b1a Calling Ultimate with: /usr/bin/java -Dosgi.configuration.area=/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_fcaf6f6d-930b-4402-93cd-14a0711eb2d4/bin/utaipan-TEXQjIfE4P/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_fcaf6f6d-930b-4402-93cd-14a0711eb2d4/bin/utaipan-TEXQjIfE4P/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_fcaf6f6d-930b-4402-93cd-14a0711eb2d4/bin/utaipan-TEXQjIfE4P/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_fcaf6f6d-930b-4402-93cd-14a0711eb2d4/bin/utaipan-TEXQjIfE4P/config/TaipanReach.xml -i ../../sv-benchmarks/c/recursive/Fibonacci05.c -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_fcaf6f6d-930b-4402-93cd-14a0711eb2d4/bin/utaipan-TEXQjIfE4P/config/svcomp-Reach-32bit-Taipan_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_fcaf6f6d-930b-4402-93cd-14a0711eb2d4/bin/utaipan-TEXQjIfE4P --witnessprinter.witness.filename witness.graphml --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(G ! call(reach_error())) ) --witnessprinter.graph.data.producer Taipan --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash 97829031814878890268a6b8dbba5c3e987e2ec78ab2dc94181f9e68090060bd --- Real Ultimate output --- This is Ultimate 0.2.1-dev-53f42b1 [2021-11-20 22:45:29,369 INFO L177 SettingsManager]: Resetting all preferences to default values... [2021-11-20 22:45:29,372 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2021-11-20 22:45:29,421 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2021-11-20 22:45:29,421 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2021-11-20 22:45:29,423 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2021-11-20 22:45:29,424 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2021-11-20 22:45:29,427 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2021-11-20 22:45:29,428 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2021-11-20 22:45:29,430 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2021-11-20 22:45:29,431 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2021-11-20 22:45:29,432 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2021-11-20 22:45:29,433 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2021-11-20 22:45:29,434 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2021-11-20 22:45:29,436 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2021-11-20 22:45:29,437 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2021-11-20 22:45:29,438 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2021-11-20 22:45:29,439 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2021-11-20 22:45:29,442 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2021-11-20 22:45:29,445 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2021-11-20 22:45:29,447 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2021-11-20 22:45:29,453 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2021-11-20 22:45:29,454 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2021-11-20 22:45:29,455 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2021-11-20 22:45:29,459 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2021-11-20 22:45:29,468 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2021-11-20 22:45:29,468 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2021-11-20 22:45:29,469 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2021-11-20 22:45:29,470 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2021-11-20 22:45:29,471 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2021-11-20 22:45:29,472 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2021-11-20 22:45:29,472 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2021-11-20 22:45:29,475 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2021-11-20 22:45:29,476 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2021-11-20 22:45:29,478 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2021-11-20 22:45:29,479 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2021-11-20 22:45:29,480 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2021-11-20 22:45:29,481 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2021-11-20 22:45:29,481 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2021-11-20 22:45:29,482 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2021-11-20 22:45:29,483 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2021-11-20 22:45:29,484 INFO L101 SettingsManager]: Beginning loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_fcaf6f6d-930b-4402-93cd-14a0711eb2d4/bin/utaipan-TEXQjIfE4P/config/svcomp-Reach-32bit-Taipan_Default.epf [2021-11-20 22:45:29,508 INFO L113 SettingsManager]: Loading preferences was successful [2021-11-20 22:45:29,509 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2021-11-20 22:45:29,509 INFO L136 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2021-11-20 22:45:29,509 INFO L138 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2021-11-20 22:45:29,510 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2021-11-20 22:45:29,510 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2021-11-20 22:45:29,510 INFO L138 SettingsManager]: * User list type=DISABLED [2021-11-20 22:45:29,510 INFO L136 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2021-11-20 22:45:29,511 INFO L138 SettingsManager]: * Explicit value domain=true [2021-11-20 22:45:29,511 INFO L138 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2021-11-20 22:45:29,511 INFO L138 SettingsManager]: * Octagon Domain=false [2021-11-20 22:45:29,511 INFO L138 SettingsManager]: * Abstract domain=CompoundDomain [2021-11-20 22:45:29,511 INFO L138 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2021-11-20 22:45:29,512 INFO L138 SettingsManager]: * Use the RCFG-of-the-future interface=true [2021-11-20 22:45:29,512 INFO L138 SettingsManager]: * Interval Domain=false [2021-11-20 22:45:29,512 INFO L136 SettingsManager]: Preferences of Sifa differ from their defaults: [2021-11-20 22:45:29,512 INFO L138 SettingsManager]: * Call Summarizer=TopInputCallSummarizer [2021-11-20 22:45:29,513 INFO L138 SettingsManager]: * Simplification Technique=POLY_PAC [2021-11-20 22:45:29,513 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2021-11-20 22:45:29,513 INFO L138 SettingsManager]: * sizeof long=4 [2021-11-20 22:45:29,514 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2021-11-20 22:45:29,514 INFO L138 SettingsManager]: * sizeof POINTER=4 [2021-11-20 22:45:29,514 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2021-11-20 22:45:29,514 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2021-11-20 22:45:29,514 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2021-11-20 22:45:29,515 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2021-11-20 22:45:29,515 INFO L138 SettingsManager]: * sizeof long double=12 [2021-11-20 22:45:29,515 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2021-11-20 22:45:29,515 INFO L138 SettingsManager]: * Use constant arrays=true [2021-11-20 22:45:29,515 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2021-11-20 22:45:29,516 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2021-11-20 22:45:29,516 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2021-11-20 22:45:29,516 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2021-11-20 22:45:29,516 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2021-11-20 22:45:29,516 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2021-11-20 22:45:29,517 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2021-11-20 22:45:29,517 INFO L138 SettingsManager]: * Trace refinement strategy=SIFA_TAIPAN [2021-11-20 22:45:29,517 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2021-11-20 22:45:29,517 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2021-11-20 22:45:29,517 INFO L138 SettingsManager]: * Trace refinement exception blacklist=NONE [2021-11-20 22:45:29,518 INFO L138 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2021-11-20 22:45:29,518 INFO L138 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_fcaf6f6d-930b-4402-93cd-14a0711eb2d4/bin/utaipan-TEXQjIfE4P/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_fcaf6f6d-930b-4402-93cd-14a0711eb2d4/bin/utaipan-TEXQjIfE4P Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness.graphml 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 ! call(reach_error())) ) 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 -> 32bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> 97829031814878890268a6b8dbba5c3e987e2ec78ab2dc94181f9e68090060bd [2021-11-20 22:45:29,735 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2021-11-20 22:45:29,754 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2021-11-20 22:45:29,756 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2021-11-20 22:45:29,758 INFO L271 PluginConnector]: Initializing CDTParser... [2021-11-20 22:45:29,758 INFO L275 PluginConnector]: CDTParser initialized [2021-11-20 22:45:29,760 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_fcaf6f6d-930b-4402-93cd-14a0711eb2d4/bin/utaipan-TEXQjIfE4P/../../sv-benchmarks/c/recursive/Fibonacci05.c [2021-11-20 22:45:29,819 INFO L220 CDTParser]: Created temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_fcaf6f6d-930b-4402-93cd-14a0711eb2d4/bin/utaipan-TEXQjIfE4P/data/e47a57806/7a3ee6b2fea344048bbc16b4356878cc/FLAG3bc8ae4f4 [2021-11-20 22:45:30,233 INFO L306 CDTParser]: Found 1 translation units. [2021-11-20 22:45:30,233 INFO L160 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_fcaf6f6d-930b-4402-93cd-14a0711eb2d4/sv-benchmarks/c/recursive/Fibonacci05.c [2021-11-20 22:45:30,243 INFO L349 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_fcaf6f6d-930b-4402-93cd-14a0711eb2d4/bin/utaipan-TEXQjIfE4P/data/e47a57806/7a3ee6b2fea344048bbc16b4356878cc/FLAG3bc8ae4f4 [2021-11-20 22:45:30,628 INFO L357 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_fcaf6f6d-930b-4402-93cd-14a0711eb2d4/bin/utaipan-TEXQjIfE4P/data/e47a57806/7a3ee6b2fea344048bbc16b4356878cc [2021-11-20 22:45:30,631 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2021-11-20 22:45:30,632 INFO L131 ToolchainWalker]: Walking toolchain with 6 elements. [2021-11-20 22:45:30,634 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2021-11-20 22:45:30,634 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2021-11-20 22:45:30,637 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2021-11-20 22:45:30,638 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 20.11 10:45:30" (1/1) ... [2021-11-20 22:45:30,639 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@43cb2bfe and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.11 10:45:30, skipping insertion in model container [2021-11-20 22:45:30,639 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 20.11 10:45:30" (1/1) ... [2021-11-20 22:45:30,645 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2021-11-20 22:45:30,657 INFO L178 MainTranslator]: Built tables and reachable declarations [2021-11-20 22:45:30,816 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_fcaf6f6d-930b-4402-93cd-14a0711eb2d4/sv-benchmarks/c/recursive/Fibonacci05.c[746,759] [2021-11-20 22:45:30,825 INFO L209 PostProcessor]: Analyzing one entry point: main [2021-11-20 22:45:30,833 INFO L203 MainTranslator]: Completed pre-run [2021-11-20 22:45:30,847 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_fcaf6f6d-930b-4402-93cd-14a0711eb2d4/sv-benchmarks/c/recursive/Fibonacci05.c[746,759] [2021-11-20 22:45:30,847 INFO L209 PostProcessor]: Analyzing one entry point: main [2021-11-20 22:45:30,859 INFO L208 MainTranslator]: Completed translation [2021-11-20 22:45:30,860 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.11 10:45:30 WrapperNode [2021-11-20 22:45:30,860 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2021-11-20 22:45:30,861 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2021-11-20 22:45:30,861 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2021-11-20 22:45:30,862 INFO L275 PluginConnector]: Boogie Procedure Inliner initialized [2021-11-20 22:45:30,869 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.11 10:45:30" (1/1) ... [2021-11-20 22:45:30,874 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.11 10:45:30" (1/1) ... [2021-11-20 22:45:30,889 INFO L137 Inliner]: procedures = 13, calls = 10, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 23 [2021-11-20 22:45:30,890 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2021-11-20 22:45:30,891 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2021-11-20 22:45:30,891 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2021-11-20 22:45:30,891 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2021-11-20 22:45:30,898 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.11 10:45:30" (1/1) ... [2021-11-20 22:45:30,899 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.11 10:45:30" (1/1) ... [2021-11-20 22:45:30,900 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.11 10:45:30" (1/1) ... [2021-11-20 22:45:30,900 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.11 10:45:30" (1/1) ... [2021-11-20 22:45:30,903 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.11 10:45:30" (1/1) ... [2021-11-20 22:45:30,904 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.11 10:45:30" (1/1) ... [2021-11-20 22:45:30,905 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.11 10:45:30" (1/1) ... [2021-11-20 22:45:30,906 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2021-11-20 22:45:30,907 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2021-11-20 22:45:30,907 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2021-11-20 22:45:30,908 INFO L275 PluginConnector]: RCFGBuilder initialized [2021-11-20 22:45:30,909 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.11 10:45:30" (1/1) ... [2021-11-20 22:45:30,922 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2021-11-20 22:45:30,935 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_fcaf6f6d-930b-4402-93cd-14a0711eb2d4/bin/utaipan-TEXQjIfE4P/z3 [2021-11-20 22:45:30,964 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_fcaf6f6d-930b-4402-93cd-14a0711eb2d4/bin/utaipan-TEXQjIfE4P/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2021-11-20 22:45:30,994 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_fcaf6f6d-930b-4402-93cd-14a0711eb2d4/bin/utaipan-TEXQjIfE4P/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2021-11-20 22:45:31,013 INFO L130 BoogieDeclarations]: Found specification of procedure fibonacci [2021-11-20 22:45:31,013 INFO L138 BoogieDeclarations]: Found implementation of procedure fibonacci [2021-11-20 22:45:31,013 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2021-11-20 22:45:31,014 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2021-11-20 22:45:31,014 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2021-11-20 22:45:31,014 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2021-11-20 22:45:31,076 INFO L236 CfgBuilder]: Building ICFG [2021-11-20 22:45:31,077 INFO L262 CfgBuilder]: Building CFG for each procedure with an implementation [2021-11-20 22:45:31,213 INFO L277 CfgBuilder]: Performing block encoding [2021-11-20 22:45:31,225 INFO L296 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2021-11-20 22:45:31,227 INFO L301 CfgBuilder]: Removed 0 assume(true) statements. [2021-11-20 22:45:31,230 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.11 10:45:31 BoogieIcfgContainer [2021-11-20 22:45:31,230 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2021-11-20 22:45:31,232 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2021-11-20 22:45:31,232 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2021-11-20 22:45:31,235 INFO L275 PluginConnector]: TraceAbstraction initialized [2021-11-20 22:45:31,235 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 20.11 10:45:30" (1/3) ... [2021-11-20 22:45:31,237 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4fb7855c and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 20.11 10:45:31, skipping insertion in model container [2021-11-20 22:45:31,237 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.11 10:45:30" (2/3) ... [2021-11-20 22:45:31,238 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4fb7855c and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 20.11 10:45:31, skipping insertion in model container [2021-11-20 22:45:31,238 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.11 10:45:31" (3/3) ... [2021-11-20 22:45:31,239 INFO L111 eAbstractionObserver]: Analyzing ICFG Fibonacci05.c [2021-11-20 22:45:31,247 INFO L204 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2021-11-20 22:45:31,248 INFO L163 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2021-11-20 22:45:31,294 INFO L338 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2021-11-20 22:45:31,301 INFO L339 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=LoopsAndPotentialCycles, 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, mLoopAccelerationTechnique=FAST_UPR [2021-11-20 22:45:31,301 INFO L340 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2021-11-20 22:45:31,329 INFO L276 IsEmpty]: Start isEmpty. Operand has 17 states, 11 states have (on average 1.3636363636363635) internal successors, (15), 12 states have internal predecessors, (15), 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) [2021-11-20 22:45:31,335 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 10 [2021-11-20 22:45:31,335 INFO L506 BasicCegarLoop]: Found error trace [2021-11-20 22:45:31,336 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-20 22:45:31,336 INFO L402 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-20 22:45:31,340 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-20 22:45:31,340 INFO L85 PathProgramCache]: Analyzing trace with hash -1615401540, now seen corresponding path program 1 times [2021-11-20 22:45:31,349 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-20 22:45:31,350 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [232287082] [2021-11-20 22:45:31,350 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-20 22:45:31,351 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-20 22:45:31,437 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-20 22:45:31,525 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-11-20 22:45:31,525 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-20 22:45:31,526 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [232287082] [2021-11-20 22:45:31,526 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [232287082] provided 1 perfect and 0 imperfect interpolant sequences [2021-11-20 22:45:31,527 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-11-20 22:45:31,527 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2021-11-20 22:45:31,528 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [634706704] [2021-11-20 22:45:31,529 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-11-20 22:45:31,533 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2021-11-20 22:45:31,533 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-20 22:45:31,588 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2021-11-20 22:45:31,589 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2021-11-20 22:45:31,591 INFO L87 Difference]: Start difference. First operand has 17 states, 11 states have (on average 1.3636363636363635) internal successors, (15), 12 states have internal predecessors, (15), 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 5 states, 5 states have (on average 1.4) internal successors, (7), 5 states have internal predecessors, (7), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2021-11-20 22:45:31,670 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-20 22:45:31,670 INFO L93 Difference]: Finished difference Result 27 states and 32 transitions. [2021-11-20 22:45:31,671 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2021-11-20 22:45:31,672 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.4) internal successors, (7), 5 states have internal predecessors, (7), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 9 [2021-11-20 22:45:31,673 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-20 22:45:31,680 INFO L225 Difference]: With dead ends: 27 [2021-11-20 22:45:31,680 INFO L226 Difference]: Without dead ends: 17 [2021-11-20 22:45:31,683 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2021-11-20 22:45:31,687 INFO L933 BasicCegarLoop]: 10 mSDtfsCounter, 10 mSDsluCounter, 21 mSDsCounter, 0 mSdLazyCounter, 43 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 26 SdHoareTripleChecker+Invalid, 43 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 43 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-11-20 22:45:31,688 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [14 Valid, 26 Invalid, 43 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 43 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-11-20 22:45:31,721 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 17 states. [2021-11-20 22:45:31,756 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 17 to 17. [2021-11-20 22:45:31,757 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 17 states, 11 states have (on average 1.1818181818181819) internal successors, (13), 12 states have internal predecessors, (13), 3 states have call successors, (3), 1 states have call predecessors, (3), 2 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) [2021-11-20 22:45:31,759 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 17 states to 17 states and 21 transitions. [2021-11-20 22:45:31,760 INFO L78 Accepts]: Start accepts. Automaton has 17 states and 21 transitions. Word has length 9 [2021-11-20 22:45:31,760 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-20 22:45:31,761 INFO L470 AbstractCegarLoop]: Abstraction has 17 states and 21 transitions. [2021-11-20 22:45:31,761 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.4) internal successors, (7), 5 states have internal predecessors, (7), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2021-11-20 22:45:31,761 INFO L276 IsEmpty]: Start isEmpty. Operand 17 states and 21 transitions. [2021-11-20 22:45:31,762 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 11 [2021-11-20 22:45:31,762 INFO L506 BasicCegarLoop]: Found error trace [2021-11-20 22:45:31,763 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-20 22:45:31,763 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2021-11-20 22:45:31,763 INFO L402 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-20 22:45:31,764 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-20 22:45:31,764 INFO L85 PathProgramCache]: Analyzing trace with hash -2136894566, now seen corresponding path program 1 times [2021-11-20 22:45:31,765 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-20 22:45:31,765 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [137532949] [2021-11-20 22:45:31,765 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-20 22:45:31,765 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-20 22:45:31,777 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-20 22:45:31,816 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-11-20 22:45:31,816 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-20 22:45:31,817 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [137532949] [2021-11-20 22:45:31,817 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [137532949] provided 1 perfect and 0 imperfect interpolant sequences [2021-11-20 22:45:31,817 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-11-20 22:45:31,818 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2021-11-20 22:45:31,818 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1604414794] [2021-11-20 22:45:31,818 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-11-20 22:45:31,820 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2021-11-20 22:45:31,820 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-20 22:45:31,821 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2021-11-20 22:45:31,821 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2021-11-20 22:45:31,821 INFO L87 Difference]: Start difference. First operand 17 states and 21 transitions. Second operand has 5 states, 5 states have (on average 1.6) internal successors, (8), 5 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2021-11-20 22:45:31,870 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-20 22:45:31,870 INFO L93 Difference]: Finished difference Result 23 states and 28 transitions. [2021-11-20 22:45:31,871 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2021-11-20 22:45:31,871 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.6) internal successors, (8), 5 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 10 [2021-11-20 22:45:31,872 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-20 22:45:31,873 INFO L225 Difference]: With dead ends: 23 [2021-11-20 22:45:31,873 INFO L226 Difference]: Without dead ends: 19 [2021-11-20 22:45:31,873 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2021-11-20 22:45:31,875 INFO L933 BasicCegarLoop]: 10 mSDtfsCounter, 7 mSDsluCounter, 18 mSDsCounter, 0 mSdLazyCounter, 34 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 26 SdHoareTripleChecker+Invalid, 35 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 34 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-11-20 22:45:31,876 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [11 Valid, 26 Invalid, 35 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 34 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-11-20 22:45:31,878 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 19 states. [2021-11-20 22:45:31,882 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 19 to 17. [2021-11-20 22:45:31,882 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 17 states, 11 states have (on average 1.1818181818181819) internal successors, (13), 12 states have internal predecessors, (13), 3 states have call successors, (3), 1 states have call predecessors, (3), 2 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) [2021-11-20 22:45:31,883 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 17 states to 17 states and 21 transitions. [2021-11-20 22:45:31,884 INFO L78 Accepts]: Start accepts. Automaton has 17 states and 21 transitions. Word has length 10 [2021-11-20 22:45:31,884 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-20 22:45:31,884 INFO L470 AbstractCegarLoop]: Abstraction has 17 states and 21 transitions. [2021-11-20 22:45:31,885 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.6) internal successors, (8), 5 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2021-11-20 22:45:31,885 INFO L276 IsEmpty]: Start isEmpty. Operand 17 states and 21 transitions. [2021-11-20 22:45:31,886 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2021-11-20 22:45:31,886 INFO L506 BasicCegarLoop]: Found error trace [2021-11-20 22:45:31,886 INFO L514 BasicCegarLoop]: trace histogram [3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-20 22:45:31,887 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2021-11-20 22:45:31,887 INFO L402 AbstractCegarLoop]: === Iteration 3 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-20 22:45:31,888 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-20 22:45:31,888 INFO L85 PathProgramCache]: Analyzing trace with hash -338238899, now seen corresponding path program 1 times [2021-11-20 22:45:31,888 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-20 22:45:31,889 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [992844353] [2021-11-20 22:45:31,889 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-20 22:45:31,889 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-20 22:45:31,907 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-20 22:45:31,968 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 5 proven. 3 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2021-11-20 22:45:31,968 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-20 22:45:31,969 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [992844353] [2021-11-20 22:45:31,969 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [992844353] provided 0 perfect and 1 imperfect interpolant sequences [2021-11-20 22:45:31,970 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1819625965] [2021-11-20 22:45:31,972 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-20 22:45:31,973 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-20 22:45:31,973 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_fcaf6f6d-930b-4402-93cd-14a0711eb2d4/bin/utaipan-TEXQjIfE4P/z3 [2021-11-20 22:45:31,979 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_fcaf6f6d-930b-4402-93cd-14a0711eb2d4/bin/utaipan-TEXQjIfE4P/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-20 22:45:32,002 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_fcaf6f6d-930b-4402-93cd-14a0711eb2d4/bin/utaipan-TEXQjIfE4P/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2021-11-20 22:45:32,038 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-20 22:45:32,040 INFO L263 TraceCheckSpWp]: Trace formula consists of 75 conjuncts, 6 conjunts are in the unsatisfiable core [2021-11-20 22:45:32,045 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-20 22:45:32,167 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 2 proven. 6 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2021-11-20 22:45:32,168 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-11-20 22:45:32,392 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 2 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2021-11-20 22:45:32,393 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1819625965] provided 0 perfect and 2 imperfect interpolant sequences [2021-11-20 22:45:32,393 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1527220090] [2021-11-20 22:45:32,413 INFO L159 IcfgInterpreter]: Started Sifa with 15 locations of interest [2021-11-20 22:45:32,414 INFO L166 IcfgInterpreter]: Building call graph [2021-11-20 22:45:32,419 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:94) 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:67) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getOrConstruct(IpTcStrategyModuleBase.java:100) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getInterpolantComputationStatus(IpTcStrategyModuleBase.java:76) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.AutomatonFreeRefinementEngine.tryExecuteInterpolantGenerator(AutomatonFreeRefinementEngine.java:268) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.AutomatonFreeRefinementEngine.generateProof(AutomatonFreeRefinementEngine.java:150) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.AutomatonFreeRefinementEngine.executeStrategy(AutomatonFreeRefinementEngine.java:140) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.AutomatonFreeRefinementEngine.(AutomatonFreeRefinementEngine.java:88) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.TraceAbstractionRefinementEngine.(TraceAbstractionRefinementEngine.java:76) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.BasicCegarLoop.isCounterexampleFeasible(BasicCegarLoop.java:610) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterate(AbstractCegarLoop.java:413) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.startCegar(AbstractCegarLoop.java:348) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.runCegar(AbstractCegarLoop.java:330) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.CegarLoopUtils.getCegarLoopResult(CegarLoopUtils.java:56) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.executeCegarLoop(TraceAbstractionStarter.java:393) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseProgram(TraceAbstractionStarter.java:303) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseSequentialProgram(TraceAbstractionStarter.java:263) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.runCegarLoops(TraceAbstractionStarter.java:176) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.(TraceAbstractionStarter.java:155) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver.finish(TraceAbstractionObserver.java:123) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runObserver(PluginConnector.java:168) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runTool(PluginConnector.java:151) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.run(PluginConnector.java:128) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.executePluginConnector(ToolchainWalker.java:232) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.processPlugin(ToolchainWalker.java:226) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walkUnprotected(ToolchainWalker.java:142) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walk(ToolchainWalker.java:104) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainManager$Toolchain.processToolchain(ToolchainManager.java:320) 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) [2021-11-20 22:45:32,421 INFO L186 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2021-11-20 22:45:32,421 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6, 7] total 12 [2021-11-20 22:45:32,421 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2145557783] [2021-11-20 22:45:32,422 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2021-11-20 22:45:32,422 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2021-11-20 22:45:32,423 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-20 22:45:32,423 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2021-11-20 22:45:32,424 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=35, Invalid=97, Unknown=0, NotChecked=0, Total=132 [2021-11-20 22:45:32,424 INFO L87 Difference]: Start difference. First operand 17 states and 21 transitions. Second operand has 12 states, 11 states have (on average 2.909090909090909) internal successors, (32), 12 states have internal predecessors, (32), 7 states have call successors, (7), 1 states have call predecessors, (7), 5 states have return successors, (9), 5 states have call predecessors, (9), 7 states have call successors, (9) [2021-11-20 22:45:32,546 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-20 22:45:32,546 INFO L93 Difference]: Finished difference Result 41 states and 59 transitions. [2021-11-20 22:45:32,546 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2021-11-20 22:45:32,547 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 11 states have (on average 2.909090909090909) internal successors, (32), 12 states have internal predecessors, (32), 7 states have call successors, (7), 1 states have call predecessors, (7), 5 states have return successors, (9), 5 states have call predecessors, (9), 7 states have call successors, (9) Word has length 22 [2021-11-20 22:45:32,547 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-20 22:45:32,548 INFO L225 Difference]: With dead ends: 41 [2021-11-20 22:45:32,549 INFO L226 Difference]: Without dead ends: 24 [2021-11-20 22:45:32,550 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 57 GetRequests, 40 SyntacticMatches, 2 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 29 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=76, Invalid=196, Unknown=0, NotChecked=0, Total=272 [2021-11-20 22:45:32,551 INFO L933 BasicCegarLoop]: 12 mSDtfsCounter, 26 mSDsluCounter, 40 mSDsCounter, 0 mSdLazyCounter, 72 mSolverCounterSat, 40 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 26 SdHoareTripleChecker+Valid, 47 SdHoareTripleChecker+Invalid, 112 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 40 IncrementalHoareTripleChecker+Valid, 72 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2021-11-20 22:45:32,552 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [26 Valid, 47 Invalid, 112 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [40 Valid, 72 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2021-11-20 22:45:32,553 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 24 states. [2021-11-20 22:45:32,559 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 24 to 24. [2021-11-20 22:45:32,559 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 24 states, 15 states have (on average 1.1333333333333333) internal successors, (17), 17 states have internal predecessors, (17), 4 states have call successors, (4), 1 states have call predecessors, (4), 4 states have return successors, (12), 5 states have call predecessors, (12), 4 states have call successors, (12) [2021-11-20 22:45:32,561 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 33 transitions. [2021-11-20 22:45:32,561 INFO L78 Accepts]: Start accepts. Automaton has 24 states and 33 transitions. Word has length 22 [2021-11-20 22:45:32,561 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-20 22:45:32,562 INFO L470 AbstractCegarLoop]: Abstraction has 24 states and 33 transitions. [2021-11-20 22:45:32,562 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 11 states have (on average 2.909090909090909) internal successors, (32), 12 states have internal predecessors, (32), 7 states have call successors, (7), 1 states have call predecessors, (7), 5 states have return successors, (9), 5 states have call predecessors, (9), 7 states have call successors, (9) [2021-11-20 22:45:32,562 INFO L276 IsEmpty]: Start isEmpty. Operand 24 states and 33 transitions. [2021-11-20 22:45:32,565 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2021-11-20 22:45:32,565 INFO L506 BasicCegarLoop]: Found error trace [2021-11-20 22:45:32,565 INFO L514 BasicCegarLoop]: trace histogram [7, 7, 5, 3, 3, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1] [2021-11-20 22:45:32,603 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_fcaf6f6d-930b-4402-93cd-14a0711eb2d4/bin/utaipan-TEXQjIfE4P/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2021-11-20 22:45:32,790 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_fcaf6f6d-930b-4402-93cd-14a0711eb2d4/bin/utaipan-TEXQjIfE4P/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-20 22:45:32,791 INFO L402 AbstractCegarLoop]: === Iteration 4 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-20 22:45:32,791 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-20 22:45:32,792 INFO L85 PathProgramCache]: Analyzing trace with hash 271867855, now seen corresponding path program 1 times [2021-11-20 22:45:32,792 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-20 22:45:32,797 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [648820009] [2021-11-20 22:45:32,797 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-20 22:45:32,797 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-20 22:45:32,829 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-20 22:45:32,936 INFO L134 CoverageAnalysis]: Checked inductivity of 106 backedges. 11 proven. 48 refuted. 0 times theorem prover too weak. 47 trivial. 0 not checked. [2021-11-20 22:45:32,936 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-20 22:45:32,937 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [648820009] [2021-11-20 22:45:32,937 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [648820009] provided 0 perfect and 1 imperfect interpolant sequences [2021-11-20 22:45:32,937 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [910432449] [2021-11-20 22:45:32,937 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-20 22:45:32,938 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-20 22:45:32,938 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_fcaf6f6d-930b-4402-93cd-14a0711eb2d4/bin/utaipan-TEXQjIfE4P/z3 [2021-11-20 22:45:32,939 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_fcaf6f6d-930b-4402-93cd-14a0711eb2d4/bin/utaipan-TEXQjIfE4P/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-20 22:45:32,959 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_fcaf6f6d-930b-4402-93cd-14a0711eb2d4/bin/utaipan-TEXQjIfE4P/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2021-11-20 22:45:32,989 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-20 22:45:32,990 INFO L263 TraceCheckSpWp]: Trace formula consists of 137 conjuncts, 8 conjunts are in the unsatisfiable core [2021-11-20 22:45:32,993 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-20 22:45:33,109 INFO L134 CoverageAnalysis]: Checked inductivity of 106 backedges. 11 proven. 48 refuted. 0 times theorem prover too weak. 47 trivial. 0 not checked. [2021-11-20 22:45:33,109 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-11-20 22:45:33,522 INFO L134 CoverageAnalysis]: Checked inductivity of 106 backedges. 11 proven. 55 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2021-11-20 22:45:33,524 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [910432449] provided 0 perfect and 2 imperfect interpolant sequences [2021-11-20 22:45:33,530 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [988807011] [2021-11-20 22:45:33,535 INFO L159 IcfgInterpreter]: Started Sifa with 15 locations of interest [2021-11-20 22:45:33,535 INFO L166 IcfgInterpreter]: Building call graph [2021-11-20 22:45:33,536 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:94) 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:67) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getOrConstruct(IpTcStrategyModuleBase.java:100) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getInterpolantComputationStatus(IpTcStrategyModuleBase.java:76) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.AutomatonFreeRefinementEngine.tryExecuteInterpolantGenerator(AutomatonFreeRefinementEngine.java:268) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.AutomatonFreeRefinementEngine.generateProof(AutomatonFreeRefinementEngine.java:150) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.AutomatonFreeRefinementEngine.executeStrategy(AutomatonFreeRefinementEngine.java:140) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.AutomatonFreeRefinementEngine.(AutomatonFreeRefinementEngine.java:88) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.TraceAbstractionRefinementEngine.(TraceAbstractionRefinementEngine.java:76) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.BasicCegarLoop.isCounterexampleFeasible(BasicCegarLoop.java:610) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterate(AbstractCegarLoop.java:413) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.startCegar(AbstractCegarLoop.java:348) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.runCegar(AbstractCegarLoop.java:330) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.CegarLoopUtils.getCegarLoopResult(CegarLoopUtils.java:56) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.executeCegarLoop(TraceAbstractionStarter.java:393) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseProgram(TraceAbstractionStarter.java:303) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseSequentialProgram(TraceAbstractionStarter.java:263) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.runCegarLoops(TraceAbstractionStarter.java:176) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.(TraceAbstractionStarter.java:155) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver.finish(TraceAbstractionObserver.java:123) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runObserver(PluginConnector.java:168) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runTool(PluginConnector.java:151) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.run(PluginConnector.java:128) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.executePluginConnector(ToolchainWalker.java:232) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.processPlugin(ToolchainWalker.java:226) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walkUnprotected(ToolchainWalker.java:142) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walk(ToolchainWalker.java:104) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainManager$Toolchain.processToolchain(ToolchainManager.java:320) 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) [2021-11-20 22:45:33,536 INFO L186 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2021-11-20 22:45:33,537 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 9] total 12 [2021-11-20 22:45:33,537 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [714099418] [2021-11-20 22:45:33,537 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2021-11-20 22:45:33,538 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2021-11-20 22:45:33,538 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-20 22:45:33,538 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2021-11-20 22:45:33,539 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=38, Invalid=94, Unknown=0, NotChecked=0, Total=132 [2021-11-20 22:45:33,539 INFO L87 Difference]: Start difference. First operand 24 states and 33 transitions. Second operand has 12 states, 12 states have (on average 3.0833333333333335) internal successors, (37), 12 states have internal predecessors, (37), 7 states have call successors, (9), 1 states have call predecessors, (9), 5 states have return successors, (11), 6 states have call predecessors, (11), 7 states have call successors, (11) [2021-11-20 22:45:33,662 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-20 22:45:33,663 INFO L93 Difference]: Finished difference Result 43 states and 73 transitions. [2021-11-20 22:45:33,663 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2021-11-20 22:45:33,664 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 3.0833333333333335) internal successors, (37), 12 states have internal predecessors, (37), 7 states have call successors, (9), 1 states have call predecessors, (9), 5 states have return successors, (11), 6 states have call predecessors, (11), 7 states have call successors, (11) Word has length 50 [2021-11-20 22:45:33,665 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-20 22:45:33,672 INFO L225 Difference]: With dead ends: 43 [2021-11-20 22:45:33,672 INFO L226 Difference]: Without dead ends: 37 [2021-11-20 22:45:33,673 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 111 GetRequests, 97 SyntacticMatches, 0 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 20 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=78, Invalid=162, Unknown=0, NotChecked=0, Total=240 [2021-11-20 22:45:33,677 INFO L933 BasicCegarLoop]: 10 mSDtfsCounter, 16 mSDsluCounter, 44 mSDsCounter, 0 mSdLazyCounter, 78 mSolverCounterSat, 21 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 24 SdHoareTripleChecker+Valid, 48 SdHoareTripleChecker+Invalid, 99 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 21 IncrementalHoareTripleChecker+Valid, 78 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2021-11-20 22:45:33,680 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [24 Valid, 48 Invalid, 99 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [21 Valid, 78 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2021-11-20 22:45:33,683 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 37 states. [2021-11-20 22:45:33,698 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 37 to 34. [2021-11-20 22:45:33,701 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 34 states, 21 states have (on average 1.0952380952380953) internal successors, (23), 23 states have internal predecessors, (23), 6 states have call successors, (6), 1 states have call predecessors, (6), 6 states have return successors, (30), 9 states have call predecessors, (30), 6 states have call successors, (30) [2021-11-20 22:45:33,705 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 34 states to 34 states and 59 transitions. [2021-11-20 22:45:33,705 INFO L78 Accepts]: Start accepts. Automaton has 34 states and 59 transitions. Word has length 50 [2021-11-20 22:45:33,706 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-20 22:45:33,707 INFO L470 AbstractCegarLoop]: Abstraction has 34 states and 59 transitions. [2021-11-20 22:45:33,708 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 3.0833333333333335) internal successors, (37), 12 states have internal predecessors, (37), 7 states have call successors, (9), 1 states have call predecessors, (9), 5 states have return successors, (11), 6 states have call predecessors, (11), 7 states have call successors, (11) [2021-11-20 22:45:33,710 INFO L276 IsEmpty]: Start isEmpty. Operand 34 states and 59 transitions. [2021-11-20 22:45:33,719 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 131 [2021-11-20 22:45:33,721 INFO L506 BasicCegarLoop]: Found error trace [2021-11-20 22:45:33,722 INFO L514 BasicCegarLoop]: trace histogram [19, 19, 13, 9, 9, 9, 9, 9, 9, 9, 6, 4, 1, 1, 1, 1, 1, 1] [2021-11-20 22:45:33,761 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_fcaf6f6d-930b-4402-93cd-14a0711eb2d4/bin/utaipan-TEXQjIfE4P/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2021-11-20 22:45:33,938 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_fcaf6f6d-930b-4402-93cd-14a0711eb2d4/bin/utaipan-TEXQjIfE4P/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-20 22:45:33,939 INFO L402 AbstractCegarLoop]: === Iteration 5 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-20 22:45:33,939 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-20 22:45:33,939 INFO L85 PathProgramCache]: Analyzing trace with hash -1035226507, now seen corresponding path program 2 times [2021-11-20 22:45:33,939 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-20 22:45:33,940 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [219442226] [2021-11-20 22:45:33,940 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-20 22:45:33,940 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-20 22:45:34,042 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-20 22:45:34,230 INFO L134 CoverageAnalysis]: Checked inductivity of 906 backedges. 52 proven. 316 refuted. 0 times theorem prover too weak. 538 trivial. 0 not checked. [2021-11-20 22:45:34,230 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-20 22:45:34,231 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [219442226] [2021-11-20 22:45:34,231 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [219442226] provided 0 perfect and 1 imperfect interpolant sequences [2021-11-20 22:45:34,231 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [582251694] [2021-11-20 22:45:34,231 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2021-11-20 22:45:34,231 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-20 22:45:34,232 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_fcaf6f6d-930b-4402-93cd-14a0711eb2d4/bin/utaipan-TEXQjIfE4P/z3 [2021-11-20 22:45:34,232 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_fcaf6f6d-930b-4402-93cd-14a0711eb2d4/bin/utaipan-TEXQjIfE4P/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-20 22:45:34,252 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_fcaf6f6d-930b-4402-93cd-14a0711eb2d4/bin/utaipan-TEXQjIfE4P/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2021-11-20 22:45:34,293 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2021-11-20 22:45:34,293 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-11-20 22:45:34,294 INFO L263 TraceCheckSpWp]: Trace formula consists of 152 conjuncts, 8 conjunts are in the unsatisfiable core [2021-11-20 22:45:34,300 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-20 22:45:34,612 INFO L134 CoverageAnalysis]: Checked inductivity of 906 backedges. 476 proven. 13 refuted. 0 times theorem prover too weak. 417 trivial. 0 not checked. [2021-11-20 22:45:34,612 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-11-20 22:45:35,300 INFO L134 CoverageAnalysis]: Checked inductivity of 906 backedges. 267 proven. 60 refuted. 0 times theorem prover too weak. 579 trivial. 0 not checked. [2021-11-20 22:45:35,301 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [582251694] provided 0 perfect and 2 imperfect interpolant sequences [2021-11-20 22:45:35,301 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1767920042] [2021-11-20 22:45:35,304 INFO L159 IcfgInterpreter]: Started Sifa with 15 locations of interest [2021-11-20 22:45:35,304 INFO L166 IcfgInterpreter]: Building call graph [2021-11-20 22:45:35,304 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:94) 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:67) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getOrConstruct(IpTcStrategyModuleBase.java:100) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getInterpolantComputationStatus(IpTcStrategyModuleBase.java:76) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.AutomatonFreeRefinementEngine.tryExecuteInterpolantGenerator(AutomatonFreeRefinementEngine.java:268) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.AutomatonFreeRefinementEngine.generateProof(AutomatonFreeRefinementEngine.java:150) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.AutomatonFreeRefinementEngine.executeStrategy(AutomatonFreeRefinementEngine.java:140) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.AutomatonFreeRefinementEngine.(AutomatonFreeRefinementEngine.java:88) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.TraceAbstractionRefinementEngine.(TraceAbstractionRefinementEngine.java:76) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.BasicCegarLoop.isCounterexampleFeasible(BasicCegarLoop.java:610) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterate(AbstractCegarLoop.java:413) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.startCegar(AbstractCegarLoop.java:348) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.runCegar(AbstractCegarLoop.java:330) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.CegarLoopUtils.getCegarLoopResult(CegarLoopUtils.java:56) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.executeCegarLoop(TraceAbstractionStarter.java:393) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseProgram(TraceAbstractionStarter.java:303) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseSequentialProgram(TraceAbstractionStarter.java:263) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.runCegarLoops(TraceAbstractionStarter.java:176) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.(TraceAbstractionStarter.java:155) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver.finish(TraceAbstractionObserver.java:123) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runObserver(PluginConnector.java:168) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runTool(PluginConnector.java:151) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.run(PluginConnector.java:128) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.executePluginConnector(ToolchainWalker.java:232) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.processPlugin(ToolchainWalker.java:226) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walkUnprotected(ToolchainWalker.java:142) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walk(ToolchainWalker.java:104) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainManager$Toolchain.processToolchain(ToolchainManager.java:320) 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) [2021-11-20 22:45:35,305 INFO L186 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2021-11-20 22:45:35,306 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 8, 9] total 17 [2021-11-20 22:45:35,306 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [556637132] [2021-11-20 22:45:35,306 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2021-11-20 22:45:35,307 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2021-11-20 22:45:35,307 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-20 22:45:35,308 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2021-11-20 22:45:35,308 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=55, Invalid=217, Unknown=0, NotChecked=0, Total=272 [2021-11-20 22:45:35,309 INFO L87 Difference]: Start difference. First operand 34 states and 59 transitions. Second operand has 17 states, 17 states have (on average 3.411764705882353) internal successors, (58), 17 states have internal predecessors, (58), 11 states have call successors, (15), 2 states have call predecessors, (15), 10 states have return successors, (22), 9 states have call predecessors, (22), 11 states have call successors, (22) [2021-11-20 22:45:35,705 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-20 22:45:35,706 INFO L93 Difference]: Finished difference Result 86 states and 173 transitions. [2021-11-20 22:45:35,706 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2021-11-20 22:45:35,706 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 17 states have (on average 3.411764705882353) internal successors, (58), 17 states have internal predecessors, (58), 11 states have call successors, (15), 2 states have call predecessors, (15), 10 states have return successors, (22), 9 states have call predecessors, (22), 11 states have call successors, (22) Word has length 130 [2021-11-20 22:45:35,707 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-20 22:45:35,708 INFO L225 Difference]: With dead ends: 86 [2021-11-20 22:45:35,709 INFO L226 Difference]: Without dead ends: 54 [2021-11-20 22:45:35,711 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 287 GetRequests, 256 SyntacticMatches, 0 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 155 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=279, Invalid=777, Unknown=0, NotChecked=0, Total=1056 [2021-11-20 22:45:35,712 INFO L933 BasicCegarLoop]: 17 mSDtfsCounter, 89 mSDsluCounter, 69 mSDsCounter, 0 mSdLazyCounter, 194 mSolverCounterSat, 119 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 89 SdHoareTripleChecker+Valid, 79 SdHoareTripleChecker+Invalid, 313 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 119 IncrementalHoareTripleChecker+Valid, 194 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2021-11-20 22:45:35,712 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [89 Valid, 79 Invalid, 313 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [119 Valid, 194 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2021-11-20 22:45:35,713 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states. [2021-11-20 22:45:35,727 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 54. [2021-11-20 22:45:35,732 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 54 states, 37 states have (on average 1.1081081081081081) internal successors, (41), 36 states have internal predecessors, (41), 9 states have call successors, (9), 6 states have call predecessors, (9), 7 states have return successors, (23), 11 states have call predecessors, (23), 9 states have call successors, (23) [2021-11-20 22:45:35,734 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 73 transitions. [2021-11-20 22:45:35,735 INFO L78 Accepts]: Start accepts. Automaton has 54 states and 73 transitions. Word has length 130 [2021-11-20 22:45:35,736 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-20 22:45:35,738 INFO L470 AbstractCegarLoop]: Abstraction has 54 states and 73 transitions. [2021-11-20 22:45:35,738 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 17 states have (on average 3.411764705882353) internal successors, (58), 17 states have internal predecessors, (58), 11 states have call successors, (15), 2 states have call predecessors, (15), 10 states have return successors, (22), 9 states have call predecessors, (22), 11 states have call successors, (22) [2021-11-20 22:45:35,738 INFO L276 IsEmpty]: Start isEmpty. Operand 54 states and 73 transitions. [2021-11-20 22:45:35,747 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 174 [2021-11-20 22:45:35,754 INFO L506 BasicCegarLoop]: Found error trace [2021-11-20 22:45:35,754 INFO L514 BasicCegarLoop]: trace histogram [25, 25, 20, 12, 12, 12, 12, 12, 12, 12, 8, 5, 1, 1, 1, 1, 1, 1] [2021-11-20 22:45:35,791 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_fcaf6f6d-930b-4402-93cd-14a0711eb2d4/bin/utaipan-TEXQjIfE4P/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2021-11-20 22:45:35,970 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_fcaf6f6d-930b-4402-93cd-14a0711eb2d4/bin/utaipan-TEXQjIfE4P/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-20 22:45:35,971 INFO L402 AbstractCegarLoop]: === Iteration 6 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-20 22:45:35,971 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-20 22:45:35,971 INFO L85 PathProgramCache]: Analyzing trace with hash -454540380, now seen corresponding path program 3 times [2021-11-20 22:45:35,971 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-20 22:45:35,971 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1206499473] [2021-11-20 22:45:35,971 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-20 22:45:35,972 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-20 22:45:36,048 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-20 22:45:36,165 INFO L134 CoverageAnalysis]: Checked inductivity of 1654 backedges. 93 proven. 533 refuted. 0 times theorem prover too weak. 1028 trivial. 0 not checked. [2021-11-20 22:45:36,166 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-20 22:45:36,166 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1206499473] [2021-11-20 22:45:36,166 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1206499473] provided 0 perfect and 1 imperfect interpolant sequences [2021-11-20 22:45:36,166 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1980574634] [2021-11-20 22:45:36,166 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2021-11-20 22:45:36,166 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-20 22:45:36,166 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_fcaf6f6d-930b-4402-93cd-14a0711eb2d4/bin/utaipan-TEXQjIfE4P/z3 [2021-11-20 22:45:36,167 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_fcaf6f6d-930b-4402-93cd-14a0711eb2d4/bin/utaipan-TEXQjIfE4P/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-20 22:45:36,168 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_fcaf6f6d-930b-4402-93cd-14a0711eb2d4/bin/utaipan-TEXQjIfE4P/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2021-11-20 22:45:36,249 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2021-11-20 22:45:36,249 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-11-20 22:45:36,251 INFO L263 TraceCheckSpWp]: Trace formula consists of 410 conjuncts, 14 conjunts are in the unsatisfiable core [2021-11-20 22:45:36,256 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-20 22:45:36,550 INFO L134 CoverageAnalysis]: Checked inductivity of 1654 backedges. 93 proven. 533 refuted. 0 times theorem prover too weak. 1028 trivial. 0 not checked. [2021-11-20 22:45:36,550 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-11-20 22:45:37,983 INFO L134 CoverageAnalysis]: Checked inductivity of 1654 backedges. 93 proven. 573 refuted. 0 times theorem prover too weak. 988 trivial. 0 not checked. [2021-11-20 22:45:37,983 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1980574634] provided 0 perfect and 2 imperfect interpolant sequences [2021-11-20 22:45:37,983 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [168928434] [2021-11-20 22:45:37,986 INFO L159 IcfgInterpreter]: Started Sifa with 15 locations of interest [2021-11-20 22:45:37,986 INFO L166 IcfgInterpreter]: Building call graph [2021-11-20 22:45:37,987 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:94) 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:67) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getOrConstruct(IpTcStrategyModuleBase.java:100) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getInterpolantComputationStatus(IpTcStrategyModuleBase.java:76) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.AutomatonFreeRefinementEngine.tryExecuteInterpolantGenerator(AutomatonFreeRefinementEngine.java:268) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.AutomatonFreeRefinementEngine.generateProof(AutomatonFreeRefinementEngine.java:150) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.AutomatonFreeRefinementEngine.executeStrategy(AutomatonFreeRefinementEngine.java:140) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.AutomatonFreeRefinementEngine.(AutomatonFreeRefinementEngine.java:88) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.TraceAbstractionRefinementEngine.(TraceAbstractionRefinementEngine.java:76) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.BasicCegarLoop.isCounterexampleFeasible(BasicCegarLoop.java:610) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterate(AbstractCegarLoop.java:413) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.startCegar(AbstractCegarLoop.java:348) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.runCegar(AbstractCegarLoop.java:330) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.CegarLoopUtils.getCegarLoopResult(CegarLoopUtils.java:56) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.executeCegarLoop(TraceAbstractionStarter.java:393) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseProgram(TraceAbstractionStarter.java:303) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseSequentialProgram(TraceAbstractionStarter.java:263) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.runCegarLoops(TraceAbstractionStarter.java:176) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.(TraceAbstractionStarter.java:155) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver.finish(TraceAbstractionObserver.java:123) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runObserver(PluginConnector.java:168) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runTool(PluginConnector.java:151) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.run(PluginConnector.java:128) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.executePluginConnector(ToolchainWalker.java:232) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.processPlugin(ToolchainWalker.java:226) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walkUnprotected(ToolchainWalker.java:142) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walk(ToolchainWalker.java:104) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainManager$Toolchain.processToolchain(ToolchainManager.java:320) 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) [2021-11-20 22:45:37,987 INFO L186 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2021-11-20 22:45:37,987 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10, 15] total 18 [2021-11-20 22:45:37,987 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1046109336] [2021-11-20 22:45:37,987 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2021-11-20 22:45:37,988 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2021-11-20 22:45:37,989 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-20 22:45:37,989 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2021-11-20 22:45:37,989 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=83, Invalid=223, Unknown=0, NotChecked=0, Total=306 [2021-11-20 22:45:37,990 INFO L87 Difference]: Start difference. First operand 54 states and 73 transitions. Second operand has 18 states, 18 states have (on average 3.0555555555555554) internal successors, (55), 18 states have internal predecessors, (55), 13 states have call successors, (15), 1 states have call predecessors, (15), 8 states have return successors, (20), 9 states have call predecessors, (20), 13 states have call successors, (20) [2021-11-20 22:45:38,189 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-20 22:45:38,190 INFO L93 Difference]: Finished difference Result 70 states and 108 transitions. [2021-11-20 22:45:38,190 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2021-11-20 22:45:38,190 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 18 states have (on average 3.0555555555555554) internal successors, (55), 18 states have internal predecessors, (55), 13 states have call successors, (15), 1 states have call predecessors, (15), 8 states have return successors, (20), 9 states have call predecessors, (20), 13 states have call successors, (20) Word has length 173 [2021-11-20 22:45:38,192 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-20 22:45:38,193 INFO L225 Difference]: With dead ends: 70 [2021-11-20 22:45:38,194 INFO L226 Difference]: Without dead ends: 64 [2021-11-20 22:45:38,194 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 366 GetRequests, 343 SyntacticMatches, 0 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 68 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=195, Invalid=405, Unknown=0, NotChecked=0, Total=600 [2021-11-20 22:45:38,195 INFO L933 BasicCegarLoop]: 10 mSDtfsCounter, 69 mSDsluCounter, 61 mSDsCounter, 0 mSdLazyCounter, 114 mSolverCounterSat, 96 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 83 SdHoareTripleChecker+Valid, 63 SdHoareTripleChecker+Invalid, 210 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 96 IncrementalHoareTripleChecker+Valid, 114 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2021-11-20 22:45:38,195 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [83 Valid, 63 Invalid, 210 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [96 Valid, 114 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2021-11-20 22:45:38,196 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 64 states. [2021-11-20 22:45:38,206 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 64 to 64. [2021-11-20 22:45:38,207 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 64 states, 43 states have (on average 1.0930232558139534) internal successors, (47), 42 states have internal predecessors, (47), 11 states have call successors, (11), 6 states have call predecessors, (11), 9 states have return successors, (43), 15 states have call predecessors, (43), 11 states have call successors, (43) [2021-11-20 22:45:38,209 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 64 states to 64 states and 101 transitions. [2021-11-20 22:45:38,209 INFO L78 Accepts]: Start accepts. Automaton has 64 states and 101 transitions. Word has length 173 [2021-11-20 22:45:38,210 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-20 22:45:38,210 INFO L470 AbstractCegarLoop]: Abstraction has 64 states and 101 transitions. [2021-11-20 22:45:38,210 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 18 states, 18 states have (on average 3.0555555555555554) internal successors, (55), 18 states have internal predecessors, (55), 13 states have call successors, (15), 1 states have call predecessors, (15), 8 states have return successors, (20), 9 states have call predecessors, (20), 13 states have call successors, (20) [2021-11-20 22:45:38,210 INFO L276 IsEmpty]: Start isEmpty. Operand 64 states and 101 transitions. [2021-11-20 22:45:38,225 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 583 [2021-11-20 22:45:38,225 INFO L506 BasicCegarLoop]: Found error trace [2021-11-20 22:45:38,226 INFO L514 BasicCegarLoop]: trace histogram [85, 85, 69, 42, 42, 42, 42, 42, 42, 42, 27, 16, 1, 1, 1, 1, 1, 1] [2021-11-20 22:45:38,262 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_fcaf6f6d-930b-4402-93cd-14a0711eb2d4/bin/utaipan-TEXQjIfE4P/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2021-11-20 22:45:38,450 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_fcaf6f6d-930b-4402-93cd-14a0711eb2d4/bin/utaipan-TEXQjIfE4P/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-20 22:45:38,450 INFO L402 AbstractCegarLoop]: === Iteration 7 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-20 22:45:38,451 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-20 22:45:38,451 INFO L85 PathProgramCache]: Analyzing trace with hash 268512456, now seen corresponding path program 4 times [2021-11-20 22:45:38,451 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-20 22:45:38,451 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [33374461] [2021-11-20 22:45:38,451 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-20 22:45:38,452 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-20 22:45:38,620 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-20 22:45:38,958 INFO L134 CoverageAnalysis]: Checked inductivity of 20070 backedges. 1155 proven. 3628 refuted. 0 times theorem prover too weak. 15287 trivial. 0 not checked. [2021-11-20 22:45:38,959 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-20 22:45:38,959 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [33374461] [2021-11-20 22:45:38,959 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [33374461] provided 0 perfect and 1 imperfect interpolant sequences [2021-11-20 22:45:38,959 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [951142064] [2021-11-20 22:45:38,959 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2021-11-20 22:45:38,959 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-20 22:45:38,959 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_fcaf6f6d-930b-4402-93cd-14a0711eb2d4/bin/utaipan-TEXQjIfE4P/z3 [2021-11-20 22:45:38,960 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_fcaf6f6d-930b-4402-93cd-14a0711eb2d4/bin/utaipan-TEXQjIfE4P/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-20 22:45:38,981 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_fcaf6f6d-930b-4402-93cd-14a0711eb2d4/bin/utaipan-TEXQjIfE4P/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2021-11-20 22:45:39,187 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-20 22:45:39,192 INFO L263 TraceCheckSpWp]: Trace formula consists of 1318 conjuncts, 26 conjunts are in the unsatisfiable core [2021-11-20 22:45:39,209 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-20 22:45:40,168 INFO L134 CoverageAnalysis]: Checked inductivity of 20070 backedges. 9532 proven. 2375 refuted. 0 times theorem prover too weak. 8163 trivial. 0 not checked. [2021-11-20 22:45:40,169 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-11-20 22:45:44,897 INFO L134 CoverageAnalysis]: Checked inductivity of 20070 backedges. 1322 proven. 4180 refuted. 0 times theorem prover too weak. 14568 trivial. 0 not checked. [2021-11-20 22:45:44,897 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [951142064] provided 0 perfect and 2 imperfect interpolant sequences [2021-11-20 22:45:44,898 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1527409272] [2021-11-20 22:45:44,900 INFO L159 IcfgInterpreter]: Started Sifa with 15 locations of interest [2021-11-20 22:45:44,901 INFO L166 IcfgInterpreter]: Building call graph [2021-11-20 22:45:44,901 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:94) 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:67) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getOrConstruct(IpTcStrategyModuleBase.java:100) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getInterpolantComputationStatus(IpTcStrategyModuleBase.java:76) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.AutomatonFreeRefinementEngine.tryExecuteInterpolantGenerator(AutomatonFreeRefinementEngine.java:268) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.AutomatonFreeRefinementEngine.generateProof(AutomatonFreeRefinementEngine.java:150) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.AutomatonFreeRefinementEngine.executeStrategy(AutomatonFreeRefinementEngine.java:140) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.AutomatonFreeRefinementEngine.(AutomatonFreeRefinementEngine.java:88) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.TraceAbstractionRefinementEngine.(TraceAbstractionRefinementEngine.java:76) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.BasicCegarLoop.isCounterexampleFeasible(BasicCegarLoop.java:610) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterate(AbstractCegarLoop.java:413) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.startCegar(AbstractCegarLoop.java:348) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.runCegar(AbstractCegarLoop.java:330) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.CegarLoopUtils.getCegarLoopResult(CegarLoopUtils.java:56) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.executeCegarLoop(TraceAbstractionStarter.java:393) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseProgram(TraceAbstractionStarter.java:303) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseSequentialProgram(TraceAbstractionStarter.java:263) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.runCegarLoops(TraceAbstractionStarter.java:176) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.(TraceAbstractionStarter.java:155) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver.finish(TraceAbstractionObserver.java:123) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runObserver(PluginConnector.java:168) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runTool(PluginConnector.java:151) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.run(PluginConnector.java:128) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.executePluginConnector(ToolchainWalker.java:232) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.processPlugin(ToolchainWalker.java:226) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walkUnprotected(ToolchainWalker.java:142) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walk(ToolchainWalker.java:104) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainManager$Toolchain.processToolchain(ToolchainManager.java:320) 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) [2021-11-20 22:45:44,902 INFO L186 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2021-11-20 22:45:44,903 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 17, 27] total 32 [2021-11-20 22:45:44,903 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [686938069] [2021-11-20 22:45:44,903 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2021-11-20 22:45:44,905 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 32 states [2021-11-20 22:45:44,905 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-20 22:45:44,906 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 32 interpolants. [2021-11-20 22:45:44,906 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=169, Invalid=823, Unknown=0, NotChecked=0, Total=992 [2021-11-20 22:45:44,907 INFO L87 Difference]: Start difference. First operand 64 states and 101 transitions. Second operand has 32 states, 32 states have (on average 3.1875) internal successors, (102), 32 states have internal predecessors, (102), 26 states have call successors, (32), 2 states have call predecessors, (32), 14 states have return successors, (43), 15 states have call predecessors, (43), 26 states have call successors, (43) [2021-11-20 22:45:45,778 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-20 22:45:45,779 INFO L93 Difference]: Finished difference Result 165 states and 343 transitions. [2021-11-20 22:45:45,779 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 33 states. [2021-11-20 22:45:45,779 INFO L78 Accepts]: Start accepts. Automaton has has 32 states, 32 states have (on average 3.1875) internal successors, (102), 32 states have internal predecessors, (102), 26 states have call successors, (32), 2 states have call predecessors, (32), 14 states have return successors, (43), 15 states have call predecessors, (43), 26 states have call successors, (43) Word has length 582 [2021-11-20 22:45:45,781 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-20 22:45:45,783 INFO L225 Difference]: With dead ends: 165 [2021-11-20 22:45:45,783 INFO L226 Difference]: Without dead ends: 105 [2021-11-20 22:45:45,791 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 1213 GetRequests, 1155 SyntacticMatches, 2 SemanticMatches, 56 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 678 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=824, Invalid=2482, Unknown=0, NotChecked=0, Total=3306 [2021-11-20 22:45:45,792 INFO L933 BasicCegarLoop]: 31 mSDtfsCounter, 315 mSDsluCounter, 133 mSDsCounter, 0 mSdLazyCounter, 461 mSolverCounterSat, 512 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 315 SdHoareTripleChecker+Valid, 149 SdHoareTripleChecker+Invalid, 973 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 512 IncrementalHoareTripleChecker+Valid, 461 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2021-11-20 22:45:45,792 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [315 Valid, 149 Invalid, 973 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [512 Valid, 461 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2021-11-20 22:45:45,793 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 105 states. [2021-11-20 22:45:45,811 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 105 to 94. [2021-11-20 22:45:45,811 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 94 states, 67 states have (on average 1.044776119402985) internal successors, (70), 64 states have internal predecessors, (70), 17 states have call successors, (17), 14 states have call predecessors, (17), 9 states have return successors, (43), 15 states have call predecessors, (43), 17 states have call successors, (43) [2021-11-20 22:45:45,813 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 94 states to 94 states and 130 transitions. [2021-11-20 22:45:45,813 INFO L78 Accepts]: Start accepts. Automaton has 94 states and 130 transitions. Word has length 582 [2021-11-20 22:45:45,817 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-20 22:45:45,817 INFO L470 AbstractCegarLoop]: Abstraction has 94 states and 130 transitions. [2021-11-20 22:45:45,818 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 32 states, 32 states have (on average 3.1875) internal successors, (102), 32 states have internal predecessors, (102), 26 states have call successors, (32), 2 states have call predecessors, (32), 14 states have return successors, (43), 15 states have call predecessors, (43), 26 states have call successors, (43) [2021-11-20 22:45:45,818 INFO L276 IsEmpty]: Start isEmpty. Operand 94 states and 130 transitions. [2021-11-20 22:45:45,839 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 664 [2021-11-20 22:45:45,839 INFO L506 BasicCegarLoop]: Found error trace [2021-11-20 22:45:45,839 INFO L514 BasicCegarLoop]: trace histogram [97, 97, 78, 48, 48, 48, 48, 48, 48, 48, 30, 19, 1, 1, 1, 1, 1, 1] [2021-11-20 22:45:45,881 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_fcaf6f6d-930b-4402-93cd-14a0711eb2d4/bin/utaipan-TEXQjIfE4P/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2021-11-20 22:45:46,066 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_fcaf6f6d-930b-4402-93cd-14a0711eb2d4/bin/utaipan-TEXQjIfE4P/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable6 [2021-11-20 22:45:46,067 INFO L402 AbstractCegarLoop]: === Iteration 8 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-20 22:45:46,067 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-20 22:45:46,067 INFO L85 PathProgramCache]: Analyzing trace with hash -1312747780, now seen corresponding path program 5 times [2021-11-20 22:45:46,067 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-20 22:45:46,067 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1977437527] [2021-11-20 22:45:46,067 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-20 22:45:46,068 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-20 22:45:46,202 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-20 22:45:46,564 INFO L134 CoverageAnalysis]: Checked inductivity of 26139 backedges. 2015 proven. 4150 refuted. 0 times theorem prover too weak. 19974 trivial. 0 not checked. [2021-11-20 22:45:46,564 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-20 22:45:46,564 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1977437527] [2021-11-20 22:45:46,564 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1977437527] provided 0 perfect and 1 imperfect interpolant sequences [2021-11-20 22:45:46,565 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [580882923] [2021-11-20 22:45:46,565 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2021-11-20 22:45:46,565 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-20 22:45:46,565 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_fcaf6f6d-930b-4402-93cd-14a0711eb2d4/bin/utaipan-TEXQjIfE4P/z3 [2021-11-20 22:45:46,570 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_fcaf6f6d-930b-4402-93cd-14a0711eb2d4/bin/utaipan-TEXQjIfE4P/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-20 22:45:46,590 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_fcaf6f6d-930b-4402-93cd-14a0711eb2d4/bin/utaipan-TEXQjIfE4P/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2021-11-20 22:45:46,886 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 53 check-sat command(s) [2021-11-20 22:45:46,886 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-11-20 22:45:46,890 INFO L263 TraceCheckSpWp]: Trace formula consists of 1007 conjuncts, 16 conjunts are in the unsatisfiable core [2021-11-20 22:45:46,900 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-20 22:45:47,958 INFO L134 CoverageAnalysis]: Checked inductivity of 26139 backedges. 3458 proven. 339 refuted. 0 times theorem prover too weak. 22342 trivial. 0 not checked. [2021-11-20 22:45:47,958 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-11-20 22:45:50,812 INFO L134 CoverageAnalysis]: Checked inductivity of 26139 backedges. 3458 proven. 360 refuted. 0 times theorem prover too weak. 22321 trivial. 0 not checked. [2021-11-20 22:45:50,812 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [580882923] provided 0 perfect and 2 imperfect interpolant sequences [2021-11-20 22:45:50,812 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [627031272] [2021-11-20 22:45:50,816 INFO L159 IcfgInterpreter]: Started Sifa with 15 locations of interest [2021-11-20 22:45:50,816 INFO L166 IcfgInterpreter]: Building call graph [2021-11-20 22:45:50,816 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:94) 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:67) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getOrConstruct(IpTcStrategyModuleBase.java:100) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getInterpolantComputationStatus(IpTcStrategyModuleBase.java:76) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.AutomatonFreeRefinementEngine.tryExecuteInterpolantGenerator(AutomatonFreeRefinementEngine.java:268) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.AutomatonFreeRefinementEngine.generateProof(AutomatonFreeRefinementEngine.java:150) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.AutomatonFreeRefinementEngine.executeStrategy(AutomatonFreeRefinementEngine.java:140) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.AutomatonFreeRefinementEngine.(AutomatonFreeRefinementEngine.java:88) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.TraceAbstractionRefinementEngine.(TraceAbstractionRefinementEngine.java:76) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.BasicCegarLoop.isCounterexampleFeasible(BasicCegarLoop.java:610) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterate(AbstractCegarLoop.java:413) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.startCegar(AbstractCegarLoop.java:348) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.runCegar(AbstractCegarLoop.java:330) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.CegarLoopUtils.getCegarLoopResult(CegarLoopUtils.java:56) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.executeCegarLoop(TraceAbstractionStarter.java:393) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseProgram(TraceAbstractionStarter.java:303) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseSequentialProgram(TraceAbstractionStarter.java:263) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.runCegarLoops(TraceAbstractionStarter.java:176) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.(TraceAbstractionStarter.java:155) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver.finish(TraceAbstractionObserver.java:123) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runObserver(PluginConnector.java:168) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runTool(PluginConnector.java:151) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.run(PluginConnector.java:128) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.executePluginConnector(ToolchainWalker.java:232) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.processPlugin(ToolchainWalker.java:226) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walkUnprotected(ToolchainWalker.java:142) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walk(ToolchainWalker.java:104) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainManager$Toolchain.processToolchain(ToolchainManager.java:320) 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) [2021-11-20 22:45:50,817 INFO L186 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2021-11-20 22:45:50,818 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 12, 17] total 30 [2021-11-20 22:45:50,818 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [675063066] [2021-11-20 22:45:50,818 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2021-11-20 22:45:50,821 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 30 states [2021-11-20 22:45:50,821 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-20 22:45:50,823 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 30 interpolants. [2021-11-20 22:45:50,823 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=155, Invalid=715, Unknown=0, NotChecked=0, Total=870 [2021-11-20 22:45:50,824 INFO L87 Difference]: Start difference. First operand 94 states and 130 transitions. Second operand has 30 states, 30 states have (on average 3.0) internal successors, (90), 30 states have internal predecessors, (90), 21 states have call successors, (30), 1 states have call predecessors, (30), 16 states have return successors, (45), 22 states have call predecessors, (45), 21 states have call successors, (45) [2021-11-20 22:45:51,770 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-20 22:45:51,770 INFO L93 Difference]: Finished difference Result 221 states and 355 transitions. [2021-11-20 22:45:51,770 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 41 states. [2021-11-20 22:45:51,771 INFO L78 Accepts]: Start accepts. Automaton has has 30 states, 30 states have (on average 3.0) internal successors, (90), 30 states have internal predecessors, (90), 21 states have call successors, (30), 1 states have call predecessors, (30), 16 states have return successors, (45), 22 states have call predecessors, (45), 21 states have call successors, (45) Word has length 663 [2021-11-20 22:45:51,772 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-20 22:45:51,774 INFO L225 Difference]: With dead ends: 221 [2021-11-20 22:45:51,774 INFO L226 Difference]: Without dead ends: 131 [2021-11-20 22:45:51,776 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 1385 GetRequests, 1322 SyntacticMatches, 3 SemanticMatches, 60 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 864 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=841, Invalid=2941, Unknown=0, NotChecked=0, Total=3782 [2021-11-20 22:45:51,777 INFO L933 BasicCegarLoop]: 31 mSDtfsCounter, 339 mSDsluCounter, 136 mSDsCounter, 0 mSdLazyCounter, 485 mSolverCounterSat, 375 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 339 SdHoareTripleChecker+Valid, 156 SdHoareTripleChecker+Invalid, 860 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 375 IncrementalHoareTripleChecker+Valid, 485 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2021-11-20 22:45:51,777 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [339 Valid, 156 Invalid, 860 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [375 Valid, 485 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2021-11-20 22:45:51,778 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 131 states. [2021-11-20 22:45:51,791 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 131 to 112. [2021-11-20 22:45:51,791 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 112 states, 80 states have (on average 1.05) internal successors, (84), 77 states have internal predecessors, (84), 22 states have call successors, (22), 18 states have call predecessors, (22), 9 states have return successors, (46), 16 states have call predecessors, (46), 22 states have call successors, (46) [2021-11-20 22:45:51,793 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 112 states to 112 states and 152 transitions. [2021-11-20 22:45:51,794 INFO L78 Accepts]: Start accepts. Automaton has 112 states and 152 transitions. Word has length 663 [2021-11-20 22:45:51,795 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-20 22:45:51,795 INFO L470 AbstractCegarLoop]: Abstraction has 112 states and 152 transitions. [2021-11-20 22:45:51,795 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 30 states, 30 states have (on average 3.0) internal successors, (90), 30 states have internal predecessors, (90), 21 states have call successors, (30), 1 states have call predecessors, (30), 16 states have return successors, (45), 22 states have call predecessors, (45), 21 states have call successors, (45) [2021-11-20 22:45:51,795 INFO L276 IsEmpty]: Start isEmpty. Operand 112 states and 152 transitions. [2021-11-20 22:45:51,798 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 460 [2021-11-20 22:45:51,799 INFO L506 BasicCegarLoop]: Found error trace [2021-11-20 22:45:51,799 INFO L514 BasicCegarLoop]: trace histogram [67, 67, 54, 33, 33, 33, 33, 33, 33, 33, 21, 13, 1, 1, 1, 1, 1, 1] [2021-11-20 22:45:51,838 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_fcaf6f6d-930b-4402-93cd-14a0711eb2d4/bin/utaipan-TEXQjIfE4P/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2021-11-20 22:45:52,026 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,7 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_fcaf6f6d-930b-4402-93cd-14a0711eb2d4/bin/utaipan-TEXQjIfE4P/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-20 22:45:52,027 INFO L402 AbstractCegarLoop]: === Iteration 9 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-20 22:45:52,027 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-20 22:45:52,027 INFO L85 PathProgramCache]: Analyzing trace with hash 2068824531, now seen corresponding path program 6 times [2021-11-20 22:45:52,027 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-20 22:45:52,027 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1715736426] [2021-11-20 22:45:52,027 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-20 22:45:52,027 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-20 22:45:52,123 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-11-20 22:45:52,124 INFO L355 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2021-11-20 22:45:52,215 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-11-20 22:45:52,316 INFO L133 FreeRefinementEngine]: Strategy SIFA_TAIPAN found a feasible trace [2021-11-20 22:45:52,316 INFO L628 BasicCegarLoop]: Counterexample is feasible [2021-11-20 22:45:52,317 INFO L764 garLoopResultBuilder]: Registering result UNSAFE for location ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2021-11-20 22:45:52,318 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8 [2021-11-20 22:45:52,322 INFO L732 BasicCegarLoop]: Path program histogram: [6, 1, 1, 1] [2021-11-20 22:45:52,327 INFO L179 ceAbstractionStarter]: Computing trace abstraction results [2021-11-20 22:45:52,491 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 20.11 10:45:52 BoogieIcfgContainer [2021-11-20 22:45:52,491 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2021-11-20 22:45:52,492 INFO L113 PluginConnector]: ------------------------Witness Printer---------------------------- [2021-11-20 22:45:52,492 INFO L271 PluginConnector]: Initializing Witness Printer... [2021-11-20 22:45:52,492 INFO L275 PluginConnector]: Witness Printer initialized [2021-11-20 22:45:52,492 INFO L185 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.11 10:45:31" (3/4) ... [2021-11-20 22:45:52,494 INFO L131 WitnessPrinter]: Generating witness for reachability counterexample [2021-11-20 22:45:52,577 INFO L141 WitnessManager]: Wrote witness to /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_fcaf6f6d-930b-4402-93cd-14a0711eb2d4/bin/utaipan-TEXQjIfE4P/witness.graphml [2021-11-20 22:45:52,577 INFO L132 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2021-11-20 22:45:52,578 INFO L158 Benchmark]: Toolchain (without parser) took 21946.05ms. Allocated memory was 104.9MB in the beginning and 195.0MB in the end (delta: 90.2MB). Free memory was 72.6MB in the beginning and 137.4MB in the end (delta: -64.8MB). Peak memory consumption was 25.8MB. Max. memory is 16.1GB. [2021-11-20 22:45:52,579 INFO L158 Benchmark]: CDTParser took 0.21ms. Allocated memory is still 104.9MB. Free memory was 57.0MB in the beginning and 57.0MB in the end (delta: 46.5kB). There was no memory consumed. Max. memory is 16.1GB. [2021-11-20 22:45:52,579 INFO L158 Benchmark]: CACSL2BoogieTranslator took 226.80ms. Allocated memory is still 104.9MB. Free memory was 72.4MB in the beginning and 80.7MB in the end (delta: -8.3MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. [2021-11-20 22:45:52,579 INFO L158 Benchmark]: Boogie Procedure Inliner took 28.71ms. Allocated memory is still 104.9MB. Free memory was 80.3MB in the beginning and 79.2MB in the end (delta: 1.1MB). There was no memory consumed. Max. memory is 16.1GB. [2021-11-20 22:45:52,580 INFO L158 Benchmark]: Boogie Preprocessor took 16.10ms. Allocated memory is still 104.9MB. Free memory was 79.2MB in the beginning and 78.1MB in the end (delta: 1.1MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2021-11-20 22:45:52,580 INFO L158 Benchmark]: RCFGBuilder took 322.87ms. Allocated memory is still 104.9MB. Free memory was 78.1MB in the beginning and 69.3MB in the end (delta: 8.8MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2021-11-20 22:45:52,580 INFO L158 Benchmark]: TraceAbstraction took 21259.31ms. Allocated memory was 104.9MB in the beginning and 195.0MB in the end (delta: 90.2MB). Free memory was 68.6MB in the beginning and 149.0MB in the end (delta: -80.3MB). Peak memory consumption was 110.4MB. Max. memory is 16.1GB. [2021-11-20 22:45:52,581 INFO L158 Benchmark]: Witness Printer took 85.86ms. Allocated memory is still 195.0MB. Free memory was 149.0MB in the beginning and 137.4MB in the end (delta: 11.5MB). Peak memory consumption was 12.6MB. Max. memory is 16.1GB. [2021-11-20 22:45:52,583 INFO L339 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.21ms. Allocated memory is still 104.9MB. Free memory was 57.0MB in the beginning and 57.0MB in the end (delta: 46.5kB). There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 226.80ms. Allocated memory is still 104.9MB. Free memory was 72.4MB in the beginning and 80.7MB in the end (delta: -8.3MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 28.71ms. Allocated memory is still 104.9MB. Free memory was 80.3MB in the beginning and 79.2MB in the end (delta: 1.1MB). There was no memory consumed. Max. memory is 16.1GB. * Boogie Preprocessor took 16.10ms. Allocated memory is still 104.9MB. Free memory was 79.2MB in the beginning and 78.1MB in the end (delta: 1.1MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * RCFGBuilder took 322.87ms. Allocated memory is still 104.9MB. Free memory was 78.1MB in the beginning and 69.3MB in the end (delta: 8.8MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * TraceAbstraction took 21259.31ms. Allocated memory was 104.9MB in the beginning and 195.0MB in the end (delta: 90.2MB). Free memory was 68.6MB in the beginning and 149.0MB in the end (delta: -80.3MB). Peak memory consumption was 110.4MB. Max. memory is 16.1GB. * Witness Printer took 85.86ms. Allocated memory is still 195.0MB. Free memory was 149.0MB in the beginning and 137.4MB in the end (delta: 11.5MB). Peak memory consumption was 12.6MB. Max. memory is 16.1GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: ErrorAutomatonStatistics NumberErrorTraces: 0, NumberStatementsAllTraces: 0, NumberRelevantStatements: 0, 0.0s ErrorAutomatonConstructionTimeTotal, 0.0s FaulLocalizationTime, NumberStatementsFirstTrace: -1, TraceLengthAvg: 0, 0.0s ErrorAutomatonConstructionTimeAvg, 0.0s ErrorAutomatonDifferenceTimeAvg, 0.0s ErrorAutomatonDifferenceTimeTotal, NumberOfNoEnhancement: 0, NumberOfFiniteEnhancement: 0, NumberOfInfiniteEnhancement: 0 - CounterExampleResult [Line: 33]: a call to reach_error is reachable a call to reach_error is reachable We found a FailurePath: [L28] int x = __VERIFIER_nondet_int(); [L29] CALL, EXPR fibonacci(x) VAL [\old(n)=8] [L17] COND FALSE !(n < 1) VAL [\old(n)=8, n=8] [L19] COND FALSE !(n == 1) VAL [\old(n)=8, n=8] [L22] CALL, EXPR fibonacci(n-1) VAL [\old(n)=7] [L17] COND FALSE !(n < 1) VAL [\old(n)=7, n=7] [L19] COND FALSE !(n == 1) VAL [\old(n)=7, n=7] [L22] CALL, EXPR fibonacci(n-1) VAL [\old(n)=6] [L17] COND FALSE !(n < 1) VAL [\old(n)=6, n=6] [L19] COND FALSE !(n == 1) VAL [\old(n)=6, n=6] [L22] CALL, EXPR fibonacci(n-1) VAL [\old(n)=5] [L17] COND FALSE !(n < 1) VAL [\old(n)=5, n=5] [L19] COND FALSE !(n == 1) VAL [\old(n)=5, n=5] [L22] CALL, EXPR fibonacci(n-1) VAL [\old(n)=4] [L17] COND FALSE !(n < 1) VAL [\old(n)=4, n=4] [L19] COND FALSE !(n == 1) VAL [\old(n)=4, n=4] [L22] CALL, EXPR fibonacci(n-1) VAL [\old(n)=3] [L17] COND FALSE !(n < 1) VAL [\old(n)=3, n=3] [L19] COND FALSE !(n == 1) VAL [\old(n)=3, n=3] [L22] CALL, EXPR fibonacci(n-1) VAL [\old(n)=2] [L17] COND FALSE !(n < 1) VAL [\old(n)=2, n=2] [L19] COND FALSE !(n == 1) VAL [\old(n)=2, n=2] [L22] CALL, EXPR fibonacci(n-1) VAL [\old(n)=1] [L17] COND FALSE !(n < 1) VAL [\old(n)=1, n=1] [L19] COND TRUE n == 1 [L20] return 1; VAL [\old(n)=1, \result=1, n=1] [L22] RET, EXPR fibonacci(n-1) VAL [\old(n)=2, fibonacci(n-1)=1, n=2] [L22] CALL, EXPR fibonacci(n-2) VAL [\old(n)=0] [L17] COND TRUE n < 1 [L18] return 0; VAL [\old(n)=0, \result=0, n=0] [L22] RET, EXPR fibonacci(n-2) VAL [\old(n)=2, fibonacci(n-1)=1, fibonacci(n-2)=0, n=2] [L22] return fibonacci(n-1) + fibonacci(n-2); [L22] RET, EXPR fibonacci(n-1) VAL [\old(n)=3, fibonacci(n-1)=1, n=3] [L22] CALL, EXPR fibonacci(n-2) VAL [\old(n)=1] [L17] COND FALSE !(n < 1) VAL [\old(n)=1, n=1] [L19] COND TRUE n == 1 [L20] return 1; VAL [\old(n)=1, \result=1, n=1] [L22] RET, EXPR fibonacci(n-2) VAL [\old(n)=3, fibonacci(n-1)=1, fibonacci(n-2)=1, n=3] [L22] return fibonacci(n-1) + fibonacci(n-2); [L22] RET, EXPR fibonacci(n-1) VAL [\old(n)=4, fibonacci(n-1)=2, n=4] [L22] CALL, EXPR fibonacci(n-2) VAL [\old(n)=2] [L17] COND FALSE !(n < 1) VAL [\old(n)=2, n=2] [L19] COND FALSE !(n == 1) VAL [\old(n)=2, n=2] [L22] CALL, EXPR fibonacci(n-1) VAL [\old(n)=1] [L17] COND FALSE !(n < 1) VAL [\old(n)=1, n=1] [L19] COND TRUE n == 1 [L20] return 1; VAL [\old(n)=1, \result=1, n=1] [L22] RET, EXPR fibonacci(n-1) VAL [\old(n)=2, fibonacci(n-1)=1, n=2] [L22] CALL, EXPR fibonacci(n-2) VAL [\old(n)=0] [L17] COND TRUE n < 1 [L18] return 0; VAL [\old(n)=0, \result=0, n=0] [L22] RET, EXPR fibonacci(n-2) VAL [\old(n)=2, fibonacci(n-1)=1, fibonacci(n-2)=0, n=2] [L22] return fibonacci(n-1) + fibonacci(n-2); [L22] RET, EXPR fibonacci(n-2) VAL [\old(n)=4, fibonacci(n-1)=2, fibonacci(n-2)=1, n=4] [L22] return fibonacci(n-1) + fibonacci(n-2); [L22] RET, EXPR fibonacci(n-1) VAL [\old(n)=5, fibonacci(n-1)=3, n=5] [L22] CALL, EXPR fibonacci(n-2) VAL [\old(n)=3] [L17] COND FALSE !(n < 1) VAL [\old(n)=3, n=3] [L19] COND FALSE !(n == 1) VAL [\old(n)=3, n=3] [L22] CALL, EXPR fibonacci(n-1) VAL [\old(n)=2] [L17] COND FALSE !(n < 1) VAL [\old(n)=2, n=2] [L19] COND FALSE !(n == 1) VAL [\old(n)=2, n=2] [L22] CALL, EXPR fibonacci(n-1) VAL [\old(n)=1] [L17] COND FALSE !(n < 1) VAL [\old(n)=1, n=1] [L19] COND TRUE n == 1 [L20] return 1; VAL [\old(n)=1, \result=1, n=1] [L22] RET, EXPR fibonacci(n-1) VAL [\old(n)=2, fibonacci(n-1)=1, n=2] [L22] CALL, EXPR fibonacci(n-2) VAL [\old(n)=0] [L17] COND TRUE n < 1 [L18] return 0; VAL [\old(n)=0, \result=0, n=0] [L22] RET, EXPR fibonacci(n-2) VAL [\old(n)=2, fibonacci(n-1)=1, fibonacci(n-2)=0, n=2] [L22] return fibonacci(n-1) + fibonacci(n-2); [L22] RET, EXPR fibonacci(n-1) VAL [\old(n)=3, fibonacci(n-1)=1, n=3] [L22] CALL, EXPR fibonacci(n-2) VAL [\old(n)=1] [L17] COND FALSE !(n < 1) VAL [\old(n)=1, n=1] [L19] COND TRUE n == 1 [L20] return 1; VAL [\old(n)=1, \result=1, n=1] [L22] RET, EXPR fibonacci(n-2) VAL [\old(n)=3, fibonacci(n-1)=1, fibonacci(n-2)=1, n=3] [L22] return fibonacci(n-1) + fibonacci(n-2); [L22] RET, EXPR fibonacci(n-2) VAL [\old(n)=5, fibonacci(n-1)=3, fibonacci(n-2)=2, n=5] [L22] return fibonacci(n-1) + fibonacci(n-2); [L22] RET, EXPR fibonacci(n-1) VAL [\old(n)=6, fibonacci(n-1)=5, n=6] [L22] CALL, EXPR fibonacci(n-2) VAL [\old(n)=4] [L17] COND FALSE !(n < 1) VAL [\old(n)=4, n=4] [L19] COND FALSE !(n == 1) VAL [\old(n)=4, n=4] [L22] CALL, EXPR fibonacci(n-1) VAL [\old(n)=3] [L17] COND FALSE !(n < 1) VAL [\old(n)=3, n=3] [L19] COND FALSE !(n == 1) VAL [\old(n)=3, n=3] [L22] CALL, EXPR fibonacci(n-1) VAL [\old(n)=2] [L17] COND FALSE !(n < 1) VAL [\old(n)=2, n=2] [L19] COND FALSE !(n == 1) VAL [\old(n)=2, n=2] [L22] CALL, EXPR fibonacci(n-1) VAL [\old(n)=1] [L17] COND FALSE !(n < 1) VAL [\old(n)=1, n=1] [L19] COND TRUE n == 1 [L20] return 1; VAL [\old(n)=1, \result=1, n=1] [L22] RET, EXPR fibonacci(n-1) VAL [\old(n)=2, fibonacci(n-1)=1, n=2] [L22] CALL, EXPR fibonacci(n-2) VAL [\old(n)=0] [L17] COND TRUE n < 1 [L18] return 0; VAL [\old(n)=0, \result=0, n=0] [L22] RET, EXPR fibonacci(n-2) VAL [\old(n)=2, fibonacci(n-1)=1, fibonacci(n-2)=0, n=2] [L22] return fibonacci(n-1) + fibonacci(n-2); [L22] RET, EXPR fibonacci(n-1) VAL [\old(n)=3, fibonacci(n-1)=1, n=3] [L22] CALL, EXPR fibonacci(n-2) VAL [\old(n)=1] [L17] COND FALSE !(n < 1) VAL [\old(n)=1, n=1] [L19] COND TRUE n == 1 [L20] return 1; VAL [\old(n)=1, \result=1, n=1] [L22] RET, EXPR fibonacci(n-2) VAL [\old(n)=3, fibonacci(n-1)=1, fibonacci(n-2)=1, n=3] [L22] return fibonacci(n-1) + fibonacci(n-2); [L22] RET, EXPR fibonacci(n-1) VAL [\old(n)=4, fibonacci(n-1)=2, n=4] [L22] CALL, EXPR fibonacci(n-2) VAL [\old(n)=2] [L17] COND FALSE !(n < 1) VAL [\old(n)=2, n=2] [L19] COND FALSE !(n == 1) VAL [\old(n)=2, n=2] [L22] CALL, EXPR fibonacci(n-1) VAL [\old(n)=1] [L17] COND FALSE !(n < 1) VAL [\old(n)=1, n=1] [L19] COND TRUE n == 1 [L20] return 1; VAL [\old(n)=1, \result=1, n=1] [L22] RET, EXPR fibonacci(n-1) VAL [\old(n)=2, fibonacci(n-1)=1, n=2] [L22] CALL, EXPR fibonacci(n-2) VAL [\old(n)=0] [L17] COND TRUE n < 1 [L18] return 0; VAL [\old(n)=0, \result=0, n=0] [L22] RET, EXPR fibonacci(n-2) VAL [\old(n)=2, fibonacci(n-1)=1, fibonacci(n-2)=0, n=2] [L22] return fibonacci(n-1) + fibonacci(n-2); [L22] RET, EXPR fibonacci(n-2) VAL [\old(n)=4, fibonacci(n-1)=2, fibonacci(n-2)=1, n=4] [L22] return fibonacci(n-1) + fibonacci(n-2); [L22] RET, EXPR fibonacci(n-2) VAL [\old(n)=6, fibonacci(n-1)=5, fibonacci(n-2)=3, n=6] [L22] return fibonacci(n-1) + fibonacci(n-2); [L22] RET, EXPR fibonacci(n-1) VAL [\old(n)=7, fibonacci(n-1)=8, n=7] [L22] CALL, EXPR fibonacci(n-2) VAL [\old(n)=5] [L17] COND FALSE !(n < 1) VAL [\old(n)=5, n=5] [L19] COND FALSE !(n == 1) VAL [\old(n)=5, n=5] [L22] CALL, EXPR fibonacci(n-1) VAL [\old(n)=4] [L17] COND FALSE !(n < 1) VAL [\old(n)=4, n=4] [L19] COND FALSE !(n == 1) VAL [\old(n)=4, n=4] [L22] CALL, EXPR fibonacci(n-1) VAL [\old(n)=3] [L17] COND FALSE !(n < 1) VAL [\old(n)=3, n=3] [L19] COND FALSE !(n == 1) VAL [\old(n)=3, n=3] [L22] CALL, EXPR fibonacci(n-1) VAL [\old(n)=2] [L17] COND FALSE !(n < 1) VAL [\old(n)=2, n=2] [L19] COND FALSE !(n == 1) VAL [\old(n)=2, n=2] [L22] CALL, EXPR fibonacci(n-1) VAL [\old(n)=1] [L17] COND FALSE !(n < 1) VAL [\old(n)=1, n=1] [L19] COND TRUE n == 1 [L20] return 1; VAL [\old(n)=1, \result=1, n=1] [L22] RET, EXPR fibonacci(n-1) VAL [\old(n)=2, fibonacci(n-1)=1, n=2] [L22] CALL, EXPR fibonacci(n-2) VAL [\old(n)=0] [L17] COND TRUE n < 1 [L18] return 0; VAL [\old(n)=0, \result=0, n=0] [L22] RET, EXPR fibonacci(n-2) VAL [\old(n)=2, fibonacci(n-1)=1, fibonacci(n-2)=0, n=2] [L22] return fibonacci(n-1) + fibonacci(n-2); [L22] RET, EXPR fibonacci(n-1) VAL [\old(n)=3, fibonacci(n-1)=1, n=3] [L22] CALL, EXPR fibonacci(n-2) VAL [\old(n)=1] [L17] COND FALSE !(n < 1) VAL [\old(n)=1, n=1] [L19] COND TRUE n == 1 [L20] return 1; VAL [\old(n)=1, \result=1, n=1] [L22] RET, EXPR fibonacci(n-2) VAL [\old(n)=3, fibonacci(n-1)=1, fibonacci(n-2)=1, n=3] [L22] return fibonacci(n-1) + fibonacci(n-2); [L22] RET, EXPR fibonacci(n-1) VAL [\old(n)=4, fibonacci(n-1)=2, n=4] [L22] CALL, EXPR fibonacci(n-2) VAL [\old(n)=2] [L17] COND FALSE !(n < 1) VAL [\old(n)=2, n=2] [L19] COND FALSE !(n == 1) VAL [\old(n)=2, n=2] [L22] CALL, EXPR fibonacci(n-1) VAL [\old(n)=1] [L17] COND FALSE !(n < 1) VAL [\old(n)=1, n=1] [L19] COND TRUE n == 1 [L20] return 1; VAL [\old(n)=1, \result=1, n=1] [L22] RET, EXPR fibonacci(n-1) VAL [\old(n)=2, fibonacci(n-1)=1, n=2] [L22] CALL, EXPR fibonacci(n-2) VAL [\old(n)=0] [L17] COND TRUE n < 1 [L18] return 0; VAL [\old(n)=0, \result=0, n=0] [L22] RET, EXPR fibonacci(n-2) VAL [\old(n)=2, fibonacci(n-1)=1, fibonacci(n-2)=0, n=2] [L22] return fibonacci(n-1) + fibonacci(n-2); [L22] RET, EXPR fibonacci(n-2) VAL [\old(n)=4, fibonacci(n-1)=2, fibonacci(n-2)=1, n=4] [L22] return fibonacci(n-1) + fibonacci(n-2); [L22] RET, EXPR fibonacci(n-1) VAL [\old(n)=5, fibonacci(n-1)=3, n=5] [L22] CALL, EXPR fibonacci(n-2) VAL [\old(n)=3] [L17] COND FALSE !(n < 1) VAL [\old(n)=3, n=3] [L19] COND FALSE !(n == 1) VAL [\old(n)=3, n=3] [L22] CALL, EXPR fibonacci(n-1) VAL [\old(n)=2] [L17] COND FALSE !(n < 1) VAL [\old(n)=2, n=2] [L19] COND FALSE !(n == 1) VAL [\old(n)=2, n=2] [L22] CALL, EXPR fibonacci(n-1) VAL [\old(n)=1] [L17] COND FALSE !(n < 1) VAL [\old(n)=1, n=1] [L19] COND TRUE n == 1 [L20] return 1; VAL [\old(n)=1, \result=1, n=1] [L22] RET, EXPR fibonacci(n-1) VAL [\old(n)=2, fibonacci(n-1)=1, n=2] [L22] CALL, EXPR fibonacci(n-2) VAL [\old(n)=0] [L17] COND TRUE n < 1 [L18] return 0; VAL [\old(n)=0, \result=0, n=0] [L22] RET, EXPR fibonacci(n-2) VAL [\old(n)=2, fibonacci(n-1)=1, fibonacci(n-2)=0, n=2] [L22] return fibonacci(n-1) + fibonacci(n-2); [L22] RET, EXPR fibonacci(n-1) VAL [\old(n)=3, fibonacci(n-1)=1, n=3] [L22] CALL, EXPR fibonacci(n-2) VAL [\old(n)=1] [L17] COND FALSE !(n < 1) VAL [\old(n)=1, n=1] [L19] COND TRUE n == 1 [L20] return 1; VAL [\old(n)=1, \result=1, n=1] [L22] RET, EXPR fibonacci(n-2) VAL [\old(n)=3, fibonacci(n-1)=1, fibonacci(n-2)=1, n=3] [L22] return fibonacci(n-1) + fibonacci(n-2); [L22] RET, EXPR fibonacci(n-2) VAL [\old(n)=5, fibonacci(n-1)=3, fibonacci(n-2)=2, n=5] [L22] return fibonacci(n-1) + fibonacci(n-2); [L22] RET, EXPR fibonacci(n-2) VAL [\old(n)=7, fibonacci(n-1)=8, fibonacci(n-2)=5, n=7] [L22] return fibonacci(n-1) + fibonacci(n-2); [L22] RET, EXPR fibonacci(n-1) VAL [\old(n)=8, fibonacci(n-1)=13, n=8] [L22] CALL, EXPR fibonacci(n-2) VAL [\old(n)=6] [L17] COND FALSE !(n < 1) VAL [\old(n)=6, n=6] [L19] COND FALSE !(n == 1) VAL [\old(n)=6, n=6] [L22] CALL, EXPR fibonacci(n-1) VAL [\old(n)=5] [L17] COND FALSE !(n < 1) VAL [\old(n)=5, n=5] [L19] COND FALSE !(n == 1) VAL [\old(n)=5, n=5] [L22] CALL, EXPR fibonacci(n-1) VAL [\old(n)=4] [L17] COND FALSE !(n < 1) VAL [\old(n)=4, n=4] [L19] COND FALSE !(n == 1) VAL [\old(n)=4, n=4] [L22] CALL, EXPR fibonacci(n-1) VAL [\old(n)=3] [L17] COND FALSE !(n < 1) VAL [\old(n)=3, n=3] [L19] COND FALSE !(n == 1) VAL [\old(n)=3, n=3] [L22] CALL, EXPR fibonacci(n-1) VAL [\old(n)=2] [L17] COND FALSE !(n < 1) VAL [\old(n)=2, n=2] [L19] COND FALSE !(n == 1) VAL [\old(n)=2, n=2] [L22] CALL, EXPR fibonacci(n-1) VAL [\old(n)=1] [L17] COND FALSE !(n < 1) VAL [\old(n)=1, n=1] [L19] COND TRUE n == 1 [L20] return 1; VAL [\old(n)=1, \result=1, n=1] [L22] RET, EXPR fibonacci(n-1) VAL [\old(n)=2, fibonacci(n-1)=1, n=2] [L22] CALL, EXPR fibonacci(n-2) VAL [\old(n)=0] [L17] COND TRUE n < 1 [L18] return 0; VAL [\old(n)=0, \result=0, n=0] [L22] RET, EXPR fibonacci(n-2) VAL [\old(n)=2, fibonacci(n-1)=1, fibonacci(n-2)=0, n=2] [L22] return fibonacci(n-1) + fibonacci(n-2); [L22] RET, EXPR fibonacci(n-1) VAL [\old(n)=3, fibonacci(n-1)=1, n=3] [L22] CALL, EXPR fibonacci(n-2) VAL [\old(n)=1] [L17] COND FALSE !(n < 1) VAL [\old(n)=1, n=1] [L19] COND TRUE n == 1 [L20] return 1; VAL [\old(n)=1, \result=1, n=1] [L22] RET, EXPR fibonacci(n-2) VAL [\old(n)=3, fibonacci(n-1)=1, fibonacci(n-2)=1, n=3] [L22] return fibonacci(n-1) + fibonacci(n-2); [L22] RET, EXPR fibonacci(n-1) VAL [\old(n)=4, fibonacci(n-1)=2, n=4] [L22] CALL, EXPR fibonacci(n-2) VAL [\old(n)=2] [L17] COND FALSE !(n < 1) VAL [\old(n)=2, n=2] [L19] COND FALSE !(n == 1) VAL [\old(n)=2, n=2] [L22] CALL, EXPR fibonacci(n-1) VAL [\old(n)=1] [L17] COND FALSE !(n < 1) VAL [\old(n)=1, n=1] [L19] COND TRUE n == 1 [L20] return 1; VAL [\old(n)=1, \result=1, n=1] [L22] RET, EXPR fibonacci(n-1) VAL [\old(n)=2, fibonacci(n-1)=1, n=2] [L22] CALL, EXPR fibonacci(n-2) VAL [\old(n)=0] [L17] COND TRUE n < 1 [L18] return 0; VAL [\old(n)=0, \result=0, n=0] [L22] RET, EXPR fibonacci(n-2) VAL [\old(n)=2, fibonacci(n-1)=1, fibonacci(n-2)=0, n=2] [L22] return fibonacci(n-1) + fibonacci(n-2); [L22] RET, EXPR fibonacci(n-2) VAL [\old(n)=4, fibonacci(n-1)=2, fibonacci(n-2)=1, n=4] [L22] return fibonacci(n-1) + fibonacci(n-2); [L22] RET, EXPR fibonacci(n-1) VAL [\old(n)=5, fibonacci(n-1)=3, n=5] [L22] CALL, EXPR fibonacci(n-2) VAL [\old(n)=3] [L17] COND FALSE !(n < 1) VAL [\old(n)=3, n=3] [L19] COND FALSE !(n == 1) VAL [\old(n)=3, n=3] [L22] CALL, EXPR fibonacci(n-1) VAL [\old(n)=2] [L17] COND FALSE !(n < 1) VAL [\old(n)=2, n=2] [L19] COND FALSE !(n == 1) VAL [\old(n)=2, n=2] [L22] CALL, EXPR fibonacci(n-1) VAL [\old(n)=1] [L17] COND FALSE !(n < 1) VAL [\old(n)=1, n=1] [L19] COND TRUE n == 1 [L20] return 1; VAL [\old(n)=1, \result=1, n=1] [L22] RET, EXPR fibonacci(n-1) VAL [\old(n)=2, fibonacci(n-1)=1, n=2] [L22] CALL, EXPR fibonacci(n-2) VAL [\old(n)=0] [L17] COND TRUE n < 1 [L18] return 0; VAL [\old(n)=0, \result=0, n=0] [L22] RET, EXPR fibonacci(n-2) VAL [\old(n)=2, fibonacci(n-1)=1, fibonacci(n-2)=0, n=2] [L22] return fibonacci(n-1) + fibonacci(n-2); [L22] RET, EXPR fibonacci(n-1) VAL [\old(n)=3, fibonacci(n-1)=1, n=3] [L22] CALL, EXPR fibonacci(n-2) VAL [\old(n)=1] [L17] COND FALSE !(n < 1) VAL [\old(n)=1, n=1] [L19] COND TRUE n == 1 [L20] return 1; VAL [\old(n)=1, \result=1, n=1] [L22] RET, EXPR fibonacci(n-2) VAL [\old(n)=3, fibonacci(n-1)=1, fibonacci(n-2)=1, n=3] [L22] return fibonacci(n-1) + fibonacci(n-2); [L22] RET, EXPR fibonacci(n-2) VAL [\old(n)=5, fibonacci(n-1)=3, fibonacci(n-2)=2, n=5] [L22] return fibonacci(n-1) + fibonacci(n-2); [L22] RET, EXPR fibonacci(n-1) VAL [\old(n)=6, fibonacci(n-1)=5, n=6] [L22] CALL, EXPR fibonacci(n-2) VAL [\old(n)=4] [L17] COND FALSE !(n < 1) VAL [\old(n)=4, n=4] [L19] COND FALSE !(n == 1) VAL [\old(n)=4, n=4] [L22] CALL, EXPR fibonacci(n-1) VAL [\old(n)=3] [L17] COND FALSE !(n < 1) VAL [\old(n)=3, n=3] [L19] COND FALSE !(n == 1) VAL [\old(n)=3, n=3] [L22] CALL, EXPR fibonacci(n-1) VAL [\old(n)=2] [L17] COND FALSE !(n < 1) VAL [\old(n)=2, n=2] [L19] COND FALSE !(n == 1) VAL [\old(n)=2, n=2] [L22] CALL, EXPR fibonacci(n-1) VAL [\old(n)=1] [L17] COND FALSE !(n < 1) VAL [\old(n)=1, n=1] [L19] COND TRUE n == 1 [L20] return 1; VAL [\old(n)=1, \result=1, n=1] [L22] RET, EXPR fibonacci(n-1) VAL [\old(n)=2, fibonacci(n-1)=1, n=2] [L22] CALL, EXPR fibonacci(n-2) VAL [\old(n)=0] [L17] COND TRUE n < 1 [L18] return 0; VAL [\old(n)=0, \result=0, n=0] [L22] RET, EXPR fibonacci(n-2) VAL [\old(n)=2, fibonacci(n-1)=1, fibonacci(n-2)=0, n=2] [L22] return fibonacci(n-1) + fibonacci(n-2); [L22] RET, EXPR fibonacci(n-1) VAL [\old(n)=3, fibonacci(n-1)=1, n=3] [L22] CALL, EXPR fibonacci(n-2) VAL [\old(n)=1] [L17] COND FALSE !(n < 1) VAL [\old(n)=1, n=1] [L19] COND TRUE n == 1 [L20] return 1; VAL [\old(n)=1, \result=1, n=1] [L22] RET, EXPR fibonacci(n-2) VAL [\old(n)=3, fibonacci(n-1)=1, fibonacci(n-2)=1, n=3] [L22] return fibonacci(n-1) + fibonacci(n-2); [L22] RET, EXPR fibonacci(n-1) VAL [\old(n)=4, fibonacci(n-1)=2, n=4] [L22] CALL, EXPR fibonacci(n-2) VAL [\old(n)=2] [L17] COND FALSE !(n < 1) VAL [\old(n)=2, n=2] [L19] COND FALSE !(n == 1) VAL [\old(n)=2, n=2] [L22] CALL, EXPR fibonacci(n-1) VAL [\old(n)=1] [L17] COND FALSE !(n < 1) VAL [\old(n)=1, n=1] [L19] COND TRUE n == 1 [L20] return 1; VAL [\old(n)=1, \result=1, n=1] [L22] RET, EXPR fibonacci(n-1) VAL [\old(n)=2, fibonacci(n-1)=1, n=2] [L22] CALL, EXPR fibonacci(n-2) VAL [\old(n)=0] [L17] COND TRUE n < 1 [L18] return 0; VAL [\old(n)=0, \result=0, n=0] [L22] RET, EXPR fibonacci(n-2) VAL [\old(n)=2, fibonacci(n-1)=1, fibonacci(n-2)=0, n=2] [L22] return fibonacci(n-1) + fibonacci(n-2); [L22] RET, EXPR fibonacci(n-2) VAL [\old(n)=4, fibonacci(n-1)=2, fibonacci(n-2)=1, n=4] [L22] return fibonacci(n-1) + fibonacci(n-2); [L22] RET, EXPR fibonacci(n-2) VAL [\old(n)=6, fibonacci(n-1)=5, fibonacci(n-2)=3, n=6] [L22] return fibonacci(n-1) + fibonacci(n-2); [L22] RET, EXPR fibonacci(n-2) VAL [\old(n)=8, fibonacci(n-1)=13, fibonacci(n-2)=8, n=8] [L22] return fibonacci(n-1) + fibonacci(n-2); [L29] RET, EXPR fibonacci(x) VAL [fibonacci(x)=21, x=8] [L29] int result = fibonacci(x); [L30] COND FALSE !(x < 8 || result >= 34) VAL [result=21, x=8] [L33] reach_error() VAL [result=21, x=8] - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 17 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 21.0s, OverallIterations: 9, TraceHistogramMax: 97, PathProgramHistogramMax: 6, EmptinessCheckTime: 0.1s, AutomataDifference: 3.0s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, PartialOrderReductionTime: 0.0s, HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 901 SdHoareTripleChecker+Valid, 1.4s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 871 mSDsluCounter, 594 SdHoareTripleChecker+Invalid, 1.1s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 522 mSDsCounter, 1164 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 1481 IncrementalHoareTripleChecker+Invalid, 2645 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 1164 mSolverCounterUnsat, 131 mSDtfsCounter, 1481 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 3431 GetRequests, 3217 SyntacticMatches, 7 SemanticMatches, 207 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1814 ImplicationChecksByTransitivity, 2.1s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=112occurred in iteration=8, InterpolantAutomatonStates: 134, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.1s AutomataMinimizationTime, 8 MinimizatonAttempts, 35 StatesRemovedByMinimization, 4 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.2s SsaConstructionTime, 1.1s SatisfiabilityAnalysisTime, 14.5s InterpolantComputationTime, 3718 NumberOfCodeBlocks, 3424 NumberOfCodeBlocksAsserted, 73 NumberOfCheckSat, 4859 ConstructedInterpolants, 0 QuantifiedInterpolants, 6811 SizeOfPredicates, 33 NumberOfNonLiveVariables, 3099 ConjunctsInSsa, 78 ConjunctsInUnsatCore, 20 InterpolantComputations, 2 PerfectInterpolantSequences, 129434/146661 InterpolantCoveringCapability, INVARIANT_SYNTHESIS: No data available, INTERPOLANT_CONSOLIDATION: No data available, ABSTRACT_INTERPRETATION: No data available, PDR: No data available, ACCELERATED_INTERPOLATION: No data available, SIFA: No data available, ReuseStatistics: No data available RESULT: Ultimate proved your program to be incorrect! [2021-11-20 22:45:52,640 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_fcaf6f6d-930b-4402-93cd-14a0711eb2d4/bin/utaipan-TEXQjIfE4P/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Forceful destruction successful, exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Writing output log to file Ultimate.log Writing human readable error path to file UltimateCounterExample.errorpath Result: FALSE