./Ultimate.py --spec ../../sv-benchmarks/c/properties/unreach-call.prp --file ../../sv-benchmarks/c/recursive-simple/fibo_2calls_4-1.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 9bd2c7ff 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_f655a5ba-7841-42da-b3b4-5e48da5e0710/bin/utaipan-verify-t7M7D8N6sZ/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f655a5ba-7841-42da-b3b4-5e48da5e0710/bin/utaipan-verify-t7M7D8N6sZ/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f655a5ba-7841-42da-b3b4-5e48da5e0710/bin/utaipan-verify-t7M7D8N6sZ/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f655a5ba-7841-42da-b3b4-5e48da5e0710/bin/utaipan-verify-t7M7D8N6sZ/config/TaipanReach.xml -i ../../sv-benchmarks/c/recursive-simple/fibo_2calls_4-1.c -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f655a5ba-7841-42da-b3b4-5e48da5e0710/bin/utaipan-verify-t7M7D8N6sZ/config/svcomp-Reach-32bit-Taipan_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f655a5ba-7841-42da-b3b4-5e48da5e0710/bin/utaipan-verify-t7M7D8N6sZ --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 0724aefed4fd629206cc51e19e964e04af92729823366947a0cfe01fe4e4d102 --- Real Ultimate output --- This is Ultimate 0.2.3-dev-9bd2c7f [2023-11-19 04:52:49,891 INFO L188 SettingsManager]: Resetting all preferences to default values... [2023-11-19 04:52:50,002 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f655a5ba-7841-42da-b3b4-5e48da5e0710/bin/utaipan-verify-t7M7D8N6sZ/config/svcomp-Reach-32bit-Taipan_Default.epf [2023-11-19 04:52:50,009 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2023-11-19 04:52:50,009 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2023-11-19 04:52:50,051 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2023-11-19 04:52:50,051 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2023-11-19 04:52:50,052 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2023-11-19 04:52:50,053 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2023-11-19 04:52:50,058 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2023-11-19 04:52:50,058 INFO L153 SettingsManager]: * User list type=DISABLED [2023-11-19 04:52:50,059 INFO L151 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2023-11-19 04:52:50,059 INFO L153 SettingsManager]: * Explicit value domain=true [2023-11-19 04:52:50,060 INFO L153 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2023-11-19 04:52:50,061 INFO L153 SettingsManager]: * Octagon Domain=false [2023-11-19 04:52:50,061 INFO L153 SettingsManager]: * Abstract domain=CompoundDomain [2023-11-19 04:52:50,062 INFO L153 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2023-11-19 04:52:50,062 INFO L153 SettingsManager]: * Use the RCFG-of-the-future interface=true [2023-11-19 04:52:50,062 INFO L153 SettingsManager]: * Interval Domain=false [2023-11-19 04:52:50,063 INFO L151 SettingsManager]: Preferences of Sifa differ from their defaults: [2023-11-19 04:52:50,063 INFO L153 SettingsManager]: * Call Summarizer=TopInputCallSummarizer [2023-11-19 04:52:50,064 INFO L153 SettingsManager]: * Simplification Technique=POLY_PAC [2023-11-19 04:52:50,065 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2023-11-19 04:52:50,065 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2023-11-19 04:52:50,065 INFO L153 SettingsManager]: * sizeof long=4 [2023-11-19 04:52:50,066 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2023-11-19 04:52:50,066 INFO L153 SettingsManager]: * sizeof POINTER=4 [2023-11-19 04:52:50,067 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2023-11-19 04:52:50,067 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2023-11-19 04:52:50,067 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2023-11-19 04:52:50,069 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2023-11-19 04:52:50,069 INFO L153 SettingsManager]: * sizeof long double=12 [2023-11-19 04:52:50,069 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2023-11-19 04:52:50,069 INFO L153 SettingsManager]: * Use constant arrays=true [2023-11-19 04:52:50,069 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2023-11-19 04:52:50,070 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2023-11-19 04:52:50,070 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-11-19 04:52:50,070 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2023-11-19 04:52:50,070 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2023-11-19 04:52:50,070 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2023-11-19 04:52:50,071 INFO L153 SettingsManager]: * Trace refinement strategy=SIFA_TAIPAN [2023-11-19 04:52:50,071 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2023-11-19 04:52:50,071 INFO L153 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2023-11-19 04:52:50,071 INFO L153 SettingsManager]: * Trace refinement exception blacklist=NONE [2023-11-19 04:52:50,072 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2023-11-19 04:52:50,072 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_f655a5ba-7841-42da-b3b4-5e48da5e0710/bin/utaipan-verify-t7M7D8N6sZ/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_f655a5ba-7841-42da-b3b4-5e48da5e0710/bin/utaipan-verify-t7M7D8N6sZ 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 -> 0724aefed4fd629206cc51e19e964e04af92729823366947a0cfe01fe4e4d102 [2023-11-19 04:52:50,313 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2023-11-19 04:52:50,341 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2023-11-19 04:52:50,343 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2023-11-19 04:52:50,345 INFO L270 PluginConnector]: Initializing CDTParser... [2023-11-19 04:52:50,345 INFO L274 PluginConnector]: CDTParser initialized [2023-11-19 04:52:50,347 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f655a5ba-7841-42da-b3b4-5e48da5e0710/bin/utaipan-verify-t7M7D8N6sZ/../../sv-benchmarks/c/recursive-simple/fibo_2calls_4-1.c [2023-11-19 04:52:53,520 INFO L533 CDTParser]: Created temporary CDT project at NULL [2023-11-19 04:52:53,698 INFO L384 CDTParser]: Found 1 translation units. [2023-11-19 04:52:53,701 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f655a5ba-7841-42da-b3b4-5e48da5e0710/sv-benchmarks/c/recursive-simple/fibo_2calls_4-1.c [2023-11-19 04:52:53,709 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f655a5ba-7841-42da-b3b4-5e48da5e0710/bin/utaipan-verify-t7M7D8N6sZ/data/a496caa7f/e4ef1a9a9a5342dfbe0ea18ad761f858/FLAGdd4e04684 [2023-11-19 04:52:53,722 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f655a5ba-7841-42da-b3b4-5e48da5e0710/bin/utaipan-verify-t7M7D8N6sZ/data/a496caa7f/e4ef1a9a9a5342dfbe0ea18ad761f858 [2023-11-19 04:52:53,724 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2023-11-19 04:52:53,726 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2023-11-19 04:52:53,727 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2023-11-19 04:52:53,727 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2023-11-19 04:52:53,736 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2023-11-19 04:52:53,737 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 19.11 04:52:53" (1/1) ... [2023-11-19 04:52:53,738 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@57bdeceb and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 04:52:53, skipping insertion in model container [2023-11-19 04:52:53,738 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 19.11 04:52:53" (1/1) ... [2023-11-19 04:52:53,758 INFO L177 MainTranslator]: Built tables and reachable declarations [2023-11-19 04:52:53,910 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_f655a5ba-7841-42da-b3b4-5e48da5e0710/sv-benchmarks/c/recursive-simple/fibo_2calls_4-1.c[946,959] [2023-11-19 04:52:53,915 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-19 04:52:53,926 INFO L202 MainTranslator]: Completed pre-run [2023-11-19 04:52:53,941 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_f655a5ba-7841-42da-b3b4-5e48da5e0710/sv-benchmarks/c/recursive-simple/fibo_2calls_4-1.c[946,959] [2023-11-19 04:52:53,942 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-19 04:52:53,956 INFO L206 MainTranslator]: Completed translation [2023-11-19 04:52:53,956 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 04:52:53 WrapperNode [2023-11-19 04:52:53,957 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2023-11-19 04:52:53,958 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2023-11-19 04:52:53,958 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2023-11-19 04:52:53,958 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2023-11-19 04:52:53,966 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 04:52:53" (1/1) ... [2023-11-19 04:52:53,972 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 04:52:53" (1/1) ... [2023-11-19 04:52:53,988 INFO L138 Inliner]: procedures = 14, calls = 12, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 20 [2023-11-19 04:52:53,989 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2023-11-19 04:52:53,989 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2023-11-19 04:52:53,990 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2023-11-19 04:52:53,990 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2023-11-19 04:52:53,998 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 04:52:53" (1/1) ... [2023-11-19 04:52:53,999 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 04:52:53" (1/1) ... [2023-11-19 04:52:54,014 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 04:52:53" (1/1) ... [2023-11-19 04:52:54,014 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 04:52:53" (1/1) ... [2023-11-19 04:52:54,018 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 04:52:53" (1/1) ... [2023-11-19 04:52:54,024 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 04:52:53" (1/1) ... [2023-11-19 04:52:54,031 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 04:52:53" (1/1) ... [2023-11-19 04:52:54,033 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 04:52:53" (1/1) ... [2023-11-19 04:52:54,035 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2023-11-19 04:52:54,036 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2023-11-19 04:52:54,036 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2023-11-19 04:52:54,036 INFO L274 PluginConnector]: RCFGBuilder initialized [2023-11-19 04:52:54,037 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 04:52:53" (1/1) ... [2023-11-19 04:52:54,044 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-11-19 04:52:54,059 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f655a5ba-7841-42da-b3b4-5e48da5e0710/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 04:52:54,070 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f655a5ba-7841-42da-b3b4-5e48da5e0710/bin/utaipan-verify-t7M7D8N6sZ/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2023-11-19 04:52:54,077 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f655a5ba-7841-42da-b3b4-5e48da5e0710/bin/utaipan-verify-t7M7D8N6sZ/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2023-11-19 04:52:54,106 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2023-11-19 04:52:54,107 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2023-11-19 04:52:54,107 INFO L130 BoogieDeclarations]: Found specification of procedure fibo2 [2023-11-19 04:52:54,107 INFO L138 BoogieDeclarations]: Found implementation of procedure fibo2 [2023-11-19 04:52:54,107 INFO L130 BoogieDeclarations]: Found specification of procedure fibo1 [2023-11-19 04:52:54,107 INFO L138 BoogieDeclarations]: Found implementation of procedure fibo1 [2023-11-19 04:52:54,109 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2023-11-19 04:52:54,109 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2023-11-19 04:52:54,183 INFO L236 CfgBuilder]: Building ICFG [2023-11-19 04:52:54,186 INFO L262 CfgBuilder]: Building CFG for each procedure with an implementation [2023-11-19 04:52:54,333 INFO L277 CfgBuilder]: Performing block encoding [2023-11-19 04:52:54,351 INFO L297 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2023-11-19 04:52:54,351 INFO L302 CfgBuilder]: Removed 0 assume(true) statements. [2023-11-19 04:52:54,356 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 19.11 04:52:54 BoogieIcfgContainer [2023-11-19 04:52:54,356 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2023-11-19 04:52:54,358 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2023-11-19 04:52:54,359 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2023-11-19 04:52:54,362 INFO L274 PluginConnector]: TraceAbstraction initialized [2023-11-19 04:52:54,362 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 19.11 04:52:53" (1/3) ... [2023-11-19 04:52:54,363 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@70127511 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 19.11 04:52:54, skipping insertion in model container [2023-11-19 04:52:54,363 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 04:52:53" (2/3) ... [2023-11-19 04:52:54,363 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@70127511 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 19.11 04:52:54, skipping insertion in model container [2023-11-19 04:52:54,364 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 19.11 04:52:54" (3/3) ... [2023-11-19 04:52:54,365 INFO L112 eAbstractionObserver]: Analyzing ICFG fibo_2calls_4-1.c [2023-11-19 04:52:54,383 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2023-11-19 04:52:54,384 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2023-11-19 04:52:54,431 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-11-19 04:52:54,437 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;@52411c55, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2023-11-19 04:52:54,438 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2023-11-19 04:52:54,441 INFO L276 IsEmpty]: Start isEmpty. Operand has 26 states, 17 states have (on average 1.3529411764705883) internal successors, (23), 18 states have internal predecessors, (23), 5 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2023-11-19 04:52:54,448 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 10 [2023-11-19 04:52:54,448 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 04:52:54,448 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-19 04:52:54,449 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 04:52:54,454 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 04:52:54,454 INFO L85 PathProgramCache]: Analyzing trace with hash 2097990987, now seen corresponding path program 1 times [2023-11-19 04:52:54,464 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 04:52:54,465 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1504911871] [2023-11-19 04:52:54,465 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 04:52:54,466 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 04:52:54,564 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 04:52:54,708 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-19 04:52:54,712 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 04:52:54,712 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1504911871] [2023-11-19 04:52:54,713 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1504911871] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-19 04:52:54,713 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-19 04:52:54,714 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2023-11-19 04:52:54,716 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2064735055] [2023-11-19 04:52:54,717 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-19 04:52:54,720 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-11-19 04:52:54,721 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 04:52:54,748 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-11-19 04:52:54,749 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2023-11-19 04:52:54,751 INFO L87 Difference]: Start difference. First operand has 26 states, 17 states have (on average 1.3529411764705883) internal successors, (23), 18 states have internal predecessors, (23), 5 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) 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-11-19 04:52:54,932 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 04:52:54,932 INFO L93 Difference]: Finished difference Result 34 states and 43 transitions. [2023-11-19 04:52:54,933 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2023-11-19 04:52:54,934 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-11-19 04:52:54,934 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 04:52:54,941 INFO L225 Difference]: With dead ends: 34 [2023-11-19 04:52:54,941 INFO L226 Difference]: Without dead ends: 26 [2023-11-19 04:52:54,944 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2023-11-19 04:52:54,947 INFO L413 NwaCegarLoop]: 23 mSDtfsCounter, 12 mSDsluCounter, 50 mSDsCounter, 0 mSdLazyCounter, 38 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 15 SdHoareTripleChecker+Valid, 73 SdHoareTripleChecker+Invalid, 38 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 38 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-19 04:52:54,949 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [15 Valid, 73 Invalid, 38 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 38 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-19 04:52:54,965 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 26 states. [2023-11-19 04:52:54,992 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 26 to 26. [2023-11-19 04:52:54,993 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 26 states, 17 states have (on average 1.2352941176470589) internal successors, (21), 18 states have internal predecessors, (21), 5 states have call successors, (5), 2 states have call predecessors, (5), 3 states have return successors, (7), 5 states have call predecessors, (7), 5 states have call successors, (7) [2023-11-19 04:52:54,995 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 33 transitions. [2023-11-19 04:52:54,996 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 33 transitions. Word has length 9 [2023-11-19 04:52:54,997 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 04:52:54,997 INFO L495 AbstractCegarLoop]: Abstraction has 26 states and 33 transitions. [2023-11-19 04:52:54,997 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-11-19 04:52:54,997 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 33 transitions. [2023-11-19 04:52:54,999 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 11 [2023-11-19 04:52:54,999 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 04:52:54,999 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-19 04:52:54,999 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2023-11-19 04:52:55,000 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 04:52:55,000 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 04:52:55,000 INFO L85 PathProgramCache]: Analyzing trace with hash 1328370967, now seen corresponding path program 1 times [2023-11-19 04:52:55,001 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 04:52:55,001 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1396168415] [2023-11-19 04:52:55,001 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 04:52:55,001 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 04:52:55,015 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 04:52:55,077 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-19 04:52:55,077 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 04:52:55,078 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1396168415] [2023-11-19 04:52:55,078 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1396168415] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-19 04:52:55,078 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-19 04:52:55,079 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2023-11-19 04:52:55,079 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1304857893] [2023-11-19 04:52:55,079 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-19 04:52:55,080 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-11-19 04:52:55,081 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 04:52:55,081 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-11-19 04:52:55,082 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2023-11-19 04:52:55,082 INFO L87 Difference]: Start difference. First operand 26 states and 33 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-11-19 04:52:55,133 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 04:52:55,133 INFO L93 Difference]: Finished difference Result 32 states and 40 transitions. [2023-11-19 04:52:55,134 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2023-11-19 04:52:55,134 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-11-19 04:52:55,135 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 04:52:55,136 INFO L225 Difference]: With dead ends: 32 [2023-11-19 04:52:55,136 INFO L226 Difference]: Without dead ends: 28 [2023-11-19 04:52:55,137 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-11-19 04:52:55,138 INFO L413 NwaCegarLoop]: 22 mSDtfsCounter, 10 mSDsluCounter, 48 mSDsCounter, 0 mSdLazyCounter, 33 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 70 SdHoareTripleChecker+Invalid, 34 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 33 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-11-19 04:52:55,139 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [13 Valid, 70 Invalid, 34 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 33 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-11-19 04:52:55,140 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 28 states. [2023-11-19 04:52:55,146 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 28 to 26. [2023-11-19 04:52:55,146 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 26 states, 17 states have (on average 1.2352941176470589) internal successors, (21), 18 states have internal predecessors, (21), 5 states have call successors, (5), 2 states have call predecessors, (5), 3 states have return successors, (7), 5 states have call predecessors, (7), 5 states have call successors, (7) [2023-11-19 04:52:55,148 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 33 transitions. [2023-11-19 04:52:55,149 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 33 transitions. Word has length 10 [2023-11-19 04:52:55,150 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 04:52:55,150 INFO L495 AbstractCegarLoop]: Abstraction has 26 states and 33 transitions. [2023-11-19 04:52:55,150 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-11-19 04:52:55,150 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 33 transitions. [2023-11-19 04:52:55,152 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2023-11-19 04:52:55,152 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 04:52:55,152 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-19 04:52:55,152 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2023-11-19 04:52:55,153 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 04:52:55,153 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 04:52:55,153 INFO L85 PathProgramCache]: Analyzing trace with hash -1296553538, now seen corresponding path program 1 times [2023-11-19 04:52:55,154 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 04:52:55,154 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [420107067] [2023-11-19 04:52:55,154 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 04:52:55,154 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 04:52:55,192 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 04:52:55,300 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2023-11-19 04:52:55,301 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 04:52:55,301 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [420107067] [2023-11-19 04:52:55,301 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [420107067] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-19 04:52:55,301 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [731834884] [2023-11-19 04:52:55,302 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 04:52:55,302 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 04:52:55,302 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f655a5ba-7841-42da-b3b4-5e48da5e0710/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 04:52:55,304 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f655a5ba-7841-42da-b3b4-5e48da5e0710/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 04:52:55,319 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f655a5ba-7841-42da-b3b4-5e48da5e0710/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2023-11-19 04:52:55,365 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 04:52:55,366 INFO L262 TraceCheckSpWp]: Trace formula consists of 70 conjuncts, 6 conjunts are in the unsatisfiable core [2023-11-19 04:52:55,372 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-19 04:52:55,469 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2023-11-19 04:52:55,469 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-19 04:52:55,667 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2023-11-19 04:52:55,667 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [731834884] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-19 04:52:55,668 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1469053099] [2023-11-19 04:52:55,688 INFO L159 IcfgInterpreter]: Started Sifa with 19 locations of interest [2023-11-19 04:52:55,688 INFO L166 IcfgInterpreter]: Building call graph [2023-11-19 04:52:55,692 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-19 04:52:55,697 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-19 04:52:55,698 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-19 04:52:55,788 INFO L197 IcfgInterpreter]: Interpreting procedure fibo1 with input of size 35 for LOIs [2023-11-19 04:52:55,883 INFO L197 IcfgInterpreter]: Interpreting procedure fibo2 with input of size 34 for LOIs [2023-11-19 04:52:55,898 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-19 04:52:56,172 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSifa [1469053099] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-19 04:52:56,173 INFO L185 FreeRefinementEngine]: Found 1 perfect and 3 imperfect interpolant sequences. [2023-11-19 04:52:56,173 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [6, 7, 7] total 17 [2023-11-19 04:52:56,174 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [183811922] [2023-11-19 04:52:56,174 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-19 04:52:56,174 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2023-11-19 04:52:56,175 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 04:52:56,176 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2023-11-19 04:52:56,176 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=48, Invalid=224, Unknown=0, NotChecked=0, Total=272 [2023-11-19 04:52:56,176 INFO L87 Difference]: Start difference. First operand 26 states and 33 transitions. Second operand has 7 states, 6 states have (on average 2.1666666666666665) internal successors, (13), 4 states have internal predecessors, (13), 3 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (3), 1 states have call predecessors, (3), 3 states have call successors, (3) [2023-11-19 04:52:56,327 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 04:52:56,327 INFO L93 Difference]: Finished difference Result 68 states and 91 transitions. [2023-11-19 04:52:56,328 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2023-11-19 04:52:56,328 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 6 states have (on average 2.1666666666666665) internal successors, (13), 4 states have internal predecessors, (13), 3 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (3), 1 states have call predecessors, (3), 3 states have call successors, (3) Word has length 22 [2023-11-19 04:52:56,328 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 04:52:56,335 INFO L225 Difference]: With dead ends: 68 [2023-11-19 04:52:56,335 INFO L226 Difference]: Without dead ends: 44 [2023-11-19 04:52:56,337 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 71 GetRequests, 54 SyntacticMatches, 2 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 43 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=48, Invalid=224, Unknown=0, NotChecked=0, Total=272 [2023-11-19 04:52:56,341 INFO L413 NwaCegarLoop]: 28 mSDtfsCounter, 16 mSDsluCounter, 73 mSDsCounter, 0 mSdLazyCounter, 68 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 21 SdHoareTripleChecker+Valid, 101 SdHoareTripleChecker+Invalid, 73 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 68 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-19 04:52:56,343 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [21 Valid, 101 Invalid, 73 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 68 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-19 04:52:56,345 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 44 states. [2023-11-19 04:52:56,362 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 44 to 42. [2023-11-19 04:52:56,362 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 42 states, 28 states have (on average 1.1428571428571428) internal successors, (32), 28 states have internal predecessors, (32), 9 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2023-11-19 04:52:56,366 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 42 states to 42 states and 50 transitions. [2023-11-19 04:52:56,366 INFO L78 Accepts]: Start accepts. Automaton has 42 states and 50 transitions. Word has length 22 [2023-11-19 04:52:56,366 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 04:52:56,367 INFO L495 AbstractCegarLoop]: Abstraction has 42 states and 50 transitions. [2023-11-19 04:52:56,368 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 6 states have (on average 2.1666666666666665) internal successors, (13), 4 states have internal predecessors, (13), 3 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (3), 1 states have call predecessors, (3), 3 states have call successors, (3) [2023-11-19 04:52:56,368 INFO L276 IsEmpty]: Start isEmpty. Operand 42 states and 50 transitions. [2023-11-19 04:52:56,371 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2023-11-19 04:52:56,372 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 04:52:56,372 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-19 04:52:56,396 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f655a5ba-7841-42da-b3b4-5e48da5e0710/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2023-11-19 04:52:56,587 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f655a5ba-7841-42da-b3b4-5e48da5e0710/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 04:52:56,588 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 04:52:56,588 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 04:52:56,588 INFO L85 PathProgramCache]: Analyzing trace with hash -28918515, now seen corresponding path program 1 times [2023-11-19 04:52:56,589 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 04:52:56,589 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2076784271] [2023-11-19 04:52:56,589 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 04:52:56,589 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 04:52:56,608 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 04:52:56,786 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 5 proven. 5 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2023-11-19 04:52:56,787 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 04:52:56,787 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2076784271] [2023-11-19 04:52:56,787 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2076784271] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-19 04:52:56,789 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1076544784] [2023-11-19 04:52:56,790 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 04:52:56,790 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 04:52:56,791 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f655a5ba-7841-42da-b3b4-5e48da5e0710/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 04:52:56,793 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f655a5ba-7841-42da-b3b4-5e48da5e0710/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 04:52:56,815 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f655a5ba-7841-42da-b3b4-5e48da5e0710/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2023-11-19 04:52:56,856 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 04:52:56,857 INFO L262 TraceCheckSpWp]: Trace formula consists of 99 conjuncts, 8 conjunts are in the unsatisfiable core [2023-11-19 04:52:56,860 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-19 04:52:56,962 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 2 proven. 9 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2023-11-19 04:52:56,962 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-19 04:52:57,397 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 2 proven. 10 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2023-11-19 04:52:57,398 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1076544784] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-19 04:52:57,398 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1844484838] [2023-11-19 04:52:57,402 INFO L159 IcfgInterpreter]: Started Sifa with 24 locations of interest [2023-11-19 04:52:57,403 INFO L166 IcfgInterpreter]: Building call graph [2023-11-19 04:52:57,406 FATAL L? ?]: Ignoring exception! java.lang.IllegalArgumentException: Recursive programs are not supported. at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.topsortRelevant(CallGraph.java:132) at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.(CallGraph.java:97) at de.uni_freiburg.informatik.ultimate.lib.sifa.IcfgInterpreter.(IcfgInterpreter.java:92) at de.uni_freiburg.informatik.ultimate.plugins.sifa.SifaBuilder.construct(SifaBuilder.java:96) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.SifaRunner.(SifaRunner.java:98) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleSifa.construct(IpTcStrategyModuleSifa.java:68) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getOrConstruct(IpTcStrategyModuleBase.java:101) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getInterpolantComputationStatus(IpTcStrategyModuleBase.java:77) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.tryExecuteInterpolantGenerator(AutomatonFreeRefinementEngine.java:267) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.generateProof(AutomatonFreeRefinementEngine.java:148) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.executeStrategy(AutomatonFreeRefinementEngine.java:137) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.(AutomatonFreeRefinementEngine.java:85) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.TraceAbstractionRefinementEngine.(TraceAbstractionRefinementEngine.java:82) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.BasicCegarLoop.isCounterexampleFeasible(BasicCegarLoop.java:337) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterate(AbstractCegarLoop.java:431) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.startCegar(AbstractCegarLoop.java:366) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.runCegar(AbstractCegarLoop.java:348) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.executeCegarLoop(TraceAbstractionStarter.java:415) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseProgram(TraceAbstractionStarter.java:302) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseSequentialProgram(TraceAbstractionStarter.java:262) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.runCegarLoops(TraceAbstractionStarter.java:175) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.(TraceAbstractionStarter.java:154) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver.finish(TraceAbstractionObserver.java:124) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runObserver(PluginConnector.java:167) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runTool(PluginConnector.java:150) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.run(PluginConnector.java:127) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.executePluginConnector(ToolchainWalker.java:233) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.processPlugin(ToolchainWalker.java:227) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walkUnprotected(ToolchainWalker.java:144) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walk(ToolchainWalker.java:106) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainManager$Toolchain.processToolchain(ToolchainManager.java:319) at de.uni_freiburg.informatik.ultimate.core.coreplugin.toolchain.DefaultToolchainJob.run(DefaultToolchainJob.java:145) at org.eclipse.core.internal.jobs.Worker.run(Worker.java:63) [2023-11-19 04:52:57,412 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-19 04:52:57,412 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 8, 9] total 14 [2023-11-19 04:52:57,414 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [682185159] [2023-11-19 04:52:57,414 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-19 04:52:57,416 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2023-11-19 04:52:57,416 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 04:52:57,419 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2023-11-19 04:52:57,420 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=36, Invalid=146, Unknown=0, NotChecked=0, Total=182 [2023-11-19 04:52:57,420 INFO L87 Difference]: Start difference. First operand 42 states and 50 transitions. Second operand has 14 states, 11 states have (on average 4.0) internal successors, (44), 14 states have internal predecessors, (44), 11 states have call successors, (13), 1 states have call predecessors, (13), 5 states have return successors, (13), 3 states have call predecessors, (13), 11 states have call successors, (13) [2023-11-19 04:52:57,636 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 04:52:57,636 INFO L93 Difference]: Finished difference Result 85 states and 121 transitions. [2023-11-19 04:52:57,636 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2023-11-19 04:52:57,637 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 11 states have (on average 4.0) internal successors, (44), 14 states have internal predecessors, (44), 11 states have call successors, (13), 1 states have call predecessors, (13), 5 states have return successors, (13), 3 states have call predecessors, (13), 11 states have call successors, (13) Word has length 35 [2023-11-19 04:52:57,637 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 04:52:57,639 INFO L225 Difference]: With dead ends: 85 [2023-11-19 04:52:57,639 INFO L226 Difference]: Without dead ends: 53 [2023-11-19 04:52:57,641 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 84 GetRequests, 63 SyntacticMatches, 3 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 44 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=75, Invalid=305, Unknown=0, NotChecked=0, Total=380 [2023-11-19 04:52:57,642 INFO L413 NwaCegarLoop]: 18 mSDtfsCounter, 39 mSDsluCounter, 83 mSDsCounter, 0 mSdLazyCounter, 122 mSolverCounterSat, 25 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 44 SdHoareTripleChecker+Valid, 101 SdHoareTripleChecker+Invalid, 147 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 25 IncrementalHoareTripleChecker+Valid, 122 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-19 04:52:57,642 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [44 Valid, 101 Invalid, 147 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [25 Valid, 122 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-19 04:52:57,643 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 53 states. [2023-11-19 04:52:57,657 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 53 to 44. [2023-11-19 04:52:57,657 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 44 states, 29 states have (on average 1.1379310344827587) internal successors, (33), 30 states have internal predecessors, (33), 9 states have call successors, (9), 4 states have call predecessors, (9), 5 states have return successors, (11), 9 states have call predecessors, (11), 9 states have call successors, (11) [2023-11-19 04:52:57,659 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 44 states to 44 states and 53 transitions. [2023-11-19 04:52:57,659 INFO L78 Accepts]: Start accepts. Automaton has 44 states and 53 transitions. Word has length 35 [2023-11-19 04:52:57,659 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 04:52:57,660 INFO L495 AbstractCegarLoop]: Abstraction has 44 states and 53 transitions. [2023-11-19 04:52:57,660 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 11 states have (on average 4.0) internal successors, (44), 14 states have internal predecessors, (44), 11 states have call successors, (13), 1 states have call predecessors, (13), 5 states have return successors, (13), 3 states have call predecessors, (13), 11 states have call successors, (13) [2023-11-19 04:52:57,660 INFO L276 IsEmpty]: Start isEmpty. Operand 44 states and 53 transitions. [2023-11-19 04:52:57,662 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2023-11-19 04:52:57,662 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 04:52:57,663 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-19 04:52:57,695 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f655a5ba-7841-42da-b3b4-5e48da5e0710/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2023-11-19 04:52:57,888 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f655a5ba-7841-42da-b3b4-5e48da5e0710/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 04:52:57,889 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 04:52:57,889 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 04:52:57,890 INFO L85 PathProgramCache]: Analyzing trace with hash -243412115, now seen corresponding path program 1 times [2023-11-19 04:52:57,890 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 04:52:57,890 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1424875622] [2023-11-19 04:52:57,890 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 04:52:57,890 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 04:52:57,920 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 04:52:58,081 INFO L134 CoverageAnalysis]: Checked inductivity of 17 backedges. 4 proven. 3 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2023-11-19 04:52:58,081 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 04:52:58,081 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1424875622] [2023-11-19 04:52:58,081 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1424875622] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-19 04:52:58,082 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1575542573] [2023-11-19 04:52:58,082 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 04:52:58,082 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 04:52:58,082 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f655a5ba-7841-42da-b3b4-5e48da5e0710/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 04:52:58,083 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f655a5ba-7841-42da-b3b4-5e48da5e0710/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 04:52:58,103 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f655a5ba-7841-42da-b3b4-5e48da5e0710/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2023-11-19 04:52:58,149 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 04:52:58,150 INFO L262 TraceCheckSpWp]: Trace formula consists of 101 conjuncts, 8 conjunts are in the unsatisfiable core [2023-11-19 04:52:58,156 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-19 04:52:58,243 INFO L134 CoverageAnalysis]: Checked inductivity of 17 backedges. 2 proven. 9 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2023-11-19 04:52:58,243 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-19 04:52:58,579 INFO L134 CoverageAnalysis]: Checked inductivity of 17 backedges. 2 proven. 11 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2023-11-19 04:52:58,580 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1575542573] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-19 04:52:58,580 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [629895787] [2023-11-19 04:52:58,583 INFO L159 IcfgInterpreter]: Started Sifa with 24 locations of interest [2023-11-19 04:52:58,583 INFO L166 IcfgInterpreter]: Building call graph [2023-11-19 04:52:58,583 FATAL L? ?]: Ignoring exception! java.lang.IllegalArgumentException: Recursive programs are not supported. at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.topsortRelevant(CallGraph.java:132) at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.(CallGraph.java:97) at de.uni_freiburg.informatik.ultimate.lib.sifa.IcfgInterpreter.(IcfgInterpreter.java:92) at de.uni_freiburg.informatik.ultimate.plugins.sifa.SifaBuilder.construct(SifaBuilder.java:96) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.SifaRunner.(SifaRunner.java:98) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleSifa.construct(IpTcStrategyModuleSifa.java:68) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getOrConstruct(IpTcStrategyModuleBase.java:101) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getInterpolantComputationStatus(IpTcStrategyModuleBase.java:77) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.tryExecuteInterpolantGenerator(AutomatonFreeRefinementEngine.java:267) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.generateProof(AutomatonFreeRefinementEngine.java:148) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.executeStrategy(AutomatonFreeRefinementEngine.java:137) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.(AutomatonFreeRefinementEngine.java:85) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.TraceAbstractionRefinementEngine.(TraceAbstractionRefinementEngine.java:82) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.BasicCegarLoop.isCounterexampleFeasible(BasicCegarLoop.java:337) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterate(AbstractCegarLoop.java:431) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.startCegar(AbstractCegarLoop.java:366) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.runCegar(AbstractCegarLoop.java:348) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.executeCegarLoop(TraceAbstractionStarter.java:415) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseProgram(TraceAbstractionStarter.java:302) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseSequentialProgram(TraceAbstractionStarter.java:262) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.runCegarLoops(TraceAbstractionStarter.java:175) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.(TraceAbstractionStarter.java:154) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver.finish(TraceAbstractionObserver.java:124) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runObserver(PluginConnector.java:167) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runTool(PluginConnector.java:150) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.run(PluginConnector.java:127) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.executePluginConnector(ToolchainWalker.java:233) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.processPlugin(ToolchainWalker.java:227) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walkUnprotected(ToolchainWalker.java:144) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walk(ToolchainWalker.java:106) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainManager$Toolchain.processToolchain(ToolchainManager.java:319) at de.uni_freiburg.informatik.ultimate.core.coreplugin.toolchain.DefaultToolchainJob.run(DefaultToolchainJob.java:145) at org.eclipse.core.internal.jobs.Worker.run(Worker.java:63) [2023-11-19 04:52:58,584 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-19 04:52:58,584 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 8, 9] total 17 [2023-11-19 04:52:58,584 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [626110136] [2023-11-19 04:52:58,584 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-19 04:52:58,585 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2023-11-19 04:52:58,585 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 04:52:58,586 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2023-11-19 04:52:58,586 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=46, Invalid=226, Unknown=0, NotChecked=0, Total=272 [2023-11-19 04:52:58,586 INFO L87 Difference]: Start difference. First operand 44 states and 53 transitions. Second operand has 17 states, 16 states have (on average 3.0) internal successors, (48), 17 states have internal predecessors, (48), 10 states have call successors, (12), 1 states have call predecessors, (12), 7 states have return successors, (12), 6 states have call predecessors, (12), 10 states have call successors, (12) [2023-11-19 04:52:59,042 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 04:52:59,042 INFO L93 Difference]: Finished difference Result 121 states and 203 transitions. [2023-11-19 04:52:59,042 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2023-11-19 04:52:59,043 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 16 states have (on average 3.0) internal successors, (48), 17 states have internal predecessors, (48), 10 states have call successors, (12), 1 states have call predecessors, (12), 7 states have return successors, (12), 6 states have call predecessors, (12), 10 states have call successors, (12) Word has length 36 [2023-11-19 04:52:59,043 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 04:52:59,045 INFO L225 Difference]: With dead ends: 121 [2023-11-19 04:52:59,045 INFO L226 Difference]: Without dead ends: 77 [2023-11-19 04:52:59,047 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 98 GetRequests, 68 SyntacticMatches, 4 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 118 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=139, Invalid=617, Unknown=0, NotChecked=0, Total=756 [2023-11-19 04:52:59,048 INFO L413 NwaCegarLoop]: 27 mSDtfsCounter, 56 mSDsluCounter, 185 mSDsCounter, 0 mSdLazyCounter, 314 mSolverCounterSat, 55 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 60 SdHoareTripleChecker+Valid, 212 SdHoareTripleChecker+Invalid, 369 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 55 IncrementalHoareTripleChecker+Valid, 314 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2023-11-19 04:52:59,048 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [60 Valid, 212 Invalid, 369 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [55 Valid, 314 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2023-11-19 04:52:59,049 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 77 states. [2023-11-19 04:52:59,064 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 77 to 63. [2023-11-19 04:52:59,065 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 63 states, 40 states have (on average 1.15) internal successors, (46), 43 states have internal predecessors, (46), 14 states have call successors, (14), 5 states have call predecessors, (14), 8 states have return successors, (31), 14 states have call predecessors, (31), 14 states have call successors, (31) [2023-11-19 04:52:59,066 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 63 states to 63 states and 91 transitions. [2023-11-19 04:52:59,067 INFO L78 Accepts]: Start accepts. Automaton has 63 states and 91 transitions. Word has length 36 [2023-11-19 04:52:59,067 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 04:52:59,067 INFO L495 AbstractCegarLoop]: Abstraction has 63 states and 91 transitions. [2023-11-19 04:52:59,068 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 16 states have (on average 3.0) internal successors, (48), 17 states have internal predecessors, (48), 10 states have call successors, (12), 1 states have call predecessors, (12), 7 states have return successors, (12), 6 states have call predecessors, (12), 10 states have call successors, (12) [2023-11-19 04:52:59,068 INFO L276 IsEmpty]: Start isEmpty. Operand 63 states and 91 transitions. [2023-11-19 04:52:59,071 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2023-11-19 04:52:59,071 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 04:52:59,071 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-19 04:52:59,098 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f655a5ba-7841-42da-b3b4-5e48da5e0710/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2023-11-19 04:52:59,287 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f655a5ba-7841-42da-b3b4-5e48da5e0710/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 04:52:59,288 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 04:52:59,288 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 04:52:59,288 INFO L85 PathProgramCache]: Analyzing trace with hash 403750738, now seen corresponding path program 1 times [2023-11-19 04:52:59,288 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 04:52:59,288 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [247407510] [2023-11-19 04:52:59,289 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 04:52:59,289 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 04:52:59,305 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 04:52:59,434 INFO L134 CoverageAnalysis]: Checked inductivity of 44 backedges. 12 proven. 12 refuted. 0 times theorem prover too weak. 20 trivial. 0 not checked. [2023-11-19 04:52:59,435 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 04:52:59,435 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [247407510] [2023-11-19 04:52:59,435 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [247407510] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-19 04:52:59,435 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [115741228] [2023-11-19 04:52:59,435 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 04:52:59,435 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 04:52:59,436 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f655a5ba-7841-42da-b3b4-5e48da5e0710/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 04:52:59,437 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f655a5ba-7841-42da-b3b4-5e48da5e0710/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 04:52:59,455 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f655a5ba-7841-42da-b3b4-5e48da5e0710/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2023-11-19 04:52:59,494 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 04:52:59,495 INFO L262 TraceCheckSpWp]: Trace formula consists of 132 conjuncts, 8 conjunts are in the unsatisfiable core [2023-11-19 04:52:59,497 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-19 04:52:59,536 INFO L134 CoverageAnalysis]: Checked inductivity of 44 backedges. 12 proven. 12 refuted. 0 times theorem prover too weak. 20 trivial. 0 not checked. [2023-11-19 04:52:59,536 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-19 04:52:59,866 INFO L134 CoverageAnalysis]: Checked inductivity of 44 backedges. 12 proven. 13 refuted. 0 times theorem prover too weak. 19 trivial. 0 not checked. [2023-11-19 04:52:59,866 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [115741228] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-19 04:52:59,867 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1585777734] [2023-11-19 04:52:59,869 INFO L159 IcfgInterpreter]: Started Sifa with 24 locations of interest [2023-11-19 04:52:59,869 INFO L166 IcfgInterpreter]: Building call graph [2023-11-19 04:52:59,870 FATAL L? ?]: Ignoring exception! java.lang.IllegalArgumentException: Recursive programs are not supported. at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.topsortRelevant(CallGraph.java:132) at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.(CallGraph.java:97) at de.uni_freiburg.informatik.ultimate.lib.sifa.IcfgInterpreter.(IcfgInterpreter.java:92) at de.uni_freiburg.informatik.ultimate.plugins.sifa.SifaBuilder.construct(SifaBuilder.java:96) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.SifaRunner.(SifaRunner.java:98) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleSifa.construct(IpTcStrategyModuleSifa.java:68) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getOrConstruct(IpTcStrategyModuleBase.java:101) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getInterpolantComputationStatus(IpTcStrategyModuleBase.java:77) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.tryExecuteInterpolantGenerator(AutomatonFreeRefinementEngine.java:267) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.generateProof(AutomatonFreeRefinementEngine.java:148) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.executeStrategy(AutomatonFreeRefinementEngine.java:137) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.(AutomatonFreeRefinementEngine.java:85) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.TraceAbstractionRefinementEngine.(TraceAbstractionRefinementEngine.java:82) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.BasicCegarLoop.isCounterexampleFeasible(BasicCegarLoop.java:337) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterate(AbstractCegarLoop.java:431) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.startCegar(AbstractCegarLoop.java:366) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.runCegar(AbstractCegarLoop.java:348) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.executeCegarLoop(TraceAbstractionStarter.java:415) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseProgram(TraceAbstractionStarter.java:302) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseSequentialProgram(TraceAbstractionStarter.java:262) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.runCegarLoops(TraceAbstractionStarter.java:175) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.(TraceAbstractionStarter.java:154) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver.finish(TraceAbstractionObserver.java:124) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runObserver(PluginConnector.java:167) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runTool(PluginConnector.java:150) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.run(PluginConnector.java:127) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.executePluginConnector(ToolchainWalker.java:233) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.processPlugin(ToolchainWalker.java:227) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walkUnprotected(ToolchainWalker.java:144) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walk(ToolchainWalker.java:106) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainManager$Toolchain.processToolchain(ToolchainManager.java:319) at de.uni_freiburg.informatik.ultimate.core.coreplugin.toolchain.DefaultToolchainJob.run(DefaultToolchainJob.java:145) at org.eclipse.core.internal.jobs.Worker.run(Worker.java:63) [2023-11-19 04:52:59,871 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-19 04:52:59,871 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 9] total 11 [2023-11-19 04:52:59,871 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [30658653] [2023-11-19 04:52:59,872 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-19 04:52:59,872 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2023-11-19 04:52:59,872 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 04:52:59,873 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2023-11-19 04:52:59,873 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=83, Unknown=0, NotChecked=0, Total=110 [2023-11-19 04:52:59,874 INFO L87 Difference]: Start difference. First operand 63 states and 91 transitions. Second operand has 11 states, 10 states have (on average 3.8) internal successors, (38), 11 states have internal predecessors, (38), 7 states have call successors, (10), 1 states have call predecessors, (10), 4 states have return successors, (10), 6 states have call predecessors, (10), 7 states have call successors, (10) [2023-11-19 04:52:59,985 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 04:52:59,985 INFO L93 Difference]: Finished difference Result 88 states and 133 transitions. [2023-11-19 04:52:59,986 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2023-11-19 04:52:59,986 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 10 states have (on average 3.8) internal successors, (38), 11 states have internal predecessors, (38), 7 states have call successors, (10), 1 states have call predecessors, (10), 4 states have return successors, (10), 6 states have call predecessors, (10), 7 states have call successors, (10) Word has length 50 [2023-11-19 04:52:59,987 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 04:52:59,988 INFO L225 Difference]: With dead ends: 88 [2023-11-19 04:52:59,988 INFO L226 Difference]: Without dead ends: 76 [2023-11-19 04:52:59,989 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 113 GetRequests, 97 SyntacticMatches, 4 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 13 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=46, Invalid=136, Unknown=0, NotChecked=0, Total=182 [2023-11-19 04:52:59,990 INFO L413 NwaCegarLoop]: 16 mSDtfsCounter, 30 mSDsluCounter, 69 mSDsCounter, 0 mSdLazyCounter, 92 mSolverCounterSat, 16 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 38 SdHoareTripleChecker+Valid, 85 SdHoareTripleChecker+Invalid, 108 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 16 IncrementalHoareTripleChecker+Valid, 92 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-19 04:52:59,990 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [38 Valid, 85 Invalid, 108 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [16 Valid, 92 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-19 04:52:59,991 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 76 states. [2023-11-19 04:53:00,020 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 76 to 71. [2023-11-19 04:53:00,020 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 71 states, 45 states have (on average 1.1333333333333333) internal successors, (51), 48 states have internal predecessors, (51), 15 states have call successors, (15), 5 states have call predecessors, (15), 10 states have return successors, (41), 17 states have call predecessors, (41), 15 states have call successors, (41) [2023-11-19 04:53:00,023 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 71 states to 71 states and 107 transitions. [2023-11-19 04:53:00,024 INFO L78 Accepts]: Start accepts. Automaton has 71 states and 107 transitions. Word has length 50 [2023-11-19 04:53:00,026 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 04:53:00,026 INFO L495 AbstractCegarLoop]: Abstraction has 71 states and 107 transitions. [2023-11-19 04:53:00,027 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 10 states have (on average 3.8) internal successors, (38), 11 states have internal predecessors, (38), 7 states have call successors, (10), 1 states have call predecessors, (10), 4 states have return successors, (10), 6 states have call predecessors, (10), 7 states have call successors, (10) [2023-11-19 04:53:00,027 INFO L276 IsEmpty]: Start isEmpty. Operand 71 states and 107 transitions. [2023-11-19 04:53:00,030 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 52 [2023-11-19 04:53:00,033 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 04:53:00,033 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-19 04:53:00,058 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f655a5ba-7841-42da-b3b4-5e48da5e0710/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2023-11-19 04:53:00,247 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f655a5ba-7841-42da-b3b4-5e48da5e0710/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable5 [2023-11-19 04:53:00,248 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 04:53:00,248 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 04:53:00,248 INFO L85 PathProgramCache]: Analyzing trace with hash -534686422, now seen corresponding path program 1 times [2023-11-19 04:53:00,248 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 04:53:00,248 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1249662077] [2023-11-19 04:53:00,248 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 04:53:00,249 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 04:53:00,262 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 04:53:00,344 INFO L134 CoverageAnalysis]: Checked inductivity of 46 backedges. 18 proven. 5 refuted. 0 times theorem prover too weak. 23 trivial. 0 not checked. [2023-11-19 04:53:00,344 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 04:53:00,344 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1249662077] [2023-11-19 04:53:00,344 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1249662077] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-19 04:53:00,345 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2126934464] [2023-11-19 04:53:00,345 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 04:53:00,345 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 04:53:00,345 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f655a5ba-7841-42da-b3b4-5e48da5e0710/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 04:53:00,346 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f655a5ba-7841-42da-b3b4-5e48da5e0710/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 04:53:00,348 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f655a5ba-7841-42da-b3b4-5e48da5e0710/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2023-11-19 04:53:00,401 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 04:53:00,402 INFO L262 TraceCheckSpWp]: Trace formula consists of 134 conjuncts, 6 conjunts are in the unsatisfiable core [2023-11-19 04:53:00,404 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-19 04:53:00,429 INFO L134 CoverageAnalysis]: Checked inductivity of 46 backedges. 18 proven. 5 refuted. 0 times theorem prover too weak. 23 trivial. 0 not checked. [2023-11-19 04:53:00,430 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-19 04:53:00,614 INFO L134 CoverageAnalysis]: Checked inductivity of 46 backedges. 18 proven. 5 refuted. 0 times theorem prover too weak. 23 trivial. 0 not checked. [2023-11-19 04:53:00,614 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2126934464] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-19 04:53:00,615 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1793086737] [2023-11-19 04:53:00,617 INFO L159 IcfgInterpreter]: Started Sifa with 24 locations of interest [2023-11-19 04:53:00,617 INFO L166 IcfgInterpreter]: Building call graph [2023-11-19 04:53:00,618 FATAL L? ?]: Ignoring exception! java.lang.IllegalArgumentException: Recursive programs are not supported. at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.topsortRelevant(CallGraph.java:132) at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.(CallGraph.java:97) at de.uni_freiburg.informatik.ultimate.lib.sifa.IcfgInterpreter.(IcfgInterpreter.java:92) at de.uni_freiburg.informatik.ultimate.plugins.sifa.SifaBuilder.construct(SifaBuilder.java:96) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.SifaRunner.(SifaRunner.java:98) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleSifa.construct(IpTcStrategyModuleSifa.java:68) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getOrConstruct(IpTcStrategyModuleBase.java:101) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getInterpolantComputationStatus(IpTcStrategyModuleBase.java:77) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.tryExecuteInterpolantGenerator(AutomatonFreeRefinementEngine.java:267) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.generateProof(AutomatonFreeRefinementEngine.java:148) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.executeStrategy(AutomatonFreeRefinementEngine.java:137) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.(AutomatonFreeRefinementEngine.java:85) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.TraceAbstractionRefinementEngine.(TraceAbstractionRefinementEngine.java:82) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.BasicCegarLoop.isCounterexampleFeasible(BasicCegarLoop.java:337) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterate(AbstractCegarLoop.java:431) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.startCegar(AbstractCegarLoop.java:366) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.runCegar(AbstractCegarLoop.java:348) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.executeCegarLoop(TraceAbstractionStarter.java:415) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseProgram(TraceAbstractionStarter.java:302) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseSequentialProgram(TraceAbstractionStarter.java:262) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.runCegarLoops(TraceAbstractionStarter.java:175) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.(TraceAbstractionStarter.java:154) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver.finish(TraceAbstractionObserver.java:124) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runObserver(PluginConnector.java:167) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runTool(PluginConnector.java:150) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.run(PluginConnector.java:127) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.executePluginConnector(ToolchainWalker.java:233) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.processPlugin(ToolchainWalker.java:227) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walkUnprotected(ToolchainWalker.java:144) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walk(ToolchainWalker.java:106) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainManager$Toolchain.processToolchain(ToolchainManager.java:319) at de.uni_freiburg.informatik.ultimate.core.coreplugin.toolchain.DefaultToolchainJob.run(DefaultToolchainJob.java:145) at org.eclipse.core.internal.jobs.Worker.run(Worker.java:63) [2023-11-19 04:53:00,619 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-19 04:53:00,619 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 9 [2023-11-19 04:53:00,619 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [4458384] [2023-11-19 04:53:00,620 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-19 04:53:00,620 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2023-11-19 04:53:00,620 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 04:53:00,621 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2023-11-19 04:53:00,621 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=19, Invalid=53, Unknown=0, NotChecked=0, Total=72 [2023-11-19 04:53:00,622 INFO L87 Difference]: Start difference. First operand 71 states and 107 transitions. Second operand has 9 states, 8 states have (on average 4.5) internal successors, (36), 9 states have internal predecessors, (36), 4 states have call successors, (9), 1 states have call predecessors, (9), 3 states have return successors, (9), 5 states have call predecessors, (9), 4 states have call successors, (9) [2023-11-19 04:53:00,694 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 04:53:00,694 INFO L93 Difference]: Finished difference Result 87 states and 125 transitions. [2023-11-19 04:53:00,694 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2023-11-19 04:53:00,695 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 8 states have (on average 4.5) internal successors, (36), 9 states have internal predecessors, (36), 4 states have call successors, (9), 1 states have call predecessors, (9), 3 states have return successors, (9), 5 states have call predecessors, (9), 4 states have call successors, (9) Word has length 51 [2023-11-19 04:53:00,695 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 04:53:00,696 INFO L225 Difference]: With dead ends: 87 [2023-11-19 04:53:00,696 INFO L226 Difference]: Without dead ends: 80 [2023-11-19 04:53:00,697 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 110 GetRequests, 98 SyntacticMatches, 3 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=29, Invalid=81, Unknown=0, NotChecked=0, Total=110 [2023-11-19 04:53:00,698 INFO L413 NwaCegarLoop]: 16 mSDtfsCounter, 21 mSDsluCounter, 48 mSDsCounter, 0 mSdLazyCounter, 67 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 28 SdHoareTripleChecker+Valid, 64 SdHoareTripleChecker+Invalid, 76 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 67 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-11-19 04:53:00,698 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [28 Valid, 64 Invalid, 76 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 67 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-11-19 04:53:00,699 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 80 states. [2023-11-19 04:53:00,711 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 80 to 71. [2023-11-19 04:53:00,712 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 71 states, 45 states have (on average 1.1333333333333333) internal successors, (51), 48 states have internal predecessors, (51), 15 states have call successors, (15), 5 states have call predecessors, (15), 10 states have return successors, (40), 17 states have call predecessors, (40), 15 states have call successors, (40) [2023-11-19 04:53:00,713 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 71 states to 71 states and 106 transitions. [2023-11-19 04:53:00,714 INFO L78 Accepts]: Start accepts. Automaton has 71 states and 106 transitions. Word has length 51 [2023-11-19 04:53:00,714 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 04:53:00,714 INFO L495 AbstractCegarLoop]: Abstraction has 71 states and 106 transitions. [2023-11-19 04:53:00,714 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 8 states have (on average 4.5) internal successors, (36), 9 states have internal predecessors, (36), 4 states have call successors, (9), 1 states have call predecessors, (9), 3 states have return successors, (9), 5 states have call predecessors, (9), 4 states have call successors, (9) [2023-11-19 04:53:00,715 INFO L276 IsEmpty]: Start isEmpty. Operand 71 states and 106 transitions. [2023-11-19 04:53:00,716 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 65 [2023-11-19 04:53:00,717 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 04:53:00,717 INFO L195 NwaCegarLoop]: trace histogram [5, 5, 4, 4, 4, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-19 04:53:00,744 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f655a5ba-7841-42da-b3b4-5e48da5e0710/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2023-11-19 04:53:00,931 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f655a5ba-7841-42da-b3b4-5e48da5e0710/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable6 [2023-11-19 04:53:00,932 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 04:53:00,932 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 04:53:00,932 INFO L85 PathProgramCache]: Analyzing trace with hash 955443101, now seen corresponding path program 1 times [2023-11-19 04:53:00,932 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 04:53:00,932 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [467259406] [2023-11-19 04:53:00,932 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 04:53:00,932 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 04:53:00,947 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 04:53:01,317 INFO L134 CoverageAnalysis]: Checked inductivity of 81 backedges. 0 proven. 28 refuted. 0 times theorem prover too weak. 53 trivial. 0 not checked. [2023-11-19 04:53:01,317 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 04:53:01,317 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [467259406] [2023-11-19 04:53:01,317 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [467259406] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-19 04:53:01,318 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1457096839] [2023-11-19 04:53:01,318 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 04:53:01,318 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 04:53:01,318 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f655a5ba-7841-42da-b3b4-5e48da5e0710/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 04:53:01,319 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f655a5ba-7841-42da-b3b4-5e48da5e0710/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 04:53:01,341 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f655a5ba-7841-42da-b3b4-5e48da5e0710/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2023-11-19 04:53:01,383 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 04:53:01,384 INFO L262 TraceCheckSpWp]: Trace formula consists of 163 conjuncts, 39 conjunts are in the unsatisfiable core [2023-11-19 04:53:01,387 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-19 04:53:01,476 INFO L134 CoverageAnalysis]: Checked inductivity of 81 backedges. 0 proven. 28 refuted. 0 times theorem prover too weak. 53 trivial. 0 not checked. [2023-11-19 04:53:01,476 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-19 04:53:01,772 INFO L134 CoverageAnalysis]: Checked inductivity of 81 backedges. 0 proven. 28 refuted. 0 times theorem prover too weak. 53 trivial. 0 not checked. [2023-11-19 04:53:01,773 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1457096839] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-19 04:53:01,773 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [902846799] [2023-11-19 04:53:01,775 INFO L159 IcfgInterpreter]: Started Sifa with 24 locations of interest [2023-11-19 04:53:01,775 INFO L166 IcfgInterpreter]: Building call graph [2023-11-19 04:53:01,776 FATAL L? ?]: Ignoring exception! java.lang.IllegalArgumentException: Recursive programs are not supported. at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.topsortRelevant(CallGraph.java:132) at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.(CallGraph.java:97) at de.uni_freiburg.informatik.ultimate.lib.sifa.IcfgInterpreter.(IcfgInterpreter.java:92) at de.uni_freiburg.informatik.ultimate.plugins.sifa.SifaBuilder.construct(SifaBuilder.java:96) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.SifaRunner.(SifaRunner.java:98) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleSifa.construct(IpTcStrategyModuleSifa.java:68) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getOrConstruct(IpTcStrategyModuleBase.java:101) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getInterpolantComputationStatus(IpTcStrategyModuleBase.java:77) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.tryExecuteInterpolantGenerator(AutomatonFreeRefinementEngine.java:267) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.generateProof(AutomatonFreeRefinementEngine.java:148) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.executeStrategy(AutomatonFreeRefinementEngine.java:137) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.(AutomatonFreeRefinementEngine.java:85) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.TraceAbstractionRefinementEngine.(TraceAbstractionRefinementEngine.java:82) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.BasicCegarLoop.isCounterexampleFeasible(BasicCegarLoop.java:337) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterate(AbstractCegarLoop.java:431) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.startCegar(AbstractCegarLoop.java:366) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.runCegar(AbstractCegarLoop.java:348) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.executeCegarLoop(TraceAbstractionStarter.java:415) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseProgram(TraceAbstractionStarter.java:302) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseSequentialProgram(TraceAbstractionStarter.java:262) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.runCegarLoops(TraceAbstractionStarter.java:175) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.(TraceAbstractionStarter.java:154) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver.finish(TraceAbstractionObserver.java:124) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runObserver(PluginConnector.java:167) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runTool(PluginConnector.java:150) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.run(PluginConnector.java:127) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.executePluginConnector(ToolchainWalker.java:233) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.processPlugin(ToolchainWalker.java:227) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walkUnprotected(ToolchainWalker.java:144) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walk(ToolchainWalker.java:106) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainManager$Toolchain.processToolchain(ToolchainManager.java:319) at de.uni_freiburg.informatik.ultimate.core.coreplugin.toolchain.DefaultToolchainJob.run(DefaultToolchainJob.java:145) at org.eclipse.core.internal.jobs.Worker.run(Worker.java:63) [2023-11-19 04:53:01,777 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-19 04:53:01,777 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 17, 17] total 21 [2023-11-19 04:53:01,777 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1298108730] [2023-11-19 04:53:01,777 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-19 04:53:01,778 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2023-11-19 04:53:01,778 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 04:53:01,779 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2023-11-19 04:53:01,779 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=47, Invalid=373, Unknown=0, NotChecked=0, Total=420 [2023-11-19 04:53:01,779 INFO L87 Difference]: Start difference. First operand 71 states and 106 transitions. Second operand has 21 states, 21 states have (on average 1.4761904761904763) internal successors, (31), 12 states have internal predecessors, (31), 4 states have call successors, (6), 1 states have call predecessors, (6), 6 states have return successors, (12), 12 states have call predecessors, (12), 4 states have call successors, (12) [2023-11-19 04:53:01,953 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 04:53:01,953 INFO L93 Difference]: Finished difference Result 130 states and 234 transitions. [2023-11-19 04:53:01,954 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2023-11-19 04:53:01,954 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 21 states have (on average 1.4761904761904763) internal successors, (31), 12 states have internal predecessors, (31), 4 states have call successors, (6), 1 states have call predecessors, (6), 6 states have return successors, (12), 12 states have call predecessors, (12), 4 states have call successors, (12) Word has length 64 [2023-11-19 04:53:01,955 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 04:53:01,956 INFO L225 Difference]: With dead ends: 130 [2023-11-19 04:53:01,957 INFO L226 Difference]: Without dead ends: 123 [2023-11-19 04:53:01,957 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 148 GetRequests, 128 SyntacticMatches, 0 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 43 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=51, Invalid=411, Unknown=0, NotChecked=0, Total=462 [2023-11-19 04:53:01,958 INFO L413 NwaCegarLoop]: 42 mSDtfsCounter, 0 mSDsluCounter, 634 mSDsCounter, 0 mSdLazyCounter, 244 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 676 SdHoareTripleChecker+Invalid, 245 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 244 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-19 04:53:01,958 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [5 Valid, 676 Invalid, 245 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 244 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-19 04:53:01,959 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 123 states. [2023-11-19 04:53:01,982 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 123 to 96. [2023-11-19 04:53:01,983 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 96 states, 60 states have (on average 1.1) internal successors, (66), 63 states have internal predecessors, (66), 20 states have call successors, (20), 5 states have call predecessors, (20), 15 states have return successors, (87), 27 states have call predecessors, (87), 20 states have call successors, (87) [2023-11-19 04:53:01,985 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 96 states to 96 states and 173 transitions. [2023-11-19 04:53:01,985 INFO L78 Accepts]: Start accepts. Automaton has 96 states and 173 transitions. Word has length 64 [2023-11-19 04:53:01,986 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 04:53:01,986 INFO L495 AbstractCegarLoop]: Abstraction has 96 states and 173 transitions. [2023-11-19 04:53:01,986 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 21 states have (on average 1.4761904761904763) internal successors, (31), 12 states have internal predecessors, (31), 4 states have call successors, (6), 1 states have call predecessors, (6), 6 states have return successors, (12), 12 states have call predecessors, (12), 4 states have call successors, (12) [2023-11-19 04:53:01,986 INFO L276 IsEmpty]: Start isEmpty. Operand 96 states and 173 transitions. [2023-11-19 04:53:01,989 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 78 [2023-11-19 04:53:01,989 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 04:53:01,989 INFO L195 NwaCegarLoop]: trace histogram [6, 6, 5, 5, 5, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1] [2023-11-19 04:53:02,011 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f655a5ba-7841-42da-b3b4-5e48da5e0710/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2023-11-19 04:53:02,209 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,7 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f655a5ba-7841-42da-b3b4-5e48da5e0710/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 04:53:02,209 INFO L420 AbstractCegarLoop]: === Iteration 9 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 04:53:02,209 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 04:53:02,210 INFO L85 PathProgramCache]: Analyzing trace with hash 923773556, now seen corresponding path program 2 times [2023-11-19 04:53:02,210 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 04:53:02,210 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [288512953] [2023-11-19 04:53:02,210 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 04:53:02,210 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 04:53:02,226 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 04:53:02,358 INFO L134 CoverageAnalysis]: Checked inductivity of 129 backedges. 47 proven. 13 refuted. 0 times theorem prover too weak. 69 trivial. 0 not checked. [2023-11-19 04:53:02,359 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 04:53:02,359 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [288512953] [2023-11-19 04:53:02,359 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [288512953] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-19 04:53:02,359 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [161250374] [2023-11-19 04:53:02,359 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-11-19 04:53:02,360 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 04:53:02,360 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f655a5ba-7841-42da-b3b4-5e48da5e0710/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 04:53:02,361 INFO L229 MonitoredProcess]: Starting monitored process 8 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f655a5ba-7841-42da-b3b4-5e48da5e0710/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 04:53:02,383 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f655a5ba-7841-42da-b3b4-5e48da5e0710/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2023-11-19 04:53:02,428 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 2 check-sat command(s) [2023-11-19 04:53:02,428 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-19 04:53:02,431 INFO L262 TraceCheckSpWp]: Trace formula consists of 100 conjuncts, 5 conjunts are in the unsatisfiable core [2023-11-19 04:53:02,435 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-19 04:53:02,489 INFO L134 CoverageAnalysis]: Checked inductivity of 129 backedges. 61 proven. 0 refuted. 0 times theorem prover too weak. 68 trivial. 0 not checked. [2023-11-19 04:53:02,489 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-11-19 04:53:02,489 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [161250374] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-19 04:53:02,489 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-11-19 04:53:02,490 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [8] total 12 [2023-11-19 04:53:02,492 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1886711504] [2023-11-19 04:53:02,492 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-19 04:53:02,493 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2023-11-19 04:53:02,493 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 04:53:02,494 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2023-11-19 04:53:02,494 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=23, Invalid=109, Unknown=0, NotChecked=0, Total=132 [2023-11-19 04:53:02,495 INFO L87 Difference]: Start difference. First operand 96 states and 173 transitions. Second operand has 6 states, 5 states have (on average 6.2) internal successors, (31), 6 states have internal predecessors, (31), 3 states have call successors, (7), 2 states have call predecessors, (7), 3 states have return successors, (9), 2 states have call predecessors, (9), 3 states have call successors, (9) [2023-11-19 04:53:02,552 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 04:53:02,552 INFO L93 Difference]: Finished difference Result 173 states and 334 transitions. [2023-11-19 04:53:02,553 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-11-19 04:53:02,553 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 6.2) internal successors, (31), 6 states have internal predecessors, (31), 3 states have call successors, (7), 2 states have call predecessors, (7), 3 states have return successors, (9), 2 states have call predecessors, (9), 3 states have call successors, (9) Word has length 77 [2023-11-19 04:53:02,555 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 04:53:02,556 INFO L225 Difference]: With dead ends: 173 [2023-11-19 04:53:02,556 INFO L226 Difference]: Without dead ends: 94 [2023-11-19 04:53:02,558 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 86 GetRequests, 75 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=27, Invalid=129, Unknown=0, NotChecked=0, Total=156 [2023-11-19 04:53:02,560 INFO L413 NwaCegarLoop]: 25 mSDtfsCounter, 15 mSDsluCounter, 52 mSDsCounter, 0 mSdLazyCounter, 40 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 21 SdHoareTripleChecker+Valid, 77 SdHoareTripleChecker+Invalid, 43 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 40 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-11-19 04:53:02,561 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [21 Valid, 77 Invalid, 43 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 40 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-11-19 04:53:02,561 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 94 states. [2023-11-19 04:53:02,589 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 94 to 80. [2023-11-19 04:53:02,589 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 80 states, 50 states have (on average 1.12) internal successors, (56), 54 states have internal predecessors, (56), 17 states have call successors, (17), 5 states have call predecessors, (17), 12 states have return successors, (48), 20 states have call predecessors, (48), 17 states have call successors, (48) [2023-11-19 04:53:02,593 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 80 states to 80 states and 121 transitions. [2023-11-19 04:53:02,594 INFO L78 Accepts]: Start accepts. Automaton has 80 states and 121 transitions. Word has length 77 [2023-11-19 04:53:02,595 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 04:53:02,595 INFO L495 AbstractCegarLoop]: Abstraction has 80 states and 121 transitions. [2023-11-19 04:53:02,596 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 6.2) internal successors, (31), 6 states have internal predecessors, (31), 3 states have call successors, (7), 2 states have call predecessors, (7), 3 states have return successors, (9), 2 states have call predecessors, (9), 3 states have call successors, (9) [2023-11-19 04:53:02,596 INFO L276 IsEmpty]: Start isEmpty. Operand 80 states and 121 transitions. [2023-11-19 04:53:02,598 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 66 [2023-11-19 04:53:02,598 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 04:53:02,598 INFO L195 NwaCegarLoop]: trace histogram [5, 5, 5, 4, 4, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-19 04:53:02,625 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f655a5ba-7841-42da-b3b4-5e48da5e0710/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2023-11-19 04:53:02,819 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,8 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f655a5ba-7841-42da-b3b4-5e48da5e0710/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 04:53:02,820 INFO L420 AbstractCegarLoop]: === Iteration 10 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 04:53:02,820 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 04:53:02,820 INFO L85 PathProgramCache]: Analyzing trace with hash 624142861, now seen corresponding path program 3 times [2023-11-19 04:53:02,820 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 04:53:02,820 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1971619347] [2023-11-19 04:53:02,821 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 04:53:02,821 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 04:53:02,834 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 04:53:02,949 INFO L134 CoverageAnalysis]: Checked inductivity of 85 backedges. 38 proven. 8 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2023-11-19 04:53:02,949 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 04:53:02,950 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1971619347] [2023-11-19 04:53:02,950 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1971619347] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-19 04:53:02,950 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [966716001] [2023-11-19 04:53:02,950 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2023-11-19 04:53:02,950 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 04:53:02,951 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f655a5ba-7841-42da-b3b4-5e48da5e0710/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 04:53:02,956 INFO L229 MonitoredProcess]: Starting monitored process 9 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f655a5ba-7841-42da-b3b4-5e48da5e0710/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 04:53:02,979 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f655a5ba-7841-42da-b3b4-5e48da5e0710/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2023-11-19 04:53:03,027 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2023-11-19 04:53:03,027 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-19 04:53:03,029 INFO L262 TraceCheckSpWp]: Trace formula consists of 116 conjuncts, 12 conjunts are in the unsatisfiable core [2023-11-19 04:53:03,032 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-19 04:53:03,175 INFO L134 CoverageAnalysis]: Checked inductivity of 85 backedges. 27 proven. 32 refuted. 0 times theorem prover too weak. 26 trivial. 0 not checked. [2023-11-19 04:53:03,175 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-19 04:53:03,858 INFO L134 CoverageAnalysis]: Checked inductivity of 85 backedges. 27 proven. 34 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2023-11-19 04:53:03,858 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [966716001] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-19 04:53:03,858 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [445520533] [2023-11-19 04:53:03,861 INFO L159 IcfgInterpreter]: Started Sifa with 24 locations of interest [2023-11-19 04:53:03,861 INFO L166 IcfgInterpreter]: Building call graph [2023-11-19 04:53:03,861 FATAL L? ?]: Ignoring exception! java.lang.IllegalArgumentException: Recursive programs are not supported. at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.topsortRelevant(CallGraph.java:132) at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.(CallGraph.java:97) at de.uni_freiburg.informatik.ultimate.lib.sifa.IcfgInterpreter.(IcfgInterpreter.java:92) at de.uni_freiburg.informatik.ultimate.plugins.sifa.SifaBuilder.construct(SifaBuilder.java:96) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.SifaRunner.(SifaRunner.java:98) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleSifa.construct(IpTcStrategyModuleSifa.java:68) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getOrConstruct(IpTcStrategyModuleBase.java:101) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getInterpolantComputationStatus(IpTcStrategyModuleBase.java:77) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.tryExecuteInterpolantGenerator(AutomatonFreeRefinementEngine.java:267) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.generateProof(AutomatonFreeRefinementEngine.java:148) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.executeStrategy(AutomatonFreeRefinementEngine.java:137) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.(AutomatonFreeRefinementEngine.java:85) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.TraceAbstractionRefinementEngine.(TraceAbstractionRefinementEngine.java:82) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.BasicCegarLoop.isCounterexampleFeasible(BasicCegarLoop.java:337) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterate(AbstractCegarLoop.java:431) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.startCegar(AbstractCegarLoop.java:366) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.runCegar(AbstractCegarLoop.java:348) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.executeCegarLoop(TraceAbstractionStarter.java:415) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseProgram(TraceAbstractionStarter.java:302) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseSequentialProgram(TraceAbstractionStarter.java:262) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.runCegarLoops(TraceAbstractionStarter.java:175) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.(TraceAbstractionStarter.java:154) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver.finish(TraceAbstractionObserver.java:124) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runObserver(PluginConnector.java:167) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runTool(PluginConnector.java:150) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.run(PluginConnector.java:127) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.executePluginConnector(ToolchainWalker.java:233) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.processPlugin(ToolchainWalker.java:227) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walkUnprotected(ToolchainWalker.java:144) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walk(ToolchainWalker.java:106) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainManager$Toolchain.processToolchain(ToolchainManager.java:319) at de.uni_freiburg.informatik.ultimate.core.coreplugin.toolchain.DefaultToolchainJob.run(DefaultToolchainJob.java:145) at org.eclipse.core.internal.jobs.Worker.run(Worker.java:63) [2023-11-19 04:53:03,862 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-19 04:53:03,863 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 12, 13] total 19 [2023-11-19 04:53:03,863 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1251421927] [2023-11-19 04:53:03,863 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-19 04:53:03,864 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2023-11-19 04:53:03,864 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 04:53:03,865 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2023-11-19 04:53:03,865 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=49, Invalid=293, Unknown=0, NotChecked=0, Total=342 [2023-11-19 04:53:03,866 INFO L87 Difference]: Start difference. First operand 80 states and 121 transitions. Second operand has 19 states, 18 states have (on average 3.7222222222222223) internal successors, (67), 19 states have internal predecessors, (67), 12 states have call successors, (19), 1 states have call predecessors, (19), 8 states have return successors, (20), 10 states have call predecessors, (20), 12 states have call successors, (20) [2023-11-19 04:53:04,272 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 04:53:04,272 INFO L93 Difference]: Finished difference Result 194 states and 345 transitions. [2023-11-19 04:53:04,273 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2023-11-19 04:53:04,274 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 18 states have (on average 3.7222222222222223) internal successors, (67), 19 states have internal predecessors, (67), 12 states have call successors, (19), 1 states have call predecessors, (19), 8 states have return successors, (20), 10 states have call predecessors, (20), 12 states have call successors, (20) Word has length 65 [2023-11-19 04:53:04,275 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 04:53:04,277 INFO L225 Difference]: With dead ends: 194 [2023-11-19 04:53:04,277 INFO L226 Difference]: Without dead ends: 127 [2023-11-19 04:53:04,279 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 149 GetRequests, 115 SyntacticMatches, 6 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 94 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=153, Invalid=717, Unknown=0, NotChecked=0, Total=870 [2023-11-19 04:53:04,280 INFO L413 NwaCegarLoop]: 25 mSDtfsCounter, 73 mSDsluCounter, 204 mSDsCounter, 0 mSdLazyCounter, 376 mSolverCounterSat, 75 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 75 SdHoareTripleChecker+Valid, 229 SdHoareTripleChecker+Invalid, 451 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 75 IncrementalHoareTripleChecker+Valid, 376 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-11-19 04:53:04,281 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [75 Valid, 229 Invalid, 451 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [75 Valid, 376 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-11-19 04:53:04,282 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 127 states. [2023-11-19 04:53:04,307 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 127 to 121. [2023-11-19 04:53:04,307 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 121 states, 78 states have (on average 1.141025641025641) internal successors, (89), 80 states have internal predecessors, (89), 24 states have call successors, (24), 9 states have call predecessors, (24), 18 states have return successors, (81), 31 states have call predecessors, (81), 24 states have call successors, (81) [2023-11-19 04:53:04,310 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 121 states to 121 states and 194 transitions. [2023-11-19 04:53:04,311 INFO L78 Accepts]: Start accepts. Automaton has 121 states and 194 transitions. Word has length 65 [2023-11-19 04:53:04,311 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 04:53:04,311 INFO L495 AbstractCegarLoop]: Abstraction has 121 states and 194 transitions. [2023-11-19 04:53:04,311 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 18 states have (on average 3.7222222222222223) internal successors, (67), 19 states have internal predecessors, (67), 12 states have call successors, (19), 1 states have call predecessors, (19), 8 states have return successors, (20), 10 states have call predecessors, (20), 12 states have call successors, (20) [2023-11-19 04:53:04,312 INFO L276 IsEmpty]: Start isEmpty. Operand 121 states and 194 transitions. [2023-11-19 04:53:04,313 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 66 [2023-11-19 04:53:04,313 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 04:53:04,313 INFO L195 NwaCegarLoop]: trace histogram [5, 5, 4, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1] [2023-11-19 04:53:04,340 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f655a5ba-7841-42da-b3b4-5e48da5e0710/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2023-11-19 04:53:04,527 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,9 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f655a5ba-7841-42da-b3b4-5e48da5e0710/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 04:53:04,527 INFO L420 AbstractCegarLoop]: === Iteration 11 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 04:53:04,528 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 04:53:04,528 INFO L85 PathProgramCache]: Analyzing trace with hash 328038329, now seen corresponding path program 1 times [2023-11-19 04:53:04,528 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 04:53:04,528 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1284151311] [2023-11-19 04:53:04,528 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 04:53:04,528 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 04:53:04,539 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 04:53:04,680 INFO L134 CoverageAnalysis]: Checked inductivity of 84 backedges. 17 proven. 33 refuted. 0 times theorem prover too weak. 34 trivial. 0 not checked. [2023-11-19 04:53:04,680 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 04:53:04,680 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1284151311] [2023-11-19 04:53:04,680 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1284151311] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-19 04:53:04,680 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1871417725] [2023-11-19 04:53:04,681 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 04:53:04,681 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 04:53:04,681 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f655a5ba-7841-42da-b3b4-5e48da5e0710/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 04:53:04,682 INFO L229 MonitoredProcess]: Starting monitored process 10 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f655a5ba-7841-42da-b3b4-5e48da5e0710/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 04:53:04,707 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f655a5ba-7841-42da-b3b4-5e48da5e0710/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2023-11-19 04:53:04,761 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 04:53:04,762 INFO L262 TraceCheckSpWp]: Trace formula consists of 165 conjuncts, 10 conjunts are in the unsatisfiable core [2023-11-19 04:53:04,765 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-19 04:53:04,812 INFO L134 CoverageAnalysis]: Checked inductivity of 84 backedges. 17 proven. 33 refuted. 0 times theorem prover too weak. 34 trivial. 0 not checked. [2023-11-19 04:53:04,812 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-19 04:53:05,332 INFO L134 CoverageAnalysis]: Checked inductivity of 84 backedges. 19 proven. 35 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2023-11-19 04:53:05,333 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1871417725] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-19 04:53:05,333 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [626723165] [2023-11-19 04:53:05,335 INFO L159 IcfgInterpreter]: Started Sifa with 24 locations of interest [2023-11-19 04:53:05,336 INFO L166 IcfgInterpreter]: Building call graph [2023-11-19 04:53:05,336 FATAL L? ?]: Ignoring exception! java.lang.IllegalArgumentException: Recursive programs are not supported. at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.topsortRelevant(CallGraph.java:132) at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.(CallGraph.java:97) at de.uni_freiburg.informatik.ultimate.lib.sifa.IcfgInterpreter.(IcfgInterpreter.java:92) at de.uni_freiburg.informatik.ultimate.plugins.sifa.SifaBuilder.construct(SifaBuilder.java:96) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.SifaRunner.(SifaRunner.java:98) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleSifa.construct(IpTcStrategyModuleSifa.java:68) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getOrConstruct(IpTcStrategyModuleBase.java:101) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getInterpolantComputationStatus(IpTcStrategyModuleBase.java:77) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.tryExecuteInterpolantGenerator(AutomatonFreeRefinementEngine.java:267) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.generateProof(AutomatonFreeRefinementEngine.java:148) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.executeStrategy(AutomatonFreeRefinementEngine.java:137) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.(AutomatonFreeRefinementEngine.java:85) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.TraceAbstractionRefinementEngine.(TraceAbstractionRefinementEngine.java:82) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.BasicCegarLoop.isCounterexampleFeasible(BasicCegarLoop.java:337) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterate(AbstractCegarLoop.java:431) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.startCegar(AbstractCegarLoop.java:366) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.runCegar(AbstractCegarLoop.java:348) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.executeCegarLoop(TraceAbstractionStarter.java:415) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseProgram(TraceAbstractionStarter.java:302) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseSequentialProgram(TraceAbstractionStarter.java:262) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.runCegarLoops(TraceAbstractionStarter.java:175) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.(TraceAbstractionStarter.java:154) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver.finish(TraceAbstractionObserver.java:124) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runObserver(PluginConnector.java:167) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runTool(PluginConnector.java:150) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.run(PluginConnector.java:127) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.executePluginConnector(ToolchainWalker.java:233) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.processPlugin(ToolchainWalker.java:227) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walkUnprotected(ToolchainWalker.java:144) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walk(ToolchainWalker.java:106) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainManager$Toolchain.processToolchain(ToolchainManager.java:319) at de.uni_freiburg.informatik.ultimate.core.coreplugin.toolchain.DefaultToolchainJob.run(DefaultToolchainJob.java:145) at org.eclipse.core.internal.jobs.Worker.run(Worker.java:63) [2023-11-19 04:53:05,337 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-19 04:53:05,337 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9, 11] total 13 [2023-11-19 04:53:05,337 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2110001269] [2023-11-19 04:53:05,337 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-19 04:53:05,338 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2023-11-19 04:53:05,338 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 04:53:05,339 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2023-11-19 04:53:05,339 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=35, Invalid=121, Unknown=0, NotChecked=0, Total=156 [2023-11-19 04:53:05,339 INFO L87 Difference]: Start difference. First operand 121 states and 194 transitions. Second operand has 13 states, 12 states have (on average 3.8333333333333335) internal successors, (46), 13 states have internal predecessors, (46), 9 states have call successors, (12), 1 states have call predecessors, (12), 5 states have return successors, (13), 7 states have call predecessors, (13), 9 states have call successors, (13) [2023-11-19 04:53:05,519 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 04:53:05,519 INFO L93 Difference]: Finished difference Result 132 states and 214 transitions. [2023-11-19 04:53:05,520 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2023-11-19 04:53:05,520 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 12 states have (on average 3.8333333333333335) internal successors, (46), 13 states have internal predecessors, (46), 9 states have call successors, (12), 1 states have call predecessors, (12), 5 states have return successors, (13), 7 states have call predecessors, (13), 9 states have call successors, (13) Word has length 65 [2023-11-19 04:53:05,520 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 04:53:05,521 INFO L225 Difference]: With dead ends: 132 [2023-11-19 04:53:05,521 INFO L226 Difference]: Without dead ends: 0 [2023-11-19 04:53:05,522 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 145 GetRequests, 125 SyntacticMatches, 5 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 34 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=63, Invalid=209, Unknown=0, NotChecked=0, Total=272 [2023-11-19 04:53:05,523 INFO L413 NwaCegarLoop]: 24 mSDtfsCounter, 12 mSDsluCounter, 118 mSDsCounter, 0 mSdLazyCounter, 173 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 142 SdHoareTripleChecker+Invalid, 179 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 173 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-19 04:53:05,523 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [13 Valid, 142 Invalid, 179 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 173 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-19 04:53:05,524 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 0 states. [2023-11-19 04:53:05,524 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 0 to 0. [2023-11-19 04:53:05,524 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-11-19 04:53:05,524 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 0 states to 0 states and 0 transitions. [2023-11-19 04:53:05,525 INFO L78 Accepts]: Start accepts. Automaton has 0 states and 0 transitions. Word has length 65 [2023-11-19 04:53:05,525 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 04:53:05,525 INFO L495 AbstractCegarLoop]: Abstraction has 0 states and 0 transitions. [2023-11-19 04:53:05,525 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 12 states have (on average 3.8333333333333335) internal successors, (46), 13 states have internal predecessors, (46), 9 states have call successors, (12), 1 states have call predecessors, (12), 5 states have return successors, (13), 7 states have call predecessors, (13), 9 states have call successors, (13) [2023-11-19 04:53:05,525 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2023-11-19 04:53:05,525 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2023-11-19 04:53:05,528 INFO L805 garLoopResultBuilder]: Registering result SAFE for location ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2023-11-19 04:53:05,553 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f655a5ba-7841-42da-b3b4-5e48da5e0710/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2023-11-19 04:53:05,743 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,10 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f655a5ba-7841-42da-b3b4-5e48da5e0710/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 04:53:05,745 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends 0 states and 0 transitions. [2023-11-19 04:53:06,450 INFO L899 garLoopResultBuilder]: For program point ULTIMATE.startEXIT(line -1) no Hoare annotation was computed. [2023-11-19 04:53:06,451 INFO L899 garLoopResultBuilder]: For program point ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION(line 41) no Hoare annotation was computed. [2023-11-19 04:53:06,451 INFO L899 garLoopResultBuilder]: For program point $Ultimate##0(line -1) no Hoare annotation was computed. [2023-11-19 04:53:06,451 INFO L899 garLoopResultBuilder]: For program point L41(line 41) no Hoare annotation was computed. [2023-11-19 04:53:06,451 INFO L899 garLoopResultBuilder]: For program point L40(lines 40 42) no Hoare annotation was computed. [2023-11-19 04:53:06,452 INFO L895 garLoopResultBuilder]: At program point L39(line 39) the Hoare annotation is: (let ((.cse0 (select |#memory_int| 1))) (and (= (select |#length| 3) 12) (<= 1 |#StackHeapBarrier|) (= 18 (select |#length| 2)) (= 2 (select |#length| 1)) (= (select |#valid| 3) 1) (= (select |#valid| 1) 1) (= (select |#valid| 0) 0) (= (select |#valid| 2) 1) (= (select .cse0 0) 48) (= (select .cse0 1) 0) (= |ULTIMATE.start_main_~x~0#1| 4))) [2023-11-19 04:53:06,452 INFO L899 garLoopResultBuilder]: For program point L39-1(line 39) no Hoare annotation was computed. [2023-11-19 04:53:06,452 INFO L899 garLoopResultBuilder]: For program point L40-2(lines 40 42) no Hoare annotation was computed. [2023-11-19 04:53:06,452 INFO L895 garLoopResultBuilder]: At program point L25(line 25) the Hoare annotation is: (and (<= 2 fibo2_~n) (= fibo2_~n |fibo2_#in~n|)) [2023-11-19 04:53:06,452 INFO L899 garLoopResultBuilder]: For program point L25-1(line 25) no Hoare annotation was computed. [2023-11-19 04:53:06,452 INFO L895 garLoopResultBuilder]: At program point L25-2(line 25) the Hoare annotation is: (let ((.cse0 (= fibo2_~n |fibo2_#in~n|))) (or (and (<= 4 |fibo2_#in~n|) .cse0) (and (= |fibo2_#t~ret6| 1) (<= 2 fibo2_~n) .cse0))) [2023-11-19 04:53:06,452 INFO L899 garLoopResultBuilder]: For program point L22(lines 22 26) no Hoare annotation was computed. [2023-11-19 04:53:06,452 INFO L899 garLoopResultBuilder]: For program point L25-3(line 25) no Hoare annotation was computed. [2023-11-19 04:53:06,452 INFO L899 garLoopResultBuilder]: For program point L20(lines 20 26) no Hoare annotation was computed. [2023-11-19 04:53:06,452 INFO L899 garLoopResultBuilder]: For program point fibo2FINAL(lines 19 27) no Hoare annotation was computed. [2023-11-19 04:53:06,452 INFO L902 garLoopResultBuilder]: At program point $Ultimate##0(lines 19 27) the Hoare annotation is: true [2023-11-19 04:53:06,453 INFO L899 garLoopResultBuilder]: For program point fibo2EXIT(lines 19 27) no Hoare annotation was computed. [2023-11-19 04:53:06,453 INFO L895 garLoopResultBuilder]: At program point L15(line 15) the Hoare annotation is: (and (< 1 |fibo1_#in~n|) (= fibo1_~n |fibo1_#in~n|)) [2023-11-19 04:53:06,453 INFO L899 garLoopResultBuilder]: For program point L15-1(line 15) no Hoare annotation was computed. [2023-11-19 04:53:06,453 INFO L895 garLoopResultBuilder]: At program point L15-2(line 15) the Hoare annotation is: (and (let ((.cse0 (= fibo1_~n |fibo1_#in~n|))) (or (and (<= 1 |fibo1_#in~n|) (= |fibo1_#t~ret4| 1) (not (= fibo1_~n 1)) .cse0) (and (<= 3 fibo1_~n) .cse0))) (let ((.cse1 (select |#memory_int| 1))) (or (not (= (select .cse1 0) 48)) (not (= 2 (select |#length| 1))) (not (= (select |#valid| 3) 1)) (= 2 |fibo1_#t~ret4|) (not (= (select |#length| 3) 12)) (not (= (select |#valid| 0) 0)) (not (= (select .cse1 1) 0)) (not (= (select |#valid| 1) 1)) (not (= 18 (select |#length| 2))) (< |#StackHeapBarrier| 1) (not (= (select |#valid| 2) 1)) (not (= |fibo1_#in~n| 4))))) [2023-11-19 04:53:06,453 INFO L899 garLoopResultBuilder]: For program point L12(lines 12 16) no Hoare annotation was computed. [2023-11-19 04:53:06,453 INFO L899 garLoopResultBuilder]: For program point L15-3(line 15) no Hoare annotation was computed. [2023-11-19 04:53:06,453 INFO L899 garLoopResultBuilder]: For program point fibo1FINAL(lines 9 17) no Hoare annotation was computed. [2023-11-19 04:53:06,454 INFO L899 garLoopResultBuilder]: For program point L10(lines 10 16) no Hoare annotation was computed. [2023-11-19 04:53:06,454 INFO L902 garLoopResultBuilder]: At program point $Ultimate##0(lines 9 17) the Hoare annotation is: true [2023-11-19 04:53:06,454 INFO L899 garLoopResultBuilder]: For program point fibo1EXIT(lines 9 17) no Hoare annotation was computed. [2023-11-19 04:53:06,457 INFO L445 BasicCegarLoop]: Path program histogram: [3, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-19 04:53:06,458 INFO L178 ceAbstractionStarter]: Computing trace abstraction results [2023-11-19 04:53:06,469 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 19.11 04:53:06 BoogieIcfgContainer [2023-11-19 04:53:06,470 INFO L131 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2023-11-19 04:53:06,470 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2023-11-19 04:53:06,470 INFO L270 PluginConnector]: Initializing Witness Printer... [2023-11-19 04:53:06,470 INFO L274 PluginConnector]: Witness Printer initialized [2023-11-19 04:53:06,471 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 19.11 04:52:54" (3/4) ... [2023-11-19 04:53:06,473 INFO L137 WitnessPrinter]: Generating witness for correct program [2023-11-19 04:53:06,477 INFO L361 RCFGBacktranslator]: Ignoring RootEdge to procedure fibo2 [2023-11-19 04:53:06,477 INFO L361 RCFGBacktranslator]: Ignoring RootEdge to procedure fibo1 [2023-11-19 04:53:06,483 INFO L943 BoogieBacktranslator]: Reduced CFG by removing 13 nodes and edges [2023-11-19 04:53:06,484 INFO L943 BoogieBacktranslator]: Reduced CFG by removing 5 nodes and edges [2023-11-19 04:53:06,484 INFO L943 BoogieBacktranslator]: Reduced CFG by removing 3 nodes and edges [2023-11-19 04:53:06,484 INFO L943 BoogieBacktranslator]: Reduced CFG by removing 1 nodes and edges [2023-11-19 04:53:06,586 INFO L149 WitnessManager]: Wrote witness to /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f655a5ba-7841-42da-b3b4-5e48da5e0710/bin/utaipan-verify-t7M7D8N6sZ/witness.graphml [2023-11-19 04:53:06,586 INFO L149 WitnessManager]: Wrote witness to /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f655a5ba-7841-42da-b3b4-5e48da5e0710/bin/utaipan-verify-t7M7D8N6sZ/witness.yml [2023-11-19 04:53:06,587 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2023-11-19 04:53:06,587 INFO L158 Benchmark]: Toolchain (without parser) took 12861.42ms. Allocated memory was 142.6MB in the beginning and 174.1MB in the end (delta: 31.5MB). Free memory was 97.3MB in the beginning and 71.7MB in the end (delta: 25.6MB). Peak memory consumption was 58.4MB. Max. memory is 16.1GB. [2023-11-19 04:53:06,588 INFO L158 Benchmark]: CDTParser took 0.20ms. Allocated memory is still 113.2MB. Free memory was 65.5MB in the beginning and 65.2MB in the end (delta: 241.2kB). There was no memory consumed. Max. memory is 16.1GB. [2023-11-19 04:53:06,589 INFO L158 Benchmark]: CACSL2BoogieTranslator took 229.95ms. Allocated memory is still 142.6MB. Free memory was 97.3MB in the beginning and 86.9MB in the end (delta: 10.4MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. [2023-11-19 04:53:06,590 INFO L158 Benchmark]: Boogie Procedure Inliner took 31.06ms. Allocated memory is still 142.6MB. Free memory was 86.9MB in the beginning and 85.6MB in the end (delta: 1.3MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2023-11-19 04:53:06,590 INFO L158 Benchmark]: Boogie Preprocessor took 45.92ms. Allocated memory is still 142.6MB. Free memory was 85.6MB in the beginning and 84.7MB in the end (delta: 924.8kB). There was no memory consumed. Max. memory is 16.1GB. [2023-11-19 04:53:06,591 INFO L158 Benchmark]: RCFGBuilder took 319.76ms. Allocated memory is still 142.6MB. Free memory was 84.7MB in the beginning and 73.5MB in the end (delta: 11.1MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. [2023-11-19 04:53:06,591 INFO L158 Benchmark]: TraceAbstraction took 12111.26ms. Allocated memory was 142.6MB in the beginning and 174.1MB in the end (delta: 31.5MB). Free memory was 73.1MB in the beginning and 75.9MB in the end (delta: -2.8MB). Peak memory consumption was 62.6MB. Max. memory is 16.1GB. [2023-11-19 04:53:06,593 INFO L158 Benchmark]: Witness Printer took 116.51ms. Allocated memory is still 174.1MB. Free memory was 75.9MB in the beginning and 71.7MB in the end (delta: 4.2MB). Peak memory consumption was 4.2MB. Max. memory is 16.1GB. [2023-11-19 04:53:06,599 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.20ms. Allocated memory is still 113.2MB. Free memory was 65.5MB in the beginning and 65.2MB in the end (delta: 241.2kB). There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 229.95ms. Allocated memory is still 142.6MB. Free memory was 97.3MB in the beginning and 86.9MB in the end (delta: 10.4MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 31.06ms. Allocated memory is still 142.6MB. Free memory was 86.9MB in the beginning and 85.6MB in the end (delta: 1.3MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * Boogie Preprocessor took 45.92ms. Allocated memory is still 142.6MB. Free memory was 85.6MB in the beginning and 84.7MB in the end (delta: 924.8kB). There was no memory consumed. Max. memory is 16.1GB. * RCFGBuilder took 319.76ms. Allocated memory is still 142.6MB. Free memory was 84.7MB in the beginning and 73.5MB in the end (delta: 11.1MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. * TraceAbstraction took 12111.26ms. Allocated memory was 142.6MB in the beginning and 174.1MB in the end (delta: 31.5MB). Free memory was 73.1MB in the beginning and 75.9MB in the end (delta: -2.8MB). Peak memory consumption was 62.6MB. Max. memory is 16.1GB. * Witness Printer took 116.51ms. Allocated memory is still 174.1MB. Free memory was 75.9MB in the beginning and 71.7MB 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: 41]: 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 3 procedures, 26 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 12.0s, OverallIterations: 11, TraceHistogramMax: 6, PathProgramHistogramMax: 3, EmptinessCheckTime: 0.0s, AutomataDifference: 2.2s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.7s, InitialAbstractionConstructionTime: 0.0s, HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 333 SdHoareTripleChecker+Valid, 1.3s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 284 mSDsluCounter, 1830 SdHoareTripleChecker+Invalid, 1.1s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 1564 mSDsCounter, 196 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 1567 IncrementalHoareTripleChecker+Invalid, 1763 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 196 mSolverCounterUnsat, 266 mSDtfsCounter, 1567 mSolverCounterSat, 0.1s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 1016 GetRequests, 827 SyntacticMatches, 27 SemanticMatches, 162 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 400 ImplicationChecksByTransitivity, 1.9s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=121occurred in iteration=10, InterpolantAutomatonStates: 110, 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, 11 MinimizatonAttempts, 88 StatesRemovedByMinimization, 9 NontrivialMinimizations, HoareAnnotationStatistics: 0.0s HoareAnnotationTime, 7 LocationsWithAnnotation, 217 PreInvPairs, 295 NumberOfFragments, 182 HoareAnnotationTreeSize, 217 FomulaSimplifications, 6567 FormulaSimplificationTreeSizeReduction, 0.2s HoareSimplificationTime, 7 FomulaSimplificationsInter, 1265 FormulaSimplificationTreeSizeReductionInter, 0.5s HoareSimplificationTimeInter, RefinementEngineStatistics: TRACE_CHECK: 0.1s SsaConstructionTime, 0.3s SatisfiabilityAnalysisTime, 5.3s InterpolantComputationTime, 949 NumberOfCodeBlocks, 897 NumberOfCodeBlocksAsserted, 21 NumberOfCheckSat, 1309 ConstructedInterpolants, 0 QuantifiedInterpolants, 2702 SizeOfPredicates, 23 NumberOfNonLiveVariables, 1080 ConjunctsInSsa, 102 ConjunctsInUnsatCore, 28 InterpolantComputations, 3 PerfectInterpolantSequences, 1009/1389 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: OVERALL_TIME: 0.2s, ICFG_INTERPRETER_ENTERED_PROCEDURES: 3, DAG_INTERPRETER_EARLY_EXIT_QUERIES_NONTRIVIAL: 15, DAG_INTERPRETER_EARLY_EXITS: 6, TOOLS_POST_APPLICATIONS: 13, TOOLS_POST_TIME: 0.0s, TOOLS_POST_CALL_APPLICATIONS: 8, TOOLS_POST_CALL_TIME: 0.1s, TOOLS_POST_RETURN_APPLICATIONS: 6, TOOLS_POST_RETURN_TIME: 0.0s, TOOLS_QUANTIFIERELIM_APPLICATIONS: 26, TOOLS_QUANTIFIERELIM_TIME: 0.1s, TOOLS_QUANTIFIERELIM_MAX_TIME: 0.0s, FLUID_QUERY_TIME: 0.0s, FLUID_QUERIES: 35, FLUID_YES_ANSWERS: 0, DOMAIN_JOIN_APPLICATIONS: 1, DOMAIN_JOIN_TIME: 0.0s, DOMAIN_ALPHA_APPLICATIONS: 0, DOMAIN_ALPHA_TIME: 0.0s, DOMAIN_WIDEN_APPLICATIONS: 0, DOMAIN_WIDEN_TIME: 0.0s, DOMAIN_ISSUBSETEQ_APPLICATIONS: 0, DOMAIN_ISSUBSETEQ_TIME: 0.0s, DOMAIN_ISBOTTOM_APPLICATIONS: 15, DOMAIN_ISBOTTOM_TIME: 0.0s, LOOP_SUMMARIZER_APPLICATIONS: 0, LOOP_SUMMARIZER_CACHE_MISSES: 0, LOOP_SUMMARIZER_OVERALL_TIME: 0.0s, LOOP_SUMMARIZER_NEW_COMPUTATION_TIME: 0.0s, LOOP_SUMMARIZER_FIXPOINT_ITERATIONS: 0, CALL_SUMMARIZER_APPLICATIONS: 6, CALL_SUMMARIZER_CACHE_MISSES: 2, CALL_SUMMARIZER_OVERALL_TIME: 0.0s, CALL_SUMMARIZER_NEW_COMPUTATION_TIME: 0.0s, PROCEDURE_GRAPH_BUILDER_TIME: 0.0s, PATH_EXPR_TIME: 0.0s, REGEX_TO_DAG_TIME: 0.0s, DAG_COMPRESSION_TIME: 0.0s, DAG_COMPRESSION_PROCESSED_NODES: 142, DAG_COMPRESSION_RETAINED_NODES: 53, ReuseStatistics: No data available - AllSpecificationsHoldResult: All specifications hold 1 specifications checked. All of them hold RESULT: Ultimate proved your program to be correct! [2023-11-19 04:53:06,640 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f655a5ba-7841-42da-b3b4-5e48da5e0710/bin/utaipan-verify-t7M7D8N6sZ/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Forceful destruction successful, exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Writing output log to file Ultimate.log Result: TRUE