./Ultimate.py --spec ../../sv-benchmarks/c/properties/unreach-call.prp --file ../../sv-benchmarks/c/recursive/Fibonacci02.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 0e0057cc Calling Ultimate with: /usr/lib/jvm/java-11-openjdk-amd64/bin/java -Dosgi.configuration.area=/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/config/TaipanReach.xml -i ../../sv-benchmarks/c/recursive/Fibonacci02.c -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/config/svcomp-Reach-32bit-Taipan_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh --witnessprinter.witness.filename witness --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 b7261cadd839cd02322bb28945f92ad1bd2170c0a65dd385996b5ff81cbb1de7 --- Real Ultimate output --- This is Ultimate 0.2.4-dev-0e0057c [2023-12-02 16:58:09,371 INFO L188 SettingsManager]: Resetting all preferences to default values... [2023-12-02 16:58:09,433 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/config/svcomp-Reach-32bit-Taipan_Default.epf [2023-12-02 16:58:09,437 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2023-12-02 16:58:09,438 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2023-12-02 16:58:09,460 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2023-12-02 16:58:09,461 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2023-12-02 16:58:09,461 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2023-12-02 16:58:09,462 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2023-12-02 16:58:09,462 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2023-12-02 16:58:09,463 INFO L153 SettingsManager]: * User list type=DISABLED [2023-12-02 16:58:09,464 INFO L151 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2023-12-02 16:58:09,464 INFO L153 SettingsManager]: * Explicit value domain=true [2023-12-02 16:58:09,465 INFO L153 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2023-12-02 16:58:09,465 INFO L153 SettingsManager]: * Octagon Domain=false [2023-12-02 16:58:09,466 INFO L153 SettingsManager]: * Abstract domain=CompoundDomain [2023-12-02 16:58:09,466 INFO L153 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2023-12-02 16:58:09,467 INFO L153 SettingsManager]: * Use the RCFG-of-the-future interface=true [2023-12-02 16:58:09,467 INFO L153 SettingsManager]: * Interval Domain=false [2023-12-02 16:58:09,468 INFO L151 SettingsManager]: Preferences of Sifa differ from their defaults: [2023-12-02 16:58:09,469 INFO L153 SettingsManager]: * Call Summarizer=TopInputCallSummarizer [2023-12-02 16:58:09,472 INFO L153 SettingsManager]: * Simplification Technique=POLY_PAC [2023-12-02 16:58:09,473 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2023-12-02 16:58:09,474 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2023-12-02 16:58:09,474 INFO L153 SettingsManager]: * sizeof long=4 [2023-12-02 16:58:09,475 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2023-12-02 16:58:09,475 INFO L153 SettingsManager]: * sizeof POINTER=4 [2023-12-02 16:58:09,476 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2023-12-02 16:58:09,476 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2023-12-02 16:58:09,476 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2023-12-02 16:58:09,477 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2023-12-02 16:58:09,477 INFO L153 SettingsManager]: * sizeof long double=12 [2023-12-02 16:58:09,477 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2023-12-02 16:58:09,478 INFO L153 SettingsManager]: * Use constant arrays=true [2023-12-02 16:58:09,478 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2023-12-02 16:58:09,478 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2023-12-02 16:58:09,478 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2023-12-02 16:58:09,478 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-12-02 16:58:09,479 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2023-12-02 16:58:09,479 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2023-12-02 16:58:09,479 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2023-12-02 16:58:09,479 INFO L153 SettingsManager]: * Trace refinement strategy=SIFA_TAIPAN [2023-12-02 16:58:09,480 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2023-12-02 16:58:09,480 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2023-12-02 16:58:09,480 INFO L153 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2023-12-02 16:58:09,480 INFO L153 SettingsManager]: * Trace refinement exception blacklist=NONE [2023-12-02 16:58:09,481 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2023-12-02 16:58:09,481 INFO L153 SettingsManager]: * Abstract interpretation Mode=USE_PREDICATES WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/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_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Write witness besides input file -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data specification -> CHECK( init(main()), LTL(G ! 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 -> b7261cadd839cd02322bb28945f92ad1bd2170c0a65dd385996b5ff81cbb1de7 [2023-12-02 16:58:09,710 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2023-12-02 16:58:09,731 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2023-12-02 16:58:09,734 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2023-12-02 16:58:09,735 INFO L270 PluginConnector]: Initializing CDTParser... [2023-12-02 16:58:09,736 INFO L274 PluginConnector]: CDTParser initialized [2023-12-02 16:58:09,737 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/../../sv-benchmarks/c/recursive/Fibonacci02.c [2023-12-02 16:58:12,447 INFO L533 CDTParser]: Created temporary CDT project at NULL [2023-12-02 16:58:12,621 INFO L384 CDTParser]: Found 1 translation units. [2023-12-02 16:58:12,621 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/sv-benchmarks/c/recursive/Fibonacci02.c [2023-12-02 16:58:12,628 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/data/c0ae43493/eb977edde4f24d5eb727efa7c5640d91/FLAG3de588a9b [2023-12-02 16:58:12,641 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/data/c0ae43493/eb977edde4f24d5eb727efa7c5640d91 [2023-12-02 16:58:12,643 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2023-12-02 16:58:12,644 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2023-12-02 16:58:12,645 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2023-12-02 16:58:12,645 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2023-12-02 16:58:12,651 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2023-12-02 16:58:12,652 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 02.12 04:58:12" (1/1) ... [2023-12-02 16:58:12,653 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@61c9b987 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 04:58:12, skipping insertion in model container [2023-12-02 16:58:12,653 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 02.12 04:58:12" (1/1) ... [2023-12-02 16:58:12,672 INFO L177 MainTranslator]: Built tables and reachable declarations [2023-12-02 16:58:12,815 WARN L240 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_e8d5be35-432c-48a9-9c99-70d90e7722cd/sv-benchmarks/c/recursive/Fibonacci02.c[715,728] [2023-12-02 16:58:12,820 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-12-02 16:58:12,829 INFO L202 MainTranslator]: Completed pre-run [2023-12-02 16:58:12,841 WARN L240 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_e8d5be35-432c-48a9-9c99-70d90e7722cd/sv-benchmarks/c/recursive/Fibonacci02.c[715,728] [2023-12-02 16:58:12,841 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-12-02 16:58:12,852 INFO L206 MainTranslator]: Completed translation [2023-12-02 16:58:12,853 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 04:58:12 WrapperNode [2023-12-02 16:58:12,853 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2023-12-02 16:58:12,854 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2023-12-02 16:58:12,854 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2023-12-02 16:58:12,854 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2023-12-02 16:58:12,860 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 04:58:12" (1/1) ... [2023-12-02 16:58:12,866 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 04:58:12" (1/1) ... [2023-12-02 16:58:12,878 INFO L138 Inliner]: procedures = 13, calls = 10, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 20 [2023-12-02 16:58:12,879 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2023-12-02 16:58:12,879 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2023-12-02 16:58:12,879 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2023-12-02 16:58:12,880 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2023-12-02 16:58:12,886 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 04:58:12" (1/1) ... [2023-12-02 16:58:12,887 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 04:58:12" (1/1) ... [2023-12-02 16:58:12,888 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 04:58:12" (1/1) ... [2023-12-02 16:58:12,888 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 04:58:12" (1/1) ... [2023-12-02 16:58:12,891 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 04:58:12" (1/1) ... [2023-12-02 16:58:12,892 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 04:58:12" (1/1) ... [2023-12-02 16:58:12,893 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 04:58:12" (1/1) ... [2023-12-02 16:58:12,894 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 04:58:12" (1/1) ... [2023-12-02 16:58:12,896 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2023-12-02 16:58:12,897 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2023-12-02 16:58:12,897 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2023-12-02 16:58:12,897 INFO L274 PluginConnector]: RCFGBuilder initialized [2023-12-02 16:58:12,898 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 04:58:12" (1/1) ... [2023-12-02 16:58:12,904 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-12-02 16:58:12,918 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 16:58:12,935 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2023-12-02 16:58:12,940 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2023-12-02 16:58:12,967 INFO L130 BoogieDeclarations]: Found specification of procedure fibonacci [2023-12-02 16:58:12,967 INFO L138 BoogieDeclarations]: Found implementation of procedure fibonacci [2023-12-02 16:58:12,967 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2023-12-02 16:58:12,968 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2023-12-02 16:58:12,968 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2023-12-02 16:58:12,968 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2023-12-02 16:58:13,028 INFO L241 CfgBuilder]: Building ICFG [2023-12-02 16:58:13,030 INFO L267 CfgBuilder]: Building CFG for each procedure with an implementation [2023-12-02 16:58:13,135 INFO L282 CfgBuilder]: Performing block encoding [2023-12-02 16:58:13,157 INFO L304 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2023-12-02 16:58:13,157 INFO L309 CfgBuilder]: Removed 0 assume(true) statements. [2023-12-02 16:58:13,159 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 02.12 04:58:13 BoogieIcfgContainer [2023-12-02 16:58:13,159 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2023-12-02 16:58:13,162 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2023-12-02 16:58:13,162 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2023-12-02 16:58:13,165 INFO L274 PluginConnector]: TraceAbstraction initialized [2023-12-02 16:58:13,166 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 02.12 04:58:12" (1/3) ... [2023-12-02 16:58:13,166 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3694ddff and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 02.12 04:58:13, skipping insertion in model container [2023-12-02 16:58:13,167 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 04:58:12" (2/3) ... [2023-12-02 16:58:13,167 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3694ddff and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 02.12 04:58:13, skipping insertion in model container [2023-12-02 16:58:13,167 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 02.12 04:58:13" (3/3) ... [2023-12-02 16:58:13,168 INFO L112 eAbstractionObserver]: Analyzing ICFG Fibonacci02.c [2023-12-02 16:58:13,185 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2023-12-02 16:58:13,185 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2023-12-02 16:58:13,228 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-12-02 16:58:13,234 INFO L357 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=FPandBP, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mHoare=true, mAutomataTypeConcurrency=FINITE_AUTOMATA, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=LoopHeads, mDumpOnlyReuseAutomata=false, mLimitTraceHistogram=0, mErrorLocTimeLimit=0, mLimitPathProgramCount=0, mCollectInterpolantStatistics=true, mHeuristicEmptinessCheck=false, mHeuristicEmptinessCheckAStarHeuristic=ZERO, mHeuristicEmptinessCheckAStarHeuristicRandomSeed=1337, mHeuristicEmptinessCheckSmtFeatureScoringMethod=DAGSIZE, mSMTFeatureExtraction=false, mSMTFeatureExtractionDumpPath=., mOverrideInterpolantAutomaton=false, mMcrInterpolantMethod=WP, mPorIndependenceSettings=[Lde.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings;@5b814166, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2023-12-02 16:58:13,234 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2023-12-02 16:58:13,238 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) [2023-12-02 16:58:13,244 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 10 [2023-12-02 16:58:13,244 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 16:58:13,245 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 16:58:13,245 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 16:58:13,251 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 16:58:13,251 INFO L85 PathProgramCache]: Analyzing trace with hash -1615401540, now seen corresponding path program 1 times [2023-12-02 16:58:13,259 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 16:58:13,260 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [326685361] [2023-12-02 16:58:13,260 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 16:58:13,261 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 16:58:13,347 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 16:58:13,456 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-02 16:58:13,457 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 16:58:13,457 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [326685361] [2023-12-02 16:58:13,458 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [326685361] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-02 16:58:13,458 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-12-02 16:58:13,458 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2023-12-02 16:58:13,460 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1520327679] [2023-12-02 16:58:13,460 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-02 16:58:13,464 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-12-02 16:58:13,464 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 16:58:13,491 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-12-02 16:58:13,492 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2023-12-02 16:58:13,494 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, 4 states have (on average 1.75) internal successors, (7), 4 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) [2023-12-02 16:58:13,578 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 16:58:13,579 INFO L93 Difference]: Finished difference Result 25 states and 31 transitions. [2023-12-02 16:58:13,580 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2023-12-02 16:58:13,581 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 1.75) internal successors, (7), 4 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 [2023-12-02 16:58:13,582 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 16:58:13,590 INFO L225 Difference]: With dead ends: 25 [2023-12-02 16:58:13,590 INFO L226 Difference]: Without dead ends: 17 [2023-12-02 16:58:13,593 INFO L412 NwaCegarLoop]: 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 [2023-12-02 16:58:13,597 INFO L413 NwaCegarLoop]: 11 mSDtfsCounter, 12 mSDsluCounter, 16 mSDsCounter, 0 mSdLazyCounter, 36 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 17 SdHoareTripleChecker+Valid, 27 SdHoareTripleChecker+Invalid, 36 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 36 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-12-02 16:58:13,598 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [17 Valid, 27 Invalid, 36 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 36 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-12-02 16:58:13,614 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 17 states. [2023-12-02 16:58:13,633 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 17 to 17. [2023-12-02 16:58:13,634 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) [2023-12-02 16:58:13,635 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 17 states to 17 states and 21 transitions. [2023-12-02 16:58:13,637 INFO L78 Accepts]: Start accepts. Automaton has 17 states and 21 transitions. Word has length 9 [2023-12-02 16:58:13,637 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 16:58:13,637 INFO L495 AbstractCegarLoop]: Abstraction has 17 states and 21 transitions. [2023-12-02 16:58:13,637 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 1.75) internal successors, (7), 4 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) [2023-12-02 16:58:13,638 INFO L276 IsEmpty]: Start isEmpty. Operand 17 states and 21 transitions. [2023-12-02 16:58:13,639 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 11 [2023-12-02 16:58:13,639 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 16:58:13,639 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 16:58:13,640 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2023-12-02 16:58:13,640 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 16:58:13,641 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 16:58:13,641 INFO L85 PathProgramCache]: Analyzing trace with hash -2136894566, now seen corresponding path program 1 times [2023-12-02 16:58:13,641 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 16:58:13,641 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1222699817] [2023-12-02 16:58:13,641 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 16:58:13,642 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 16:58:13,654 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 16:58:13,717 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-02 16:58:13,731 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 16:58:13,732 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1222699817] [2023-12-02 16:58:13,732 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1222699817] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-02 16:58:13,732 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-12-02 16:58:13,734 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2023-12-02 16:58:13,734 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1328773253] [2023-12-02 16:58:13,734 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-02 16:58:13,736 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-12-02 16:58:13,736 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 16:58:13,737 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-12-02 16:58:13,737 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2023-12-02 16:58:13,737 INFO L87 Difference]: Start difference. First operand 17 states and 21 transitions. Second operand has 5 states, 4 states have (on average 2.0) internal successors, (8), 4 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2023-12-02 16:58:13,785 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 16:58:13,785 INFO L93 Difference]: Finished difference Result 23 states and 28 transitions. [2023-12-02 16:58:13,786 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2023-12-02 16:58:13,786 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 2.0) internal successors, (8), 4 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 10 [2023-12-02 16:58:13,786 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 16:58:13,787 INFO L225 Difference]: With dead ends: 23 [2023-12-02 16:58:13,787 INFO L226 Difference]: Without dead ends: 19 [2023-12-02 16:58:13,788 INFO L412 NwaCegarLoop]: 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 [2023-12-02 16:58:13,789 INFO L413 NwaCegarLoop]: 10 mSDtfsCounter, 10 mSDsluCounter, 14 mSDsCounter, 0 mSdLazyCounter, 31 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 15 SdHoareTripleChecker+Valid, 24 SdHoareTripleChecker+Invalid, 32 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 31 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-12-02 16:58:13,790 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [15 Valid, 24 Invalid, 32 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 31 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-12-02 16:58:13,791 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 19 states. [2023-12-02 16:58:13,796 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 19 to 17. [2023-12-02 16:58:13,796 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) [2023-12-02 16:58:13,797 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 17 states to 17 states and 21 transitions. [2023-12-02 16:58:13,797 INFO L78 Accepts]: Start accepts. Automaton has 17 states and 21 transitions. Word has length 10 [2023-12-02 16:58:13,797 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 16:58:13,798 INFO L495 AbstractCegarLoop]: Abstraction has 17 states and 21 transitions. [2023-12-02 16:58:13,798 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 2.0) internal successors, (8), 4 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2023-12-02 16:58:13,798 INFO L276 IsEmpty]: Start isEmpty. Operand 17 states and 21 transitions. [2023-12-02 16:58:13,799 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2023-12-02 16:58:13,799 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 16:58:13,799 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 16:58:13,800 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2023-12-02 16:58:13,800 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 16:58:13,800 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 16:58:13,800 INFO L85 PathProgramCache]: Analyzing trace with hash -338238899, now seen corresponding path program 1 times [2023-12-02 16:58:13,801 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 16:58:13,801 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [542673861] [2023-12-02 16:58:13,801 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 16:58:13,801 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 16:58:13,818 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 16:58:13,909 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 5 proven. 3 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2023-12-02 16:58:13,910 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 16:58:13,910 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [542673861] [2023-12-02 16:58:13,910 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [542673861] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-02 16:58:13,911 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1980072152] [2023-12-02 16:58:13,911 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 16:58:13,911 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 16:58:13,911 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 16:58:13,917 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 16:58:13,919 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2023-12-02 16:58:13,973 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 16:58:13,975 INFO L262 TraceCheckSpWp]: Trace formula consists of 70 conjuncts, 6 conjunts are in the unsatisfiable core [2023-12-02 16:58:13,982 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 16:58:14,063 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 2 proven. 6 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2023-12-02 16:58:14,063 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 16:58:14,254 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 2 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2023-12-02 16:58:14,254 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1980072152] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-02 16:58:14,254 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [73884333] [2023-12-02 16:58:14,271 INFO L159 IcfgInterpreter]: Started Sifa with 15 locations of interest [2023-12-02 16:58:14,271 INFO L166 IcfgInterpreter]: Building call graph [2023-12-02 16:58:14,275 FATAL L? ?]: Ignoring exception! java.lang.IllegalArgumentException: Recursive programs are not supported. at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.topsortRelevant(CallGraph.java:132) at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.(CallGraph.java:97) at de.uni_freiburg.informatik.ultimate.lib.sifa.IcfgInterpreter.(IcfgInterpreter.java:92) at de.uni_freiburg.informatik.ultimate.plugins.sifa.SifaBuilder.construct(SifaBuilder.java:96) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.SifaRunner.(SifaRunner.java:98) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleSifa.construct(IpTcStrategyModuleSifa.java:68) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getOrConstruct(IpTcStrategyModuleBase.java:101) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getInterpolantComputationStatus(IpTcStrategyModuleBase.java:77) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.tryExecuteInterpolantGenerator(AutomatonFreeRefinementEngine.java:267) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.generateProof(AutomatonFreeRefinementEngine.java:148) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.executeStrategy(AutomatonFreeRefinementEngine.java:137) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.(AutomatonFreeRefinementEngine.java:85) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.TraceAbstractionRefinementEngine.(TraceAbstractionRefinementEngine.java:82) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.BasicCegarLoop.isCounterexampleFeasible(BasicCegarLoop.java:337) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterate(AbstractCegarLoop.java:431) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.startCegar(AbstractCegarLoop.java:366) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.runCegar(AbstractCegarLoop.java:348) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.executeCegarLoop(TraceAbstractionStarter.java:415) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseProgram(TraceAbstractionStarter.java:302) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseSequentialProgram(TraceAbstractionStarter.java:262) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.runCegarLoops(TraceAbstractionStarter.java:175) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.(TraceAbstractionStarter.java:154) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver.finish(TraceAbstractionObserver.java:124) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runObserver(PluginConnector.java:167) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runTool(PluginConnector.java:150) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.run(PluginConnector.java:127) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.executePluginConnector(ToolchainWalker.java:233) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.processPlugin(ToolchainWalker.java:227) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walkUnprotected(ToolchainWalker.java:144) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walk(ToolchainWalker.java:106) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainManager$Toolchain.processToolchain(ToolchainManager.java:319) at de.uni_freiburg.informatik.ultimate.core.coreplugin.toolchain.DefaultToolchainJob.run(DefaultToolchainJob.java:145) at org.eclipse.core.internal.jobs.Worker.run(Worker.java:63) [2023-12-02 16:58:14,276 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-12-02 16:58:14,276 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6, 7] total 11 [2023-12-02 16:58:14,276 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [325566575] [2023-12-02 16:58:14,277 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-12-02 16:58:14,277 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2023-12-02 16:58:14,277 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 16:58:14,278 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2023-12-02 16:58:14,279 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=80, Unknown=0, NotChecked=0, Total=110 [2023-12-02 16:58:14,279 INFO L87 Difference]: Start difference. First operand 17 states and 21 transitions. Second operand has 11 states, 8 states have (on average 3.375) internal successors, (27), 11 states have internal predecessors, (27), 8 states have call successors, (8), 1 states have call predecessors, (8), 4 states have return successors, (8), 2 states have call predecessors, (8), 8 states have call successors, (8) [2023-12-02 16:58:14,392 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 16:58:14,392 INFO L93 Difference]: Finished difference Result 34 states and 45 transitions. [2023-12-02 16:58:14,392 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2023-12-02 16:58:14,393 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 8 states have (on average 3.375) internal successors, (27), 11 states have internal predecessors, (27), 8 states have call successors, (8), 1 states have call predecessors, (8), 4 states have return successors, (8), 2 states have call predecessors, (8), 8 states have call successors, (8) Word has length 22 [2023-12-02 16:58:14,393 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 16:58:14,394 INFO L225 Difference]: With dead ends: 34 [2023-12-02 16:58:14,394 INFO L226 Difference]: Without dead ends: 19 [2023-12-02 16:58:14,395 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 55 GetRequests, 40 SyntacticMatches, 2 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 23 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=59, Invalid=151, Unknown=0, NotChecked=0, Total=210 [2023-12-02 16:58:14,396 INFO L413 NwaCegarLoop]: 12 mSDtfsCounter, 15 mSDsluCounter, 47 mSDsCounter, 0 mSdLazyCounter, 89 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 16 SdHoareTripleChecker+Valid, 59 SdHoareTripleChecker+Invalid, 100 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 89 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-12-02 16:58:14,397 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [16 Valid, 59 Invalid, 100 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 89 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-12-02 16:58:14,398 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 19 states. [2023-12-02 16:58:14,401 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 19 to 19. [2023-12-02 16:58:14,402 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 19 states, 12 states have (on average 1.1666666666666667) internal successors, (14), 14 states have internal predecessors, (14), 3 states have call successors, (3), 1 states have call predecessors, (3), 3 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) [2023-12-02 16:58:14,402 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 19 states to 19 states and 23 transitions. [2023-12-02 16:58:14,403 INFO L78 Accepts]: Start accepts. Automaton has 19 states and 23 transitions. Word has length 22 [2023-12-02 16:58:14,403 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 16:58:14,403 INFO L495 AbstractCegarLoop]: Abstraction has 19 states and 23 transitions. [2023-12-02 16:58:14,403 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 8 states have (on average 3.375) internal successors, (27), 11 states have internal predecessors, (27), 8 states have call successors, (8), 1 states have call predecessors, (8), 4 states have return successors, (8), 2 states have call predecessors, (8), 8 states have call successors, (8) [2023-12-02 16:58:14,404 INFO L276 IsEmpty]: Start isEmpty. Operand 19 states and 23 transitions. [2023-12-02 16:58:14,405 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2023-12-02 16:58:14,405 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 16:58:14,405 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 16:58:14,417 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2023-12-02 16:58:14,608 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 16:58:14,608 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 16:58:14,609 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 16:58:14,609 INFO L85 PathProgramCache]: Analyzing trace with hash -2033467333, now seen corresponding path program 1 times [2023-12-02 16:58:14,609 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 16:58:14,609 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1607342109] [2023-12-02 16:58:14,609 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 16:58:14,610 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 16:58:14,622 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 16:58:14,701 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 2 proven. 6 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2023-12-02 16:58:14,701 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 16:58:14,702 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1607342109] [2023-12-02 16:58:14,702 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1607342109] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-02 16:58:14,702 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1334523409] [2023-12-02 16:58:14,702 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 16:58:14,703 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 16:58:14,703 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 16:58:14,704 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 16:58:14,708 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2023-12-02 16:58:14,747 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 16:58:14,748 INFO L262 TraceCheckSpWp]: Trace formula consists of 72 conjuncts, 6 conjunts are in the unsatisfiable core [2023-12-02 16:58:14,749 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 16:58:14,777 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 2 proven. 6 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2023-12-02 16:58:14,777 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 16:58:14,955 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 2 proven. 8 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2023-12-02 16:58:14,955 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1334523409] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-02 16:58:14,956 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [658382684] [2023-12-02 16:58:14,959 INFO L159 IcfgInterpreter]: Started Sifa with 15 locations of interest [2023-12-02 16:58:14,959 INFO L166 IcfgInterpreter]: Building call graph [2023-12-02 16:58:14,960 FATAL L? ?]: Ignoring exception! java.lang.IllegalArgumentException: Recursive programs are not supported. at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.topsortRelevant(CallGraph.java:132) at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.(CallGraph.java:97) at de.uni_freiburg.informatik.ultimate.lib.sifa.IcfgInterpreter.(IcfgInterpreter.java:92) at de.uni_freiburg.informatik.ultimate.plugins.sifa.SifaBuilder.construct(SifaBuilder.java:96) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.SifaRunner.(SifaRunner.java:98) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleSifa.construct(IpTcStrategyModuleSifa.java:68) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getOrConstruct(IpTcStrategyModuleBase.java:101) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getInterpolantComputationStatus(IpTcStrategyModuleBase.java:77) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.tryExecuteInterpolantGenerator(AutomatonFreeRefinementEngine.java:267) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.generateProof(AutomatonFreeRefinementEngine.java:148) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.executeStrategy(AutomatonFreeRefinementEngine.java:137) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.(AutomatonFreeRefinementEngine.java:85) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.TraceAbstractionRefinementEngine.(TraceAbstractionRefinementEngine.java:82) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.BasicCegarLoop.isCounterexampleFeasible(BasicCegarLoop.java:337) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterate(AbstractCegarLoop.java:431) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.startCegar(AbstractCegarLoop.java:366) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.runCegar(AbstractCegarLoop.java:348) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.executeCegarLoop(TraceAbstractionStarter.java:415) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseProgram(TraceAbstractionStarter.java:302) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseSequentialProgram(TraceAbstractionStarter.java:262) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.runCegarLoops(TraceAbstractionStarter.java:175) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.(TraceAbstractionStarter.java:154) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver.finish(TraceAbstractionObserver.java:124) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runObserver(PluginConnector.java:167) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runTool(PluginConnector.java:150) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.run(PluginConnector.java:127) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.executePluginConnector(ToolchainWalker.java:233) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.processPlugin(ToolchainWalker.java:227) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walkUnprotected(ToolchainWalker.java:144) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walk(ToolchainWalker.java:106) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainManager$Toolchain.processToolchain(ToolchainManager.java:319) at de.uni_freiburg.informatik.ultimate.core.coreplugin.toolchain.DefaultToolchainJob.run(DefaultToolchainJob.java:145) at org.eclipse.core.internal.jobs.Worker.run(Worker.java:63) [2023-12-02 16:58:14,960 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-12-02 16:58:14,960 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6, 7] total 9 [2023-12-02 16:58:14,960 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1465602596] [2023-12-02 16:58:14,969 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-12-02 16:58:14,970 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2023-12-02 16:58:14,970 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 16:58:14,971 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2023-12-02 16:58:14,971 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=22, Invalid=50, Unknown=0, NotChecked=0, Total=72 [2023-12-02 16:58:14,971 INFO L87 Difference]: Start difference. First operand 19 states and 23 transitions. Second operand has 9 states, 7 states have (on average 3.142857142857143) internal successors, (22), 9 states have internal predecessors, (22), 5 states have call successors, (5), 1 states have call predecessors, (5), 3 states have return successors, (5), 2 states have call predecessors, (5), 5 states have call successors, (5) [2023-12-02 16:58:15,031 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 16:58:15,031 INFO L93 Difference]: Finished difference Result 28 states and 37 transitions. [2023-12-02 16:58:15,032 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-12-02 16:58:15,032 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 7 states have (on average 3.142857142857143) internal successors, (22), 9 states have internal predecessors, (22), 5 states have call successors, (5), 1 states have call predecessors, (5), 3 states have return successors, (5), 2 states have call predecessors, (5), 5 states have call successors, (5) Word has length 23 [2023-12-02 16:58:15,032 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 16:58:15,034 INFO L225 Difference]: With dead ends: 28 [2023-12-02 16:58:15,034 INFO L226 Difference]: Without dead ends: 24 [2023-12-02 16:58:15,034 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 55 GetRequests, 44 SyntacticMatches, 2 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=36, Invalid=74, Unknown=0, NotChecked=0, Total=110 [2023-12-02 16:58:15,035 INFO L413 NwaCegarLoop]: 10 mSDtfsCounter, 15 mSDsluCounter, 20 mSDsCounter, 0 mSdLazyCounter, 41 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 21 SdHoareTripleChecker+Valid, 30 SdHoareTripleChecker+Invalid, 45 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 41 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-12-02 16:58:15,036 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [21 Valid, 30 Invalid, 45 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 41 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-12-02 16:58:15,037 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 24 states. [2023-12-02 16:58:15,042 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 24 to 24. [2023-12-02 16:58:15,042 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) [2023-12-02 16:58:15,043 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 33 transitions. [2023-12-02 16:58:15,043 INFO L78 Accepts]: Start accepts. Automaton has 24 states and 33 transitions. Word has length 23 [2023-12-02 16:58:15,044 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 16:58:15,044 INFO L495 AbstractCegarLoop]: Abstraction has 24 states and 33 transitions. [2023-12-02 16:58:15,044 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 7 states have (on average 3.142857142857143) internal successors, (22), 9 states have internal predecessors, (22), 5 states have call successors, (5), 1 states have call predecessors, (5), 3 states have return successors, (5), 2 states have call predecessors, (5), 5 states have call successors, (5) [2023-12-02 16:58:15,044 INFO L276 IsEmpty]: Start isEmpty. Operand 24 states and 33 transitions. [2023-12-02 16:58:15,046 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2023-12-02 16:58:15,046 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 16:58:15,046 INFO L195 NwaCegarLoop]: trace histogram [5, 5, 3, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 16:58:15,051 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2023-12-02 16:58:15,251 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 16:58:15,251 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 16:58:15,252 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 16:58:15,252 INFO L85 PathProgramCache]: Analyzing trace with hash -121874130, now seen corresponding path program 2 times [2023-12-02 16:58:15,252 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 16:58:15,252 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [723690205] [2023-12-02 16:58:15,252 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 16:58:15,252 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 16:58:15,264 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 16:58:15,399 INFO L134 CoverageAnalysis]: Checked inductivity of 47 backedges. 23 proven. 8 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2023-12-02 16:58:15,399 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 16:58:15,400 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [723690205] [2023-12-02 16:58:15,400 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [723690205] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-02 16:58:15,400 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [938189545] [2023-12-02 16:58:15,400 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-12-02 16:58:15,400 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 16:58:15,400 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 16:58:15,401 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 16:58:15,408 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2023-12-02 16:58:15,453 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 2 check-sat command(s) [2023-12-02 16:58:15,453 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-02 16:58:15,454 INFO L262 TraceCheckSpWp]: Trace formula consists of 62 conjuncts, 6 conjunts are in the unsatisfiable core [2023-12-02 16:58:15,456 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 16:58:15,507 INFO L134 CoverageAnalysis]: Checked inductivity of 47 backedges. 18 proven. 8 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2023-12-02 16:58:15,507 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 16:58:15,704 INFO L134 CoverageAnalysis]: Checked inductivity of 47 backedges. 18 proven. 9 refuted. 0 times theorem prover too weak. 20 trivial. 0 not checked. [2023-12-02 16:58:15,704 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [938189545] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-02 16:58:15,704 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [2062012393] [2023-12-02 16:58:15,707 INFO L159 IcfgInterpreter]: Started Sifa with 15 locations of interest [2023-12-02 16:58:15,707 INFO L166 IcfgInterpreter]: Building call graph [2023-12-02 16:58:15,707 FATAL L? ?]: Ignoring exception! java.lang.IllegalArgumentException: Recursive programs are not supported. at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.topsortRelevant(CallGraph.java:132) at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.(CallGraph.java:97) at de.uni_freiburg.informatik.ultimate.lib.sifa.IcfgInterpreter.(IcfgInterpreter.java:92) at de.uni_freiburg.informatik.ultimate.plugins.sifa.SifaBuilder.construct(SifaBuilder.java:96) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.SifaRunner.(SifaRunner.java:98) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleSifa.construct(IpTcStrategyModuleSifa.java:68) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getOrConstruct(IpTcStrategyModuleBase.java:101) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getInterpolantComputationStatus(IpTcStrategyModuleBase.java:77) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.tryExecuteInterpolantGenerator(AutomatonFreeRefinementEngine.java:267) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.generateProof(AutomatonFreeRefinementEngine.java:148) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.executeStrategy(AutomatonFreeRefinementEngine.java:137) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.(AutomatonFreeRefinementEngine.java:85) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.TraceAbstractionRefinementEngine.(TraceAbstractionRefinementEngine.java:82) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.BasicCegarLoop.isCounterexampleFeasible(BasicCegarLoop.java:337) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterate(AbstractCegarLoop.java:431) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.startCegar(AbstractCegarLoop.java:366) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.runCegar(AbstractCegarLoop.java:348) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.executeCegarLoop(TraceAbstractionStarter.java:415) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseProgram(TraceAbstractionStarter.java:302) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseSequentialProgram(TraceAbstractionStarter.java:262) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.runCegarLoops(TraceAbstractionStarter.java:175) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.(TraceAbstractionStarter.java:154) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver.finish(TraceAbstractionObserver.java:124) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runObserver(PluginConnector.java:167) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runTool(PluginConnector.java:150) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.run(PluginConnector.java:127) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.executePluginConnector(ToolchainWalker.java:233) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.processPlugin(ToolchainWalker.java:227) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walkUnprotected(ToolchainWalker.java:144) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walk(ToolchainWalker.java:106) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainManager$Toolchain.processToolchain(ToolchainManager.java:319) at de.uni_freiburg.informatik.ultimate.core.coreplugin.toolchain.DefaultToolchainJob.run(DefaultToolchainJob.java:145) at org.eclipse.core.internal.jobs.Worker.run(Worker.java:63) [2023-12-02 16:58:15,708 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-12-02 16:58:15,708 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 6, 7] total 14 [2023-12-02 16:58:15,708 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [209433698] [2023-12-02 16:58:15,708 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-12-02 16:58:15,709 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2023-12-02 16:58:15,709 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 16:58:15,710 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2023-12-02 16:58:15,710 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=40, Invalid=142, Unknown=0, NotChecked=0, Total=182 [2023-12-02 16:58:15,710 INFO L87 Difference]: Start difference. First operand 24 states and 33 transitions. Second operand has 14 states, 12 states have (on average 3.0833333333333335) internal successors, (37), 14 states have internal predecessors, (37), 7 states have call successors, (12), 1 states have call predecessors, (12), 5 states have return successors, (13), 8 states have call predecessors, (13), 7 states have call successors, (13) [2023-12-02 16:58:15,908 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 16:58:15,908 INFO L93 Difference]: Finished difference Result 55 states and 85 transitions. [2023-12-02 16:58:15,908 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2023-12-02 16:58:15,909 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 12 states have (on average 3.0833333333333335) internal successors, (37), 14 states have internal predecessors, (37), 7 states have call successors, (12), 1 states have call predecessors, (12), 5 states have return successors, (13), 8 states have call predecessors, (13), 7 states have call successors, (13) Word has length 36 [2023-12-02 16:58:15,909 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 16:58:15,910 INFO L225 Difference]: With dead ends: 55 [2023-12-02 16:58:15,910 INFO L226 Difference]: Without dead ends: 33 [2023-12-02 16:58:15,912 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 86 GetRequests, 65 SyntacticMatches, 2 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 56 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=111, Invalid=309, Unknown=0, NotChecked=0, Total=420 [2023-12-02 16:58:15,913 INFO L413 NwaCegarLoop]: 15 mSDtfsCounter, 26 mSDsluCounter, 60 mSDsCounter, 0 mSdLazyCounter, 131 mSolverCounterSat, 18 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 27 SdHoareTripleChecker+Valid, 75 SdHoareTripleChecker+Invalid, 149 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 18 IncrementalHoareTripleChecker+Valid, 131 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-12-02 16:58:15,913 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [27 Valid, 75 Invalid, 149 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [18 Valid, 131 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-12-02 16:58:15,914 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 33 states. [2023-12-02 16:58:15,919 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 33 to 27. [2023-12-02 16:58:15,919 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 27 states, 18 states have (on average 1.1111111111111112) internal successors, (20), 19 states have internal predecessors, (20), 4 states have call successors, (4), 2 states have call predecessors, (4), 4 states have return successors, (11), 5 states have call predecessors, (11), 4 states have call successors, (11) [2023-12-02 16:58:15,920 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 27 states to 27 states and 35 transitions. [2023-12-02 16:58:15,920 INFO L78 Accepts]: Start accepts. Automaton has 27 states and 35 transitions. Word has length 36 [2023-12-02 16:58:15,920 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 16:58:15,920 INFO L495 AbstractCegarLoop]: Abstraction has 27 states and 35 transitions. [2023-12-02 16:58:15,920 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 12 states have (on average 3.0833333333333335) internal successors, (37), 14 states have internal predecessors, (37), 7 states have call successors, (12), 1 states have call predecessors, (12), 5 states have return successors, (13), 8 states have call predecessors, (13), 7 states have call successors, (13) [2023-12-02 16:58:15,921 INFO L276 IsEmpty]: Start isEmpty. Operand 27 states and 35 transitions. [2023-12-02 16:58:15,922 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2023-12-02 16:58:15,922 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 16:58:15,922 INFO L195 NwaCegarLoop]: trace histogram [5, 5, 4, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 16:58:15,927 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2023-12-02 16:58:16,123 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 16:58:16,123 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 16:58:16,123 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 16:58:16,123 INFO L85 PathProgramCache]: Analyzing trace with hash -807024572, now seen corresponding path program 3 times [2023-12-02 16:58:16,123 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 16:58:16,124 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [438452760] [2023-12-02 16:58:16,124 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 16:58:16,124 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 16:58:16,133 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 16:58:16,224 INFO L134 CoverageAnalysis]: Checked inductivity of 50 backedges. 6 proven. 24 refuted. 0 times theorem prover too weak. 20 trivial. 0 not checked. [2023-12-02 16:58:16,224 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 16:58:16,224 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [438452760] [2023-12-02 16:58:16,224 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [438452760] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-02 16:58:16,225 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1731867228] [2023-12-02 16:58:16,225 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2023-12-02 16:58:16,225 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 16:58:16,225 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 16:58:16,226 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 16:58:16,232 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2023-12-02 16:58:16,292 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2023-12-02 16:58:16,292 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-02 16:58:16,293 INFO L262 TraceCheckSpWp]: Trace formula consists of 103 conjuncts, 8 conjunts are in the unsatisfiable core [2023-12-02 16:58:16,296 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 16:58:16,343 INFO L134 CoverageAnalysis]: Checked inductivity of 50 backedges. 6 proven. 24 refuted. 0 times theorem prover too weak. 20 trivial. 0 not checked. [2023-12-02 16:58:16,343 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 16:58:16,654 INFO L134 CoverageAnalysis]: Checked inductivity of 50 backedges. 6 proven. 31 refuted. 0 times theorem prover too weak. 13 trivial. 0 not checked. [2023-12-02 16:58:16,655 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1731867228] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-02 16:58:16,655 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [114776821] [2023-12-02 16:58:16,657 INFO L159 IcfgInterpreter]: Started Sifa with 15 locations of interest [2023-12-02 16:58:16,658 INFO L166 IcfgInterpreter]: Building call graph [2023-12-02 16:58:16,658 FATAL L? ?]: Ignoring exception! java.lang.IllegalArgumentException: Recursive programs are not supported. at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.topsortRelevant(CallGraph.java:132) at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.(CallGraph.java:97) at de.uni_freiburg.informatik.ultimate.lib.sifa.IcfgInterpreter.(IcfgInterpreter.java:92) at de.uni_freiburg.informatik.ultimate.plugins.sifa.SifaBuilder.construct(SifaBuilder.java:96) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.SifaRunner.(SifaRunner.java:98) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleSifa.construct(IpTcStrategyModuleSifa.java:68) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getOrConstruct(IpTcStrategyModuleBase.java:101) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getInterpolantComputationStatus(IpTcStrategyModuleBase.java:77) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.tryExecuteInterpolantGenerator(AutomatonFreeRefinementEngine.java:267) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.generateProof(AutomatonFreeRefinementEngine.java:148) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.executeStrategy(AutomatonFreeRefinementEngine.java:137) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.(AutomatonFreeRefinementEngine.java:85) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.TraceAbstractionRefinementEngine.(TraceAbstractionRefinementEngine.java:82) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.BasicCegarLoop.isCounterexampleFeasible(BasicCegarLoop.java:337) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterate(AbstractCegarLoop.java:431) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.startCegar(AbstractCegarLoop.java:366) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.runCegar(AbstractCegarLoop.java:348) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.executeCegarLoop(TraceAbstractionStarter.java:415) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseProgram(TraceAbstractionStarter.java:302) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseSequentialProgram(TraceAbstractionStarter.java:262) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.runCegarLoops(TraceAbstractionStarter.java:175) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.(TraceAbstractionStarter.java:154) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver.finish(TraceAbstractionObserver.java:124) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runObserver(PluginConnector.java:167) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runTool(PluginConnector.java:150) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.run(PluginConnector.java:127) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.executePluginConnector(ToolchainWalker.java:233) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.processPlugin(ToolchainWalker.java:227) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walkUnprotected(ToolchainWalker.java:144) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walk(ToolchainWalker.java:106) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainManager$Toolchain.processToolchain(ToolchainManager.java:319) at de.uni_freiburg.informatik.ultimate.core.coreplugin.toolchain.DefaultToolchainJob.run(DefaultToolchainJob.java:145) at org.eclipse.core.internal.jobs.Worker.run(Worker.java:63) [2023-12-02 16:58:16,658 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-12-02 16:58:16,658 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 9] total 11 [2023-12-02 16:58:16,659 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [499554631] [2023-12-02 16:58:16,659 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-12-02 16:58:16,659 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2023-12-02 16:58:16,659 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 16:58:16,660 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2023-12-02 16:58:16,660 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=32, Invalid=78, Unknown=0, NotChecked=0, Total=110 [2023-12-02 16:58:16,660 INFO L87 Difference]: Start difference. First operand 27 states and 35 transitions. Second operand has 11 states, 9 states have (on average 3.3333333333333335) internal successors, (30), 11 states have internal predecessors, (30), 7 states have call successors, (7), 1 states have call predecessors, (7), 4 states have return successors, (8), 3 states have call predecessors, (8), 7 states have call successors, (8) [2023-12-02 16:58:16,756 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 16:58:16,756 INFO L93 Difference]: Finished difference Result 36 states and 50 transitions. [2023-12-02 16:58:16,757 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2023-12-02 16:58:16,757 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 9 states have (on average 3.3333333333333335) internal successors, (30), 11 states have internal predecessors, (30), 7 states have call successors, (7), 1 states have call predecessors, (7), 4 states have return successors, (8), 3 states have call predecessors, (8), 7 states have call successors, (8) Word has length 37 [2023-12-02 16:58:16,757 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 16:58:16,758 INFO L225 Difference]: With dead ends: 36 [2023-12-02 16:58:16,759 INFO L226 Difference]: Without dead ends: 32 [2023-12-02 16:58:16,759 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 86 GetRequests, 71 SyntacticMatches, 3 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 24 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=59, Invalid=123, Unknown=0, NotChecked=0, Total=182 [2023-12-02 16:58:16,760 INFO L413 NwaCegarLoop]: 10 mSDtfsCounter, 34 mSDsluCounter, 26 mSDsCounter, 0 mSdLazyCounter, 48 mSolverCounterSat, 29 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 42 SdHoareTripleChecker+Valid, 36 SdHoareTripleChecker+Invalid, 77 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 29 IncrementalHoareTripleChecker+Valid, 48 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-12-02 16:58:16,760 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [42 Valid, 36 Invalid, 77 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [29 Valid, 48 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-12-02 16:58:16,761 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 32 states. [2023-12-02 16:58:16,767 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 32 to 32. [2023-12-02 16:58:16,767 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 32 states, 21 states have (on average 1.0952380952380953) internal successors, (23), 22 states have internal predecessors, (23), 5 states have call successors, (5), 2 states have call predecessors, (5), 5 states have return successors, (18), 7 states have call predecessors, (18), 5 states have call successors, (18) [2023-12-02 16:58:16,768 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 46 transitions. [2023-12-02 16:58:16,769 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 46 transitions. Word has length 37 [2023-12-02 16:58:16,769 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 16:58:16,769 INFO L495 AbstractCegarLoop]: Abstraction has 32 states and 46 transitions. [2023-12-02 16:58:16,769 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 9 states have (on average 3.3333333333333335) internal successors, (30), 11 states have internal predecessors, (30), 7 states have call successors, (7), 1 states have call predecessors, (7), 4 states have return successors, (8), 3 states have call predecessors, (8), 7 states have call successors, (8) [2023-12-02 16:58:16,770 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 46 transitions. [2023-12-02 16:58:16,772 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 65 [2023-12-02 16:58:16,772 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 16:58:16,772 INFO L195 NwaCegarLoop]: trace histogram [9, 9, 7, 4, 4, 4, 4, 4, 4, 4, 3, 2, 1, 1, 1, 1, 1, 1] [2023-12-02 16:58:16,778 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2023-12-02 16:58:16,976 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 16:58:16,976 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 16:58:16,976 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 16:58:16,977 INFO L85 PathProgramCache]: Analyzing trace with hash -429029338, now seen corresponding path program 4 times [2023-12-02 16:58:16,977 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 16:58:16,977 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [635000678] [2023-12-02 16:58:16,977 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 16:58:16,977 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 16:58:16,993 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 16:58:17,123 INFO L134 CoverageAnalysis]: Checked inductivity of 189 backedges. 17 proven. 88 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2023-12-02 16:58:17,124 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 16:58:17,124 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [635000678] [2023-12-02 16:58:17,124 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [635000678] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-02 16:58:17,124 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1432366816] [2023-12-02 16:58:17,124 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2023-12-02 16:58:17,124 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 16:58:17,124 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 16:58:17,126 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 16:58:17,131 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2023-12-02 16:58:17,188 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 16:58:17,190 INFO L262 TraceCheckSpWp]: Trace formula consists of 163 conjuncts, 10 conjunts are in the unsatisfiable core [2023-12-02 16:58:17,193 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 16:58:17,278 INFO L134 CoverageAnalysis]: Checked inductivity of 189 backedges. 17 proven. 88 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2023-12-02 16:58:17,279 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 16:58:17,832 INFO L134 CoverageAnalysis]: Checked inductivity of 189 backedges. 17 proven. 103 refuted. 0 times theorem prover too weak. 69 trivial. 0 not checked. [2023-12-02 16:58:17,832 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1432366816] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-02 16:58:17,832 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [879876581] [2023-12-02 16:58:17,835 INFO L159 IcfgInterpreter]: Started Sifa with 15 locations of interest [2023-12-02 16:58:17,835 INFO L166 IcfgInterpreter]: Building call graph [2023-12-02 16:58:17,835 FATAL L? ?]: Ignoring exception! java.lang.IllegalArgumentException: Recursive programs are not supported. at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.topsortRelevant(CallGraph.java:132) at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.(CallGraph.java:97) at de.uni_freiburg.informatik.ultimate.lib.sifa.IcfgInterpreter.(IcfgInterpreter.java:92) at de.uni_freiburg.informatik.ultimate.plugins.sifa.SifaBuilder.construct(SifaBuilder.java:96) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.SifaRunner.(SifaRunner.java:98) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleSifa.construct(IpTcStrategyModuleSifa.java:68) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getOrConstruct(IpTcStrategyModuleBase.java:101) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getInterpolantComputationStatus(IpTcStrategyModuleBase.java:77) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.tryExecuteInterpolantGenerator(AutomatonFreeRefinementEngine.java:267) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.generateProof(AutomatonFreeRefinementEngine.java:148) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.executeStrategy(AutomatonFreeRefinementEngine.java:137) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.(AutomatonFreeRefinementEngine.java:85) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.TraceAbstractionRefinementEngine.(TraceAbstractionRefinementEngine.java:82) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.BasicCegarLoop.isCounterexampleFeasible(BasicCegarLoop.java:337) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterate(AbstractCegarLoop.java:431) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.startCegar(AbstractCegarLoop.java:366) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.runCegar(AbstractCegarLoop.java:348) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.executeCegarLoop(TraceAbstractionStarter.java:415) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseProgram(TraceAbstractionStarter.java:302) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseSequentialProgram(TraceAbstractionStarter.java:262) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.runCegarLoops(TraceAbstractionStarter.java:175) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.(TraceAbstractionStarter.java:154) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver.finish(TraceAbstractionObserver.java:124) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runObserver(PluginConnector.java:167) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runTool(PluginConnector.java:150) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.run(PluginConnector.java:127) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.executePluginConnector(ToolchainWalker.java:233) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.processPlugin(ToolchainWalker.java:227) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walkUnprotected(ToolchainWalker.java:144) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walk(ToolchainWalker.java:106) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainManager$Toolchain.processToolchain(ToolchainManager.java:319) at de.uni_freiburg.informatik.ultimate.core.coreplugin.toolchain.DefaultToolchainJob.run(DefaultToolchainJob.java:145) at org.eclipse.core.internal.jobs.Worker.run(Worker.java:63) [2023-12-02 16:58:17,836 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-12-02 16:58:17,836 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 11] total 13 [2023-12-02 16:58:17,836 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1584952718] [2023-12-02 16:58:17,836 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-12-02 16:58:17,837 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2023-12-02 16:58:17,837 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 16:58:17,838 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2023-12-02 16:58:17,838 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=44, Invalid=112, Unknown=0, NotChecked=0, Total=156 [2023-12-02 16:58:17,838 INFO L87 Difference]: Start difference. First operand 32 states and 46 transitions. Second operand has 13 states, 11 states have (on average 3.5454545454545454) internal successors, (39), 13 states have internal predecessors, (39), 10 states have call successors, (11), 1 states have call predecessors, (11), 5 states have return successors, (13), 5 states have call predecessors, (13), 10 states have call successors, (13) [2023-12-02 16:58:17,967 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 16:58:17,968 INFO L93 Difference]: Finished difference Result 41 states and 63 transitions. [2023-12-02 16:58:17,968 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2023-12-02 16:58:17,969 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 11 states have (on average 3.5454545454545454) internal successors, (39), 13 states have internal predecessors, (39), 10 states have call successors, (11), 1 states have call predecessors, (11), 5 states have return successors, (13), 5 states have call predecessors, (13), 10 states have call successors, (13) Word has length 64 [2023-12-02 16:58:17,969 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 16:58:17,971 INFO L225 Difference]: With dead ends: 41 [2023-12-02 16:58:17,971 INFO L226 Difference]: Without dead ends: 37 [2023-12-02 16:58:17,972 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 141 GetRequests, 122 SyntacticMatches, 4 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 44 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=88, Invalid=184, Unknown=0, NotChecked=0, Total=272 [2023-12-02 16:58:17,972 INFO L413 NwaCegarLoop]: 10 mSDtfsCounter, 31 mSDsluCounter, 43 mSDsCounter, 0 mSdLazyCounter, 78 mSolverCounterSat, 33 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 40 SdHoareTripleChecker+Valid, 53 SdHoareTripleChecker+Invalid, 111 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 33 IncrementalHoareTripleChecker+Valid, 78 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-12-02 16:58:17,973 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [40 Valid, 53 Invalid, 111 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [33 Valid, 78 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-12-02 16:58:17,974 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 37 states. [2023-12-02 16:58:17,980 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 37 to 37. [2023-12-02 16:58:17,980 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 37 states, 24 states have (on average 1.0833333333333333) internal successors, (26), 25 states have internal predecessors, (26), 6 states have call successors, (6), 2 states have call predecessors, (6), 6 states have return successors, (27), 9 states have call predecessors, (27), 6 states have call successors, (27) [2023-12-02 16:58:17,982 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 37 states to 37 states and 59 transitions. [2023-12-02 16:58:17,982 INFO L78 Accepts]: Start accepts. Automaton has 37 states and 59 transitions. Word has length 64 [2023-12-02 16:58:17,983 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 16:58:17,983 INFO L495 AbstractCegarLoop]: Abstraction has 37 states and 59 transitions. [2023-12-02 16:58:17,983 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 11 states have (on average 3.5454545454545454) internal successors, (39), 13 states have internal predecessors, (39), 10 states have call successors, (11), 1 states have call predecessors, (11), 5 states have return successors, (13), 5 states have call predecessors, (13), 10 states have call successors, (13) [2023-12-02 16:58:17,983 INFO L276 IsEmpty]: Start isEmpty. Operand 37 states and 59 transitions. [2023-12-02 16:58:17,989 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 175 [2023-12-02 16:58:17,989 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 16:58:17,990 INFO L195 NwaCegarLoop]: trace histogram [25, 25, 21, 12, 12, 12, 12, 12, 12, 12, 9, 4, 1, 1, 1, 1, 1, 1] [2023-12-02 16:58:17,995 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2023-12-02 16:58:18,192 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 16:58:18,192 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 16:58:18,193 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 16:58:18,193 INFO L85 PathProgramCache]: Analyzing trace with hash -1317092454, now seen corresponding path program 5 times [2023-12-02 16:58:18,193 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 16:58:18,193 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1616917486] [2023-12-02 16:58:18,193 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 16:58:18,193 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 16:58:18,232 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 16:58:18,504 INFO L134 CoverageAnalysis]: Checked inductivity of 1674 backedges. 74 proven. 472 refuted. 0 times theorem prover too weak. 1128 trivial. 0 not checked. [2023-12-02 16:58:18,504 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 16:58:18,504 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1616917486] [2023-12-02 16:58:18,504 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1616917486] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-02 16:58:18,504 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [164355579] [2023-12-02 16:58:18,505 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-12-02 16:58:18,505 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 16:58:18,505 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 16:58:18,506 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 16:58:18,508 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2023-12-02 16:58:18,594 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 11 check-sat command(s) [2023-12-02 16:58:18,595 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-02 16:58:18,596 INFO L262 TraceCheckSpWp]: Trace formula consists of 240 conjuncts, 10 conjunts are in the unsatisfiable core [2023-12-02 16:58:18,602 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 16:58:18,683 INFO L134 CoverageAnalysis]: Checked inductivity of 1674 backedges. 609 proven. 67 refuted. 0 times theorem prover too weak. 998 trivial. 0 not checked. [2023-12-02 16:58:18,684 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 16:58:19,448 INFO L134 CoverageAnalysis]: Checked inductivity of 1674 backedges. 503 proven. 88 refuted. 0 times theorem prover too weak. 1083 trivial. 0 not checked. [2023-12-02 16:58:19,448 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [164355579] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-02 16:58:19,449 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1860192487] [2023-12-02 16:58:19,451 INFO L159 IcfgInterpreter]: Started Sifa with 15 locations of interest [2023-12-02 16:58:19,451 INFO L166 IcfgInterpreter]: Building call graph [2023-12-02 16:58:19,452 FATAL L? ?]: Ignoring exception! java.lang.IllegalArgumentException: Recursive programs are not supported. at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.topsortRelevant(CallGraph.java:132) at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.(CallGraph.java:97) at de.uni_freiburg.informatik.ultimate.lib.sifa.IcfgInterpreter.(IcfgInterpreter.java:92) at de.uni_freiburg.informatik.ultimate.plugins.sifa.SifaBuilder.construct(SifaBuilder.java:96) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.SifaRunner.(SifaRunner.java:98) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleSifa.construct(IpTcStrategyModuleSifa.java:68) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getOrConstruct(IpTcStrategyModuleBase.java:101) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getInterpolantComputationStatus(IpTcStrategyModuleBase.java:77) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.tryExecuteInterpolantGenerator(AutomatonFreeRefinementEngine.java:267) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.generateProof(AutomatonFreeRefinementEngine.java:148) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.executeStrategy(AutomatonFreeRefinementEngine.java:137) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.(AutomatonFreeRefinementEngine.java:85) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.TraceAbstractionRefinementEngine.(TraceAbstractionRefinementEngine.java:82) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.BasicCegarLoop.isCounterexampleFeasible(BasicCegarLoop.java:337) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterate(AbstractCegarLoop.java:431) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.startCegar(AbstractCegarLoop.java:366) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.runCegar(AbstractCegarLoop.java:348) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.executeCegarLoop(TraceAbstractionStarter.java:415) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseProgram(TraceAbstractionStarter.java:302) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseSequentialProgram(TraceAbstractionStarter.java:262) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.runCegarLoops(TraceAbstractionStarter.java:175) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.(TraceAbstractionStarter.java:154) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver.finish(TraceAbstractionObserver.java:124) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runObserver(PluginConnector.java:167) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runTool(PluginConnector.java:150) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.run(PluginConnector.java:127) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.executePluginConnector(ToolchainWalker.java:233) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.processPlugin(ToolchainWalker.java:227) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walkUnprotected(ToolchainWalker.java:144) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walk(ToolchainWalker.java:106) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainManager$Toolchain.processToolchain(ToolchainManager.java:319) at de.uni_freiburg.informatik.ultimate.core.coreplugin.toolchain.DefaultToolchainJob.run(DefaultToolchainJob.java:145) at org.eclipse.core.internal.jobs.Worker.run(Worker.java:63) [2023-12-02 16:58:19,452 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-12-02 16:58:19,452 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9, 11] total 17 [2023-12-02 16:58:19,452 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1237415094] [2023-12-02 16:58:19,453 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-12-02 16:58:19,453 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2023-12-02 16:58:19,454 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 16:58:19,455 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2023-12-02 16:58:19,455 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=53, Invalid=219, Unknown=0, NotChecked=0, Total=272 [2023-12-02 16:58:19,455 INFO L87 Difference]: Start difference. First operand 37 states and 59 transitions. Second operand has 17 states, 16 states have (on average 3.75) internal successors, (60), 17 states have internal predecessors, (60), 12 states have call successors, (19), 2 states have call predecessors, (19), 9 states have return successors, (26), 12 states have call predecessors, (26), 12 states have call successors, (26) [2023-12-02 16:58:19,790 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 16:58:19,790 INFO L93 Difference]: Finished difference Result 94 states and 191 transitions. [2023-12-02 16:58:19,790 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2023-12-02 16:58:19,790 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 16 states have (on average 3.75) internal successors, (60), 17 states have internal predecessors, (60), 12 states have call successors, (19), 2 states have call predecessors, (19), 9 states have return successors, (26), 12 states have call predecessors, (26), 12 states have call successors, (26) Word has length 174 [2023-12-02 16:58:19,791 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 16:58:19,793 INFO L225 Difference]: With dead ends: 94 [2023-12-02 16:58:19,793 INFO L226 Difference]: Without dead ends: 58 [2023-12-02 16:58:19,796 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 373 GetRequests, 339 SyntacticMatches, 5 SemanticMatches, 29 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 147 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=256, Invalid=674, Unknown=0, NotChecked=0, Total=930 [2023-12-02 16:58:19,797 INFO L413 NwaCegarLoop]: 14 mSDtfsCounter, 99 mSDsluCounter, 54 mSDsCounter, 0 mSdLazyCounter, 143 mSolverCounterSat, 103 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 100 SdHoareTripleChecker+Valid, 68 SdHoareTripleChecker+Invalid, 246 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 103 IncrementalHoareTripleChecker+Valid, 143 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-12-02 16:58:19,798 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [100 Valid, 68 Invalid, 246 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [103 Valid, 143 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-12-02 16:58:19,799 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 58 states. [2023-12-02 16:58:19,808 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 58 to 58. [2023-12-02 16:58:19,809 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 58 states, 40 states have (on average 1.15) internal successors, (46), 39 states have internal predecessors, (46), 10 states have call successors, (10), 7 states have call predecessors, (10), 7 states have return successors, (25), 11 states have call predecessors, (25), 10 states have call successors, (25) [2023-12-02 16:58:19,810 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 58 states to 58 states and 81 transitions. [2023-12-02 16:58:19,810 INFO L78 Accepts]: Start accepts. Automaton has 58 states and 81 transitions. Word has length 174 [2023-12-02 16:58:19,811 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 16:58:19,811 INFO L495 AbstractCegarLoop]: Abstraction has 58 states and 81 transitions. [2023-12-02 16:58:19,811 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 16 states have (on average 3.75) internal successors, (60), 17 states have internal predecessors, (60), 12 states have call successors, (19), 2 states have call predecessors, (19), 9 states have return successors, (26), 12 states have call predecessors, (26), 12 states have call successors, (26) [2023-12-02 16:58:19,811 INFO L276 IsEmpty]: Start isEmpty. Operand 58 states and 81 transitions. [2023-12-02 16:58:19,815 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 215 [2023-12-02 16:58:19,815 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 16:58:19,815 INFO L195 NwaCegarLoop]: trace histogram [31, 31, 25, 15, 15, 15, 15, 15, 15, 15, 10, 6, 1, 1, 1, 1, 1, 1] [2023-12-02 16:58:19,822 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2023-12-02 16:58:20,020 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,7 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 16:58:20,020 INFO L420 AbstractCegarLoop]: === Iteration 9 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 16:58:20,021 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 16:58:20,021 INFO L85 PathProgramCache]: Analyzing trace with hash 710224119, now seen corresponding path program 6 times [2023-12-02 16:58:20,021 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 16:58:20,021 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [282082448] [2023-12-02 16:58:20,021 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 16:58:20,021 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 16:58:20,063 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 16:58:20,407 INFO L134 CoverageAnalysis]: Checked inductivity of 2580 backedges. 108 proven. 716 refuted. 0 times theorem prover too weak. 1756 trivial. 0 not checked. [2023-12-02 16:58:20,407 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 16:58:20,407 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [282082448] [2023-12-02 16:58:20,407 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [282082448] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-02 16:58:20,407 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [605405641] [2023-12-02 16:58:20,407 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2023-12-02 16:58:20,407 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 16:58:20,408 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 16:58:20,408 INFO L229 MonitoredProcess]: Starting monitored process 8 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 16:58:20,411 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2023-12-02 16:58:20,511 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2023-12-02 16:58:20,511 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-02 16:58:20,513 INFO L262 TraceCheckSpWp]: Trace formula consists of 380 conjuncts, 22 conjunts are in the unsatisfiable core [2023-12-02 16:58:20,519 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 16:58:20,702 INFO L134 CoverageAnalysis]: Checked inductivity of 2580 backedges. 463 proven. 843 refuted. 0 times theorem prover too weak. 1274 trivial. 0 not checked. [2023-12-02 16:58:20,702 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 16:58:22,777 INFO L134 CoverageAnalysis]: Checked inductivity of 2580 backedges. 463 proven. 891 refuted. 0 times theorem prover too weak. 1226 trivial. 0 not checked. [2023-12-02 16:58:22,777 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [605405641] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-02 16:58:22,777 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1802943833] [2023-12-02 16:58:22,780 INFO L159 IcfgInterpreter]: Started Sifa with 15 locations of interest [2023-12-02 16:58:22,780 INFO L166 IcfgInterpreter]: Building call graph [2023-12-02 16:58:22,780 FATAL L? ?]: Ignoring exception! java.lang.IllegalArgumentException: Recursive programs are not supported. at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.topsortRelevant(CallGraph.java:132) at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.(CallGraph.java:97) at de.uni_freiburg.informatik.ultimate.lib.sifa.IcfgInterpreter.(IcfgInterpreter.java:92) at de.uni_freiburg.informatik.ultimate.plugins.sifa.SifaBuilder.construct(SifaBuilder.java:96) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.SifaRunner.(SifaRunner.java:98) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleSifa.construct(IpTcStrategyModuleSifa.java:68) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getOrConstruct(IpTcStrategyModuleBase.java:101) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getInterpolantComputationStatus(IpTcStrategyModuleBase.java:77) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.tryExecuteInterpolantGenerator(AutomatonFreeRefinementEngine.java:267) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.generateProof(AutomatonFreeRefinementEngine.java:148) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.executeStrategy(AutomatonFreeRefinementEngine.java:137) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.(AutomatonFreeRefinementEngine.java:85) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.TraceAbstractionRefinementEngine.(TraceAbstractionRefinementEngine.java:82) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.BasicCegarLoop.isCounterexampleFeasible(BasicCegarLoop.java:337) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterate(AbstractCegarLoop.java:431) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.startCegar(AbstractCegarLoop.java:366) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.runCegar(AbstractCegarLoop.java:348) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.executeCegarLoop(TraceAbstractionStarter.java:415) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseProgram(TraceAbstractionStarter.java:302) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseSequentialProgram(TraceAbstractionStarter.java:262) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.runCegarLoops(TraceAbstractionStarter.java:175) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.(TraceAbstractionStarter.java:154) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver.finish(TraceAbstractionObserver.java:124) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runObserver(PluginConnector.java:167) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runTool(PluginConnector.java:150) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.run(PluginConnector.java:127) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.executePluginConnector(ToolchainWalker.java:233) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.processPlugin(ToolchainWalker.java:227) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walkUnprotected(ToolchainWalker.java:144) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walk(ToolchainWalker.java:106) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainManager$Toolchain.processToolchain(ToolchainManager.java:319) at de.uni_freiburg.informatik.ultimate.core.coreplugin.toolchain.DefaultToolchainJob.run(DefaultToolchainJob.java:145) at org.eclipse.core.internal.jobs.Worker.run(Worker.java:63) [2023-12-02 16:58:22,780 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-12-02 16:58:22,781 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 15, 23] total 27 [2023-12-02 16:58:22,781 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2030996661] [2023-12-02 16:58:22,781 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-12-02 16:58:22,782 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 27 states [2023-12-02 16:58:22,782 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 16:58:22,783 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 27 interpolants. [2023-12-02 16:58:22,784 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=116, Invalid=586, Unknown=0, NotChecked=0, Total=702 [2023-12-02 16:58:22,784 INFO L87 Difference]: Start difference. First operand 58 states and 81 transitions. Second operand has 27 states, 26 states have (on average 3.1923076923076925) internal successors, (83), 27 states have internal predecessors, (83), 22 states have call successors, (24), 1 states have call predecessors, (24), 13 states have return successors, (32), 12 states have call predecessors, (32), 22 states have call successors, (32) [2023-12-02 16:58:23,180 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 16:58:23,180 INFO L93 Difference]: Finished difference Result 143 states and 262 transitions. [2023-12-02 16:58:23,181 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 30 states. [2023-12-02 16:58:23,181 INFO L78 Accepts]: Start accepts. Automaton has has 27 states, 26 states have (on average 3.1923076923076925) internal successors, (83), 27 states have internal predecessors, (83), 22 states have call successors, (24), 1 states have call predecessors, (24), 13 states have return successors, (32), 12 states have call predecessors, (32), 22 states have call successors, (32) Word has length 214 [2023-12-02 16:58:23,182 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 16:58:23,183 INFO L225 Difference]: With dead ends: 143 [2023-12-02 16:58:23,184 INFO L226 Difference]: Without dead ends: 91 [2023-12-02 16:58:23,186 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 462 GetRequests, 405 SyntacticMatches, 11 SemanticMatches, 46 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 472 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=561, Invalid=1695, Unknown=0, NotChecked=0, Total=2256 [2023-12-02 16:58:23,187 INFO L413 NwaCegarLoop]: 24 mSDtfsCounter, 160 mSDsluCounter, 99 mSDsCounter, 0 mSdLazyCounter, 266 mSolverCounterSat, 139 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 161 SdHoareTripleChecker+Valid, 123 SdHoareTripleChecker+Invalid, 405 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 139 IncrementalHoareTripleChecker+Valid, 266 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-12-02 16:58:23,187 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [161 Valid, 123 Invalid, 405 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [139 Valid, 266 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-12-02 16:58:23,188 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 91 states. [2023-12-02 16:58:23,200 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 91 to 83. [2023-12-02 16:58:23,201 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 83 states, 59 states have (on average 1.0508474576271187) internal successors, (62), 57 states have internal predecessors, (62), 15 states have call successors, (15), 12 states have call predecessors, (15), 8 states have return successors, (36), 13 states have call predecessors, (36), 15 states have call successors, (36) [2023-12-02 16:58:23,202 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 83 states to 83 states and 113 transitions. [2023-12-02 16:58:23,202 INFO L78 Accepts]: Start accepts. Automaton has 83 states and 113 transitions. Word has length 214 [2023-12-02 16:58:23,203 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 16:58:23,203 INFO L495 AbstractCegarLoop]: Abstraction has 83 states and 113 transitions. [2023-12-02 16:58:23,204 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 27 states, 26 states have (on average 3.1923076923076925) internal successors, (83), 27 states have internal predecessors, (83), 22 states have call successors, (24), 1 states have call predecessors, (24), 13 states have return successors, (32), 12 states have call predecessors, (32), 22 states have call successors, (32) [2023-12-02 16:58:23,204 INFO L276 IsEmpty]: Start isEmpty. Operand 83 states and 113 transitions. [2023-12-02 16:58:23,209 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 351 [2023-12-02 16:58:23,209 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 16:58:23,210 INFO L195 NwaCegarLoop]: trace histogram [51, 51, 41, 25, 25, 25, 25, 25, 25, 25, 16, 10, 1, 1, 1, 1, 1, 1] [2023-12-02 16:58:23,214 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2023-12-02 16:58:23,412 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,8 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 16:58:23,412 INFO L420 AbstractCegarLoop]: === Iteration 10 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 16:58:23,412 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 16:58:23,413 INFO L85 PathProgramCache]: Analyzing trace with hash -1745181955, now seen corresponding path program 7 times [2023-12-02 16:58:23,413 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 16:58:23,413 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1185798677] [2023-12-02 16:58:23,413 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 16:58:23,413 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 16:58:23,479 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 16:58:24,038 INFO L134 CoverageAnalysis]: Checked inductivity of 7120 backedges. 214 proven. 1491 refuted. 0 times theorem prover too weak. 5415 trivial. 0 not checked. [2023-12-02 16:58:24,038 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 16:58:24,039 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1185798677] [2023-12-02 16:58:24,039 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1185798677] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-02 16:58:24,039 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [705282116] [2023-12-02 16:58:24,039 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2023-12-02 16:58:24,039 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 16:58:24,039 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 16:58:24,040 INFO L229 MonitoredProcess]: Starting monitored process 9 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 16:58:24,043 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2023-12-02 16:58:24,218 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 16:58:24,222 INFO L262 TraceCheckSpWp]: Trace formula consists of 798 conjuncts, 16 conjunts are in the unsatisfiable core [2023-12-02 16:58:24,230 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 16:58:24,326 INFO L134 CoverageAnalysis]: Checked inductivity of 7120 backedges. 214 proven. 1491 refuted. 0 times theorem prover too weak. 5415 trivial. 0 not checked. [2023-12-02 16:58:24,326 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 16:58:26,313 INFO L134 CoverageAnalysis]: Checked inductivity of 7120 backedges. 214 proven. 1548 refuted. 0 times theorem prover too weak. 5358 trivial. 0 not checked. [2023-12-02 16:58:26,313 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [705282116] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-02 16:58:26,313 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [475657266] [2023-12-02 16:58:26,315 INFO L159 IcfgInterpreter]: Started Sifa with 15 locations of interest [2023-12-02 16:58:26,315 INFO L166 IcfgInterpreter]: Building call graph [2023-12-02 16:58:26,316 FATAL L? ?]: Ignoring exception! java.lang.IllegalArgumentException: Recursive programs are not supported. at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.topsortRelevant(CallGraph.java:132) at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.(CallGraph.java:97) at de.uni_freiburg.informatik.ultimate.lib.sifa.IcfgInterpreter.(IcfgInterpreter.java:92) at de.uni_freiburg.informatik.ultimate.plugins.sifa.SifaBuilder.construct(SifaBuilder.java:96) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.SifaRunner.(SifaRunner.java:98) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleSifa.construct(IpTcStrategyModuleSifa.java:68) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getOrConstruct(IpTcStrategyModuleBase.java:101) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getInterpolantComputationStatus(IpTcStrategyModuleBase.java:77) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.tryExecuteInterpolantGenerator(AutomatonFreeRefinementEngine.java:267) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.generateProof(AutomatonFreeRefinementEngine.java:148) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.executeStrategy(AutomatonFreeRefinementEngine.java:137) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.(AutomatonFreeRefinementEngine.java:85) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.TraceAbstractionRefinementEngine.(TraceAbstractionRefinementEngine.java:82) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.BasicCegarLoop.isCounterexampleFeasible(BasicCegarLoop.java:337) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterate(AbstractCegarLoop.java:431) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.startCegar(AbstractCegarLoop.java:366) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.runCegar(AbstractCegarLoop.java:348) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.executeCegarLoop(TraceAbstractionStarter.java:415) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseProgram(TraceAbstractionStarter.java:302) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseSequentialProgram(TraceAbstractionStarter.java:262) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.runCegarLoops(TraceAbstractionStarter.java:175) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.(TraceAbstractionStarter.java:154) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver.finish(TraceAbstractionObserver.java:124) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runObserver(PluginConnector.java:167) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runTool(PluginConnector.java:150) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.run(PluginConnector.java:127) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.executePluginConnector(ToolchainWalker.java:233) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.processPlugin(ToolchainWalker.java:227) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walkUnprotected(ToolchainWalker.java:144) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walk(ToolchainWalker.java:106) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainManager$Toolchain.processToolchain(ToolchainManager.java:319) at de.uni_freiburg.informatik.ultimate.core.coreplugin.toolchain.DefaultToolchainJob.run(DefaultToolchainJob.java:145) at org.eclipse.core.internal.jobs.Worker.run(Worker.java:63) [2023-12-02 16:58:26,316 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-12-02 16:58:26,317 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11, 17] total 19 [2023-12-02 16:58:26,317 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [232824149] [2023-12-02 16:58:26,317 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-12-02 16:58:26,318 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2023-12-02 16:58:26,318 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 16:58:26,319 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2023-12-02 16:58:26,320 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=92, Invalid=250, Unknown=0, NotChecked=0, Total=342 [2023-12-02 16:58:26,320 INFO L87 Difference]: Start difference. First operand 83 states and 113 transitions. Second operand has 19 states, 17 states have (on average 3.3529411764705883) internal successors, (57), 19 states have internal predecessors, (57), 16 states have call successors, (17), 1 states have call predecessors, (17), 8 states have return successors, (22), 8 states have call predecessors, (22), 16 states have call successors, (22) [2023-12-02 16:58:26,461 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 16:58:26,461 INFO L93 Difference]: Finished difference Result 92 states and 132 transitions. [2023-12-02 16:58:26,461 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2023-12-02 16:58:26,462 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 17 states have (on average 3.3529411764705883) internal successors, (57), 19 states have internal predecessors, (57), 16 states have call successors, (17), 1 states have call predecessors, (17), 8 states have return successors, (22), 8 states have call predecessors, (22), 16 states have call successors, (22) Word has length 350 [2023-12-02 16:58:26,463 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 16:58:26,465 INFO L225 Difference]: With dead ends: 92 [2023-12-02 16:58:26,465 INFO L226 Difference]: Without dead ends: 88 [2023-12-02 16:58:26,465 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 722 GetRequests, 691 SyntacticMatches, 7 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 140 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=211, Invalid=439, Unknown=0, NotChecked=0, Total=650 [2023-12-02 16:58:26,466 INFO L413 NwaCegarLoop]: 10 mSDtfsCounter, 27 mSDsluCounter, 61 mSDsCounter, 0 mSdLazyCounter, 94 mSolverCounterSat, 19 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 39 SdHoareTripleChecker+Valid, 71 SdHoareTripleChecker+Invalid, 113 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 19 IncrementalHoareTripleChecker+Valid, 94 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-12-02 16:58:26,467 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [39 Valid, 71 Invalid, 113 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [19 Valid, 94 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-12-02 16:58:26,467 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 88 states. [2023-12-02 16:58:26,478 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 88 to 88. [2023-12-02 16:58:26,479 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 88 states, 62 states have (on average 1.0483870967741935) internal successors, (65), 60 states have internal predecessors, (65), 16 states have call successors, (16), 12 states have call predecessors, (16), 9 states have return successors, (45), 15 states have call predecessors, (45), 16 states have call successors, (45) [2023-12-02 16:58:26,480 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 88 states to 88 states and 126 transitions. [2023-12-02 16:58:26,481 INFO L78 Accepts]: Start accepts. Automaton has 88 states and 126 transitions. Word has length 350 [2023-12-02 16:58:26,481 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 16:58:26,482 INFO L495 AbstractCegarLoop]: Abstraction has 88 states and 126 transitions. [2023-12-02 16:58:26,482 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 17 states have (on average 3.3529411764705883) internal successors, (57), 19 states have internal predecessors, (57), 16 states have call successors, (17), 1 states have call predecessors, (17), 8 states have return successors, (22), 8 states have call predecessors, (22), 16 states have call successors, (22) [2023-12-02 16:58:26,482 INFO L276 IsEmpty]: Start isEmpty. Operand 88 states and 126 transitions. [2023-12-02 16:58:26,495 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 528 [2023-12-02 16:58:26,495 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 16:58:26,495 INFO L195 NwaCegarLoop]: trace histogram [77, 77, 62, 38, 38, 38, 38, 38, 38, 38, 24, 15, 1, 1, 1, 1, 1, 1] [2023-12-02 16:58:26,501 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2023-12-02 16:58:26,701 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2023-12-02 16:58:26,702 INFO L420 AbstractCegarLoop]: === Iteration 11 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 16:58:26,702 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 16:58:26,702 INFO L85 PathProgramCache]: Analyzing trace with hash 1843792464, now seen corresponding path program 8 times [2023-12-02 16:58:26,703 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 16:58:26,703 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1515231677] [2023-12-02 16:58:26,703 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 16:58:26,703 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 16:58:26,789 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 16:58:27,516 INFO L134 CoverageAnalysis]: Checked inductivity of 16407 backedges. 421 proven. 2654 refuted. 0 times theorem prover too weak. 13332 trivial. 0 not checked. [2023-12-02 16:58:27,516 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 16:58:27,516 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1515231677] [2023-12-02 16:58:27,516 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1515231677] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-02 16:58:27,516 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1993376546] [2023-12-02 16:58:27,516 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-12-02 16:58:27,516 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 16:58:27,517 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 16:58:27,517 INFO L229 MonitoredProcess]: Starting monitored process 10 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 16:58:27,518 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2023-12-02 16:58:27,709 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 23 check-sat command(s) [2023-12-02 16:58:27,709 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-02 16:58:27,712 INFO L262 TraceCheckSpWp]: Trace formula consists of 468 conjuncts, 12 conjunts are in the unsatisfiable core [2023-12-02 16:58:27,720 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 16:58:27,806 INFO L134 CoverageAnalysis]: Checked inductivity of 16407 backedges. 1608 proven. 274 refuted. 0 times theorem prover too weak. 14525 trivial. 0 not checked. [2023-12-02 16:58:27,807 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 16:58:29,001 INFO L134 CoverageAnalysis]: Checked inductivity of 16407 backedges. 1608 proven. 308 refuted. 0 times theorem prover too weak. 14491 trivial. 0 not checked. [2023-12-02 16:58:29,001 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1993376546] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-02 16:58:29,001 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [876472921] [2023-12-02 16:58:29,003 INFO L159 IcfgInterpreter]: Started Sifa with 15 locations of interest [2023-12-02 16:58:29,004 INFO L166 IcfgInterpreter]: Building call graph [2023-12-02 16:58:29,004 FATAL L? ?]: Ignoring exception! java.lang.IllegalArgumentException: Recursive programs are not supported. at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.topsortRelevant(CallGraph.java:132) at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.(CallGraph.java:97) at de.uni_freiburg.informatik.ultimate.lib.sifa.IcfgInterpreter.(IcfgInterpreter.java:92) at de.uni_freiburg.informatik.ultimate.plugins.sifa.SifaBuilder.construct(SifaBuilder.java:96) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.SifaRunner.(SifaRunner.java:98) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleSifa.construct(IpTcStrategyModuleSifa.java:68) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getOrConstruct(IpTcStrategyModuleBase.java:101) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getInterpolantComputationStatus(IpTcStrategyModuleBase.java:77) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.tryExecuteInterpolantGenerator(AutomatonFreeRefinementEngine.java:267) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.generateProof(AutomatonFreeRefinementEngine.java:148) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.executeStrategy(AutomatonFreeRefinementEngine.java:137) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.(AutomatonFreeRefinementEngine.java:85) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.TraceAbstractionRefinementEngine.(TraceAbstractionRefinementEngine.java:82) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.BasicCegarLoop.isCounterexampleFeasible(BasicCegarLoop.java:337) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterate(AbstractCegarLoop.java:431) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.startCegar(AbstractCegarLoop.java:366) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.runCegar(AbstractCegarLoop.java:348) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.executeCegarLoop(TraceAbstractionStarter.java:415) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseProgram(TraceAbstractionStarter.java:302) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseSequentialProgram(TraceAbstractionStarter.java:262) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.runCegarLoops(TraceAbstractionStarter.java:175) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.(TraceAbstractionStarter.java:154) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver.finish(TraceAbstractionObserver.java:124) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runObserver(PluginConnector.java:167) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runTool(PluginConnector.java:150) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.run(PluginConnector.java:127) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.executePluginConnector(ToolchainWalker.java:233) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.processPlugin(ToolchainWalker.java:227) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walkUnprotected(ToolchainWalker.java:144) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walk(ToolchainWalker.java:106) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainManager$Toolchain.processToolchain(ToolchainManager.java:319) at de.uni_freiburg.informatik.ultimate.core.coreplugin.toolchain.DefaultToolchainJob.run(DefaultToolchainJob.java:145) at org.eclipse.core.internal.jobs.Worker.run(Worker.java:63) [2023-12-02 16:58:29,004 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-12-02 16:58:29,005 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 9, 13] total 18 [2023-12-02 16:58:29,005 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [905276423] [2023-12-02 16:58:29,005 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-12-02 16:58:29,007 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2023-12-02 16:58:29,007 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 16:58:29,008 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2023-12-02 16:58:29,008 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=99, Invalid=207, Unknown=0, NotChecked=0, Total=306 [2023-12-02 16:58:29,008 INFO L87 Difference]: Start difference. First operand 88 states and 126 transitions. Second operand has 18 states, 17 states have (on average 3.4705882352941178) internal successors, (59), 18 states have internal predecessors, (59), 14 states have call successors, (20), 1 states have call predecessors, (20), 10 states have return successors, (30), 14 states have call predecessors, (30), 14 states have call successors, (30) [2023-12-02 16:58:29,143 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 16:58:29,143 INFO L93 Difference]: Finished difference Result 97 states and 147 transitions. [2023-12-02 16:58:29,143 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2023-12-02 16:58:29,143 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 17 states have (on average 3.4705882352941178) internal successors, (59), 18 states have internal predecessors, (59), 14 states have call successors, (20), 1 states have call predecessors, (20), 10 states have return successors, (30), 14 states have call predecessors, (30), 14 states have call successors, (30) Word has length 527 [2023-12-02 16:58:29,145 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 16:58:29,146 INFO L225 Difference]: With dead ends: 97 [2023-12-02 16:58:29,146 INFO L226 Difference]: Without dead ends: 93 [2023-12-02 16:58:29,147 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 1080 GetRequests, 1049 SyntacticMatches, 6 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 151 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=252, Invalid=450, Unknown=0, NotChecked=0, Total=702 [2023-12-02 16:58:29,148 INFO L413 NwaCegarLoop]: 11 mSDtfsCounter, 22 mSDsluCounter, 60 mSDsCounter, 0 mSdLazyCounter, 94 mSolverCounterSat, 19 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 25 SdHoareTripleChecker+Valid, 71 SdHoareTripleChecker+Invalid, 113 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 19 IncrementalHoareTripleChecker+Valid, 94 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-12-02 16:58:29,148 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [25 Valid, 71 Invalid, 113 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [19 Valid, 94 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-12-02 16:58:29,149 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 93 states. [2023-12-02 16:58:29,160 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 93 to 93. [2023-12-02 16:58:29,160 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 93 states, 65 states have (on average 1.0461538461538462) internal successors, (68), 63 states have internal predecessors, (68), 17 states have call successors, (17), 12 states have call predecessors, (17), 10 states have return successors, (56), 17 states have call predecessors, (56), 17 states have call successors, (56) [2023-12-02 16:58:29,162 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 93 states to 93 states and 141 transitions. [2023-12-02 16:58:29,162 INFO L78 Accepts]: Start accepts. Automaton has 93 states and 141 transitions. Word has length 527 [2023-12-02 16:58:29,163 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 16:58:29,163 INFO L495 AbstractCegarLoop]: Abstraction has 93 states and 141 transitions. [2023-12-02 16:58:29,164 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 18 states, 17 states have (on average 3.4705882352941178) internal successors, (59), 18 states have internal predecessors, (59), 14 states have call successors, (20), 1 states have call predecessors, (20), 10 states have return successors, (30), 14 states have call predecessors, (30), 14 states have call successors, (30) [2023-12-02 16:58:29,164 INFO L276 IsEmpty]: Start isEmpty. Operand 93 states and 141 transitions. [2023-12-02 16:58:29,173 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1059 [2023-12-02 16:58:29,174 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 16:58:29,174 INFO L195 NwaCegarLoop]: trace histogram [155, 155, 125, 77, 77, 77, 77, 77, 77, 77, 48, 30, 1, 1, 1, 1, 1, 1] [2023-12-02 16:58:29,179 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2023-12-02 16:58:29,374 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,10 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 16:58:29,375 INFO L420 AbstractCegarLoop]: === Iteration 12 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 16:58:29,375 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 16:58:29,375 INFO L85 PathProgramCache]: Analyzing trace with hash 1954860697, now seen corresponding path program 9 times [2023-12-02 16:58:29,376 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 16:58:29,376 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1534466087] [2023-12-02 16:58:29,376 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 16:58:29,376 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 16:58:29,607 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 16:58:31,330 INFO L134 CoverageAnalysis]: Checked inductivity of 67194 backedges. 2138 proven. 3877 refuted. 0 times theorem prover too weak. 61179 trivial. 0 not checked. [2023-12-02 16:58:31,331 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 16:58:31,331 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1534466087] [2023-12-02 16:58:31,331 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1534466087] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-02 16:58:31,331 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [252372221] [2023-12-02 16:58:31,331 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2023-12-02 16:58:31,331 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 16:58:31,331 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 16:58:31,332 INFO L229 MonitoredProcess]: Starting monitored process 11 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 16:58:31,333 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2023-12-02 16:58:31,672 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2023-12-02 16:58:31,672 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-02 16:58:31,678 INFO L262 TraceCheckSpWp]: Trace formula consists of 1882 conjuncts, 30 conjunts are in the unsatisfiable core [2023-12-02 16:58:31,692 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 16:58:31,957 INFO L134 CoverageAnalysis]: Checked inductivity of 67194 backedges. 35642 proven. 3346 refuted. 0 times theorem prover too weak. 28206 trivial. 0 not checked. [2023-12-02 16:58:31,957 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 16:58:37,715 INFO L134 CoverageAnalysis]: Checked inductivity of 67194 backedges. 2436 proven. 9724 refuted. 0 times theorem prover too weak. 55034 trivial. 0 not checked. [2023-12-02 16:58:37,715 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [252372221] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-02 16:58:37,715 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [2059984373] [2023-12-02 16:58:37,717 INFO L159 IcfgInterpreter]: Started Sifa with 15 locations of interest [2023-12-02 16:58:37,717 INFO L166 IcfgInterpreter]: Building call graph [2023-12-02 16:58:37,717 FATAL L? ?]: Ignoring exception! java.lang.IllegalArgumentException: Recursive programs are not supported. at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.topsortRelevant(CallGraph.java:132) at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.(CallGraph.java:97) at de.uni_freiburg.informatik.ultimate.lib.sifa.IcfgInterpreter.(IcfgInterpreter.java:92) at de.uni_freiburg.informatik.ultimate.plugins.sifa.SifaBuilder.construct(SifaBuilder.java:96) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.SifaRunner.(SifaRunner.java:98) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleSifa.construct(IpTcStrategyModuleSifa.java:68) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getOrConstruct(IpTcStrategyModuleBase.java:101) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getInterpolantComputationStatus(IpTcStrategyModuleBase.java:77) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.tryExecuteInterpolantGenerator(AutomatonFreeRefinementEngine.java:267) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.generateProof(AutomatonFreeRefinementEngine.java:148) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.executeStrategy(AutomatonFreeRefinementEngine.java:137) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.(AutomatonFreeRefinementEngine.java:85) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.TraceAbstractionRefinementEngine.(TraceAbstractionRefinementEngine.java:82) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.BasicCegarLoop.isCounterexampleFeasible(BasicCegarLoop.java:337) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterate(AbstractCegarLoop.java:431) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.startCegar(AbstractCegarLoop.java:366) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.runCegar(AbstractCegarLoop.java:348) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.executeCegarLoop(TraceAbstractionStarter.java:415) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseProgram(TraceAbstractionStarter.java:302) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseSequentialProgram(TraceAbstractionStarter.java:262) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.runCegarLoops(TraceAbstractionStarter.java:175) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.(TraceAbstractionStarter.java:154) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver.finish(TraceAbstractionObserver.java:124) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runObserver(PluginConnector.java:167) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runTool(PluginConnector.java:150) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.run(PluginConnector.java:127) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.executePluginConnector(ToolchainWalker.java:233) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.processPlugin(ToolchainWalker.java:227) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walkUnprotected(ToolchainWalker.java:144) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walk(ToolchainWalker.java:106) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainManager$Toolchain.processToolchain(ToolchainManager.java:319) at de.uni_freiburg.informatik.ultimate.core.coreplugin.toolchain.DefaultToolchainJob.run(DefaultToolchainJob.java:145) at org.eclipse.core.internal.jobs.Worker.run(Worker.java:63) [2023-12-02 16:58:37,718 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-12-02 16:58:37,718 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 19, 31] total 39 [2023-12-02 16:58:37,719 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1543978955] [2023-12-02 16:58:37,719 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-12-02 16:58:37,721 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 39 states [2023-12-02 16:58:37,721 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 16:58:37,721 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 39 interpolants. [2023-12-02 16:58:37,722 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=243, Invalid=1239, Unknown=0, NotChecked=0, Total=1482 [2023-12-02 16:58:37,722 INFO L87 Difference]: Start difference. First operand 93 states and 141 transitions. Second operand has 39 states, 38 states have (on average 3.1578947368421053) internal successors, (120), 39 states have internal predecessors, (120), 32 states have call successors, (38), 2 states have call predecessors, (38), 18 states have return successors, (53), 19 states have call predecessors, (53), 32 states have call successors, (53) [2023-12-02 16:58:38,557 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 16:58:38,557 INFO L93 Difference]: Finished difference Result 249 states and 547 transitions. [2023-12-02 16:58:38,557 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 45 states. [2023-12-02 16:58:38,558 INFO L78 Accepts]: Start accepts. Automaton has has 39 states, 38 states have (on average 3.1578947368421053) internal successors, (120), 39 states have internal predecessors, (120), 32 states have call successors, (38), 2 states have call predecessors, (38), 18 states have return successors, (53), 19 states have call predecessors, (53), 32 states have call successors, (53) Word has length 1058 [2023-12-02 16:58:38,559 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 16:58:38,561 INFO L225 Difference]: With dead ends: 249 [2023-12-02 16:58:38,562 INFO L226 Difference]: Without dead ends: 146 [2023-12-02 16:58:38,565 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 2167 GetRequests, 2081 SyntacticMatches, 15 SemanticMatches, 71 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1508 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=1224, Invalid=4032, Unknown=0, NotChecked=0, Total=5256 [2023-12-02 16:58:38,566 INFO L413 NwaCegarLoop]: 42 mSDtfsCounter, 276 mSDsluCounter, 160 mSDsCounter, 0 mSdLazyCounter, 602 mSolverCounterSat, 252 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 277 SdHoareTripleChecker+Valid, 202 SdHoareTripleChecker+Invalid, 854 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 252 IncrementalHoareTripleChecker+Valid, 602 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2023-12-02 16:58:38,566 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [277 Valid, 202 Invalid, 854 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [252 Valid, 602 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2023-12-02 16:58:38,567 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 146 states. [2023-12-02 16:58:38,582 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 146 to 121. [2023-12-02 16:58:38,583 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 121 states, 86 states have (on average 1.0348837209302326) internal successors, (89), 84 states have internal predecessors, (89), 24 states have call successors, (24), 19 states have call predecessors, (24), 10 states have return successors, (57), 17 states have call predecessors, (57), 24 states have call successors, (57) [2023-12-02 16:58:38,585 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 121 states to 121 states and 170 transitions. [2023-12-02 16:58:38,585 INFO L78 Accepts]: Start accepts. Automaton has 121 states and 170 transitions. Word has length 1058 [2023-12-02 16:58:38,586 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 16:58:38,586 INFO L495 AbstractCegarLoop]: Abstraction has 121 states and 170 transitions. [2023-12-02 16:58:38,587 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 39 states, 38 states have (on average 3.1578947368421053) internal successors, (120), 39 states have internal predecessors, (120), 32 states have call successors, (38), 2 states have call predecessors, (38), 18 states have return successors, (53), 19 states have call predecessors, (53), 32 states have call successors, (53) [2023-12-02 16:58:38,587 INFO L276 IsEmpty]: Start isEmpty. Operand 121 states and 170 transitions. [2023-12-02 16:58:38,595 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1032 [2023-12-02 16:58:38,595 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 16:58:38,596 INFO L195 NwaCegarLoop]: trace histogram [151, 151, 122, 75, 75, 75, 75, 75, 75, 75, 47, 29, 1, 1, 1, 1, 1, 1] [2023-12-02 16:58:38,603 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Ended with exit code 0 [2023-12-02 16:58:38,796 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11,11 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 16:58:38,797 INFO L420 AbstractCegarLoop]: === Iteration 13 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 16:58:38,797 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 16:58:38,797 INFO L85 PathProgramCache]: Analyzing trace with hash 1114434405, now seen corresponding path program 10 times [2023-12-02 16:58:38,797 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 16:58:38,797 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [976214262] [2023-12-02 16:58:38,797 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 16:58:38,798 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 16:58:38,933 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 16:58:40,770 INFO L134 CoverageAnalysis]: Checked inductivity of 63781 backedges. 3494 proven. 2360 refuted. 0 times theorem prover too weak. 57927 trivial. 0 not checked. [2023-12-02 16:58:40,771 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 16:58:40,771 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [976214262] [2023-12-02 16:58:40,771 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [976214262] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-02 16:58:40,771 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1216324322] [2023-12-02 16:58:40,771 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2023-12-02 16:58:40,771 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 16:58:40,771 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 16:58:40,772 INFO L229 MonitoredProcess]: Starting monitored process 12 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 16:58:40,775 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2023-12-02 16:58:41,258 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 16:58:41,266 INFO L262 TraceCheckSpWp]: Trace formula consists of 2310 conjuncts, 20 conjunts are in the unsatisfiable core [2023-12-02 16:58:41,283 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 16:58:41,419 INFO L134 CoverageAnalysis]: Checked inductivity of 63781 backedges. 4251 proven. 3172 refuted. 0 times theorem prover too weak. 56358 trivial. 0 not checked. [2023-12-02 16:58:41,419 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 16:58:45,259 INFO L134 CoverageAnalysis]: Checked inductivity of 63781 backedges. 4251 proven. 3264 refuted. 0 times theorem prover too weak. 56266 trivial. 0 not checked. [2023-12-02 16:58:45,259 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1216324322] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-02 16:58:45,259 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1108888020] [2023-12-02 16:58:45,262 INFO L159 IcfgInterpreter]: Started Sifa with 15 locations of interest [2023-12-02 16:58:45,262 INFO L166 IcfgInterpreter]: Building call graph [2023-12-02 16:58:45,262 FATAL L? ?]: Ignoring exception! java.lang.IllegalArgumentException: Recursive programs are not supported. at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.topsortRelevant(CallGraph.java:132) at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.(CallGraph.java:97) at de.uni_freiburg.informatik.ultimate.lib.sifa.IcfgInterpreter.(IcfgInterpreter.java:92) at de.uni_freiburg.informatik.ultimate.plugins.sifa.SifaBuilder.construct(SifaBuilder.java:96) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.SifaRunner.(SifaRunner.java:98) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleSifa.construct(IpTcStrategyModuleSifa.java:68) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getOrConstruct(IpTcStrategyModuleBase.java:101) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getInterpolantComputationStatus(IpTcStrategyModuleBase.java:77) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.tryExecuteInterpolantGenerator(AutomatonFreeRefinementEngine.java:267) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.generateProof(AutomatonFreeRefinementEngine.java:148) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.executeStrategy(AutomatonFreeRefinementEngine.java:137) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.(AutomatonFreeRefinementEngine.java:85) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.TraceAbstractionRefinementEngine.(TraceAbstractionRefinementEngine.java:82) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.BasicCegarLoop.isCounterexampleFeasible(BasicCegarLoop.java:337) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterate(AbstractCegarLoop.java:431) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.startCegar(AbstractCegarLoop.java:366) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.runCegar(AbstractCegarLoop.java:348) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.executeCegarLoop(TraceAbstractionStarter.java:415) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseProgram(TraceAbstractionStarter.java:302) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseSequentialProgram(TraceAbstractionStarter.java:262) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.runCegarLoops(TraceAbstractionStarter.java:175) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.(TraceAbstractionStarter.java:154) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver.finish(TraceAbstractionObserver.java:124) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runObserver(PluginConnector.java:167) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runTool(PluginConnector.java:150) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.run(PluginConnector.java:127) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.executePluginConnector(ToolchainWalker.java:233) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.processPlugin(ToolchainWalker.java:227) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walkUnprotected(ToolchainWalker.java:144) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walk(ToolchainWalker.java:106) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainManager$Toolchain.processToolchain(ToolchainManager.java:319) at de.uni_freiburg.informatik.ultimate.core.coreplugin.toolchain.DefaultToolchainJob.run(DefaultToolchainJob.java:145) at org.eclipse.core.internal.jobs.Worker.run(Worker.java:63) [2023-12-02 16:58:45,263 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-12-02 16:58:45,263 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 13, 21] total 25 [2023-12-02 16:58:45,264 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [174774686] [2023-12-02 16:58:45,264 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-12-02 16:58:45,266 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 25 states [2023-12-02 16:58:45,266 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 16:58:45,267 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2023-12-02 16:58:45,267 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=169, Invalid=431, Unknown=0, NotChecked=0, Total=600 [2023-12-02 16:58:45,267 INFO L87 Difference]: Start difference. First operand 121 states and 170 transitions. Second operand has 25 states, 24 states have (on average 3.125) internal successors, (75), 25 states have internal predecessors, (75), 20 states have call successors, (25), 1 states have call predecessors, (25), 10 states have return successors, (33), 14 states have call predecessors, (33), 20 states have call successors, (33) [2023-12-02 16:58:45,434 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 16:58:45,434 INFO L93 Difference]: Finished difference Result 139 states and 193 transitions. [2023-12-02 16:58:45,435 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2023-12-02 16:58:45,435 INFO L78 Accepts]: Start accepts. Automaton has has 25 states, 24 states have (on average 3.125) internal successors, (75), 25 states have internal predecessors, (75), 20 states have call successors, (25), 1 states have call predecessors, (25), 10 states have return successors, (33), 14 states have call predecessors, (33), 20 states have call successors, (33) Word has length 1031 [2023-12-02 16:58:45,437 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 16:58:45,438 INFO L225 Difference]: With dead ends: 139 [2023-12-02 16:58:45,438 INFO L226 Difference]: Without dead ends: 132 [2023-12-02 16:58:45,439 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 2087 GetRequests, 2046 SyntacticMatches, 10 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 377 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=360, Invalid=696, Unknown=0, NotChecked=0, Total=1056 [2023-12-02 16:58:45,440 INFO L413 NwaCegarLoop]: 37 mSDtfsCounter, 28 mSDsluCounter, 96 mSDsCounter, 0 mSdLazyCounter, 201 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 30 SdHoareTripleChecker+Valid, 133 SdHoareTripleChecker+Invalid, 208 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 201 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-12-02 16:58:45,440 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [30 Valid, 133 Invalid, 208 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 201 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-12-02 16:58:45,440 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 132 states. [2023-12-02 16:58:45,449 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 132 to 124. [2023-12-02 16:58:45,450 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 124 states, 88 states have (on average 1.0340909090909092) internal successors, (91), 86 states have internal predecessors, (91), 24 states have call successors, (24), 19 states have call predecessors, (24), 11 states have return successors, (50), 18 states have call predecessors, (50), 24 states have call successors, (50) [2023-12-02 16:58:45,451 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 124 states to 124 states and 165 transitions. [2023-12-02 16:58:45,451 INFO L78 Accepts]: Start accepts. Automaton has 124 states and 165 transitions. Word has length 1031 [2023-12-02 16:58:45,453 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 16:58:45,453 INFO L495 AbstractCegarLoop]: Abstraction has 124 states and 165 transitions. [2023-12-02 16:58:45,453 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 25 states, 24 states have (on average 3.125) internal successors, (75), 25 states have internal predecessors, (75), 20 states have call successors, (25), 1 states have call predecessors, (25), 10 states have return successors, (33), 14 states have call predecessors, (33), 20 states have call successors, (33) [2023-12-02 16:58:45,453 INFO L276 IsEmpty]: Start isEmpty. Operand 124 states and 165 transitions. [2023-12-02 16:58:45,459 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 746 [2023-12-02 16:58:45,459 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 16:58:45,459 INFO L195 NwaCegarLoop]: trace histogram [109, 109, 88, 54, 54, 54, 54, 54, 54, 54, 34, 21, 1, 1, 1, 1, 1, 1] [2023-12-02 16:58:45,466 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Ended with exit code 0 [2023-12-02 16:58:45,660 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable12,12 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 16:58:45,660 INFO L420 AbstractCegarLoop]: === Iteration 14 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 16:58:45,660 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 16:58:45,660 INFO L85 PathProgramCache]: Analyzing trace with hash -211170596, now seen corresponding path program 11 times [2023-12-02 16:58:45,661 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 16:58:45,661 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1132602840] [2023-12-02 16:58:45,661 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 16:58:45,661 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 16:58:45,761 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 16:58:59,306 INFO L134 CoverageAnalysis]: Checked inductivity of 33096 backedges. 0 proven. 10899 refuted. 0 times theorem prover too weak. 22197 trivial. 0 not checked. [2023-12-02 16:58:59,306 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 16:58:59,306 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1132602840] [2023-12-02 16:58:59,306 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1132602840] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-02 16:58:59,307 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2083770682] [2023-12-02 16:58:59,307 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-12-02 16:58:59,307 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 16:58:59,307 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 16:58:59,308 INFO L229 MonitoredProcess]: Starting monitored process 13 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 16:58:59,308 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2023-12-02 16:58:59,906 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 93 check-sat command(s) [2023-12-02 16:58:59,906 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-02 16:58:59,917 INFO L262 TraceCheckSpWp]: Trace formula consists of 1675 conjuncts, 439 conjunts are in the unsatisfiable core [2023-12-02 16:58:59,927 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 16:59:00,573 INFO L134 CoverageAnalysis]: Checked inductivity of 33096 backedges. 0 proven. 10899 refuted. 0 times theorem prover too weak. 22197 trivial. 0 not checked. [2023-12-02 16:59:00,573 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 16:59:04,201 INFO L134 CoverageAnalysis]: Checked inductivity of 33096 backedges. 0 proven. 10899 refuted. 0 times theorem prover too weak. 22197 trivial. 0 not checked. [2023-12-02 16:59:04,202 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2083770682] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-02 16:59:04,202 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1873460898] [2023-12-02 16:59:04,204 INFO L159 IcfgInterpreter]: Started Sifa with 15 locations of interest [2023-12-02 16:59:04,204 INFO L166 IcfgInterpreter]: Building call graph [2023-12-02 16:59:04,204 FATAL L? ?]: Ignoring exception! java.lang.IllegalArgumentException: Recursive programs are not supported. at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.topsortRelevant(CallGraph.java:132) at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.(CallGraph.java:97) at de.uni_freiburg.informatik.ultimate.lib.sifa.IcfgInterpreter.(IcfgInterpreter.java:92) at de.uni_freiburg.informatik.ultimate.plugins.sifa.SifaBuilder.construct(SifaBuilder.java:96) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.SifaRunner.(SifaRunner.java:98) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleSifa.construct(IpTcStrategyModuleSifa.java:68) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getOrConstruct(IpTcStrategyModuleBase.java:101) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getInterpolantComputationStatus(IpTcStrategyModuleBase.java:77) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.tryExecuteInterpolantGenerator(AutomatonFreeRefinementEngine.java:267) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.generateProof(AutomatonFreeRefinementEngine.java:148) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.executeStrategy(AutomatonFreeRefinementEngine.java:137) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.(AutomatonFreeRefinementEngine.java:85) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.TraceAbstractionRefinementEngine.(TraceAbstractionRefinementEngine.java:82) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.BasicCegarLoop.isCounterexampleFeasible(BasicCegarLoop.java:337) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterate(AbstractCegarLoop.java:431) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.startCegar(AbstractCegarLoop.java:366) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.runCegar(AbstractCegarLoop.java:348) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.executeCegarLoop(TraceAbstractionStarter.java:415) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseProgram(TraceAbstractionStarter.java:302) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseSequentialProgram(TraceAbstractionStarter.java:262) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.runCegarLoops(TraceAbstractionStarter.java:175) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.(TraceAbstractionStarter.java:154) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver.finish(TraceAbstractionObserver.java:124) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runObserver(PluginConnector.java:167) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runTool(PluginConnector.java:150) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.run(PluginConnector.java:127) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.executePluginConnector(ToolchainWalker.java:233) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.processPlugin(ToolchainWalker.java:227) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walkUnprotected(ToolchainWalker.java:144) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walk(ToolchainWalker.java:106) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainManager$Toolchain.processToolchain(ToolchainManager.java:319) at de.uni_freiburg.informatik.ultimate.core.coreplugin.toolchain.DefaultToolchainJob.run(DefaultToolchainJob.java:145) at org.eclipse.core.internal.jobs.Worker.run(Worker.java:63) [2023-12-02 16:59:04,205 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-12-02 16:59:04,205 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [28, 28, 28] total 36 [2023-12-02 16:59:04,205 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1644422795] [2023-12-02 16:59:04,206 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-12-02 16:59:04,207 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 36 states [2023-12-02 16:59:04,207 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 16:59:04,208 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 36 interpolants. [2023-12-02 16:59:04,208 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=85, Invalid=1175, Unknown=0, NotChecked=0, Total=1260 [2023-12-02 16:59:04,209 INFO L87 Difference]: Start difference. First operand 124 states and 165 transitions. Second operand has 36 states, 36 states have (on average 1.1388888888888888) internal successors, (41), 19 states have internal predecessors, (41), 8 states have call successors, (9), 1 states have call predecessors, (9), 9 states have return successors, (24), 24 states have call predecessors, (24), 8 states have call successors, (24) [2023-12-02 16:59:04,527 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 16:59:04,527 INFO L93 Difference]: Finished difference Result 141 states and 189 transitions. [2023-12-02 16:59:04,527 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 28 states. [2023-12-02 16:59:04,527 INFO L78 Accepts]: Start accepts. Automaton has has 36 states, 36 states have (on average 1.1388888888888888) internal successors, (41), 19 states have internal predecessors, (41), 8 states have call successors, (9), 1 states have call predecessors, (9), 9 states have return successors, (24), 24 states have call predecessors, (24), 8 states have call successors, (24) Word has length 745 [2023-12-02 16:59:04,528 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 16:59:04,529 INFO L225 Difference]: With dead ends: 141 [2023-12-02 16:59:04,529 INFO L226 Difference]: Without dead ends: 134 [2023-12-02 16:59:04,530 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 1709 GetRequests, 1675 SyntacticMatches, 0 SemanticMatches, 34 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 86 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=85, Invalid=1175, Unknown=0, NotChecked=0, Total=1260 [2023-12-02 16:59:04,531 INFO L413 NwaCegarLoop]: 47 mSDtfsCounter, 0 mSDsluCounter, 970 mSDsCounter, 0 mSdLazyCounter, 817 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3 SdHoareTripleChecker+Valid, 1017 SdHoareTripleChecker+Invalid, 817 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 817 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2023-12-02 16:59:04,531 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [3 Valid, 1017 Invalid, 817 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 817 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2023-12-02 16:59:04,532 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 134 states. [2023-12-02 16:59:04,539 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 134 to 131. [2023-12-02 16:59:04,540 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 131 states, 92 states have (on average 1.0326086956521738) internal successors, (95), 90 states have internal predecessors, (95), 26 states have call successors, (26), 19 states have call predecessors, (26), 12 states have return successors, (55), 21 states have call predecessors, (55), 26 states have call successors, (55) [2023-12-02 16:59:04,541 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 131 states to 131 states and 176 transitions. [2023-12-02 16:59:04,541 INFO L78 Accepts]: Start accepts. Automaton has 131 states and 176 transitions. Word has length 745 [2023-12-02 16:59:04,542 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 16:59:04,542 INFO L495 AbstractCegarLoop]: Abstraction has 131 states and 176 transitions. [2023-12-02 16:59:04,542 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 36 states, 36 states have (on average 1.1388888888888888) internal successors, (41), 19 states have internal predecessors, (41), 8 states have call successors, (9), 1 states have call predecessors, (9), 9 states have return successors, (24), 24 states have call predecessors, (24), 8 states have call successors, (24) [2023-12-02 16:59:04,542 INFO L276 IsEmpty]: Start isEmpty. Operand 131 states and 176 transitions. [2023-12-02 16:59:04,548 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 855 [2023-12-02 16:59:04,548 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 16:59:04,549 INFO L195 NwaCegarLoop]: trace histogram [125, 125, 101, 62, 62, 62, 62, 62, 62, 62, 39, 24, 1, 1, 1, 1, 1, 1] [2023-12-02 16:59:04,556 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Forceful destruction successful, exit code 0 [2023-12-02 16:59:04,749 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable13,13 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 16:59:04,749 INFO L420 AbstractCegarLoop]: === Iteration 15 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 16:59:04,750 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 16:59:04,750 INFO L85 PathProgramCache]: Analyzing trace with hash -2106796754, now seen corresponding path program 12 times [2023-12-02 16:59:04,750 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 16:59:04,750 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [791204565] [2023-12-02 16:59:04,750 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 16:59:04,750 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 16:59:04,825 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 16:59:05,806 INFO L134 CoverageAnalysis]: Checked inductivity of 43614 backedges. 1098 proven. 4974 refuted. 0 times theorem prover too weak. 37542 trivial. 0 not checked. [2023-12-02 16:59:05,806 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 16:59:05,806 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [791204565] [2023-12-02 16:59:05,806 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [791204565] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-02 16:59:05,806 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1481803310] [2023-12-02 16:59:05,806 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2023-12-02 16:59:05,807 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 16:59:05,807 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 16:59:05,807 INFO L229 MonitoredProcess]: Starting monitored process 14 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 16:59:05,810 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2023-12-02 16:59:06,156 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2023-12-02 16:59:06,156 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-02 16:59:06,162 INFO L262 TraceCheckSpWp]: Trace formula consists of 1519 conjuncts, 26 conjunts are in the unsatisfiable core [2023-12-02 16:59:06,171 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 16:59:06,366 INFO L134 CoverageAnalysis]: Checked inductivity of 43614 backedges. 23181 proven. 1871 refuted. 0 times theorem prover too weak. 18562 trivial. 0 not checked. [2023-12-02 16:59:06,366 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 16:59:11,011 INFO L134 CoverageAnalysis]: Checked inductivity of 43614 backedges. 2091 proven. 6674 refuted. 0 times theorem prover too weak. 34849 trivial. 0 not checked. [2023-12-02 16:59:11,011 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1481803310] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-02 16:59:11,011 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [222782088] [2023-12-02 16:59:11,012 INFO L159 IcfgInterpreter]: Started Sifa with 15 locations of interest [2023-12-02 16:59:11,013 INFO L166 IcfgInterpreter]: Building call graph [2023-12-02 16:59:11,013 FATAL L? ?]: Ignoring exception! java.lang.IllegalArgumentException: Recursive programs are not supported. at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.topsortRelevant(CallGraph.java:132) at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.(CallGraph.java:97) at de.uni_freiburg.informatik.ultimate.lib.sifa.IcfgInterpreter.(IcfgInterpreter.java:92) at de.uni_freiburg.informatik.ultimate.plugins.sifa.SifaBuilder.construct(SifaBuilder.java:96) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.SifaRunner.(SifaRunner.java:98) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleSifa.construct(IpTcStrategyModuleSifa.java:68) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getOrConstruct(IpTcStrategyModuleBase.java:101) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getInterpolantComputationStatus(IpTcStrategyModuleBase.java:77) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.tryExecuteInterpolantGenerator(AutomatonFreeRefinementEngine.java:267) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.generateProof(AutomatonFreeRefinementEngine.java:148) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.executeStrategy(AutomatonFreeRefinementEngine.java:137) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.(AutomatonFreeRefinementEngine.java:85) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.TraceAbstractionRefinementEngine.(TraceAbstractionRefinementEngine.java:82) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.BasicCegarLoop.isCounterexampleFeasible(BasicCegarLoop.java:337) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterate(AbstractCegarLoop.java:431) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.startCegar(AbstractCegarLoop.java:366) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.runCegar(AbstractCegarLoop.java:348) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.executeCegarLoop(TraceAbstractionStarter.java:415) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseProgram(TraceAbstractionStarter.java:302) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseSequentialProgram(TraceAbstractionStarter.java:262) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.runCegarLoops(TraceAbstractionStarter.java:175) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.(TraceAbstractionStarter.java:154) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver.finish(TraceAbstractionObserver.java:124) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runObserver(PluginConnector.java:167) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runTool(PluginConnector.java:150) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.run(PluginConnector.java:127) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.executePluginConnector(ToolchainWalker.java:233) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.processPlugin(ToolchainWalker.java:227) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walkUnprotected(ToolchainWalker.java:144) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walk(ToolchainWalker.java:106) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainManager$Toolchain.processToolchain(ToolchainManager.java:319) at de.uni_freiburg.informatik.ultimate.core.coreplugin.toolchain.DefaultToolchainJob.run(DefaultToolchainJob.java:145) at org.eclipse.core.internal.jobs.Worker.run(Worker.java:63) [2023-12-02 16:59:11,013 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-12-02 16:59:11,014 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 17, 27] total 36 [2023-12-02 16:59:11,014 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [119218318] [2023-12-02 16:59:11,014 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-12-02 16:59:11,015 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 36 states [2023-12-02 16:59:11,015 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 16:59:11,016 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 36 interpolants. [2023-12-02 16:59:11,016 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=232, Invalid=1028, Unknown=0, NotChecked=0, Total=1260 [2023-12-02 16:59:11,017 INFO L87 Difference]: Start difference. First operand 131 states and 176 transitions. Second operand has 36 states, 35 states have (on average 3.1714285714285713) internal successors, (111), 36 states have internal predecessors, (111), 30 states have call successors, (35), 2 states have call predecessors, (35), 17 states have return successors, (48), 17 states have call predecessors, (48), 30 states have call successors, (48) [2023-12-02 16:59:11,447 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 16:59:11,447 INFO L93 Difference]: Finished difference Result 253 states and 357 transitions. [2023-12-02 16:59:11,447 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 30 states. [2023-12-02 16:59:11,448 INFO L78 Accepts]: Start accepts. Automaton has has 36 states, 35 states have (on average 3.1714285714285713) internal successors, (111), 36 states have internal predecessors, (111), 30 states have call successors, (35), 2 states have call predecessors, (35), 17 states have return successors, (48), 17 states have call predecessors, (48), 30 states have call successors, (48) Word has length 854 [2023-12-02 16:59:11,448 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 16:59:11,449 INFO L225 Difference]: With dead ends: 253 [2023-12-02 16:59:11,449 INFO L226 Difference]: Without dead ends: 0 [2023-12-02 16:59:11,452 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 1748 GetRequests, 1682 SyntacticMatches, 13 SemanticMatches, 53 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 883 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=724, Invalid=2246, Unknown=0, NotChecked=0, Total=2970 [2023-12-02 16:59:11,452 INFO L413 NwaCegarLoop]: 40 mSDtfsCounter, 127 mSDsluCounter, 112 mSDsCounter, 0 mSdLazyCounter, 539 mSolverCounterSat, 114 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 127 SdHoareTripleChecker+Valid, 152 SdHoareTripleChecker+Invalid, 653 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 114 IncrementalHoareTripleChecker+Valid, 539 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-12-02 16:59:11,452 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [127 Valid, 152 Invalid, 653 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [114 Valid, 539 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-12-02 16:59:11,453 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 0 states. [2023-12-02 16:59:11,453 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 0 to 0. [2023-12-02 16:59:11,453 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 0 states, 0 states have (on average 0.0) internal successors, (0), 0 states have internal predecessors, (0), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 16:59:11,453 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 0 states to 0 states and 0 transitions. [2023-12-02 16:59:11,453 INFO L78 Accepts]: Start accepts. Automaton has 0 states and 0 transitions. Word has length 854 [2023-12-02 16:59:11,454 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 16:59:11,454 INFO L495 AbstractCegarLoop]: Abstraction has 0 states and 0 transitions. [2023-12-02 16:59:11,454 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 36 states, 35 states have (on average 3.1714285714285713) internal successors, (111), 36 states have internal predecessors, (111), 30 states have call successors, (35), 2 states have call predecessors, (35), 17 states have return successors, (48), 17 states have call predecessors, (48), 30 states have call successors, (48) [2023-12-02 16:59:11,454 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2023-12-02 16:59:11,454 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2023-12-02 16:59:11,456 INFO L805 garLoopResultBuilder]: Registering result SAFE for location ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2023-12-02 16:59:11,463 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Ended with exit code 0 [2023-12-02 16:59:11,657 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2023-12-02 16:59:11,659 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends 0 states and 0 transitions. [2023-12-02 16:59:12,714 INFO L899 garLoopResultBuilder]: For program point fibonacciFINAL(lines 16 24) no Hoare annotation was computed. [2023-12-02 16:59:12,715 INFO L895 garLoopResultBuilder]: At program point L22(line 22) the Hoare annotation is: (and (or (< 2 |fibonacci_#in~n|) (= 2 fibonacci_~n)) (= fibonacci_~n |fibonacci_#in~n|)) [2023-12-02 16:59:12,715 INFO L899 garLoopResultBuilder]: For program point L22-1(line 22) no Hoare annotation was computed. [2023-12-02 16:59:12,715 INFO L895 garLoopResultBuilder]: At program point L22-2(line 22) the Hoare annotation is: (let ((.cse2 (= 5 |fibonacci_#in~n|))) (let ((.cse4 (= 6 |fibonacci_#in~n|)) (.cse0 (and .cse2 (= |fibonacci_#t~ret4| 3) (= 5 fibonacci_~n))) (.cse3 (= 3 |fibonacci_#in~n|)) (.cse5 (= |fibonacci_#t~ret4| 1))) (and (or (< |fibonacci_#in~n| 5) (< 5 |fibonacci_#in~n|) .cse0) (let ((.cse1 (= fibonacci_~n |fibonacci_#in~n|))) (or (and (<= 10 |fibonacci_#in~n|) .cse1) (and (= |fibonacci_#t~ret4| 13) (= 8 |fibonacci_#in~n|) (= 8 fibonacci_~n)) (and (= fibonacci_~n 4) (= 4 |fibonacci_#in~n|)) (and (= |fibonacci_#t~ret4| 21) (<= 9 |fibonacci_#in~n|) .cse1) .cse2 .cse3 (< |fibonacci_#in~n| 3) .cse4 (and (= 7 |fibonacci_#in~n|) (= |fibonacci_#t~ret4| 8)))) (or (< 6 |fibonacci_#in~n|) (and (= 6 fibonacci_~n) (= |fibonacci_#t~ret4| 5)) (< |fibonacci_#in~n| 6)) (or (<= 8 |fibonacci_#in~n|) (= |fibonacci_#t~ret4| 2) .cse4 .cse0 (< |fibonacci_#in~n| 4) (= 7 fibonacci_~n)) (or (< 2 |fibonacci_#in~n|) (and (= 2 |fibonacci_#in~n|) (= 2 fibonacci_~n) .cse5)) (or (not .cse3) (and (= 3 fibonacci_~n) .cse5))))) [2023-12-02 16:59:12,715 INFO L899 garLoopResultBuilder]: For program point L19(lines 19 23) no Hoare annotation was computed. [2023-12-02 16:59:12,716 INFO L899 garLoopResultBuilder]: For program point L22-3(line 22) no Hoare annotation was computed. [2023-12-02 16:59:12,716 INFO L899 garLoopResultBuilder]: For program point fibonacciEXIT(lines 16 24) no Hoare annotation was computed. [2023-12-02 16:59:12,716 INFO L899 garLoopResultBuilder]: For program point L17(lines 17 23) no Hoare annotation was computed. [2023-12-02 16:59:12,716 INFO L902 garLoopResultBuilder]: At program point $Ultimate##0(lines 16 24) the Hoare annotation is: true [2023-12-02 16:59:12,716 INFO L899 garLoopResultBuilder]: For program point L33(line 33) no Hoare annotation was computed. [2023-12-02 16:59:12,716 INFO L899 garLoopResultBuilder]: For program point ULTIMATE.startEXIT(line -1) no Hoare annotation was computed. [2023-12-02 16:59:12,716 INFO L899 garLoopResultBuilder]: For program point L30(lines 30 34) no Hoare annotation was computed. [2023-12-02 16:59:12,716 INFO L895 garLoopResultBuilder]: At program point L29(line 29) the Hoare annotation is: (= 9 |ULTIMATE.start_main_~x~0#1|) [2023-12-02 16:59:12,716 INFO L899 garLoopResultBuilder]: For program point L29-1(line 29) no Hoare annotation was computed. [2023-12-02 16:59:12,716 INFO L899 garLoopResultBuilder]: For program point L27(lines 27 35) no Hoare annotation was computed. [2023-12-02 16:59:12,717 INFO L899 garLoopResultBuilder]: For program point ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION(line 33) no Hoare annotation was computed. [2023-12-02 16:59:12,717 INFO L899 garLoopResultBuilder]: For program point $Ultimate##0(line -1) no Hoare annotation was computed. [2023-12-02 16:59:12,720 INFO L445 BasicCegarLoop]: Path program histogram: [12, 1, 1, 1] [2023-12-02 16:59:12,722 INFO L178 ceAbstractionStarter]: Computing trace abstraction results [2023-12-02 16:59:12,726 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 02.12 04:59:12 BoogieIcfgContainer [2023-12-02 16:59:12,726 INFO L131 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2023-12-02 16:59:12,727 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2023-12-02 16:59:12,727 INFO L270 PluginConnector]: Initializing Witness Printer... [2023-12-02 16:59:12,727 INFO L274 PluginConnector]: Witness Printer initialized [2023-12-02 16:59:12,727 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 02.12 04:58:13" (3/4) ... [2023-12-02 16:59:12,729 INFO L137 WitnessPrinter]: Generating witness for correct program [2023-12-02 16:59:12,733 INFO L361 RCFGBacktranslator]: Ignoring RootEdge to procedure fibonacci [2023-12-02 16:59:12,737 INFO L943 BoogieBacktranslator]: Reduced CFG by removing 13 nodes and edges [2023-12-02 16:59:12,737 INFO L943 BoogieBacktranslator]: Reduced CFG by removing 4 nodes and edges [2023-12-02 16:59:12,737 INFO L943 BoogieBacktranslator]: Reduced CFG by removing 3 nodes and edges [2023-12-02 16:59:12,737 INFO L943 BoogieBacktranslator]: Reduced CFG by removing 1 nodes and edges [2023-12-02 16:59:12,813 INFO L149 WitnessManager]: Wrote witness to /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/witness.graphml [2023-12-02 16:59:12,814 INFO L149 WitnessManager]: Wrote witness to /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/witness.yml [2023-12-02 16:59:12,814 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2023-12-02 16:59:12,815 INFO L158 Benchmark]: Toolchain (without parser) took 60170.32ms. Allocated memory was 157.3MB in the beginning and 1.2GB in the end (delta: 1.0GB). Free memory was 117.4MB in the beginning and 544.4MB in the end (delta: -426.9MB). Peak memory consumption was 606.5MB. Max. memory is 16.1GB. [2023-12-02 16:59:12,815 INFO L158 Benchmark]: CDTParser took 0.19ms. Allocated memory is still 109.1MB. Free memory is still 85.2MB. There was no memory consumed. Max. memory is 16.1GB. [2023-12-02 16:59:12,815 INFO L158 Benchmark]: CACSL2BoogieTranslator took 208.03ms. Allocated memory is still 157.3MB. Free memory was 117.4MB in the beginning and 106.9MB in the end (delta: 10.5MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. [2023-12-02 16:59:12,816 INFO L158 Benchmark]: Boogie Procedure Inliner took 25.02ms. Allocated memory is still 157.3MB. Free memory was 106.9MB in the beginning and 105.7MB in the end (delta: 1.2MB). There was no memory consumed. Max. memory is 16.1GB. [2023-12-02 16:59:12,816 INFO L158 Benchmark]: Boogie Preprocessor took 16.48ms. Allocated memory is still 157.3MB. Free memory was 105.7MB in the beginning and 104.9MB in the end (delta: 874.3kB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2023-12-02 16:59:12,816 INFO L158 Benchmark]: RCFGBuilder took 262.45ms. Allocated memory is still 157.3MB. Free memory was 104.9MB in the beginning and 94.4MB in the end (delta: 10.5MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. [2023-12-02 16:59:12,817 INFO L158 Benchmark]: TraceAbstraction took 59563.95ms. Allocated memory was 157.3MB in the beginning and 1.2GB in the end (delta: 1.0GB). Free memory was 93.8MB in the beginning and 548.6MB in the end (delta: -454.8MB). Peak memory consumption was 579.2MB. Max. memory is 16.1GB. [2023-12-02 16:59:12,817 INFO L158 Benchmark]: Witness Printer took 87.54ms. Allocated memory is still 1.2GB. Free memory was 548.6MB in the beginning and 544.4MB in the end (delta: 4.2MB). Peak memory consumption was 4.2MB. Max. memory is 16.1GB. [2023-12-02 16:59:12,819 INFO L338 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.19ms. Allocated memory is still 109.1MB. Free memory is still 85.2MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 208.03ms. Allocated memory is still 157.3MB. Free memory was 117.4MB in the beginning and 106.9MB in the end (delta: 10.5MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 25.02ms. Allocated memory is still 157.3MB. Free memory was 106.9MB in the beginning and 105.7MB in the end (delta: 1.2MB). There was no memory consumed. Max. memory is 16.1GB. * Boogie Preprocessor took 16.48ms. Allocated memory is still 157.3MB. Free memory was 105.7MB in the beginning and 104.9MB in the end (delta: 874.3kB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * RCFGBuilder took 262.45ms. Allocated memory is still 157.3MB. Free memory was 104.9MB in the beginning and 94.4MB in the end (delta: 10.5MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. * TraceAbstraction took 59563.95ms. Allocated memory was 157.3MB in the beginning and 1.2GB in the end (delta: 1.0GB). Free memory was 93.8MB in the beginning and 548.6MB in the end (delta: -454.8MB). Peak memory consumption was 579.2MB. Max. memory is 16.1GB. * Witness Printer took 87.54ms. Allocated memory is still 1.2GB. Free memory was 548.6MB in the beginning and 544.4MB in the end (delta: 4.2MB). Peak memory consumption was 4.2MB. 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 - PositiveResult [Line: 33]: a call to reach_error is unreachable For all program executions holds that a call to reach_error is unreachable at this location - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 17 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 59.5s, OverallIterations: 15, TraceHistogramMax: 155, PathProgramHistogramMax: 12, EmptinessCheckTime: 0.1s, AutomataDifference: 3.6s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 1.1s, InitialAbstractionConstructionTime: 0.0s, HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 940 SdHoareTripleChecker+Valid, 1.9s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 882 mSDsluCounter, 2141 SdHoareTripleChecker+Invalid, 1.6s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 1838 mSDsCounter, 749 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 3210 IncrementalHoareTripleChecker+Invalid, 3959 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 749 mSolverCounterUnsat, 303 mSDtfsCounter, 3210 mSolverCounterSat, 0.1s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 10783 GetRequests, 10314 SyntacticMatches, 80 SemanticMatches, 389 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3921 ImplicationChecksByTransitivity, 3.9s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=131occurred in iteration=14, InterpolantAutomatonStates: 242, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.2s AutomataMinimizationTime, 15 MinimizatonAttempts, 52 StatesRemovedByMinimization, 6 NontrivialMinimizations, HoareAnnotationStatistics: 0.0s HoareAnnotationTime, 4 LocationsWithAnnotation, 262 PreInvPairs, 427 NumberOfFragments, 153 HoareAnnotationTreeSize, 262 FomulaSimplifications, 4972 FormulaSimplificationTreeSizeReduction, 0.1s HoareSimplificationTime, 4 FomulaSimplificationsInter, 3453 FormulaSimplificationTreeSizeReductionInter, 0.9s HoareSimplificationTimeInter, RefinementEngineStatistics: TRACE_CHECK: 0.4s SsaConstructionTime, 2.0s SatisfiabilityAnalysisTime, 48.1s InterpolantComputationTime, 10289 NumberOfCodeBlocks, 9555 NumberOfCodeBlocksAsserted, 154 NumberOfCheckSat, 15383 ConstructedInterpolants, 0 QuantifiedInterpolants, 22269 SizeOfPredicates, 74 NumberOfNonLiveVariables, 9742 ConjunctsInSsa, 611 ConjunctsInUnsatCore, 41 InterpolantComputations, 2 PerfectInterpolantSequences, 624110/707331 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 - AllSpecificationsHoldResult: All specifications hold 1 specifications checked. All of them hold RESULT: Ultimate proved your program to be correct! [2023-12-02 16:59:12,838 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e8d5be35-432c-48a9-9c99-70d90e7722cd/bin/utaipan-verify-nQ1chXbOIh/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Ended with exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Writing output log to file Ultimate.log Result: TRUE