./Ultimate.py --spec ../../sv-benchmarks/c/properties/unreach-call.prp --file ../../sv-benchmarks/c/recursive-simple/fibo_2calls_8-2.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_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/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_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/config/TaipanReach.xml -i ../../sv-benchmarks/c/recursive-simple/fibo_2calls_8-2.c -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/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_ec6f9631-26aa-41f0-a01a-1f395959bae2/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 5952061731474d390646c291ccf1d0136c1d856e30481accbc86db371431d703 --- Real Ultimate output --- This is Ultimate 0.2.3-dev-9bd2c7f [2023-11-19 04:48:18,461 INFO L188 SettingsManager]: Resetting all preferences to default values... [2023-11-19 04:48:18,609 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/config/svcomp-Reach-32bit-Taipan_Default.epf [2023-11-19 04:48:18,624 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2023-11-19 04:48:18,625 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2023-11-19 04:48:18,674 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2023-11-19 04:48:18,675 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2023-11-19 04:48:18,676 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2023-11-19 04:48:18,677 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2023-11-19 04:48:18,683 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2023-11-19 04:48:18,684 INFO L153 SettingsManager]: * User list type=DISABLED [2023-11-19 04:48:18,686 INFO L151 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2023-11-19 04:48:18,686 INFO L153 SettingsManager]: * Explicit value domain=true [2023-11-19 04:48:18,689 INFO L153 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2023-11-19 04:48:18,689 INFO L153 SettingsManager]: * Octagon Domain=false [2023-11-19 04:48:18,690 INFO L153 SettingsManager]: * Abstract domain=CompoundDomain [2023-11-19 04:48:18,690 INFO L153 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2023-11-19 04:48:18,691 INFO L153 SettingsManager]: * Use the RCFG-of-the-future interface=true [2023-11-19 04:48:18,692 INFO L153 SettingsManager]: * Interval Domain=false [2023-11-19 04:48:18,692 INFO L151 SettingsManager]: Preferences of Sifa differ from their defaults: [2023-11-19 04:48:18,693 INFO L153 SettingsManager]: * Call Summarizer=TopInputCallSummarizer [2023-11-19 04:48:18,694 INFO L153 SettingsManager]: * Simplification Technique=POLY_PAC [2023-11-19 04:48:18,695 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2023-11-19 04:48:18,696 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2023-11-19 04:48:18,696 INFO L153 SettingsManager]: * sizeof long=4 [2023-11-19 04:48:18,697 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2023-11-19 04:48:18,698 INFO L153 SettingsManager]: * sizeof POINTER=4 [2023-11-19 04:48:18,698 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2023-11-19 04:48:18,699 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2023-11-19 04:48:18,699 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2023-11-19 04:48:18,701 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2023-11-19 04:48:18,701 INFO L153 SettingsManager]: * sizeof long double=12 [2023-11-19 04:48:18,702 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2023-11-19 04:48:18,702 INFO L153 SettingsManager]: * Use constant arrays=true [2023-11-19 04:48:18,703 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2023-11-19 04:48:18,703 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2023-11-19 04:48:18,703 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-11-19 04:48:18,704 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2023-11-19 04:48:18,704 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2023-11-19 04:48:18,704 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2023-11-19 04:48:18,705 INFO L153 SettingsManager]: * Trace refinement strategy=SIFA_TAIPAN [2023-11-19 04:48:18,705 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2023-11-19 04:48:18,706 INFO L153 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2023-11-19 04:48:18,706 INFO L153 SettingsManager]: * Trace refinement exception blacklist=NONE [2023-11-19 04:48:18,707 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2023-11-19 04:48:18,707 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_ec6f9631-26aa-41f0-a01a-1f395959bae2/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_ec6f9631-26aa-41f0-a01a-1f395959bae2/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 -> 5952061731474d390646c291ccf1d0136c1d856e30481accbc86db371431d703 [2023-11-19 04:48:19,021 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2023-11-19 04:48:19,052 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2023-11-19 04:48:19,055 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2023-11-19 04:48:19,057 INFO L270 PluginConnector]: Initializing CDTParser... [2023-11-19 04:48:19,057 INFO L274 PluginConnector]: CDTParser initialized [2023-11-19 04:48:19,060 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/../../sv-benchmarks/c/recursive-simple/fibo_2calls_8-2.c [2023-11-19 04:48:22,527 INFO L533 CDTParser]: Created temporary CDT project at NULL [2023-11-19 04:48:22,748 INFO L384 CDTParser]: Found 1 translation units. [2023-11-19 04:48:22,749 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/sv-benchmarks/c/recursive-simple/fibo_2calls_8-2.c [2023-11-19 04:48:22,758 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/data/36a3ff44f/e6c70b61669946e89345c71c0d635272/FLAGd5cbf8704 [2023-11-19 04:48:22,773 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/data/36a3ff44f/e6c70b61669946e89345c71c0d635272 [2023-11-19 04:48:22,776 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2023-11-19 04:48:22,778 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2023-11-19 04:48:22,780 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2023-11-19 04:48:22,780 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2023-11-19 04:48:22,787 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2023-11-19 04:48:22,788 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 19.11 04:48:22" (1/1) ... [2023-11-19 04:48:22,789 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@458d4f0f and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 04:48:22, skipping insertion in model container [2023-11-19 04:48:22,790 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 19.11 04:48:22" (1/1) ... [2023-11-19 04:48:22,814 INFO L177 MainTranslator]: Built tables and reachable declarations [2023-11-19 04:48:22,988 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_ec6f9631-26aa-41f0-a01a-1f395959bae2/sv-benchmarks/c/recursive-simple/fibo_2calls_8-2.c[947,960] [2023-11-19 04:48:22,994 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-19 04:48:23,006 INFO L202 MainTranslator]: Completed pre-run [2023-11-19 04:48:23,023 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_ec6f9631-26aa-41f0-a01a-1f395959bae2/sv-benchmarks/c/recursive-simple/fibo_2calls_8-2.c[947,960] [2023-11-19 04:48:23,024 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-19 04:48:23,042 INFO L206 MainTranslator]: Completed translation [2023-11-19 04:48:23,043 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 04:48:23 WrapperNode [2023-11-19 04:48:23,043 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2023-11-19 04:48:23,044 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2023-11-19 04:48:23,044 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2023-11-19 04:48:23,044 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2023-11-19 04:48:23,052 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:48:23" (1/1) ... [2023-11-19 04:48:23,060 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:48:23" (1/1) ... [2023-11-19 04:48:23,077 INFO L138 Inliner]: procedures = 14, calls = 12, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 20 [2023-11-19 04:48:23,077 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2023-11-19 04:48:23,078 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2023-11-19 04:48:23,079 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2023-11-19 04:48:23,079 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2023-11-19 04:48:23,089 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 04:48:23" (1/1) ... [2023-11-19 04:48:23,090 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 04:48:23" (1/1) ... [2023-11-19 04:48:23,091 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 04:48:23" (1/1) ... [2023-11-19 04:48:23,092 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 04:48:23" (1/1) ... [2023-11-19 04:48:23,096 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 04:48:23" (1/1) ... [2023-11-19 04:48:23,098 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 04:48:23" (1/1) ... [2023-11-19 04:48:23,099 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 04:48:23" (1/1) ... [2023-11-19 04:48:23,100 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 04:48:23" (1/1) ... [2023-11-19 04:48:23,102 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2023-11-19 04:48:23,104 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2023-11-19 04:48:23,104 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2023-11-19 04:48:23,104 INFO L274 PluginConnector]: RCFGBuilder initialized [2023-11-19 04:48:23,105 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 04:48:23" (1/1) ... [2023-11-19 04:48:23,127 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-11-19 04:48:23,143 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 04:48:23,159 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/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:48:23,171 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/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:48:23,196 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2023-11-19 04:48:23,196 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2023-11-19 04:48:23,196 INFO L130 BoogieDeclarations]: Found specification of procedure fibo2 [2023-11-19 04:48:23,196 INFO L138 BoogieDeclarations]: Found implementation of procedure fibo2 [2023-11-19 04:48:23,197 INFO L130 BoogieDeclarations]: Found specification of procedure fibo1 [2023-11-19 04:48:23,197 INFO L138 BoogieDeclarations]: Found implementation of procedure fibo1 [2023-11-19 04:48:23,197 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2023-11-19 04:48:23,197 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2023-11-19 04:48:23,279 INFO L236 CfgBuilder]: Building ICFG [2023-11-19 04:48:23,282 INFO L262 CfgBuilder]: Building CFG for each procedure with an implementation [2023-11-19 04:48:23,477 INFO L277 CfgBuilder]: Performing block encoding [2023-11-19 04:48:23,509 INFO L297 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2023-11-19 04:48:23,510 INFO L302 CfgBuilder]: Removed 0 assume(true) statements. [2023-11-19 04:48:23,515 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 19.11 04:48:23 BoogieIcfgContainer [2023-11-19 04:48:23,516 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2023-11-19 04:48:23,524 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2023-11-19 04:48:23,524 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2023-11-19 04:48:23,529 INFO L274 PluginConnector]: TraceAbstraction initialized [2023-11-19 04:48:23,529 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 19.11 04:48:22" (1/3) ... [2023-11-19 04:48:23,530 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5145f559 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 19.11 04:48:23, skipping insertion in model container [2023-11-19 04:48:23,530 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 04:48:23" (2/3) ... [2023-11-19 04:48:23,531 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5145f559 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 19.11 04:48:23, skipping insertion in model container [2023-11-19 04:48:23,531 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 19.11 04:48:23" (3/3) ... [2023-11-19 04:48:23,533 INFO L112 eAbstractionObserver]: Analyzing ICFG fibo_2calls_8-2.c [2023-11-19 04:48:23,565 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2023-11-19 04:48:23,566 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2023-11-19 04:48:23,644 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-11-19 04:48:23,653 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;@6f3b52d4, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2023-11-19 04:48:23,653 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2023-11-19 04:48:23,659 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:48:23,669 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 10 [2023-11-19 04:48:23,687 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 04:48:23,688 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-19 04:48:23,688 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 04:48:23,695 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 04:48:23,695 INFO L85 PathProgramCache]: Analyzing trace with hash 2097990987, now seen corresponding path program 1 times [2023-11-19 04:48:23,709 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 04:48:23,711 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [624981301] [2023-11-19 04:48:23,711 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 04:48:23,712 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 04:48:23,887 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 04:48:24,100 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:48:24,101 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 04:48:24,101 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [624981301] [2023-11-19 04:48:24,102 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [624981301] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-19 04:48:24,103 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-19 04:48:24,103 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2023-11-19 04:48:24,105 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1054662595] [2023-11-19 04:48:24,107 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-19 04:48:24,112 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-11-19 04:48:24,113 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 04:48:24,150 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-11-19 04:48:24,151 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2023-11-19 04:48:24,154 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, 5 states have (on average 1.4) 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:48:24,262 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 04:48:24,262 INFO L93 Difference]: Finished difference Result 35 states and 44 transitions. [2023-11-19 04:48:24,264 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2023-11-19 04:48:24,266 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.4) 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:48:24,266 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 04:48:24,276 INFO L225 Difference]: With dead ends: 35 [2023-11-19 04:48:24,276 INFO L226 Difference]: Without dead ends: 26 [2023-11-19 04:48:24,280 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2023-11-19 04:48:24,285 INFO L413 NwaCegarLoop]: 28 mSDtfsCounter, 1 mSDsluCounter, 80 mSDsCounter, 0 mSdLazyCounter, 19 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1 SdHoareTripleChecker+Valid, 108 SdHoareTripleChecker+Invalid, 19 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 19 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-19 04:48:24,286 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [1 Valid, 108 Invalid, 19 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 19 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-19 04:48:24,304 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 26 states. [2023-11-19 04:48:24,327 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 26 to 26. [2023-11-19 04:48:24,329 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:48:24,331 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 33 transitions. [2023-11-19 04:48:24,333 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 33 transitions. Word has length 9 [2023-11-19 04:48:24,333 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 04:48:24,333 INFO L495 AbstractCegarLoop]: Abstraction has 26 states and 33 transitions. [2023-11-19 04:48:24,334 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.4) 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:48:24,334 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 33 transitions. [2023-11-19 04:48:24,335 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 11 [2023-11-19 04:48:24,336 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 04:48:24,336 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-19 04:48:24,336 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2023-11-19 04:48:24,337 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 04:48:24,337 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 04:48:24,338 INFO L85 PathProgramCache]: Analyzing trace with hash 1328370967, now seen corresponding path program 1 times [2023-11-19 04:48:24,338 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 04:48:24,338 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1643522554] [2023-11-19 04:48:24,339 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 04:48:24,339 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 04:48:24,354 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 04:48:24,428 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:48:24,429 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 04:48:24,429 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1643522554] [2023-11-19 04:48:24,429 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1643522554] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-19 04:48:24,430 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-19 04:48:24,430 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2023-11-19 04:48:24,430 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1980802738] [2023-11-19 04:48:24,431 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-19 04:48:24,432 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-11-19 04:48:24,432 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 04:48:24,433 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-11-19 04:48:24,434 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2023-11-19 04:48:24,434 INFO L87 Difference]: Start difference. First operand 26 states and 33 transitions. Second operand has 5 states, 5 states have (on average 1.6) 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:48:24,462 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 04:48:24,462 INFO L93 Difference]: Finished difference Result 32 states and 40 transitions. [2023-11-19 04:48:24,463 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2023-11-19 04:48:24,463 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.6) 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:48:24,464 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 04:48:24,465 INFO L225 Difference]: With dead ends: 32 [2023-11-19 04:48:24,465 INFO L226 Difference]: Without dead ends: 28 [2023-11-19 04:48:24,466 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2023-11-19 04:48:24,468 INFO L413 NwaCegarLoop]: 31 mSDtfsCounter, 0 mSDsluCounter, 88 mSDsCounter, 0 mSdLazyCounter, 11 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 119 SdHoareTripleChecker+Invalid, 11 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 11 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-11-19 04:48:24,469 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 119 Invalid, 11 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 11 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-11-19 04:48:24,483 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 28 states. [2023-11-19 04:48:24,490 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 28 to 26. [2023-11-19 04:48:24,491 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:48:24,493 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 33 transitions. [2023-11-19 04:48:24,493 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 33 transitions. Word has length 10 [2023-11-19 04:48:24,494 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 04:48:24,494 INFO L495 AbstractCegarLoop]: Abstraction has 26 states and 33 transitions. [2023-11-19 04:48:24,494 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.6) 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:48:24,495 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 33 transitions. [2023-11-19 04:48:24,496 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2023-11-19 04:48:24,496 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 04:48:24,497 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:48:24,497 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2023-11-19 04:48:24,497 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 04:48:24,498 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 04:48:24,498 INFO L85 PathProgramCache]: Analyzing trace with hash -1296553538, now seen corresponding path program 1 times [2023-11-19 04:48:24,499 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 04:48:24,499 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [306903850] [2023-11-19 04:48:24,499 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 04:48:24,500 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 04:48:24,548 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 04:48:24,691 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:48:24,691 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 04:48:24,692 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [306903850] [2023-11-19 04:48:24,692 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [306903850] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-19 04:48:24,692 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [278059550] [2023-11-19 04:48:24,693 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 04:48:24,693 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 04:48:24,693 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 04:48:24,696 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 04:48:24,712 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2023-11-19 04:48:24,794 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 04:48:24,800 INFO L262 TraceCheckSpWp]: Trace formula consists of 71 conjuncts, 6 conjunts are in the unsatisfiable core [2023-11-19 04:48:24,807 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-19 04:48:24,927 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:48:24,929 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-19 04:48:25,155 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:48:25,156 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [278059550] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-19 04:48:25,156 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [680599243] [2023-11-19 04:48:25,180 INFO L159 IcfgInterpreter]: Started Sifa with 19 locations of interest [2023-11-19 04:48:25,180 INFO L166 IcfgInterpreter]: Building call graph [2023-11-19 04:48:25,184 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-19 04:48:25,191 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-19 04:48:25,191 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-19 04:48:25,339 INFO L197 IcfgInterpreter]: Interpreting procedure fibo1 with input of size 35 for LOIs [2023-11-19 04:48:25,424 INFO L197 IcfgInterpreter]: Interpreting procedure fibo2 with input of size 35 for LOIs [2023-11-19 04:48:25,438 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-19 04:48:25,742 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSifa [680599243] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-19 04:48:25,747 INFO L185 FreeRefinementEngine]: Found 1 perfect and 3 imperfect interpolant sequences. [2023-11-19 04:48:25,748 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [6, 7, 7] total 17 [2023-11-19 04:48:25,749 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [831218789] [2023-11-19 04:48:25,749 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-19 04:48:25,750 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2023-11-19 04:48:25,751 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 04:48:25,753 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2023-11-19 04:48:25,755 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=48, Invalid=224, Unknown=0, NotChecked=0, Total=272 [2023-11-19 04:48:25,756 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:48:25,946 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 04:48:25,946 INFO L93 Difference]: Finished difference Result 68 states and 91 transitions. [2023-11-19 04:48:25,947 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2023-11-19 04:48:25,947 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:48:25,947 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 04:48:25,955 INFO L225 Difference]: With dead ends: 68 [2023-11-19 04:48:25,955 INFO L226 Difference]: Without dead ends: 44 [2023-11-19 04:48:25,957 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:48:25,960 INFO L413 NwaCegarLoop]: 28 mSDtfsCounter, 11 mSDsluCounter, 91 mSDsCounter, 0 mSdLazyCounter, 85 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 16 SdHoareTripleChecker+Valid, 119 SdHoareTripleChecker+Invalid, 88 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 85 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-19 04:48:25,963 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [16 Valid, 119 Invalid, 88 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 85 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-19 04:48:25,965 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 44 states. [2023-11-19 04:48:25,987 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 44 to 42. [2023-11-19 04:48:25,988 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:48:25,990 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 42 states to 42 states and 50 transitions. [2023-11-19 04:48:25,990 INFO L78 Accepts]: Start accepts. Automaton has 42 states and 50 transitions. Word has length 22 [2023-11-19 04:48:25,991 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 04:48:25,991 INFO L495 AbstractCegarLoop]: Abstraction has 42 states and 50 transitions. [2023-11-19 04:48:25,992 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:48:25,993 INFO L276 IsEmpty]: Start isEmpty. Operand 42 states and 50 transitions. [2023-11-19 04:48:25,996 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2023-11-19 04:48:25,997 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 04:48:25,997 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:48:26,025 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2023-11-19 04:48:26,220 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 04:48:26,220 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 04:48:26,221 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 04:48:26,221 INFO L85 PathProgramCache]: Analyzing trace with hash -28918515, now seen corresponding path program 1 times [2023-11-19 04:48:26,221 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 04:48:26,221 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [613283254] [2023-11-19 04:48:26,222 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 04:48:26,222 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 04:48:26,245 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 04:48:26,389 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:48:26,389 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 04:48:26,389 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [613283254] [2023-11-19 04:48:26,390 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [613283254] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-19 04:48:26,393 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1378911856] [2023-11-19 04:48:26,393 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 04:48:26,397 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 04:48:26,397 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 04:48:26,398 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 04:48:26,437 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2023-11-19 04:48:26,475 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 04:48:26,476 INFO L262 TraceCheckSpWp]: Trace formula consists of 100 conjuncts, 8 conjunts are in the unsatisfiable core [2023-11-19 04:48:26,479 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-19 04:48:26,574 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:48:26,574 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-19 04:48:27,035 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:48:27,036 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1378911856] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-19 04:48:27,036 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1444070357] [2023-11-19 04:48:27,040 INFO L159 IcfgInterpreter]: Started Sifa with 24 locations of interest [2023-11-19 04:48:27,040 INFO L166 IcfgInterpreter]: Building call graph [2023-11-19 04:48:27,042 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:48:27,044 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-19 04:48:27,044 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 8, 9] total 14 [2023-11-19 04:48:27,045 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1171398584] [2023-11-19 04:48:27,045 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-19 04:48:27,046 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2023-11-19 04:48:27,046 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 04:48:27,047 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2023-11-19 04:48:27,047 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=36, Invalid=146, Unknown=0, NotChecked=0, Total=182 [2023-11-19 04:48:27,048 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:48:27,327 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 04:48:27,327 INFO L93 Difference]: Finished difference Result 85 states and 121 transitions. [2023-11-19 04:48:27,328 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2023-11-19 04:48:27,328 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:48:27,329 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 04:48:27,330 INFO L225 Difference]: With dead ends: 85 [2023-11-19 04:48:27,331 INFO L226 Difference]: Without dead ends: 53 [2023-11-19 04:48:27,332 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:48:27,333 INFO L413 NwaCegarLoop]: 18 mSDtfsCounter, 35 mSDsluCounter, 86 mSDsCounter, 0 mSdLazyCounter, 127 mSolverCounterSat, 24 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 40 SdHoareTripleChecker+Valid, 104 SdHoareTripleChecker+Invalid, 151 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 24 IncrementalHoareTripleChecker+Valid, 127 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-11-19 04:48:27,334 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [40 Valid, 104 Invalid, 151 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [24 Valid, 127 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-11-19 04:48:27,335 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 53 states. [2023-11-19 04:48:27,349 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 53 to 44. [2023-11-19 04:48:27,350 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:48:27,351 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 44 states to 44 states and 53 transitions. [2023-11-19 04:48:27,352 INFO L78 Accepts]: Start accepts. Automaton has 44 states and 53 transitions. Word has length 35 [2023-11-19 04:48:27,352 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 04:48:27,352 INFO L495 AbstractCegarLoop]: Abstraction has 44 states and 53 transitions. [2023-11-19 04:48:27,353 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:48:27,353 INFO L276 IsEmpty]: Start isEmpty. Operand 44 states and 53 transitions. [2023-11-19 04:48:27,355 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2023-11-19 04:48:27,355 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 04:48:27,356 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:48:27,389 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2023-11-19 04:48:27,580 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 04:48:27,581 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 04:48:27,581 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 04:48:27,582 INFO L85 PathProgramCache]: Analyzing trace with hash -243412115, now seen corresponding path program 1 times [2023-11-19 04:48:27,582 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 04:48:27,582 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1680179391] [2023-11-19 04:48:27,582 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 04:48:27,583 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 04:48:27,602 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 04:48:27,769 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:48:27,770 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 04:48:27,771 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1680179391] [2023-11-19 04:48:27,771 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1680179391] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-19 04:48:27,772 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [25735926] [2023-11-19 04:48:27,772 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 04:48:27,772 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 04:48:27,773 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 04:48:27,774 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 04:48:27,806 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2023-11-19 04:48:27,846 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 04:48:27,847 INFO L262 TraceCheckSpWp]: Trace formula consists of 102 conjuncts, 8 conjunts are in the unsatisfiable core [2023-11-19 04:48:27,850 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-19 04:48:27,962 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:48:27,962 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-19 04:48:28,407 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:48:28,408 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [25735926] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-19 04:48:28,408 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1392193109] [2023-11-19 04:48:28,412 INFO L159 IcfgInterpreter]: Started Sifa with 24 locations of interest [2023-11-19 04:48:28,412 INFO L166 IcfgInterpreter]: Building call graph [2023-11-19 04:48:28,413 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:48:28,417 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-19 04:48:28,418 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 8, 9] total 18 [2023-11-19 04:48:28,418 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [231637081] [2023-11-19 04:48:28,420 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-19 04:48:28,422 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2023-11-19 04:48:28,423 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 04:48:28,425 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2023-11-19 04:48:28,426 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=49, Invalid=257, Unknown=0, NotChecked=0, Total=306 [2023-11-19 04:48:28,426 INFO L87 Difference]: Start difference. First operand 44 states and 53 transitions. Second operand has 18 states, 16 states have (on average 3.0625) internal successors, (49), 18 states have internal predecessors, (49), 11 states have call successors, (13), 1 states have call predecessors, (13), 7 states have return successors, (13), 6 states have call predecessors, (13), 11 states have call successors, (13) [2023-11-19 04:48:28,994 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 04:48:28,994 INFO L93 Difference]: Finished difference Result 121 states and 203 transitions. [2023-11-19 04:48:28,995 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2023-11-19 04:48:28,995 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 16 states have (on average 3.0625) internal successors, (49), 18 states have internal predecessors, (49), 11 states have call successors, (13), 1 states have call predecessors, (13), 7 states have return successors, (13), 6 states have call predecessors, (13), 11 states have call successors, (13) Word has length 36 [2023-11-19 04:48:28,996 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 04:48:29,003 INFO L225 Difference]: With dead ends: 121 [2023-11-19 04:48:29,003 INFO L226 Difference]: Without dead ends: 77 [2023-11-19 04:48:29,010 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 98 GetRequests, 68 SyntacticMatches, 3 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 126 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=142, Invalid=670, Unknown=0, NotChecked=0, Total=812 [2023-11-19 04:48:29,011 INFO L413 NwaCegarLoop]: 28 mSDtfsCounter, 52 mSDsluCounter, 177 mSDsCounter, 0 mSdLazyCounter, 339 mSolverCounterSat, 43 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 56 SdHoareTripleChecker+Valid, 205 SdHoareTripleChecker+Invalid, 382 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 43 IncrementalHoareTripleChecker+Valid, 339 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2023-11-19 04:48:29,012 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [56 Valid, 205 Invalid, 382 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [43 Valid, 339 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2023-11-19 04:48:29,013 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 77 states. [2023-11-19 04:48:29,051 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 77 to 63. [2023-11-19 04:48:29,054 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:48:29,062 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 63 states to 63 states and 91 transitions. [2023-11-19 04:48:29,062 INFO L78 Accepts]: Start accepts. Automaton has 63 states and 91 transitions. Word has length 36 [2023-11-19 04:48:29,063 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 04:48:29,063 INFO L495 AbstractCegarLoop]: Abstraction has 63 states and 91 transitions. [2023-11-19 04:48:29,063 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 18 states, 16 states have (on average 3.0625) internal successors, (49), 18 states have internal predecessors, (49), 11 states have call successors, (13), 1 states have call predecessors, (13), 7 states have return successors, (13), 6 states have call predecessors, (13), 11 states have call successors, (13) [2023-11-19 04:48:29,063 INFO L276 IsEmpty]: Start isEmpty. Operand 63 states and 91 transitions. [2023-11-19 04:48:29,074 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2023-11-19 04:48:29,074 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 04:48:29,075 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:48:29,104 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2023-11-19 04:48:29,297 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 04:48:29,298 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 04:48:29,298 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 04:48:29,298 INFO L85 PathProgramCache]: Analyzing trace with hash 403750738, now seen corresponding path program 1 times [2023-11-19 04:48:29,298 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 04:48:29,299 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2140172172] [2023-11-19 04:48:29,299 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 04:48:29,299 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 04:48:29,320 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 04:48:29,526 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:48:29,527 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 04:48:29,527 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2140172172] [2023-11-19 04:48:29,527 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2140172172] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-19 04:48:29,527 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [782110276] [2023-11-19 04:48:29,527 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 04:48:29,528 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 04:48:29,528 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 04:48:29,529 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 04:48:29,536 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2023-11-19 04:48:29,603 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 04:48:29,604 INFO L262 TraceCheckSpWp]: Trace formula consists of 133 conjuncts, 10 conjunts are in the unsatisfiable core [2023-11-19 04:48:29,611 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-19 04:48:29,724 INFO L134 CoverageAnalysis]: Checked inductivity of 44 backedges. 4 proven. 23 refuted. 0 times theorem prover too weak. 17 trivial. 0 not checked. [2023-11-19 04:48:29,724 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-19 04:48:30,381 INFO L134 CoverageAnalysis]: Checked inductivity of 44 backedges. 4 proven. 28 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2023-11-19 04:48:30,381 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [782110276] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-19 04:48:30,381 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [330953784] [2023-11-19 04:48:30,388 INFO L159 IcfgInterpreter]: Started Sifa with 24 locations of interest [2023-11-19 04:48:30,388 INFO L166 IcfgInterpreter]: Building call graph [2023-11-19 04:48:30,389 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:48:30,390 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-19 04:48:30,391 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 9, 11] total 17 [2023-11-19 04:48:30,391 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1882386927] [2023-11-19 04:48:30,391 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-19 04:48:30,393 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2023-11-19 04:48:30,394 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 04:48:30,395 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2023-11-19 04:48:30,395 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=55, Invalid=217, Unknown=0, NotChecked=0, Total=272 [2023-11-19 04:48:30,396 INFO L87 Difference]: Start difference. First operand 63 states and 91 transitions. Second operand has 17 states, 15 states have (on average 3.6) internal successors, (54), 17 states have internal predecessors, (54), 12 states have call successors, (14), 1 states have call predecessors, (14), 8 states have return successors, (18), 8 states have call predecessors, (18), 12 states have call successors, (18) [2023-11-19 04:48:30,680 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 04:48:30,680 INFO L93 Difference]: Finished difference Result 119 states and 203 transitions. [2023-11-19 04:48:30,681 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2023-11-19 04:48:30,681 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 15 states have (on average 3.6) internal successors, (54), 17 states have internal predecessors, (54), 12 states have call successors, (14), 1 states have call predecessors, (14), 8 states have return successors, (18), 8 states have call predecessors, (18), 12 states have call successors, (18) Word has length 50 [2023-11-19 04:48:30,682 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 04:48:30,684 INFO L225 Difference]: With dead ends: 119 [2023-11-19 04:48:30,685 INFO L226 Difference]: Without dead ends: 97 [2023-11-19 04:48:30,686 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 117 GetRequests, 91 SyntacticMatches, 4 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 108 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=115, Invalid=437, Unknown=0, NotChecked=0, Total=552 [2023-11-19 04:48:30,687 INFO L413 NwaCegarLoop]: 16 mSDtfsCounter, 44 mSDsluCounter, 85 mSDsCounter, 0 mSdLazyCounter, 112 mSolverCounterSat, 37 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 56 SdHoareTripleChecker+Valid, 101 SdHoareTripleChecker+Invalid, 149 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 37 IncrementalHoareTripleChecker+Valid, 112 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-19 04:48:30,688 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [56 Valid, 101 Invalid, 149 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [37 Valid, 112 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-19 04:48:30,689 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 97 states. [2023-11-19 04:48:30,714 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 97 to 72. [2023-11-19 04:48:30,715 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 72 states, 46 states have (on average 1.1304347826086956) internal successors, (52), 49 states have internal predecessors, (52), 14 states have call successors, (14), 5 states have call predecessors, (14), 11 states have return successors, (39), 17 states have call predecessors, (39), 14 states have call successors, (39) [2023-11-19 04:48:30,717 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 72 states to 72 states and 105 transitions. [2023-11-19 04:48:30,717 INFO L78 Accepts]: Start accepts. Automaton has 72 states and 105 transitions. Word has length 50 [2023-11-19 04:48:30,718 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 04:48:30,718 INFO L495 AbstractCegarLoop]: Abstraction has 72 states and 105 transitions. [2023-11-19 04:48:30,719 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 15 states have (on average 3.6) internal successors, (54), 17 states have internal predecessors, (54), 12 states have call successors, (14), 1 states have call predecessors, (14), 8 states have return successors, (18), 8 states have call predecessors, (18), 12 states have call successors, (18) [2023-11-19 04:48:30,719 INFO L276 IsEmpty]: Start isEmpty. Operand 72 states and 105 transitions. [2023-11-19 04:48:30,722 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 93 [2023-11-19 04:48:30,723 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 04:48:30,723 INFO L195 NwaCegarLoop]: trace histogram [7, 7, 6, 6, 6, 5, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-19 04:48:30,755 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2023-11-19 04:48:30,948 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable5 [2023-11-19 04:48:30,949 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 04:48:30,949 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 04:48:30,949 INFO L85 PathProgramCache]: Analyzing trace with hash -1002637961, now seen corresponding path program 1 times [2023-11-19 04:48:30,950 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 04:48:30,950 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [933525698] [2023-11-19 04:48:30,950 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 04:48:30,950 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 04:48:30,985 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 04:48:31,270 INFO L134 CoverageAnalysis]: Checked inductivity of 193 backedges. 40 proven. 59 refuted. 0 times theorem prover too weak. 94 trivial. 0 not checked. [2023-11-19 04:48:31,270 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 04:48:31,271 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [933525698] [2023-11-19 04:48:31,271 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [933525698] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-19 04:48:31,271 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [705920238] [2023-11-19 04:48:31,271 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 04:48:31,271 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 04:48:31,271 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 04:48:31,272 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 04:48:31,276 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2023-11-19 04:48:31,370 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 04:48:31,372 INFO L262 TraceCheckSpWp]: Trace formula consists of 226 conjuncts, 12 conjunts are in the unsatisfiable core [2023-11-19 04:48:31,376 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-19 04:48:31,544 INFO L134 CoverageAnalysis]: Checked inductivity of 193 backedges. 13 proven. 92 refuted. 0 times theorem prover too weak. 88 trivial. 0 not checked. [2023-11-19 04:48:31,545 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-19 04:48:32,723 INFO L134 CoverageAnalysis]: Checked inductivity of 193 backedges. 13 proven. 102 refuted. 0 times theorem prover too weak. 78 trivial. 0 not checked. [2023-11-19 04:48:32,723 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [705920238] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-19 04:48:32,723 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1552082532] [2023-11-19 04:48:32,730 INFO L159 IcfgInterpreter]: Started Sifa with 24 locations of interest [2023-11-19 04:48:32,730 INFO L166 IcfgInterpreter]: Building call graph [2023-11-19 04:48:32,732 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:48:32,733 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-19 04:48:32,734 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 10, 13] total 23 [2023-11-19 04:48:32,734 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [757736110] [2023-11-19 04:48:32,735 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-19 04:48:32,738 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2023-11-19 04:48:32,738 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 04:48:32,739 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2023-11-19 04:48:32,740 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=67, Invalid=439, Unknown=0, NotChecked=0, Total=506 [2023-11-19 04:48:32,740 INFO L87 Difference]: Start difference. First operand 72 states and 105 transitions. Second operand has 23 states, 21 states have (on average 3.5714285714285716) internal successors, (75), 23 states have internal predecessors, (75), 18 states have call successors, (23), 1 states have call predecessors, (23), 9 states have return successors, (27), 10 states have call predecessors, (27), 18 states have call successors, (27) [2023-11-19 04:48:33,602 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 04:48:33,603 INFO L93 Difference]: Finished difference Result 204 states and 411 transitions. [2023-11-19 04:48:33,603 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 26 states. [2023-11-19 04:48:33,604 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 21 states have (on average 3.5714285714285716) internal successors, (75), 23 states have internal predecessors, (75), 18 states have call successors, (23), 1 states have call predecessors, (23), 9 states have return successors, (27), 10 states have call predecessors, (27), 18 states have call successors, (27) Word has length 92 [2023-11-19 04:48:33,604 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 04:48:33,607 INFO L225 Difference]: With dead ends: 204 [2023-11-19 04:48:33,607 INFO L226 Difference]: Without dead ends: 115 [2023-11-19 04:48:33,609 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 210 GetRequests, 167 SyntacticMatches, 5 SemanticMatches, 38 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 252 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=263, Invalid=1297, Unknown=0, NotChecked=0, Total=1560 [2023-11-19 04:48:33,610 INFO L413 NwaCegarLoop]: 35 mSDtfsCounter, 89 mSDsluCounter, 297 mSDsCounter, 0 mSdLazyCounter, 534 mSolverCounterSat, 98 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 90 SdHoareTripleChecker+Valid, 332 SdHoareTripleChecker+Invalid, 632 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 98 IncrementalHoareTripleChecker+Valid, 534 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2023-11-19 04:48:33,611 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [90 Valid, 332 Invalid, 632 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [98 Valid, 534 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2023-11-19 04:48:33,612 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 115 states. [2023-11-19 04:48:33,632 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 115 to 98. [2023-11-19 04:48:33,633 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 98 states, 64 states have (on average 1.171875) internal successors, (75), 66 states have internal predecessors, (75), 19 states have call successors, (19), 8 states have call predecessors, (19), 14 states have return successors, (50), 23 states have call predecessors, (50), 19 states have call successors, (50) [2023-11-19 04:48:33,634 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 98 states to 98 states and 144 transitions. [2023-11-19 04:48:33,635 INFO L78 Accepts]: Start accepts. Automaton has 98 states and 144 transitions. Word has length 92 [2023-11-19 04:48:33,635 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 04:48:33,635 INFO L495 AbstractCegarLoop]: Abstraction has 98 states and 144 transitions. [2023-11-19 04:48:33,636 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 21 states have (on average 3.5714285714285716) internal successors, (75), 23 states have internal predecessors, (75), 18 states have call successors, (23), 1 states have call predecessors, (23), 9 states have return successors, (27), 10 states have call predecessors, (27), 18 states have call successors, (27) [2023-11-19 04:48:33,636 INFO L276 IsEmpty]: Start isEmpty. Operand 98 states and 144 transitions. [2023-11-19 04:48:33,639 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 143 [2023-11-19 04:48:33,639 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 04:48:33,639 INFO L195 NwaCegarLoop]: trace histogram [12, 12, 9, 9, 7, 6, 6, 6, 6, 6, 6, 6, 6, 6, 4, 4, 4, 4, 4, 4, 4, 2, 2, 1, 1, 1, 1, 1, 1, 1] [2023-11-19 04:48:33,670 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2023-11-19 04:48:33,860 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 04:48:33,861 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 04:48:33,861 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 04:48:33,861 INFO L85 PathProgramCache]: Analyzing trace with hash 1596421381, now seen corresponding path program 2 times [2023-11-19 04:48:33,861 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 04:48:33,862 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1191230315] [2023-11-19 04:48:33,862 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 04:48:33,862 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 04:48:33,894 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 04:48:34,047 INFO L134 CoverageAnalysis]: Checked inductivity of 528 backedges. 39 proven. 116 refuted. 0 times theorem prover too weak. 373 trivial. 0 not checked. [2023-11-19 04:48:34,047 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 04:48:34,047 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1191230315] [2023-11-19 04:48:34,047 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1191230315] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-19 04:48:34,047 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1283211405] [2023-11-19 04:48:34,048 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-11-19 04:48:34,048 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 04:48:34,048 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 04:48:34,049 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 04:48:34,074 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2023-11-19 04:48:34,138 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 2 check-sat command(s) [2023-11-19 04:48:34,138 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-19 04:48:34,139 INFO L262 TraceCheckSpWp]: Trace formula consists of 99 conjuncts, 5 conjunts are in the unsatisfiable core [2023-11-19 04:48:34,143 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-19 04:48:34,176 INFO L134 CoverageAnalysis]: Checked inductivity of 528 backedges. 150 proven. 0 refuted. 0 times theorem prover too weak. 378 trivial. 0 not checked. [2023-11-19 04:48:34,177 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-11-19 04:48:34,178 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1283211405] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-19 04:48:34,178 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-11-19 04:48:34,178 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [6] total 6 [2023-11-19 04:48:34,179 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1281788067] [2023-11-19 04:48:34,179 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-19 04:48:34,179 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2023-11-19 04:48:34,180 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 04:48:34,181 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2023-11-19 04:48:34,181 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2023-11-19 04:48:34,181 INFO L87 Difference]: Start difference. First operand 98 states and 144 transitions. Second operand has 6 states, 5 states have (on average 6.4) internal successors, (32), 6 states have internal predecessors, (32), 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:48:34,263 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 04:48:34,263 INFO L93 Difference]: Finished difference Result 188 states and 309 transitions. [2023-11-19 04:48:34,264 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-11-19 04:48:34,264 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 6.4) internal successors, (32), 6 states have internal predecessors, (32), 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 142 [2023-11-19 04:48:34,264 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 04:48:34,267 INFO L225 Difference]: With dead ends: 188 [2023-11-19 04:48:34,267 INFO L226 Difference]: Without dead ends: 100 [2023-11-19 04:48:34,268 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 149 GetRequests, 142 SyntacticMatches, 2 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=14, Invalid=28, Unknown=0, NotChecked=0, Total=42 [2023-11-19 04:48:34,270 INFO L413 NwaCegarLoop]: 26 mSDtfsCounter, 13 mSDsluCounter, 72 mSDsCounter, 0 mSdLazyCounter, 48 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 18 SdHoareTripleChecker+Valid, 98 SdHoareTripleChecker+Invalid, 48 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 48 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-19 04:48:34,270 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [18 Valid, 98 Invalid, 48 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 48 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-19 04:48:34,271 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 100 states. [2023-11-19 04:48:34,299 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 100 to 100. [2023-11-19 04:48:34,299 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 100 states, 65 states have (on average 1.1692307692307693) internal successors, (76), 68 states have internal predecessors, (76), 19 states have call successors, (19), 8 states have call predecessors, (19), 15 states have return successors, (48), 23 states have call predecessors, (48), 19 states have call successors, (48) [2023-11-19 04:48:34,302 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 100 states to 100 states and 143 transitions. [2023-11-19 04:48:34,302 INFO L78 Accepts]: Start accepts. Automaton has 100 states and 143 transitions. Word has length 142 [2023-11-19 04:48:34,302 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 04:48:34,303 INFO L495 AbstractCegarLoop]: Abstraction has 100 states and 143 transitions. [2023-11-19 04:48:34,303 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 6.4) internal successors, (32), 6 states have internal predecessors, (32), 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:48:34,303 INFO L276 IsEmpty]: Start isEmpty. Operand 100 states and 143 transitions. [2023-11-19 04:48:34,311 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 187 [2023-11-19 04:48:34,311 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 04:48:34,311 INFO L195 NwaCegarLoop]: trace histogram [14, 14, 13, 13, 12, 9, 7, 7, 7, 7, 7, 7, 7, 6, 6, 6, 6, 6, 6, 6, 6, 4, 2, 2, 1, 1, 1, 1, 1, 1] [2023-11-19 04:48:34,332 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2023-11-19 04:48:34,537 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,7 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 04:48:34,537 INFO L420 AbstractCegarLoop]: === Iteration 9 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 04:48:34,538 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 04:48:34,538 INFO L85 PathProgramCache]: Analyzing trace with hash 1097181522, now seen corresponding path program 3 times [2023-11-19 04:48:34,538 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 04:48:34,538 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1359858873] [2023-11-19 04:48:34,538 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 04:48:34,538 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 04:48:34,582 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 04:48:34,863 INFO L134 CoverageAnalysis]: Checked inductivity of 922 backedges. 52 proven. 230 refuted. 0 times theorem prover too weak. 640 trivial. 0 not checked. [2023-11-19 04:48:34,864 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 04:48:34,864 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1359858873] [2023-11-19 04:48:34,864 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1359858873] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-19 04:48:34,864 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [530228578] [2023-11-19 04:48:34,864 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2023-11-19 04:48:34,864 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 04:48:34,865 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 04:48:34,866 INFO L229 MonitoredProcess]: Starting monitored process 8 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 04:48:34,891 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2023-11-19 04:48:34,983 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2023-11-19 04:48:34,983 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-19 04:48:34,985 INFO L262 TraceCheckSpWp]: Trace formula consists of 330 conjuncts, 8 conjunts are in the unsatisfiable core [2023-11-19 04:48:34,990 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-19 04:48:35,105 INFO L134 CoverageAnalysis]: Checked inductivity of 922 backedges. 349 proven. 6 refuted. 0 times theorem prover too weak. 567 trivial. 0 not checked. [2023-11-19 04:48:35,106 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-19 04:48:35,835 INFO L134 CoverageAnalysis]: Checked inductivity of 922 backedges. 67 proven. 214 refuted. 0 times theorem prover too weak. 641 trivial. 0 not checked. [2023-11-19 04:48:35,835 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [530228578] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-19 04:48:35,835 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [790417673] [2023-11-19 04:48:35,838 INFO L159 IcfgInterpreter]: Started Sifa with 24 locations of interest [2023-11-19 04:48:35,839 INFO L166 IcfgInterpreter]: Building call graph [2023-11-19 04:48:35,839 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:48:35,840 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-19 04:48:35,840 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 9, 9] total 18 [2023-11-19 04:48:35,841 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [276697473] [2023-11-19 04:48:35,841 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-19 04:48:35,842 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2023-11-19 04:48:35,842 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 04:48:35,843 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2023-11-19 04:48:35,843 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=43, Invalid=263, Unknown=0, NotChecked=0, Total=306 [2023-11-19 04:48:35,844 INFO L87 Difference]: Start difference. First operand 100 states and 143 transitions. Second operand has 18 states, 17 states have (on average 4.411764705882353) internal successors, (75), 18 states have internal predecessors, (75), 12 states have call successors, (22), 2 states have call predecessors, (22), 9 states have return successors, (27), 9 states have call predecessors, (27), 12 states have call successors, (27) [2023-11-19 04:48:36,379 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 04:48:36,379 INFO L93 Difference]: Finished difference Result 222 states and 343 transitions. [2023-11-19 04:48:36,380 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2023-11-19 04:48:36,380 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 17 states have (on average 4.411764705882353) internal successors, (75), 18 states have internal predecessors, (75), 12 states have call successors, (22), 2 states have call predecessors, (22), 9 states have return successors, (27), 9 states have call predecessors, (27), 12 states have call successors, (27) Word has length 186 [2023-11-19 04:48:36,381 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 04:48:36,382 INFO L225 Difference]: With dead ends: 222 [2023-11-19 04:48:36,383 INFO L226 Difference]: Without dead ends: 132 [2023-11-19 04:48:36,384 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 397 GetRequests, 363 SyntacticMatches, 4 SemanticMatches, 30 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 120 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=173, Invalid=819, Unknown=0, NotChecked=0, Total=992 [2023-11-19 04:48:36,385 INFO L413 NwaCegarLoop]: 24 mSDtfsCounter, 70 mSDsluCounter, 212 mSDsCounter, 0 mSdLazyCounter, 435 mSolverCounterSat, 59 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 71 SdHoareTripleChecker+Valid, 236 SdHoareTripleChecker+Invalid, 494 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 59 IncrementalHoareTripleChecker+Valid, 435 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2023-11-19 04:48:36,386 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [71 Valid, 236 Invalid, 494 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [59 Valid, 435 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2023-11-19 04:48:36,386 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 132 states. [2023-11-19 04:48:36,399 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 132 to 95. [2023-11-19 04:48:36,400 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 95 states, 62 states have (on average 1.1774193548387097) internal successors, (73), 64 states have internal predecessors, (73), 19 states have call successors, (19), 8 states have call predecessors, (19), 13 states have return successors, (43), 22 states have call predecessors, (43), 19 states have call successors, (43) [2023-11-19 04:48:36,401 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 95 states to 95 states and 135 transitions. [2023-11-19 04:48:36,401 INFO L78 Accepts]: Start accepts. Automaton has 95 states and 135 transitions. Word has length 186 [2023-11-19 04:48:36,402 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 04:48:36,402 INFO L495 AbstractCegarLoop]: Abstraction has 95 states and 135 transitions. [2023-11-19 04:48:36,402 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 18 states, 17 states have (on average 4.411764705882353) internal successors, (75), 18 states have internal predecessors, (75), 12 states have call successors, (22), 2 states have call predecessors, (22), 9 states have return successors, (27), 9 states have call predecessors, (27), 12 states have call successors, (27) [2023-11-19 04:48:36,402 INFO L276 IsEmpty]: Start isEmpty. Operand 95 states and 135 transitions. [2023-11-19 04:48:36,405 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 148 [2023-11-19 04:48:36,405 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 04:48:36,405 INFO L195 NwaCegarLoop]: trace histogram [12, 12, 9, 9, 9, 9, 6, 6, 6, 6, 6, 6, 6, 5, 4, 4, 4, 4, 4, 4, 4, 3, 3, 1, 1, 1, 1, 1, 1] [2023-11-19 04:48:36,432 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2023-11-19 04:48:36,627 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 8 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable8 [2023-11-19 04:48:36,628 INFO L420 AbstractCegarLoop]: === Iteration 10 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 04:48:36,628 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 04:48:36,628 INFO L85 PathProgramCache]: Analyzing trace with hash -1924457029, now seen corresponding path program 1 times [2023-11-19 04:48:36,629 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 04:48:36,629 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [34825549] [2023-11-19 04:48:36,629 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 04:48:36,629 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 04:48:36,662 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 04:48:36,904 INFO L134 CoverageAnalysis]: Checked inductivity of 564 backedges. 60 proven. 121 refuted. 0 times theorem prover too weak. 383 trivial. 0 not checked. [2023-11-19 04:48:36,905 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 04:48:36,905 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [34825549] [2023-11-19 04:48:36,905 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [34825549] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-19 04:48:36,905 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1663686122] [2023-11-19 04:48:36,905 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 04:48:36,906 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 04:48:36,906 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 04:48:36,907 INFO L229 MonitoredProcess]: Starting monitored process 9 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 04:48:36,923 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2023-11-19 04:48:37,018 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 04:48:37,020 INFO L262 TraceCheckSpWp]: Trace formula consists of 348 conjuncts, 14 conjunts are in the unsatisfiable core [2023-11-19 04:48:37,025 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-19 04:48:37,146 INFO L134 CoverageAnalysis]: Checked inductivity of 564 backedges. 36 proven. 211 refuted. 0 times theorem prover too weak. 317 trivial. 0 not checked. [2023-11-19 04:48:37,146 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-19 04:48:38,642 INFO L134 CoverageAnalysis]: Checked inductivity of 564 backedges. 36 proven. 227 refuted. 0 times theorem prover too weak. 301 trivial. 0 not checked. [2023-11-19 04:48:38,642 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1663686122] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-19 04:48:38,642 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [748750189] [2023-11-19 04:48:38,645 INFO L159 IcfgInterpreter]: Started Sifa with 24 locations of interest [2023-11-19 04:48:38,645 INFO L166 IcfgInterpreter]: Building call graph [2023-11-19 04:48:38,645 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:48:38,646 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-19 04:48:38,647 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 11, 15] total 21 [2023-11-19 04:48:38,647 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [272547176] [2023-11-19 04:48:38,647 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-19 04:48:38,648 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2023-11-19 04:48:38,648 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 04:48:38,649 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2023-11-19 04:48:38,649 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=78, Invalid=342, Unknown=0, NotChecked=0, Total=420 [2023-11-19 04:48:38,650 INFO L87 Difference]: Start difference. First operand 95 states and 135 transitions. Second operand has 21 states, 19 states have (on average 3.6842105263157894) internal successors, (70), 21 states have internal predecessors, (70), 17 states have call successors, (21), 1 states have call predecessors, (21), 10 states have return successors, (28), 11 states have call predecessors, (28), 17 states have call successors, (28) [2023-11-19 04:48:38,921 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 04:48:38,922 INFO L93 Difference]: Finished difference Result 147 states and 257 transitions. [2023-11-19 04:48:38,922 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2023-11-19 04:48:38,922 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 19 states have (on average 3.6842105263157894) internal successors, (70), 21 states have internal predecessors, (70), 17 states have call successors, (21), 1 states have call predecessors, (21), 10 states have return successors, (28), 11 states have call predecessors, (28), 17 states have call successors, (28) Word has length 147 [2023-11-19 04:48:38,924 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 04:48:38,926 INFO L225 Difference]: With dead ends: 147 [2023-11-19 04:48:38,926 INFO L226 Difference]: Without dead ends: 123 [2023-11-19 04:48:38,927 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 313 GetRequests, 279 SyntacticMatches, 6 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 226 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=173, Invalid=697, Unknown=0, NotChecked=0, Total=870 [2023-11-19 04:48:38,928 INFO L413 NwaCegarLoop]: 16 mSDtfsCounter, 35 mSDsluCounter, 137 mSDsCounter, 0 mSdLazyCounter, 161 mSolverCounterSat, 34 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 49 SdHoareTripleChecker+Valid, 153 SdHoareTripleChecker+Invalid, 195 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 34 IncrementalHoareTripleChecker+Valid, 161 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-19 04:48:38,929 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [49 Valid, 153 Invalid, 195 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [34 Valid, 161 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-19 04:48:38,930 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 123 states. [2023-11-19 04:48:38,945 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 123 to 108. [2023-11-19 04:48:38,946 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 108 states, 70 states have (on average 1.1571428571428573) internal successors, (81), 72 states have internal predecessors, (81), 21 states have call successors, (21), 8 states have call predecessors, (21), 16 states have return successors, (54), 27 states have call predecessors, (54), 21 states have call successors, (54) [2023-11-19 04:48:38,948 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 108 states to 108 states and 156 transitions. [2023-11-19 04:48:38,948 INFO L78 Accepts]: Start accepts. Automaton has 108 states and 156 transitions. Word has length 147 [2023-11-19 04:48:38,948 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 04:48:38,948 INFO L495 AbstractCegarLoop]: Abstraction has 108 states and 156 transitions. [2023-11-19 04:48:38,949 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 19 states have (on average 3.6842105263157894) internal successors, (70), 21 states have internal predecessors, (70), 17 states have call successors, (21), 1 states have call predecessors, (21), 10 states have return successors, (28), 11 states have call predecessors, (28), 17 states have call successors, (28) [2023-11-19 04:48:38,949 INFO L276 IsEmpty]: Start isEmpty. Operand 108 states and 156 transitions. [2023-11-19 04:48:38,958 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 420 [2023-11-19 04:48:38,959 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 04:48:38,959 INFO L195 NwaCegarLoop]: trace histogram [31, 31, 30, 30, 25, 25, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 10, 10, 6, 5, 1, 1, 1, 1, 1, 1] [2023-11-19 04:48:38,983 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2023-11-19 04:48:39,178 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2023-11-19 04:48:39,178 INFO L420 AbstractCegarLoop]: === Iteration 11 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 04:48:39,178 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 04:48:39,178 INFO L85 PathProgramCache]: Analyzing trace with hash 820982083, now seen corresponding path program 4 times [2023-11-19 04:48:39,179 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 04:48:39,179 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [127509355] [2023-11-19 04:48:39,179 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 04:48:39,179 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 04:48:39,242 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 04:48:39,993 INFO L134 CoverageAnalysis]: Checked inductivity of 5040 backedges. 154 proven. 887 refuted. 0 times theorem prover too weak. 3999 trivial. 0 not checked. [2023-11-19 04:48:39,994 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 04:48:39,994 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [127509355] [2023-11-19 04:48:39,994 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [127509355] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-19 04:48:39,994 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [68372455] [2023-11-19 04:48:39,994 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2023-11-19 04:48:39,995 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 04:48:39,995 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 04:48:39,996 INFO L229 MonitoredProcess]: Starting monitored process 10 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 04:48:40,024 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2023-11-19 04:48:40,211 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 04:48:40,215 INFO L262 TraceCheckSpWp]: Trace formula consists of 952 conjuncts, 16 conjunts are in the unsatisfiable core [2023-11-19 04:48:40,223 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-19 04:48:40,312 INFO L134 CoverageAnalysis]: Checked inductivity of 5040 backedges. 154 proven. 887 refuted. 0 times theorem prover too weak. 3999 trivial. 0 not checked. [2023-11-19 04:48:40,312 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-19 04:48:42,807 INFO L134 CoverageAnalysis]: Checked inductivity of 5040 backedges. 154 proven. 911 refuted. 0 times theorem prover too weak. 3975 trivial. 0 not checked. [2023-11-19 04:48:42,807 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [68372455] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-19 04:48:42,807 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [734928053] [2023-11-19 04:48:42,810 INFO L159 IcfgInterpreter]: Started Sifa with 24 locations of interest [2023-11-19 04:48:42,810 INFO L166 IcfgInterpreter]: Building call graph [2023-11-19 04:48:42,810 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:48:42,811 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-19 04:48:42,812 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12, 17] total 19 [2023-11-19 04:48:42,812 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1390070833] [2023-11-19 04:48:42,812 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-19 04:48:42,816 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2023-11-19 04:48:42,817 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 04:48:42,817 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2023-11-19 04:48:42,818 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=67, Invalid=275, Unknown=0, NotChecked=0, Total=342 [2023-11-19 04:48:42,818 INFO L87 Difference]: Start difference. First operand 108 states and 156 transitions. Second operand has 19 states, 18 states have (on average 3.7222222222222223) internal successors, (67), 19 states have internal predecessors, (67), 16 states have call successors, (19), 1 states have call predecessors, (19), 8 states have return successors, (23), 8 states have call predecessors, (23), 16 states have call successors, (23) [2023-11-19 04:48:43,071 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 04:48:43,071 INFO L93 Difference]: Finished difference Result 137 states and 214 transitions. [2023-11-19 04:48:43,072 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2023-11-19 04:48:43,072 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), 16 states have call successors, (19), 1 states have call predecessors, (19), 8 states have return successors, (23), 8 states have call predecessors, (23), 16 states have call successors, (23) Word has length 419 [2023-11-19 04:48:43,074 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 04:48:43,076 INFO L225 Difference]: With dead ends: 137 [2023-11-19 04:48:43,076 INFO L226 Difference]: Without dead ends: 123 [2023-11-19 04:48:43,077 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 860 GetRequests, 828 SyntacticMatches, 8 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 123 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=138, Invalid=512, Unknown=0, NotChecked=0, Total=650 [2023-11-19 04:48:43,078 INFO L413 NwaCegarLoop]: 16 mSDtfsCounter, 47 mSDsluCounter, 129 mSDsCounter, 0 mSdLazyCounter, 159 mSolverCounterSat, 46 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 64 SdHoareTripleChecker+Valid, 145 SdHoareTripleChecker+Invalid, 205 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 46 IncrementalHoareTripleChecker+Valid, 159 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-11-19 04:48:43,079 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [64 Valid, 145 Invalid, 205 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [46 Valid, 159 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-11-19 04:48:43,079 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 123 states. [2023-11-19 04:48:43,095 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 123 to 106. [2023-11-19 04:48:43,095 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 106 states, 69 states have (on average 1.1594202898550725) internal successors, (80), 71 states have internal predecessors, (80), 20 states have call successors, (20), 8 states have call predecessors, (20), 16 states have return successors, (51), 26 states have call predecessors, (51), 20 states have call successors, (51) [2023-11-19 04:48:43,097 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 106 states to 106 states and 151 transitions. [2023-11-19 04:48:43,097 INFO L78 Accepts]: Start accepts. Automaton has 106 states and 151 transitions. Word has length 419 [2023-11-19 04:48:43,098 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 04:48:43,098 INFO L495 AbstractCegarLoop]: Abstraction has 106 states and 151 transitions. [2023-11-19 04:48:43,098 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), 16 states have call successors, (19), 1 states have call predecessors, (19), 8 states have return successors, (23), 8 states have call predecessors, (23), 16 states have call successors, (23) [2023-11-19 04:48:43,098 INFO L276 IsEmpty]: Start isEmpty. Operand 106 states and 151 transitions. [2023-11-19 04:48:43,105 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 366 [2023-11-19 04:48:43,105 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 04:48:43,105 INFO L195 NwaCegarLoop]: trace histogram [27, 27, 26, 26, 22, 22, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 9, 9, 5, 4, 1, 1, 1, 1, 1, 1] [2023-11-19 04:48:43,126 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2023-11-19 04:48:43,319 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2023-11-19 04:48:43,319 INFO L420 AbstractCegarLoop]: === Iteration 12 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 04:48:43,320 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 04:48:43,320 INFO L85 PathProgramCache]: Analyzing trace with hash 783992227, now seen corresponding path program 5 times [2023-11-19 04:48:43,320 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 04:48:43,320 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [343422503] [2023-11-19 04:48:43,320 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 04:48:43,320 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 04:48:43,399 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 04:48:44,025 INFO L134 CoverageAnalysis]: Checked inductivity of 3790 backedges. 170 proven. 599 refuted. 0 times theorem prover too weak. 3021 trivial. 0 not checked. [2023-11-19 04:48:44,025 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 04:48:44,025 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [343422503] [2023-11-19 04:48:44,025 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [343422503] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-19 04:48:44,026 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1745247442] [2023-11-19 04:48:44,026 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-11-19 04:48:44,026 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 04:48:44,026 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 04:48:44,027 INFO L229 MonitoredProcess]: Starting monitored process 11 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 04:48:44,051 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2023-11-19 04:48:44,197 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 7 check-sat command(s) [2023-11-19 04:48:44,197 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-19 04:48:44,199 INFO L262 TraceCheckSpWp]: Trace formula consists of 299 conjuncts, 12 conjunts are in the unsatisfiable core [2023-11-19 04:48:44,215 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-19 04:48:44,300 INFO L134 CoverageAnalysis]: Checked inductivity of 3790 backedges. 556 proven. 91 refuted. 0 times theorem prover too weak. 3143 trivial. 0 not checked. [2023-11-19 04:48:44,301 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-19 04:48:45,738 INFO L134 CoverageAnalysis]: Checked inductivity of 3790 backedges. 560 proven. 97 refuted. 0 times theorem prover too weak. 3133 trivial. 0 not checked. [2023-11-19 04:48:45,738 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1745247442] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-19 04:48:45,738 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1629472498] [2023-11-19 04:48:45,741 INFO L159 IcfgInterpreter]: Started Sifa with 24 locations of interest [2023-11-19 04:48:45,741 INFO L166 IcfgInterpreter]: Building call graph [2023-11-19 04:48:45,741 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:48:45,742 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-19 04:48:45,743 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 10, 13] total 19 [2023-11-19 04:48:45,743 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1648130394] [2023-11-19 04:48:45,743 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-19 04:48:45,744 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2023-11-19 04:48:45,744 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 04:48:45,745 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2023-11-19 04:48:45,745 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=69, Invalid=273, Unknown=0, NotChecked=0, Total=342 [2023-11-19 04:48:45,746 INFO L87 Difference]: Start difference. First operand 106 states and 151 transitions. Second operand has 19 states, 18 states have (on average 3.8333333333333335) internal successors, (69), 19 states have internal predecessors, (69), 14 states have call successors, (21), 1 states have call predecessors, (21), 10 states have return successors, (28), 13 states have call predecessors, (28), 14 states have call successors, (28) [2023-11-19 04:48:46,010 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 04:48:46,011 INFO L93 Difference]: Finished difference Result 143 states and 232 transitions. [2023-11-19 04:48:46,011 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2023-11-19 04:48:46,012 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 18 states have (on average 3.8333333333333335) internal successors, (69), 19 states have internal predecessors, (69), 14 states have call successors, (21), 1 states have call predecessors, (21), 10 states have return successors, (28), 13 states have call predecessors, (28), 14 states have call successors, (28) Word has length 365 [2023-11-19 04:48:46,013 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 04:48:46,016 INFO L225 Difference]: With dead ends: 143 [2023-11-19 04:48:46,016 INFO L226 Difference]: Without dead ends: 129 [2023-11-19 04:48:46,017 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 752 GetRequests, 720 SyntacticMatches, 6 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 172 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=159, Invalid=597, Unknown=0, NotChecked=0, Total=756 [2023-11-19 04:48:46,018 INFO L413 NwaCegarLoop]: 16 mSDtfsCounter, 47 mSDsluCounter, 125 mSDsCounter, 0 mSdLazyCounter, 156 mSolverCounterSat, 56 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 54 SdHoareTripleChecker+Valid, 141 SdHoareTripleChecker+Invalid, 212 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 56 IncrementalHoareTripleChecker+Valid, 156 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-11-19 04:48:46,019 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [54 Valid, 141 Invalid, 212 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [56 Valid, 156 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-11-19 04:48:46,020 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 129 states. [2023-11-19 04:48:46,037 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 129 to 111. [2023-11-19 04:48:46,038 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 111 states, 72 states have (on average 1.1527777777777777) internal successors, (83), 74 states have internal predecessors, (83), 21 states have call successors, (21), 8 states have call predecessors, (21), 17 states have return successors, (60), 28 states have call predecessors, (60), 21 states have call successors, (60) [2023-11-19 04:48:46,040 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 111 states to 111 states and 164 transitions. [2023-11-19 04:48:46,041 INFO L78 Accepts]: Start accepts. Automaton has 111 states and 164 transitions. Word has length 365 [2023-11-19 04:48:46,043 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 04:48:46,043 INFO L495 AbstractCegarLoop]: Abstraction has 111 states and 164 transitions. [2023-11-19 04:48:46,043 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 18 states have (on average 3.8333333333333335) internal successors, (69), 19 states have internal predecessors, (69), 14 states have call successors, (21), 1 states have call predecessors, (21), 10 states have return successors, (28), 13 states have call predecessors, (28), 14 states have call successors, (28) [2023-11-19 04:48:46,043 INFO L276 IsEmpty]: Start isEmpty. Operand 111 states and 164 transitions. [2023-11-19 04:48:46,052 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 351 [2023-11-19 04:48:46,052 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 04:48:46,052 INFO L195 NwaCegarLoop]: trace histogram [27, 27, 24, 24, 22, 19, 13, 13, 13, 13, 13, 13, 13, 12, 12, 12, 12, 12, 12, 12, 10, 6, 5, 5, 1, 1, 1, 1, 1, 1] [2023-11-19 04:48:46,085 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2023-11-19 04:48:46,275 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11,11 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 04:48:46,276 INFO L420 AbstractCegarLoop]: === Iteration 13 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 04:48:46,276 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 04:48:46,276 INFO L85 PathProgramCache]: Analyzing trace with hash 305354234, now seen corresponding path program 6 times [2023-11-19 04:48:46,276 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 04:48:46,276 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1374648313] [2023-11-19 04:48:46,277 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 04:48:46,277 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 04:48:46,342 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 04:48:46,837 INFO L134 CoverageAnalysis]: Checked inductivity of 3486 backedges. 246 proven. 484 refuted. 0 times theorem prover too weak. 2756 trivial. 0 not checked. [2023-11-19 04:48:46,837 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 04:48:46,838 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1374648313] [2023-11-19 04:48:46,838 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1374648313] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-19 04:48:46,838 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1871083126] [2023-11-19 04:48:46,838 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2023-11-19 04:48:46,838 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 04:48:46,839 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 04:48:46,840 INFO L229 MonitoredProcess]: Starting monitored process 12 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 04:48:46,876 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2023-11-19 04:48:47,073 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2023-11-19 04:48:47,074 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-19 04:48:47,077 INFO L262 TraceCheckSpWp]: Trace formula consists of 622 conjuncts, 18 conjunts are in the unsatisfiable core [2023-11-19 04:48:47,086 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-19 04:48:47,295 INFO L134 CoverageAnalysis]: Checked inductivity of 3486 backedges. 1909 proven. 176 refuted. 0 times theorem prover too weak. 1401 trivial. 0 not checked. [2023-11-19 04:48:47,295 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-19 04:48:49,965 INFO L134 CoverageAnalysis]: Checked inductivity of 3486 backedges. 276 proven. 851 refuted. 0 times theorem prover too weak. 2359 trivial. 0 not checked. [2023-11-19 04:48:49,965 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1871083126] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-19 04:48:49,965 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1996931117] [2023-11-19 04:48:49,967 INFO L159 IcfgInterpreter]: Started Sifa with 24 locations of interest [2023-11-19 04:48:49,968 INFO L166 IcfgInterpreter]: Building call graph [2023-11-19 04:48:49,968 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:48:49,969 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-19 04:48:49,969 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 15, 19] total 27 [2023-11-19 04:48:49,970 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [189881946] [2023-11-19 04:48:49,970 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-19 04:48:49,971 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 27 states [2023-11-19 04:48:49,971 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 04:48:49,971 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 27 interpolants. [2023-11-19 04:48:49,972 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=83, Invalid=619, Unknown=0, NotChecked=0, Total=702 [2023-11-19 04:48:49,972 INFO L87 Difference]: Start difference. First operand 111 states and 164 transitions. Second operand has 27 states, 26 states have (on average 4.038461538461538) internal successors, (105), 27 states have internal predecessors, (105), 22 states have call successors, (32), 2 states have call predecessors, (32), 13 states have return successors, (40), 13 states have call predecessors, (40), 22 states have call successors, (40) [2023-11-19 04:48:51,021 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 04:48:51,021 INFO L93 Difference]: Finished difference Result 261 states and 504 transitions. [2023-11-19 04:48:51,021 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 40 states. [2023-11-19 04:48:51,022 INFO L78 Accepts]: Start accepts. Automaton has has 27 states, 26 states have (on average 4.038461538461538) internal successors, (105), 27 states have internal predecessors, (105), 22 states have call successors, (32), 2 states have call predecessors, (32), 13 states have return successors, (40), 13 states have call predecessors, (40), 22 states have call successors, (40) Word has length 350 [2023-11-19 04:48:51,023 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 04:48:51,025 INFO L225 Difference]: With dead ends: 261 [2023-11-19 04:48:51,025 INFO L226 Difference]: Without dead ends: 154 [2023-11-19 04:48:51,029 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 741 GetRequests, 679 SyntacticMatches, 9 SemanticMatches, 53 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 619 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=458, Invalid=2512, Unknown=0, NotChecked=0, Total=2970 [2023-11-19 04:48:51,030 INFO L413 NwaCegarLoop]: 35 mSDtfsCounter, 121 mSDsluCounter, 366 mSDsCounter, 0 mSdLazyCounter, 778 mSolverCounterSat, 126 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 122 SdHoareTripleChecker+Valid, 401 SdHoareTripleChecker+Invalid, 904 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 126 IncrementalHoareTripleChecker+Valid, 778 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2023-11-19 04:48:51,031 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [122 Valid, 401 Invalid, 904 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [126 Valid, 778 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2023-11-19 04:48:51,031 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 154 states. [2023-11-19 04:48:51,047 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 154 to 135. [2023-11-19 04:48:51,048 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 135 states, 92 states have (on average 1.141304347826087) internal successors, (105), 92 states have internal predecessors, (105), 25 states have call successors, (25), 16 states have call predecessors, (25), 17 states have return successors, (64), 26 states have call predecessors, (64), 25 states have call successors, (64) [2023-11-19 04:48:51,050 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 135 states to 135 states and 194 transitions. [2023-11-19 04:48:51,051 INFO L78 Accepts]: Start accepts. Automaton has 135 states and 194 transitions. Word has length 350 [2023-11-19 04:48:51,051 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 04:48:51,052 INFO L495 AbstractCegarLoop]: Abstraction has 135 states and 194 transitions. [2023-11-19 04:48:51,052 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 27 states, 26 states have (on average 4.038461538461538) internal successors, (105), 27 states have internal predecessors, (105), 22 states have call successors, (32), 2 states have call predecessors, (32), 13 states have return successors, (40), 13 states have call predecessors, (40), 22 states have call successors, (40) [2023-11-19 04:48:51,052 INFO L276 IsEmpty]: Start isEmpty. Operand 135 states and 194 transitions. [2023-11-19 04:48:51,061 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 419 [2023-11-19 04:48:51,061 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 04:48:51,062 INFO L195 NwaCegarLoop]: trace histogram [33, 33, 28, 28, 26, 23, 16, 16, 16, 16, 16, 16, 16, 14, 14, 14, 14, 14, 14, 14, 12, 7, 7, 5, 1, 1, 1, 1, 1, 1] [2023-11-19 04:48:51,093 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2023-11-19 04:48:51,287 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable12,12 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 04:48:51,288 INFO L420 AbstractCegarLoop]: === Iteration 14 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 04:48:51,288 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 04:48:51,288 INFO L85 PathProgramCache]: Analyzing trace with hash 1354655231, now seen corresponding path program 7 times [2023-11-19 04:48:51,288 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 04:48:51,289 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1628154006] [2023-11-19 04:48:51,289 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 04:48:51,289 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 04:48:51,384 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 04:48:51,939 INFO L134 CoverageAnalysis]: Checked inductivity of 5046 backedges. 406 proven. 351 refuted. 0 times theorem prover too weak. 4289 trivial. 0 not checked. [2023-11-19 04:48:51,940 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 04:48:51,940 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1628154006] [2023-11-19 04:48:51,940 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1628154006] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-19 04:48:51,940 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [90889973] [2023-11-19 04:48:51,940 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2023-11-19 04:48:51,941 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 04:48:51,941 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 04:48:51,942 INFO L229 MonitoredProcess]: Starting monitored process 13 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 04:48:51,963 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2023-11-19 04:48:52,279 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 04:48:52,283 INFO L262 TraceCheckSpWp]: Trace formula consists of 950 conjuncts, 18 conjunts are in the unsatisfiable core [2023-11-19 04:48:52,293 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-19 04:48:52,561 INFO L134 CoverageAnalysis]: Checked inductivity of 5046 backedges. 430 proven. 740 refuted. 0 times theorem prover too weak. 3876 trivial. 0 not checked. [2023-11-19 04:48:52,562 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-19 04:48:56,117 INFO L134 CoverageAnalysis]: Checked inductivity of 5046 backedges. 432 proven. 768 refuted. 0 times theorem prover too weak. 3846 trivial. 0 not checked. [2023-11-19 04:48:56,117 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [90889973] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-19 04:48:56,117 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1181188656] [2023-11-19 04:48:56,120 INFO L159 IcfgInterpreter]: Started Sifa with 24 locations of interest [2023-11-19 04:48:56,120 INFO L166 IcfgInterpreter]: Building call graph [2023-11-19 04:48:56,121 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:48:56,122 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-19 04:48:56,122 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 13, 19] total 29 [2023-11-19 04:48:56,123 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1901408214] [2023-11-19 04:48:56,123 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-19 04:48:56,124 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 29 states [2023-11-19 04:48:56,124 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 04:48:56,125 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 29 interpolants. [2023-11-19 04:48:56,126 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=99, Invalid=713, Unknown=0, NotChecked=0, Total=812 [2023-11-19 04:48:56,126 INFO L87 Difference]: Start difference. First operand 135 states and 194 transitions. Second operand has 29 states, 27 states have (on average 3.4814814814814814) internal successors, (94), 29 states have internal predecessors, (94), 22 states have call successors, (28), 1 states have call predecessors, (28), 14 states have return successors, (35), 16 states have call predecessors, (35), 22 states have call successors, (35) [2023-11-19 04:48:57,661 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 04:48:57,661 INFO L93 Difference]: Finished difference Result 447 states and 910 transitions. [2023-11-19 04:48:57,662 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 46 states. [2023-11-19 04:48:57,662 INFO L78 Accepts]: Start accepts. Automaton has has 29 states, 27 states have (on average 3.4814814814814814) internal successors, (94), 29 states have internal predecessors, (94), 22 states have call successors, (28), 1 states have call predecessors, (28), 14 states have return successors, (35), 16 states have call predecessors, (35), 22 states have call successors, (35) Word has length 418 [2023-11-19 04:48:57,666 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 04:48:57,680 INFO L225 Difference]: With dead ends: 447 [2023-11-19 04:48:57,680 INFO L226 Difference]: Without dead ends: 245 [2023-11-19 04:48:57,686 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 880 GetRequests, 811 SyntacticMatches, 9 SemanticMatches, 60 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 900 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=521, Invalid=3261, Unknown=0, NotChecked=0, Total=3782 [2023-11-19 04:48:57,688 INFO L413 NwaCegarLoop]: 47 mSDtfsCounter, 121 mSDsluCounter, 576 mSDsCounter, 0 mSdLazyCounter, 1241 mSolverCounterSat, 116 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 121 SdHoareTripleChecker+Valid, 623 SdHoareTripleChecker+Invalid, 1357 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 116 IncrementalHoareTripleChecker+Valid, 1241 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.9s IncrementalHoareTripleChecker+Time [2023-11-19 04:48:57,689 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [121 Valid, 623 Invalid, 1357 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [116 Valid, 1241 Invalid, 0 Unknown, 0 Unchecked, 0.9s Time] [2023-11-19 04:48:57,690 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 245 states. [2023-11-19 04:48:57,717 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 245 to 200. [2023-11-19 04:48:57,718 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 200 states, 139 states have (on average 1.1366906474820144) internal successors, (158), 138 states have internal predecessors, (158), 42 states have call successors, (42), 30 states have call predecessors, (42), 18 states have return successors, (97), 31 states have call predecessors, (97), 42 states have call successors, (97) [2023-11-19 04:48:57,722 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 200 states to 200 states and 297 transitions. [2023-11-19 04:48:57,722 INFO L78 Accepts]: Start accepts. Automaton has 200 states and 297 transitions. Word has length 418 [2023-11-19 04:48:57,723 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 04:48:57,723 INFO L495 AbstractCegarLoop]: Abstraction has 200 states and 297 transitions. [2023-11-19 04:48:57,724 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 29 states, 27 states have (on average 3.4814814814814814) internal successors, (94), 29 states have internal predecessors, (94), 22 states have call successors, (28), 1 states have call predecessors, (28), 14 states have return successors, (35), 16 states have call predecessors, (35), 22 states have call successors, (35) [2023-11-19 04:48:57,724 INFO L276 IsEmpty]: Start isEmpty. Operand 200 states and 297 transitions. [2023-11-19 04:48:57,734 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 786 [2023-11-19 04:48:57,734 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 04:48:57,734 INFO L195 NwaCegarLoop]: trace histogram [59, 59, 56, 56, 47, 45, 29, 29, 29, 29, 29, 29, 29, 28, 28, 28, 28, 28, 28, 28, 18, 17, 14, 9, 1, 1, 1, 1, 1, 1] [2023-11-19 04:48:57,766 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Forceful destruction successful, exit code 0 [2023-11-19 04:48:57,950 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2023-11-19 04:48:57,950 INFO L420 AbstractCegarLoop]: === Iteration 15 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 04:48:57,951 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 04:48:57,951 INFO L85 PathProgramCache]: Analyzing trace with hash 1968917106, now seen corresponding path program 8 times [2023-11-19 04:48:57,951 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 04:48:57,951 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1459860114] [2023-11-19 04:48:57,952 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 04:48:57,952 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 04:48:58,134 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 04:48:59,612 INFO L134 CoverageAnalysis]: Checked inductivity of 18211 backedges. 603 proven. 1284 refuted. 0 times theorem prover too weak. 16324 trivial. 0 not checked. [2023-11-19 04:48:59,612 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 04:48:59,613 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1459860114] [2023-11-19 04:48:59,613 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1459860114] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-19 04:48:59,613 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [326704096] [2023-11-19 04:48:59,613 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-11-19 04:48:59,613 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 04:48:59,614 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 04:48:59,617 INFO L229 MonitoredProcess]: Starting monitored process 14 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 04:48:59,632 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2023-11-19 04:49:00,026 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 24 check-sat command(s) [2023-11-19 04:49:00,026 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-19 04:49:00,031 INFO L262 TraceCheckSpWp]: Trace formula consists of 814 conjuncts, 12 conjunts are in the unsatisfiable core [2023-11-19 04:49:00,050 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-19 04:49:00,243 INFO L134 CoverageAnalysis]: Checked inductivity of 18211 backedges. 8902 proven. 31 refuted. 0 times theorem prover too weak. 9278 trivial. 0 not checked. [2023-11-19 04:49:00,243 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-19 04:49:03,208 INFO L134 CoverageAnalysis]: Checked inductivity of 18211 backedges. 1544 proven. 598 refuted. 0 times theorem prover too weak. 16069 trivial. 0 not checked. [2023-11-19 04:49:03,209 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [326704096] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-19 04:49:03,209 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [167507758] [2023-11-19 04:49:03,213 INFO L159 IcfgInterpreter]: Started Sifa with 24 locations of interest [2023-11-19 04:49:03,213 INFO L166 IcfgInterpreter]: Building call graph [2023-11-19 04:49:03,214 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:49:03,215 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-19 04:49:03,216 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 12, 13] total 27 [2023-11-19 04:49:03,217 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1725974124] [2023-11-19 04:49:03,217 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-19 04:49:03,219 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 27 states [2023-11-19 04:49:03,220 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 04:49:03,221 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 27 interpolants. [2023-11-19 04:49:03,221 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=98, Invalid=604, Unknown=0, NotChecked=0, Total=702 [2023-11-19 04:49:03,222 INFO L87 Difference]: Start difference. First operand 200 states and 297 transitions. Second operand has 27 states, 26 states have (on average 3.730769230769231) internal successors, (97), 27 states have internal predecessors, (97), 15 states have call successors, (30), 2 states have call predecessors, (30), 13 states have return successors, (40), 18 states have call predecessors, (40), 15 states have call successors, (40) [2023-11-19 04:49:04,042 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 04:49:04,043 INFO L93 Difference]: Finished difference Result 454 states and 741 transitions. [2023-11-19 04:49:04,043 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 25 states. [2023-11-19 04:49:04,044 INFO L78 Accepts]: Start accepts. Automaton has has 27 states, 26 states have (on average 3.730769230769231) internal successors, (97), 27 states have internal predecessors, (97), 15 states have call successors, (30), 2 states have call predecessors, (30), 13 states have return successors, (40), 18 states have call predecessors, (40), 15 states have call successors, (40) Word has length 785 [2023-11-19 04:49:04,045 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 04:49:04,049 INFO L225 Difference]: With dead ends: 454 [2023-11-19 04:49:04,049 INFO L226 Difference]: Without dead ends: 219 [2023-11-19 04:49:04,055 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 1601 GetRequests, 1554 SyntacticMatches, 6 SemanticMatches, 41 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 428 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=301, Invalid=1505, Unknown=0, NotChecked=0, Total=1806 [2023-11-19 04:49:04,056 INFO L413 NwaCegarLoop]: 44 mSDtfsCounter, 64 mSDsluCounter, 411 mSDsCounter, 0 mSdLazyCounter, 751 mSolverCounterSat, 35 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 65 SdHoareTripleChecker+Valid, 455 SdHoareTripleChecker+Invalid, 786 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 35 IncrementalHoareTripleChecker+Valid, 751 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2023-11-19 04:49:04,057 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [65 Valid, 455 Invalid, 786 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [35 Valid, 751 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2023-11-19 04:49:04,058 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 219 states. [2023-11-19 04:49:04,090 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 219 to 215. [2023-11-19 04:49:04,091 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 215 states, 150 states have (on average 1.12) internal successors, (168), 148 states have internal predecessors, (168), 45 states have call successors, (45), 33 states have call predecessors, (45), 19 states have return successors, (107), 33 states have call predecessors, (107), 45 states have call successors, (107) [2023-11-19 04:49:04,097 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 215 states to 215 states and 320 transitions. [2023-11-19 04:49:04,098 INFO L78 Accepts]: Start accepts. Automaton has 215 states and 320 transitions. Word has length 785 [2023-11-19 04:49:04,099 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 04:49:04,100 INFO L495 AbstractCegarLoop]: Abstraction has 215 states and 320 transitions. [2023-11-19 04:49:04,100 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 27 states, 26 states have (on average 3.730769230769231) internal successors, (97), 27 states have internal predecessors, (97), 15 states have call successors, (30), 2 states have call predecessors, (30), 13 states have return successors, (40), 18 states have call predecessors, (40), 15 states have call successors, (40) [2023-11-19 04:49:04,100 INFO L276 IsEmpty]: Start isEmpty. Operand 215 states and 320 transitions. [2023-11-19 04:49:04,107 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 549 [2023-11-19 04:49:04,107 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 04:49:04,108 INFO L195 NwaCegarLoop]: trace histogram [41, 41, 40, 38, 38, 31, 21, 20, 20, 20, 20, 20, 20, 20, 19, 19, 19, 19, 19, 19, 19, 11, 7, 1, 1, 1, 1, 1, 1, 1] [2023-11-19 04:49:04,136 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Forceful destruction successful, exit code 0 [2023-11-19 04:49:04,323 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2023-11-19 04:49:04,323 INFO L420 AbstractCegarLoop]: === Iteration 16 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 04:49:04,324 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 04:49:04,324 INFO L85 PathProgramCache]: Analyzing trace with hash 598953712, now seen corresponding path program 9 times [2023-11-19 04:49:04,324 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 04:49:04,324 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2076746300] [2023-11-19 04:49:04,324 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 04:49:04,324 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 04:49:04,429 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 04:49:05,260 INFO L134 CoverageAnalysis]: Checked inductivity of 8781 backedges. 832 proven. 450 refuted. 0 times theorem prover too weak. 7499 trivial. 0 not checked. [2023-11-19 04:49:05,261 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 04:49:05,261 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2076746300] [2023-11-19 04:49:05,261 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2076746300] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-19 04:49:05,261 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1864811678] [2023-11-19 04:49:05,262 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2023-11-19 04:49:05,262 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 04:49:05,262 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 04:49:05,263 INFO L229 MonitoredProcess]: Starting monitored process 15 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 04:49:05,287 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ec6f9631-26aa-41f0-a01a-1f395959bae2/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2023-11-19 04:49:05,644 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2023-11-19 04:49:05,644 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-19 04:49:05,648 INFO L262 TraceCheckSpWp]: Trace formula consists of 976 conjuncts, 12 conjunts are in the unsatisfiable core [2023-11-19 04:49:05,660 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-19 04:49:05,891 INFO L134 CoverageAnalysis]: Checked inductivity of 8781 backedges. 2151 proven. 32 refuted. 0 times theorem prover too weak. 6598 trivial. 0 not checked. [2023-11-19 04:49:05,891 INFO L327 TraceCheckSpWp]: Computing backward predicates...