./Ultimate.py --spec ../../sv-benchmarks/c/properties/unreach-call.prp --file ../../sv-benchmarks/c/float-benchs/zonotope_3.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 0e0057cc Calling Ultimate with: /usr/lib/jvm/java-11-openjdk-amd64/bin/java -Dosgi.configuration.area=/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1da6b7e5-f792-4cbb-9349-461660b658ca/bin/utaipan-verify-nQ1chXbOIh/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1da6b7e5-f792-4cbb-9349-461660b658ca/bin/utaipan-verify-nQ1chXbOIh/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1da6b7e5-f792-4cbb-9349-461660b658ca/bin/utaipan-verify-nQ1chXbOIh/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1da6b7e5-f792-4cbb-9349-461660b658ca/bin/utaipan-verify-nQ1chXbOIh/config/TaipanReach.xml -i ../../sv-benchmarks/c/float-benchs/zonotope_3.c -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1da6b7e5-f792-4cbb-9349-461660b658ca/bin/utaipan-verify-nQ1chXbOIh/config/svcomp-Reach-32bit-Taipan_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1da6b7e5-f792-4cbb-9349-461660b658ca/bin/utaipan-verify-nQ1chXbOIh --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(G ! call(reach_error())) ) --witnessprinter.graph.data.producer Taipan --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash c1619194307da84227512f62eb582bffd66266544ce804bd80ee6a40fe157ac7 --- Real Ultimate output --- This is Ultimate 0.2.4-dev-0e0057c [2023-12-02 20:04:00,430 INFO L188 SettingsManager]: Resetting all preferences to default values... [2023-12-02 20:04:00,493 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1da6b7e5-f792-4cbb-9349-461660b658ca/bin/utaipan-verify-nQ1chXbOIh/config/svcomp-Reach-32bit-Taipan_Default.epf [2023-12-02 20:04:00,497 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2023-12-02 20:04:00,498 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2023-12-02 20:04:00,521 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2023-12-02 20:04:00,521 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2023-12-02 20:04:00,522 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2023-12-02 20:04:00,522 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2023-12-02 20:04:00,523 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2023-12-02 20:04:00,523 INFO L153 SettingsManager]: * User list type=DISABLED [2023-12-02 20:04:00,524 INFO L151 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2023-12-02 20:04:00,524 INFO L153 SettingsManager]: * Explicit value domain=true [2023-12-02 20:04:00,525 INFO L153 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2023-12-02 20:04:00,525 INFO L153 SettingsManager]: * Octagon Domain=false [2023-12-02 20:04:00,526 INFO L153 SettingsManager]: * Abstract domain=CompoundDomain [2023-12-02 20:04:00,526 INFO L153 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2023-12-02 20:04:00,527 INFO L153 SettingsManager]: * Use the RCFG-of-the-future interface=true [2023-12-02 20:04:00,527 INFO L153 SettingsManager]: * Interval Domain=false [2023-12-02 20:04:00,528 INFO L151 SettingsManager]: Preferences of Sifa differ from their defaults: [2023-12-02 20:04:00,528 INFO L153 SettingsManager]: * Call Summarizer=TopInputCallSummarizer [2023-12-02 20:04:00,531 INFO L153 SettingsManager]: * Simplification Technique=POLY_PAC [2023-12-02 20:04:00,532 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2023-12-02 20:04:00,532 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2023-12-02 20:04:00,532 INFO L153 SettingsManager]: * sizeof long=4 [2023-12-02 20:04:00,533 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2023-12-02 20:04:00,533 INFO L153 SettingsManager]: * sizeof POINTER=4 [2023-12-02 20:04:00,533 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2023-12-02 20:04:00,534 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2023-12-02 20:04:00,534 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2023-12-02 20:04:00,534 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2023-12-02 20:04:00,535 INFO L153 SettingsManager]: * sizeof long double=12 [2023-12-02 20:04:00,535 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2023-12-02 20:04:00,535 INFO L153 SettingsManager]: * Use constant arrays=true [2023-12-02 20:04:00,535 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2023-12-02 20:04:00,536 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2023-12-02 20:04:00,536 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2023-12-02 20:04:00,536 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-12-02 20:04:00,536 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2023-12-02 20:04:00,536 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2023-12-02 20:04:00,537 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2023-12-02 20:04:00,537 INFO L153 SettingsManager]: * Trace refinement strategy=SIFA_TAIPAN [2023-12-02 20:04:00,537 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2023-12-02 20:04:00,537 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2023-12-02 20:04:00,537 INFO L153 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2023-12-02 20:04:00,538 INFO L153 SettingsManager]: * Trace refinement exception blacklist=NONE [2023-12-02 20:04:00,538 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2023-12-02 20:04:00,538 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_1da6b7e5-f792-4cbb-9349-461660b658ca/bin/utaipan-verify-nQ1chXbOIh/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Entry function -> main Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness directory -> /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1da6b7e5-f792-4cbb-9349-461660b658ca/bin/utaipan-verify-nQ1chXbOIh Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Write witness besides input file -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data specification -> CHECK( init(main()), LTL(G ! call(reach_error())) ) Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data producer -> Taipan Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data architecture -> 32bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> c1619194307da84227512f62eb582bffd66266544ce804bd80ee6a40fe157ac7 [2023-12-02 20:04:00,756 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2023-12-02 20:04:00,775 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2023-12-02 20:04:00,778 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2023-12-02 20:04:00,779 INFO L270 PluginConnector]: Initializing CDTParser... [2023-12-02 20:04:00,780 INFO L274 PluginConnector]: CDTParser initialized [2023-12-02 20:04:00,781 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1da6b7e5-f792-4cbb-9349-461660b658ca/bin/utaipan-verify-nQ1chXbOIh/../../sv-benchmarks/c/float-benchs/zonotope_3.c [2023-12-02 20:04:03,502 INFO L533 CDTParser]: Created temporary CDT project at NULL [2023-12-02 20:04:03,679 INFO L384 CDTParser]: Found 1 translation units. [2023-12-02 20:04:03,679 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1da6b7e5-f792-4cbb-9349-461660b658ca/sv-benchmarks/c/float-benchs/zonotope_3.c [2023-12-02 20:04:03,685 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1da6b7e5-f792-4cbb-9349-461660b658ca/bin/utaipan-verify-nQ1chXbOIh/data/faf0b518f/4a147de34b094b07a4c93e7044e538a9/FLAGec53af4ab [2023-12-02 20:04:03,697 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1da6b7e5-f792-4cbb-9349-461660b658ca/bin/utaipan-verify-nQ1chXbOIh/data/faf0b518f/4a147de34b094b07a4c93e7044e538a9 [2023-12-02 20:04:03,699 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2023-12-02 20:04:03,700 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2023-12-02 20:04:03,701 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2023-12-02 20:04:03,701 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2023-12-02 20:04:03,705 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2023-12-02 20:04:03,706 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 02.12 08:04:03" (1/1) ... [2023-12-02 20:04:03,707 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@784e01d7 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 08:04:03, skipping insertion in model container [2023-12-02 20:04:03,707 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 02.12 08:04:03" (1/1) ... [2023-12-02 20:04:03,724 INFO L177 MainTranslator]: Built tables and reachable declarations [2023-12-02 20:04:03,847 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_1da6b7e5-f792-4cbb-9349-461660b658ca/sv-benchmarks/c/float-benchs/zonotope_3.c[604,617] [2023-12-02 20:04:03,863 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-12-02 20:04:03,871 INFO L202 MainTranslator]: Completed pre-run [2023-12-02 20:04:03,880 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_1da6b7e5-f792-4cbb-9349-461660b658ca/sv-benchmarks/c/float-benchs/zonotope_3.c[604,617] [2023-12-02 20:04:03,886 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-12-02 20:04:03,898 INFO L206 MainTranslator]: Completed translation [2023-12-02 20:04:03,899 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 08:04:03 WrapperNode [2023-12-02 20:04:03,899 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2023-12-02 20:04:03,900 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2023-12-02 20:04:03,900 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2023-12-02 20:04:03,900 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2023-12-02 20:04:03,907 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 08:04:03" (1/1) ... [2023-12-02 20:04:03,914 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 08:04:03" (1/1) ... [2023-12-02 20:04:03,933 INFO L138 Inliner]: procedures = 16, calls = 17, calls flagged for inlining = 4, calls inlined = 4, statements flattened = 65 [2023-12-02 20:04:03,933 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2023-12-02 20:04:03,934 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2023-12-02 20:04:03,934 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2023-12-02 20:04:03,935 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2023-12-02 20:04:03,943 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 08:04:03" (1/1) ... [2023-12-02 20:04:03,943 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 08:04:03" (1/1) ... [2023-12-02 20:04:03,945 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 08:04:03" (1/1) ... [2023-12-02 20:04:03,945 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 08:04:03" (1/1) ... [2023-12-02 20:04:03,950 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 08:04:03" (1/1) ... [2023-12-02 20:04:03,953 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 08:04:03" (1/1) ... [2023-12-02 20:04:03,954 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 08:04:03" (1/1) ... [2023-12-02 20:04:03,955 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 08:04:03" (1/1) ... [2023-12-02 20:04:03,956 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2023-12-02 20:04:03,957 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2023-12-02 20:04:03,958 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2023-12-02 20:04:03,958 INFO L274 PluginConnector]: RCFGBuilder initialized [2023-12-02 20:04:03,958 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 08:04:03" (1/1) ... [2023-12-02 20:04:03,964 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-12-02 20:04:03,976 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1da6b7e5-f792-4cbb-9349-461660b658ca/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 20:04:03,991 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1da6b7e5-f792-4cbb-9349-461660b658ca/bin/utaipan-verify-nQ1chXbOIh/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2023-12-02 20:04:03,997 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1da6b7e5-f792-4cbb-9349-461660b658ca/bin/utaipan-verify-nQ1chXbOIh/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2023-12-02 20:04:04,029 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2023-12-02 20:04:04,029 INFO L130 BoogieDeclarations]: Found specification of procedure f [2023-12-02 20:04:04,029 INFO L138 BoogieDeclarations]: Found implementation of procedure f [2023-12-02 20:04:04,029 INFO L130 BoogieDeclarations]: Found specification of procedure g [2023-12-02 20:04:04,029 INFO L138 BoogieDeclarations]: Found implementation of procedure g [2023-12-02 20:04:04,030 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2023-12-02 20:04:04,030 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2023-12-02 20:04:04,030 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2023-12-02 20:04:04,099 INFO L241 CfgBuilder]: Building ICFG [2023-12-02 20:04:04,101 INFO L267 CfgBuilder]: Building CFG for each procedure with an implementation [2023-12-02 20:04:04,218 INFO L282 CfgBuilder]: Performing block encoding [2023-12-02 20:04:04,259 INFO L304 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2023-12-02 20:04:04,259 INFO L309 CfgBuilder]: Removed 1 assume(true) statements. [2023-12-02 20:04:04,260 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 02.12 08:04:04 BoogieIcfgContainer [2023-12-02 20:04:04,260 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2023-12-02 20:04:04,263 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2023-12-02 20:04:04,263 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2023-12-02 20:04:04,267 INFO L274 PluginConnector]: TraceAbstraction initialized [2023-12-02 20:04:04,267 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 02.12 08:04:03" (1/3) ... [2023-12-02 20:04:04,268 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@2c403b2f and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 02.12 08:04:04, skipping insertion in model container [2023-12-02 20:04:04,268 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 08:04:03" (2/3) ... [2023-12-02 20:04:04,268 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@2c403b2f and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 02.12 08:04:04, skipping insertion in model container [2023-12-02 20:04:04,268 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 02.12 08:04:04" (3/3) ... [2023-12-02 20:04:04,270 INFO L112 eAbstractionObserver]: Analyzing ICFG zonotope_3.c [2023-12-02 20:04:04,286 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2023-12-02 20:04:04,286 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2023-12-02 20:04:04,322 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-12-02 20:04:04,329 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;@177ad879, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2023-12-02 20:04:04,329 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2023-12-02 20:04:04,333 INFO L276 IsEmpty]: Start isEmpty. Operand has 27 states, 15 states have (on average 1.2) internal successors, (18), 16 states have internal predecessors, (18), 8 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2023-12-02 20:04:04,340 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2023-12-02 20:04:04,341 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 20:04:04,341 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 20:04:04,341 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 20:04:04,345 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 20:04:04,346 INFO L85 PathProgramCache]: Analyzing trace with hash -786684961, now seen corresponding path program 1 times [2023-12-02 20:04:04,353 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 20:04:04,353 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1069718966] [2023-12-02 20:04:04,354 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 20:04:04,354 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 20:04:04,459 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 20:04:04,562 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2023-12-02 20:04:04,562 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 20:04:04,562 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1069718966] [2023-12-02 20:04:04,563 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1069718966] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-02 20:04:04,563 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-12-02 20:04:04,564 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2023-12-02 20:04:04,565 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1999044265] [2023-12-02 20:04:04,566 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-02 20:04:04,570 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-12-02 20:04:04,570 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 20:04:04,599 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-12-02 20:04:04,600 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2023-12-02 20:04:04,602 INFO L87 Difference]: Start difference. First operand has 27 states, 15 states have (on average 1.2) internal successors, (18), 16 states have internal predecessors, (18), 8 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) Second operand has 3 states, 3 states have (on average 3.3333333333333335) internal successors, (10), 3 states have internal predecessors, (10), 1 states have call successors, (4), 1 states have call predecessors, (4), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2023-12-02 20:04:04,668 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 20:04:04,668 INFO L93 Difference]: Finished difference Result 41 states and 53 transitions. [2023-12-02 20:04:04,669 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-12-02 20:04:04,670 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 3.3333333333333335) internal successors, (10), 3 states have internal predecessors, (10), 1 states have call successors, (4), 1 states have call predecessors, (4), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 20 [2023-12-02 20:04:04,671 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 20:04:04,676 INFO L225 Difference]: With dead ends: 41 [2023-12-02 20:04:04,676 INFO L226 Difference]: Without dead ends: 34 [2023-12-02 20:04:04,679 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2023-12-02 20:04:04,682 INFO L413 NwaCegarLoop]: 26 mSDtfsCounter, 4 mSDsluCounter, 25 mSDsCounter, 0 mSdLazyCounter, 14 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 51 SdHoareTripleChecker+Invalid, 14 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 14 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-12-02 20:04:04,683 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 51 Invalid, 14 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 14 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-12-02 20:04:04,696 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 34 states. [2023-12-02 20:04:04,713 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 34 to 26. [2023-12-02 20:04:04,714 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 26 states, 15 states have (on average 1.0666666666666667) internal successors, (16), 15 states have internal predecessors, (16), 8 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2023-12-02 20:04:04,716 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 32 transitions. [2023-12-02 20:04:04,717 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 32 transitions. Word has length 20 [2023-12-02 20:04:04,717 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 20:04:04,717 INFO L495 AbstractCegarLoop]: Abstraction has 26 states and 32 transitions. [2023-12-02 20:04:04,718 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 3.3333333333333335) internal successors, (10), 3 states have internal predecessors, (10), 1 states have call successors, (4), 1 states have call predecessors, (4), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2023-12-02 20:04:04,718 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 32 transitions. [2023-12-02 20:04:04,719 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2023-12-02 20:04:04,719 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 20:04:04,720 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 1, 1, 1, 1, 1, 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-12-02 20:04:04,720 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2023-12-02 20:04:04,720 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 20:04:04,721 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 20:04:04,721 INFO L85 PathProgramCache]: Analyzing trace with hash 977538669, now seen corresponding path program 1 times [2023-12-02 20:04:04,721 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 20:04:04,721 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1419804251] [2023-12-02 20:04:04,722 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 20:04:04,722 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 20:04:04,748 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 20:04:04,848 INFO L134 CoverageAnalysis]: Checked inductivity of 25 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2023-12-02 20:04:04,848 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 20:04:04,848 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1419804251] [2023-12-02 20:04:04,848 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1419804251] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-02 20:04:04,849 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [548212469] [2023-12-02 20:04:04,849 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 20:04:04,849 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 20:04:04,849 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1da6b7e5-f792-4cbb-9349-461660b658ca/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 20:04:04,857 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1da6b7e5-f792-4cbb-9349-461660b658ca/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 20:04:04,859 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1da6b7e5-f792-4cbb-9349-461660b658ca/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2023-12-02 20:04:04,935 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 20:04:04,937 INFO L262 TraceCheckSpWp]: Trace formula consists of 113 conjuncts, 3 conjunts are in the unsatisfiable core [2023-12-02 20:04:04,943 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 20:04:05,008 INFO L134 CoverageAnalysis]: Checked inductivity of 25 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2023-12-02 20:04:05,008 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 20:04:05,071 INFO L134 CoverageAnalysis]: Checked inductivity of 25 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2023-12-02 20:04:05,071 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [548212469] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-02 20:04:05,072 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [964031400] [2023-12-02 20:04:05,091 INFO L159 IcfgInterpreter]: Started Sifa with 25 locations of interest [2023-12-02 20:04:05,091 INFO L166 IcfgInterpreter]: Building call graph [2023-12-02 20:04:05,093 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-12-02 20:04:05,097 INFO L176 IcfgInterpreter]: Starting interpretation [2023-12-02 20:04:05,098 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-12-02 20:04:06,128 INFO L197 IcfgInterpreter]: Interpreting procedure g with input of size 3 for LOIs [2023-12-02 20:04:06,129 INFO L197 IcfgInterpreter]: Interpreting procedure f with input of size 3 for LOIs [2023-12-02 20:04:06,130 INFO L180 IcfgInterpreter]: Interpretation finished [2023-12-02 20:04:06,315 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '351#(and (<= 1 |#StackHeapBarrier|) (= |ULTIMATE.start___VERIFIER_assert_~cond#1| 0) (= |ULTIMATE.start___VERIFIER_assert_#in~cond#1| 0) (<= 100001 |ULTIMATE.start_main_~i~0#1|))' at error location [2023-12-02 20:04:06,315 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-12-02 20:04:06,315 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-12-02 20:04:06,316 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4, 4] total 7 [2023-12-02 20:04:06,317 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [366180051] [2023-12-02 20:04:06,317 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-12-02 20:04:06,318 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2023-12-02 20:04:06,318 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 20:04:06,319 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2023-12-02 20:04:06,319 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=50, Invalid=160, Unknown=0, NotChecked=0, Total=210 [2023-12-02 20:04:06,320 INFO L87 Difference]: Start difference. First operand 26 states and 32 transitions. Second operand has 7 states, 7 states have (on average 4.0) internal successors, (28), 7 states have internal predecessors, (28), 4 states have call successors, (16), 1 states have call predecessors, (16), 1 states have return successors, (16), 4 states have call predecessors, (16), 4 states have call successors, (16) [2023-12-02 20:04:06,394 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 20:04:06,395 INFO L93 Difference]: Finished difference Result 56 states and 76 transitions. [2023-12-02 20:04:06,395 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-12-02 20:04:06,395 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 4.0) internal successors, (28), 7 states have internal predecessors, (28), 4 states have call successors, (16), 1 states have call predecessors, (16), 1 states have return successors, (16), 4 states have call predecessors, (16), 4 states have call successors, (16) Word has length 37 [2023-12-02 20:04:06,396 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 20:04:06,397 INFO L225 Difference]: With dead ends: 56 [2023-12-02 20:04:06,397 INFO L226 Difference]: Without dead ends: 53 [2023-12-02 20:04:06,398 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 113 GetRequests, 100 SyntacticMatches, 0 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 59 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=50, Invalid=160, Unknown=0, NotChecked=0, Total=210 [2023-12-02 20:04:06,399 INFO L413 NwaCegarLoop]: 25 mSDtfsCounter, 8 mSDsluCounter, 63 mSDsCounter, 0 mSdLazyCounter, 43 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 16 SdHoareTripleChecker+Valid, 88 SdHoareTripleChecker+Invalid, 45 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 43 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-12-02 20:04:06,400 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [16 Valid, 88 Invalid, 45 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 43 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-12-02 20:04:06,401 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 53 states. [2023-12-02 20:04:06,410 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 53 to 53. [2023-12-02 20:04:06,411 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 53 states, 30 states have (on average 1.0333333333333334) internal successors, (31), 30 states have internal predecessors, (31), 20 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (20), 20 states have call predecessors, (20), 20 states have call successors, (20) [2023-12-02 20:04:06,413 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 53 states to 53 states and 71 transitions. [2023-12-02 20:04:06,413 INFO L78 Accepts]: Start accepts. Automaton has 53 states and 71 transitions. Word has length 37 [2023-12-02 20:04:06,414 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 20:04:06,414 INFO L495 AbstractCegarLoop]: Abstraction has 53 states and 71 transitions. [2023-12-02 20:04:06,414 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 4.0) internal successors, (28), 7 states have internal predecessors, (28), 4 states have call successors, (16), 1 states have call predecessors, (16), 1 states have return successors, (16), 4 states have call predecessors, (16), 4 states have call successors, (16) [2023-12-02 20:04:06,414 INFO L276 IsEmpty]: Start isEmpty. Operand 53 states and 71 transitions. [2023-12-02 20:04:06,418 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 89 [2023-12-02 20:04:06,418 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 20:04:06,418 INFO L195 NwaCegarLoop]: trace histogram [10, 10, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 20:04:06,426 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1da6b7e5-f792-4cbb-9349-461660b658ca/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2023-12-02 20:04:06,621 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1da6b7e5-f792-4cbb-9349-461660b658ca/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 20:04:06,622 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 20:04:06,622 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 20:04:06,622 INFO L85 PathProgramCache]: Analyzing trace with hash 926551903, now seen corresponding path program 2 times [2023-12-02 20:04:06,623 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 20:04:06,623 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1501646860] [2023-12-02 20:04:06,623 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 20:04:06,623 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 20:04:06,656 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 20:04:06,838 INFO L134 CoverageAnalysis]: Checked inductivity of 238 backedges. 0 proven. 58 refuted. 0 times theorem prover too weak. 180 trivial. 0 not checked. [2023-12-02 20:04:06,839 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 20:04:06,839 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1501646860] [2023-12-02 20:04:06,839 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1501646860] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-02 20:04:06,839 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1670350085] [2023-12-02 20:04:06,839 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-12-02 20:04:06,840 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 20:04:06,840 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1da6b7e5-f792-4cbb-9349-461660b658ca/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 20:04:06,842 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1da6b7e5-f792-4cbb-9349-461660b658ca/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 20:04:06,846 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1da6b7e5-f792-4cbb-9349-461660b658ca/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2023-12-02 20:04:06,936 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 9 check-sat command(s) [2023-12-02 20:04:06,936 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-02 20:04:06,938 INFO L262 TraceCheckSpWp]: Trace formula consists of 219 conjuncts, 6 conjunts are in the unsatisfiable core [2023-12-02 20:04:06,943 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 20:04:07,006 INFO L134 CoverageAnalysis]: Checked inductivity of 238 backedges. 0 proven. 58 refuted. 0 times theorem prover too weak. 180 trivial. 0 not checked. [2023-12-02 20:04:07,007 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 20:04:07,163 INFO L134 CoverageAnalysis]: Checked inductivity of 238 backedges. 0 proven. 58 refuted. 0 times theorem prover too weak. 180 trivial. 0 not checked. [2023-12-02 20:04:07,164 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1670350085] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-02 20:04:07,164 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [182895101] [2023-12-02 20:04:07,167 INFO L159 IcfgInterpreter]: Started Sifa with 25 locations of interest [2023-12-02 20:04:07,167 INFO L166 IcfgInterpreter]: Building call graph [2023-12-02 20:04:07,168 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-12-02 20:04:07,168 INFO L176 IcfgInterpreter]: Starting interpretation [2023-12-02 20:04:07,168 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-12-02 20:04:07,710 INFO L197 IcfgInterpreter]: Interpreting procedure g with input of size 3 for LOIs [2023-12-02 20:04:07,712 INFO L197 IcfgInterpreter]: Interpreting procedure f with input of size 3 for LOIs [2023-12-02 20:04:07,713 INFO L180 IcfgInterpreter]: Interpretation finished [2023-12-02 20:04:07,893 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1057#(and (<= 1 |#StackHeapBarrier|) (= |ULTIMATE.start___VERIFIER_assert_~cond#1| 0) (= |ULTIMATE.start___VERIFIER_assert_#in~cond#1| 0) (<= 100001 |ULTIMATE.start_main_~i~0#1|))' at error location [2023-12-02 20:04:07,894 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-12-02 20:04:07,894 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-12-02 20:04:07,894 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 13 [2023-12-02 20:04:07,894 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2140001982] [2023-12-02 20:04:07,894 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-12-02 20:04:07,896 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2023-12-02 20:04:07,896 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 20:04:07,897 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2023-12-02 20:04:07,897 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=107, Invalid=313, Unknown=0, NotChecked=0, Total=420 [2023-12-02 20:04:07,898 INFO L87 Difference]: Start difference. First operand 53 states and 71 transitions. Second operand has 13 states, 13 states have (on average 4.461538461538462) internal successors, (58), 13 states have internal predecessors, (58), 10 states have call successors, (40), 1 states have call predecessors, (40), 1 states have return successors, (40), 10 states have call predecessors, (40), 10 states have call successors, (40) [2023-12-02 20:04:08,029 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 20:04:08,029 INFO L93 Difference]: Finished difference Result 110 states and 157 transitions. [2023-12-02 20:04:08,030 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2023-12-02 20:04:08,030 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 4.461538461538462) internal successors, (58), 13 states have internal predecessors, (58), 10 states have call successors, (40), 1 states have call predecessors, (40), 1 states have return successors, (40), 10 states have call predecessors, (40), 10 states have call successors, (40) Word has length 88 [2023-12-02 20:04:08,031 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 20:04:08,033 INFO L225 Difference]: With dead ends: 110 [2023-12-02 20:04:08,033 INFO L226 Difference]: Without dead ends: 107 [2023-12-02 20:04:08,034 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 269 GetRequests, 250 SyntacticMatches, 0 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 143 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=107, Invalid=313, Unknown=0, NotChecked=0, Total=420 [2023-12-02 20:04:08,035 INFO L413 NwaCegarLoop]: 25 mSDtfsCounter, 8 mSDsluCounter, 98 mSDsCounter, 0 mSdLazyCounter, 83 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 16 SdHoareTripleChecker+Valid, 123 SdHoareTripleChecker+Invalid, 85 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 83 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-12-02 20:04:08,035 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [16 Valid, 123 Invalid, 85 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 83 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-12-02 20:04:08,036 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 107 states. [2023-12-02 20:04:08,052 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 107 to 107. [2023-12-02 20:04:08,053 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 107 states, 60 states have (on average 1.0166666666666666) internal successors, (61), 60 states have internal predecessors, (61), 44 states have call successors, (44), 2 states have call predecessors, (44), 2 states have return successors, (44), 44 states have call predecessors, (44), 44 states have call successors, (44) [2023-12-02 20:04:08,056 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 107 states to 107 states and 149 transitions. [2023-12-02 20:04:08,056 INFO L78 Accepts]: Start accepts. Automaton has 107 states and 149 transitions. Word has length 88 [2023-12-02 20:04:08,057 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 20:04:08,057 INFO L495 AbstractCegarLoop]: Abstraction has 107 states and 149 transitions. [2023-12-02 20:04:08,057 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 4.461538461538462) internal successors, (58), 13 states have internal predecessors, (58), 10 states have call successors, (40), 1 states have call predecessors, (40), 1 states have return successors, (40), 10 states have call predecessors, (40), 10 states have call successors, (40) [2023-12-02 20:04:08,057 INFO L276 IsEmpty]: Start isEmpty. Operand 107 states and 149 transitions. [2023-12-02 20:04:08,061 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 191 [2023-12-02 20:04:08,061 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 20:04:08,062 INFO L195 NwaCegarLoop]: trace histogram [22, 22, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 20:04:08,067 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1da6b7e5-f792-4cbb-9349-461660b658ca/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2023-12-02 20:04:08,267 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1da6b7e5-f792-4cbb-9349-461660b658ca/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable2 [2023-12-02 20:04:08,267 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 20:04:08,268 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 20:04:08,268 INFO L85 PathProgramCache]: Analyzing trace with hash 76621983, now seen corresponding path program 3 times [2023-12-02 20:04:08,268 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 20:04:08,268 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1752588157] [2023-12-02 20:04:08,268 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 20:04:08,268 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 20:04:08,307 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 20:04:08,708 INFO L134 CoverageAnalysis]: Checked inductivity of 1339 backedges. 0 proven. 415 refuted. 0 times theorem prover too weak. 924 trivial. 0 not checked. [2023-12-02 20:04:08,708 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 20:04:08,708 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1752588157] [2023-12-02 20:04:08,709 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1752588157] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-02 20:04:08,709 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [487377378] [2023-12-02 20:04:08,709 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2023-12-02 20:04:08,709 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 20:04:08,709 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1da6b7e5-f792-4cbb-9349-461660b658ca/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 20:04:08,710 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1da6b7e5-f792-4cbb-9349-461660b658ca/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 20:04:08,713 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1da6b7e5-f792-4cbb-9349-461660b658ca/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2023-12-02 20:04:08,848 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2023-12-02 20:04:08,848 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-02 20:04:08,851 INFO L262 TraceCheckSpWp]: Trace formula consists of 491 conjuncts, 12 conjunts are in the unsatisfiable core [2023-12-02 20:04:08,860 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 20:04:09,002 INFO L134 CoverageAnalysis]: Checked inductivity of 1339 backedges. 0 proven. 415 refuted. 0 times theorem prover too weak. 924 trivial. 0 not checked. [2023-12-02 20:04:09,002 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 20:04:09,366 INFO L134 CoverageAnalysis]: Checked inductivity of 1339 backedges. 0 proven. 415 refuted. 0 times theorem prover too weak. 924 trivial. 0 not checked. [2023-12-02 20:04:09,366 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [487377378] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-02 20:04:09,366 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1440930109] [2023-12-02 20:04:09,369 INFO L159 IcfgInterpreter]: Started Sifa with 25 locations of interest [2023-12-02 20:04:09,369 INFO L166 IcfgInterpreter]: Building call graph [2023-12-02 20:04:09,370 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-12-02 20:04:09,370 INFO L176 IcfgInterpreter]: Starting interpretation [2023-12-02 20:04:09,370 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-12-02 20:04:09,803 INFO L197 IcfgInterpreter]: Interpreting procedure g with input of size 3 for LOIs [2023-12-02 20:04:09,805 INFO L197 IcfgInterpreter]: Interpreting procedure f with input of size 3 for LOIs [2023-12-02 20:04:09,806 INFO L180 IcfgInterpreter]: Interpretation finished [2023-12-02 20:04:09,983 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '2555#(and (<= 1 |#StackHeapBarrier|) (= |ULTIMATE.start___VERIFIER_assert_~cond#1| 0) (= |ULTIMATE.start___VERIFIER_assert_#in~cond#1| 0) (<= 100001 |ULTIMATE.start_main_~i~0#1|))' at error location [2023-12-02 20:04:09,983 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-12-02 20:04:09,983 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-12-02 20:04:09,984 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13, 13] total 25 [2023-12-02 20:04:09,984 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1830673366] [2023-12-02 20:04:09,984 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-12-02 20:04:09,986 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 25 states [2023-12-02 20:04:09,986 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 20:04:09,987 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2023-12-02 20:04:09,988 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=329, Invalid=727, Unknown=0, NotChecked=0, Total=1056 [2023-12-02 20:04:09,989 INFO L87 Difference]: Start difference. First operand 107 states and 149 transitions. Second operand has 25 states, 25 states have (on average 4.72) internal successors, (118), 25 states have internal predecessors, (118), 22 states have call successors, (88), 1 states have call predecessors, (88), 1 states have return successors, (88), 22 states have call predecessors, (88), 22 states have call successors, (88) [2023-12-02 20:04:10,276 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 20:04:10,276 INFO L93 Difference]: Finished difference Result 218 states and 319 transitions. [2023-12-02 20:04:10,276 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2023-12-02 20:04:10,277 INFO L78 Accepts]: Start accepts. Automaton has has 25 states, 25 states have (on average 4.72) internal successors, (118), 25 states have internal predecessors, (118), 22 states have call successors, (88), 1 states have call predecessors, (88), 1 states have return successors, (88), 22 states have call predecessors, (88), 22 states have call successors, (88) Word has length 190 [2023-12-02 20:04:10,278 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 20:04:10,281 INFO L225 Difference]: With dead ends: 218 [2023-12-02 20:04:10,281 INFO L226 Difference]: Without dead ends: 215 [2023-12-02 20:04:10,282 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 581 GetRequests, 550 SyntacticMatches, 0 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 311 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=329, Invalid=727, Unknown=0, NotChecked=0, Total=1056 [2023-12-02 20:04:10,283 INFO L413 NwaCegarLoop]: 25 mSDtfsCounter, 8 mSDsluCounter, 97 mSDsCounter, 0 mSdLazyCounter, 141 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 16 SdHoareTripleChecker+Valid, 122 SdHoareTripleChecker+Invalid, 143 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 141 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-12-02 20:04:10,284 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [16 Valid, 122 Invalid, 143 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 141 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-12-02 20:04:10,285 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 215 states. [2023-12-02 20:04:10,310 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 215 to 215. [2023-12-02 20:04:10,311 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 215 states, 120 states have (on average 1.0083333333333333) internal successors, (121), 120 states have internal predecessors, (121), 92 states have call successors, (92), 2 states have call predecessors, (92), 2 states have return successors, (92), 92 states have call predecessors, (92), 92 states have call successors, (92) [2023-12-02 20:04:10,315 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 215 states to 215 states and 305 transitions. [2023-12-02 20:04:10,315 INFO L78 Accepts]: Start accepts. Automaton has 215 states and 305 transitions. Word has length 190 [2023-12-02 20:04:10,316 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 20:04:10,316 INFO L495 AbstractCegarLoop]: Abstraction has 215 states and 305 transitions. [2023-12-02 20:04:10,317 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 25 states, 25 states have (on average 4.72) internal successors, (118), 25 states have internal predecessors, (118), 22 states have call successors, (88), 1 states have call predecessors, (88), 1 states have return successors, (88), 22 states have call predecessors, (88), 22 states have call successors, (88) [2023-12-02 20:04:10,317 INFO L276 IsEmpty]: Start isEmpty. Operand 215 states and 305 transitions. [2023-12-02 20:04:10,326 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 395 [2023-12-02 20:04:10,326 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 20:04:10,326 INFO L195 NwaCegarLoop]: trace histogram [46, 46, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 20:04:10,332 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1da6b7e5-f792-4cbb-9349-461660b658ca/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2023-12-02 20:04:10,532 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1da6b7e5-f792-4cbb-9349-461660b658ca/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 20:04:10,532 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 20:04:10,533 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 20:04:10,533 INFO L85 PathProgramCache]: Analyzing trace with hash -954299617, now seen corresponding path program 4 times [2023-12-02 20:04:10,533 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 20:04:10,533 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [851869241] [2023-12-02 20:04:10,533 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 20:04:10,534 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 20:04:10,588 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 20:04:11,731 INFO L134 CoverageAnalysis]: Checked inductivity of 6241 backedges. 0 proven. 2101 refuted. 0 times theorem prover too weak. 4140 trivial. 0 not checked. [2023-12-02 20:04:11,732 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 20:04:11,732 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [851869241] [2023-12-02 20:04:11,732 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [851869241] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-02 20:04:11,732 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1834002463] [2023-12-02 20:04:11,732 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2023-12-02 20:04:11,732 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 20:04:11,732 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1da6b7e5-f792-4cbb-9349-461660b658ca/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 20:04:11,733 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1da6b7e5-f792-4cbb-9349-461660b658ca/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 20:04:11,741 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1da6b7e5-f792-4cbb-9349-461660b658ca/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2023-12-02 20:04:11,966 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 20:04:11,970 INFO L262 TraceCheckSpWp]: Trace formula consists of 995 conjuncts, 24 conjunts are in the unsatisfiable core [2023-12-02 20:04:11,983 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 20:04:12,238 INFO L134 CoverageAnalysis]: Checked inductivity of 6241 backedges. 0 proven. 2101 refuted. 0 times theorem prover too weak. 4140 trivial. 0 not checked. [2023-12-02 20:04:12,238 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 20:04:13,175 INFO L134 CoverageAnalysis]: Checked inductivity of 6241 backedges. 0 proven. 2101 refuted. 0 times theorem prover too weak. 4140 trivial. 0 not checked. [2023-12-02 20:04:13,176 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1834002463] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-02 20:04:13,176 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1666527854] [2023-12-02 20:04:13,179 INFO L159 IcfgInterpreter]: Started Sifa with 25 locations of interest [2023-12-02 20:04:13,179 INFO L166 IcfgInterpreter]: Building call graph [2023-12-02 20:04:13,179 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-12-02 20:04:13,179 INFO L176 IcfgInterpreter]: Starting interpretation [2023-12-02 20:04:13,179 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-12-02 20:04:13,586 INFO L197 IcfgInterpreter]: Interpreting procedure g with input of size 3 for LOIs [2023-12-02 20:04:13,587 INFO L197 IcfgInterpreter]: Interpreting procedure f with input of size 3 for LOIs [2023-12-02 20:04:13,588 INFO L180 IcfgInterpreter]: Interpretation finished [2023-12-02 20:04:13,791 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '5637#(and (<= 1 |#StackHeapBarrier|) (= |ULTIMATE.start___VERIFIER_assert_~cond#1| 0) (= |ULTIMATE.start___VERIFIER_assert_#in~cond#1| 0) (<= 100001 |ULTIMATE.start_main_~i~0#1|))' at error location [2023-12-02 20:04:13,792 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-12-02 20:04:13,792 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-12-02 20:04:13,792 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [25, 25, 25] total 49 [2023-12-02 20:04:13,792 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1863437467] [2023-12-02 20:04:13,793 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-12-02 20:04:13,795 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 49 states [2023-12-02 20:04:13,795 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 20:04:13,798 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 49 interpolants. [2023-12-02 20:04:13,799 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1205, Invalid=1987, Unknown=0, NotChecked=0, Total=3192 [2023-12-02 20:04:13,800 INFO L87 Difference]: Start difference. First operand 215 states and 305 transitions. Second operand has 49 states, 49 states have (on average 4.857142857142857) internal successors, (238), 49 states have internal predecessors, (238), 46 states have call successors, (184), 1 states have call predecessors, (184), 1 states have return successors, (184), 46 states have call predecessors, (184), 46 states have call successors, (184) [2023-12-02 20:04:14,367 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 20:04:14,368 INFO L93 Difference]: Finished difference Result 434 states and 643 transitions. [2023-12-02 20:04:14,368 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 48 states. [2023-12-02 20:04:14,369 INFO L78 Accepts]: Start accepts. Automaton has has 49 states, 49 states have (on average 4.857142857142857) internal successors, (238), 49 states have internal predecessors, (238), 46 states have call successors, (184), 1 states have call predecessors, (184), 1 states have return successors, (184), 46 states have call predecessors, (184), 46 states have call successors, (184) Word has length 394 [2023-12-02 20:04:14,371 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 20:04:14,374 INFO L225 Difference]: With dead ends: 434 [2023-12-02 20:04:14,375 INFO L226 Difference]: Without dead ends: 431 [2023-12-02 20:04:14,377 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 1205 GetRequests, 1150 SyntacticMatches, 0 SemanticMatches, 55 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 647 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=1205, Invalid=1987, Unknown=0, NotChecked=0, Total=3192 [2023-12-02 20:04:14,377 INFO L413 NwaCegarLoop]: 25 mSDtfsCounter, 8 mSDsluCounter, 220 mSDsCounter, 0 mSdLazyCounter, 297 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 16 SdHoareTripleChecker+Valid, 245 SdHoareTripleChecker+Invalid, 299 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 297 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2023-12-02 20:04:14,378 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [16 Valid, 245 Invalid, 299 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 297 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2023-12-02 20:04:14,379 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 431 states. [2023-12-02 20:04:14,413 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 431 to 431. [2023-12-02 20:04:14,415 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 431 states, 240 states have (on average 1.0041666666666667) internal successors, (241), 240 states have internal predecessors, (241), 188 states have call successors, (188), 2 states have call predecessors, (188), 2 states have return successors, (188), 188 states have call predecessors, (188), 188 states have call successors, (188) [2023-12-02 20:04:14,420 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 431 states to 431 states and 617 transitions. [2023-12-02 20:04:14,421 INFO L78 Accepts]: Start accepts. Automaton has 431 states and 617 transitions. Word has length 394 [2023-12-02 20:04:14,423 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 20:04:14,423 INFO L495 AbstractCegarLoop]: Abstraction has 431 states and 617 transitions. [2023-12-02 20:04:14,424 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 49 states, 49 states have (on average 4.857142857142857) internal successors, (238), 49 states have internal predecessors, (238), 46 states have call successors, (184), 1 states have call predecessors, (184), 1 states have return successors, (184), 46 states have call predecessors, (184), 46 states have call successors, (184) [2023-12-02 20:04:14,424 INFO L276 IsEmpty]: Start isEmpty. Operand 431 states and 617 transitions. [2023-12-02 20:04:14,453 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 803 [2023-12-02 20:04:14,453 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 20:04:14,453 INFO L195 NwaCegarLoop]: trace histogram [94, 94, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 20:04:14,460 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1da6b7e5-f792-4cbb-9349-461660b658ca/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2023-12-02 20:04:14,657 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1da6b7e5-f792-4cbb-9349-461660b658ca/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 20:04:14,658 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 20:04:14,658 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 20:04:14,658 INFO L85 PathProgramCache]: Analyzing trace with hash -328855521, now seen corresponding path program 5 times [2023-12-02 20:04:14,658 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 20:04:14,658 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1708166957] [2023-12-02 20:04:14,658 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 20:04:14,659 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 20:04:14,732 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 20:04:18,045 INFO L134 CoverageAnalysis]: Checked inductivity of 26845 backedges. 0 proven. 9361 refuted. 0 times theorem prover too weak. 17484 trivial. 0 not checked. [2023-12-02 20:04:18,046 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 20:04:18,046 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1708166957] [2023-12-02 20:04:18,046 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1708166957] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-02 20:04:18,046 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [381378947] [2023-12-02 20:04:18,046 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-12-02 20:04:18,046 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 20:04:18,046 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1da6b7e5-f792-4cbb-9349-461660b658ca/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 20:04:18,047 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1da6b7e5-f792-4cbb-9349-461660b658ca/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 20:04:18,049 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1da6b7e5-f792-4cbb-9349-461660b658ca/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2023-12-02 20:04:18,579 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 64 check-sat command(s) [2023-12-02 20:04:18,579 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-02 20:04:18,586 INFO L262 TraceCheckSpWp]: Trace formula consists of 1983 conjuncts, 48 conjunts are in the unsatisfiable core [2023-12-02 20:04:18,607 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 20:04:19,058 INFO L134 CoverageAnalysis]: Checked inductivity of 26845 backedges. 0 proven. 9361 refuted. 0 times theorem prover too weak. 17484 trivial. 0 not checked. [2023-12-02 20:04:19,058 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 20:04:21,916 INFO L134 CoverageAnalysis]: Checked inductivity of 26845 backedges. 0 proven. 9361 refuted. 0 times theorem prover too weak. 17484 trivial. 0 not checked. [2023-12-02 20:04:21,916 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [381378947] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-02 20:04:21,916 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [217807291] [2023-12-02 20:04:21,919 INFO L159 IcfgInterpreter]: Started Sifa with 25 locations of interest [2023-12-02 20:04:21,919 INFO L166 IcfgInterpreter]: Building call graph [2023-12-02 20:04:21,920 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-12-02 20:04:21,920 INFO L176 IcfgInterpreter]: Starting interpretation [2023-12-02 20:04:21,920 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-12-02 20:04:22,293 INFO L197 IcfgInterpreter]: Interpreting procedure g with input of size 3 for LOIs [2023-12-02 20:04:22,294 INFO L197 IcfgInterpreter]: Interpreting procedure f with input of size 3 for LOIs [2023-12-02 20:04:22,295 INFO L180 IcfgInterpreter]: Interpretation finished [2023-12-02 20:04:22,580 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '11887#(and (<= 1 |#StackHeapBarrier|) (= |ULTIMATE.start___VERIFIER_assert_~cond#1| 0) (= |ULTIMATE.start___VERIFIER_assert_#in~cond#1| 0) (<= 100001 |ULTIMATE.start_main_~i~0#1|))' at error location [2023-12-02 20:04:22,581 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-12-02 20:04:22,581 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-12-02 20:04:22,581 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [49, 49, 49] total 97 [2023-12-02 20:04:22,582 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [87457819] [2023-12-02 20:04:22,582 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-12-02 20:04:22,584 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 97 states [2023-12-02 20:04:22,585 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 20:04:22,589 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 97 interpolants. [2023-12-02 20:04:22,592 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=4685, Invalid=6235, Unknown=0, NotChecked=0, Total=10920 [2023-12-02 20:04:22,593 INFO L87 Difference]: Start difference. First operand 431 states and 617 transitions. Second operand has 97 states, 97 states have (on average 4.927835051546392) internal successors, (478), 97 states have internal predecessors, (478), 94 states have call successors, (376), 1 states have call predecessors, (376), 1 states have return successors, (376), 94 states have call predecessors, (376), 94 states have call successors, (376) [2023-12-02 20:04:23,611 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 20:04:23,611 INFO L93 Difference]: Finished difference Result 866 states and 1291 transitions. [2023-12-02 20:04:23,611 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 96 states. [2023-12-02 20:04:23,612 INFO L78 Accepts]: Start accepts. Automaton has has 97 states, 97 states have (on average 4.927835051546392) internal successors, (478), 97 states have internal predecessors, (478), 94 states have call successors, (376), 1 states have call predecessors, (376), 1 states have return successors, (376), 94 states have call predecessors, (376), 94 states have call successors, (376) Word has length 802 [2023-12-02 20:04:23,613 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 20:04:23,619 INFO L225 Difference]: With dead ends: 866 [2023-12-02 20:04:23,620 INFO L226 Difference]: Without dead ends: 863 [2023-12-02 20:04:23,624 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 2453 GetRequests, 2350 SyntacticMatches, 0 SemanticMatches, 103 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1319 ImplicationChecksByTransitivity, 3.2s TimeCoverageRelationStatistics Valid=4685, Invalid=6235, Unknown=0, NotChecked=0, Total=10920 [2023-12-02 20:04:23,625 INFO L413 NwaCegarLoop]: 25 mSDtfsCounter, 8 mSDsluCounter, 316 mSDsCounter, 0 mSdLazyCounter, 579 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 16 SdHoareTripleChecker+Valid, 341 SdHoareTripleChecker+Invalid, 581 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 579 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2023-12-02 20:04:23,626 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [16 Valid, 341 Invalid, 581 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 579 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2023-12-02 20:04:23,627 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 863 states. [2023-12-02 20:04:23,664 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 863 to 863. [2023-12-02 20:04:23,666 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 863 states, 480 states have (on average 1.0020833333333334) internal successors, (481), 480 states have internal predecessors, (481), 380 states have call successors, (380), 2 states have call predecessors, (380), 2 states have return successors, (380), 380 states have call predecessors, (380), 380 states have call successors, (380) [2023-12-02 20:04:23,671 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 863 states to 863 states and 1241 transitions. [2023-12-02 20:04:23,671 INFO L78 Accepts]: Start accepts. Automaton has 863 states and 1241 transitions. Word has length 802 [2023-12-02 20:04:23,674 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 20:04:23,674 INFO L495 AbstractCegarLoop]: Abstraction has 863 states and 1241 transitions. [2023-12-02 20:04:23,675 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 97 states, 97 states have (on average 4.927835051546392) internal successors, (478), 97 states have internal predecessors, (478), 94 states have call successors, (376), 1 states have call predecessors, (376), 1 states have return successors, (376), 94 states have call predecessors, (376), 94 states have call successors, (376) [2023-12-02 20:04:23,675 INFO L276 IsEmpty]: Start isEmpty. Operand 863 states and 1241 transitions. [2023-12-02 20:04:23,694 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1619 [2023-12-02 20:04:23,694 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 20:04:23,695 INFO L195 NwaCegarLoop]: trace histogram [190, 190, 94, 94, 94, 94, 94, 94, 94, 94, 94, 94, 94, 94, 94, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 20:04:23,701 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1da6b7e5-f792-4cbb-9349-461660b658ca/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2023-12-02 20:04:23,895 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1da6b7e5-f792-4cbb-9349-461660b658ca/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable5 [2023-12-02 20:04:23,895 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 20:04:23,896 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 20:04:23,896 INFO L85 PathProgramCache]: Analyzing trace with hash -987227617, now seen corresponding path program 6 times [2023-12-02 20:04:23,896 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 20:04:23,896 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1395681545] [2023-12-02 20:04:23,896 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 20:04:23,897 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 20:04:24,032 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 20:04:38,206 INFO L134 CoverageAnalysis]: Checked inductivity of 111253 backedges. 0 proven. 39433 refuted. 0 times theorem prover too weak. 71820 trivial. 0 not checked. [2023-12-02 20:04:38,206 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 20:04:38,206 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1395681545] [2023-12-02 20:04:38,206 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1395681545] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-02 20:04:38,206 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1887436011] [2023-12-02 20:04:38,206 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2023-12-02 20:04:38,206 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 20:04:38,207 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1da6b7e5-f792-4cbb-9349-461660b658ca/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 20:04:38,207 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1da6b7e5-f792-4cbb-9349-461660b658ca/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 20:04:38,209 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1da6b7e5-f792-4cbb-9349-461660b658ca/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2023-12-02 20:04:38,864 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2023-12-02 20:04:38,864 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-02 20:04:38,879 INFO L262 TraceCheckSpWp]: Trace formula consists of 4019 conjuncts, 96 conjunts are in the unsatisfiable core [2023-12-02 20:04:38,904 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 20:04:39,748 INFO L134 CoverageAnalysis]: Checked inductivity of 111253 backedges. 0 proven. 39433 refuted. 0 times theorem prover too weak. 71820 trivial. 0 not checked. [2023-12-02 20:04:39,748 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 20:04:49,414 INFO L134 CoverageAnalysis]: Checked inductivity of 111253 backedges. 0 proven. 39433 refuted. 0 times theorem prover too weak. 71820 trivial. 0 not checked. [2023-12-02 20:04:49,414 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1887436011] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-02 20:04:49,414 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [87499912] [2023-12-02 20:04:49,416 INFO L159 IcfgInterpreter]: Started Sifa with 25 locations of interest [2023-12-02 20:04:49,416 INFO L166 IcfgInterpreter]: Building call graph [2023-12-02 20:04:49,417 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-12-02 20:04:49,417 INFO L176 IcfgInterpreter]: Starting interpretation [2023-12-02 20:04:49,417 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-12-02 20:04:49,770 INFO L197 IcfgInterpreter]: Interpreting procedure g with input of size 3 for LOIs [2023-12-02 20:04:49,771 INFO L197 IcfgInterpreter]: Interpreting procedure f with input of size 3 for LOIs [2023-12-02 20:04:49,772 INFO L180 IcfgInterpreter]: Interpretation finished [2023-12-02 20:04:50,219 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '24473#(and (<= 1 |#StackHeapBarrier|) (= |ULTIMATE.start___VERIFIER_assert_~cond#1| 0) (= |ULTIMATE.start___VERIFIER_assert_#in~cond#1| 0) (<= 100001 |ULTIMATE.start_main_~i~0#1|))' at error location [2023-12-02 20:04:50,219 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-12-02 20:04:50,219 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-12-02 20:04:50,221 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [97, 97, 97] total 193 [2023-12-02 20:04:50,221 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [473640519] [2023-12-02 20:04:50,221 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-12-02 20:04:50,225 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 193 states [2023-12-02 20:04:50,226 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 20:04:50,235 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 193 interpolants. [2023-12-02 20:04:50,249 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=18557, Invalid=21643, Unknown=0, NotChecked=0, Total=40200 [2023-12-02 20:04:50,251 INFO L87 Difference]: Start difference. First operand 863 states and 1241 transitions. Second operand has 193 states, 193 states have (on average 4.963730569948186) internal successors, (958), 193 states have internal predecessors, (958), 190 states have call successors, (760), 1 states have call predecessors, (760), 1 states have return successors, (760), 190 states have call predecessors, (760), 190 states have call successors, (760) [2023-12-02 20:04:54,541 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 20:04:54,541 INFO L93 Difference]: Finished difference Result 1730 states and 2587 transitions. [2023-12-02 20:04:54,542 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 192 states. [2023-12-02 20:04:54,543 INFO L78 Accepts]: Start accepts. Automaton has has 193 states, 193 states have (on average 4.963730569948186) internal successors, (958), 193 states have internal predecessors, (958), 190 states have call successors, (760), 1 states have call predecessors, (760), 1 states have return successors, (760), 190 states have call predecessors, (760), 190 states have call successors, (760) Word has length 1618 [2023-12-02 20:04:54,546 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 20:04:54,557 INFO L225 Difference]: With dead ends: 1730 [2023-12-02 20:04:54,558 INFO L226 Difference]: Without dead ends: 1727 [2023-12-02 20:04:54,566 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 4949 GetRequests, 4750 SyntacticMatches, 0 SemanticMatches, 199 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2663 ImplicationChecksByTransitivity, 11.8s TimeCoverageRelationStatistics Valid=18557, Invalid=21643, Unknown=0, NotChecked=0, Total=40200 [2023-12-02 20:04:54,567 INFO L413 NwaCegarLoop]: 25 mSDtfsCounter, 8 mSDsluCounter, 686 mSDsCounter, 0 mSdLazyCounter, 1169 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 16 SdHoareTripleChecker+Valid, 711 SdHoareTripleChecker+Invalid, 1171 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 1169 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.3s IncrementalHoareTripleChecker+Time [2023-12-02 20:04:54,567 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [16 Valid, 711 Invalid, 1171 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 1169 Invalid, 0 Unknown, 0 Unchecked, 1.3s Time] [2023-12-02 20:04:54,569 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1727 states. [2023-12-02 20:04:54,664 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1727 to 1727. [2023-12-02 20:04:54,669 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1727 states, 960 states have (on average 1.0010416666666666) internal successors, (961), 960 states have internal predecessors, (961), 764 states have call successors, (764), 2 states have call predecessors, (764), 2 states have return successors, (764), 764 states have call predecessors, (764), 764 states have call successors, (764) [2023-12-02 20:04:54,682 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1727 states to 1727 states and 2489 transitions. [2023-12-02 20:04:54,683 INFO L78 Accepts]: Start accepts. Automaton has 1727 states and 2489 transitions. Word has length 1618 [2023-12-02 20:04:54,687 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 20:04:54,688 INFO L495 AbstractCegarLoop]: Abstraction has 1727 states and 2489 transitions. [2023-12-02 20:04:54,690 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 193 states, 193 states have (on average 4.963730569948186) internal successors, (958), 193 states have internal predecessors, (958), 190 states have call successors, (760), 1 states have call predecessors, (760), 1 states have return successors, (760), 190 states have call predecessors, (760), 190 states have call successors, (760) [2023-12-02 20:04:54,690 INFO L276 IsEmpty]: Start isEmpty. Operand 1727 states and 2489 transitions. [2023-12-02 20:04:54,770 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 3251 [2023-12-02 20:04:54,770 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 20:04:54,772 INFO L195 NwaCegarLoop]: trace histogram [382, 382, 190, 190, 190, 190, 190, 190, 190, 190, 190, 190, 190, 190, 190, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 20:04:54,781 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1da6b7e5-f792-4cbb-9349-461660b658ca/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2023-12-02 20:04:54,972 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 7 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1da6b7e5-f792-4cbb-9349-461660b658ca/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable6 [2023-12-02 20:04:54,973 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 20:04:54,973 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 20:04:54,973 INFO L85 PathProgramCache]: Analyzing trace with hash -1686622689, now seen corresponding path program 7 times [2023-12-02 20:04:54,973 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 20:04:54,974 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1905203582] [2023-12-02 20:04:54,974 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 20:04:54,974 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 20:04:55,239 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 20:06:30,573 INFO L134 CoverageAnalysis]: Checked inductivity of 452869 backedges. 0 proven. 161785 refuted. 0 times theorem prover too weak. 291084 trivial. 0 not checked. [2023-12-02 20:06:30,574 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 20:06:30,574 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1905203582] [2023-12-02 20:06:30,574 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1905203582] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-02 20:06:30,574 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1030246055] [2023-12-02 20:06:30,574 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2023-12-02 20:06:30,574 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 20:06:30,574 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1da6b7e5-f792-4cbb-9349-461660b658ca/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 20:06:30,575 INFO L229 MonitoredProcess]: Starting monitored process 8 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1da6b7e5-f792-4cbb-9349-461660b658ca/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 20:06:30,576 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1da6b7e5-f792-4cbb-9349-461660b658ca/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2023-12-02 20:06:31,819 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 20:06:31,850 INFO L262 TraceCheckSpWp]: Trace formula consists of 8051 conjuncts, 192 conjunts are in the unsatisfiable core [2023-12-02 20:06:31,900 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 20:06:33,484 INFO L134 CoverageAnalysis]: Checked inductivity of 452869 backedges. 0 proven. 161785 refuted. 0 times theorem prover too weak. 291084 trivial. 0 not checked. [2023-12-02 20:06:33,485 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 20:07:09,064 INFO L134 CoverageAnalysis]: Checked inductivity of 452869 backedges. 0 proven. 161785 refuted. 0 times theorem prover too weak. 291084 trivial. 0 not checked. [2023-12-02 20:07:09,065 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1030246055] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-02 20:07:09,065 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1020324097] [2023-12-02 20:07:09,069 INFO L159 IcfgInterpreter]: Started Sifa with 25 locations of interest [2023-12-02 20:07:09,069 INFO L166 IcfgInterpreter]: Building call graph [2023-12-02 20:07:09,069 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-12-02 20:07:09,070 INFO L176 IcfgInterpreter]: Starting interpretation [2023-12-02 20:07:09,070 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-12-02 20:07:09,392 INFO L197 IcfgInterpreter]: Interpreting procedure g with input of size 3 for LOIs [2023-12-02 20:07:09,393 INFO L197 IcfgInterpreter]: Interpreting procedure f with input of size 3 for LOIs [2023-12-02 20:07:09,394 INFO L180 IcfgInterpreter]: Interpretation finished [2023-12-02 20:07:10,212 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '49731#(and (<= 1 |#StackHeapBarrier|) (= |ULTIMATE.start___VERIFIER_assert_~cond#1| 0) (= |ULTIMATE.start___VERIFIER_assert_#in~cond#1| 0) (<= 100001 |ULTIMATE.start_main_~i~0#1|))' at error location [2023-12-02 20:07:10,212 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-12-02 20:07:10,213 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-12-02 20:07:10,215 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [193, 193, 193] total 385 [2023-12-02 20:07:10,216 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [700025384] [2023-12-02 20:07:10,216 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-12-02 20:07:10,224 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 385 states [2023-12-02 20:07:10,225 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 20:07:10,251 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 385 interpolants. [2023-12-02 20:07:10,269 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=73949, Invalid=80107, Unknown=0, NotChecked=0, Total=154056 [2023-12-02 20:07:10,272 INFO L87 Difference]: Start difference. First operand 1727 states and 2489 transitions. Second operand has 385 states, 385 states have (on average 4.9818181818181815) internal successors, (1918), 385 states have internal predecessors, (1918), 382 states have call successors, (1528), 1 states have call predecessors, (1528), 1 states have return successors, (1528), 382 states have call predecessors, (1528), 382 states have call successors, (1528) [2023-12-02 20:07:26,728 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 20:07:26,729 INFO L93 Difference]: Finished difference Result 3458 states and 5179 transitions. [2023-12-02 20:07:26,729 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 384 states. [2023-12-02 20:07:26,732 INFO L78 Accepts]: Start accepts. Automaton has has 385 states, 385 states have (on average 4.9818181818181815) internal successors, (1918), 385 states have internal predecessors, (1918), 382 states have call successors, (1528), 1 states have call predecessors, (1528), 1 states have return successors, (1528), 382 states have call predecessors, (1528), 382 states have call successors, (1528) Word has length 3250 [2023-12-02 20:07:26,736 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 20:07:26,753 INFO L225 Difference]: With dead ends: 3458 [2023-12-02 20:07:26,754 INFO L226 Difference]: Without dead ends: 3455 [2023-12-02 20:07:26,770 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 9941 GetRequests, 9550 SyntacticMatches, 0 SemanticMatches, 391 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5351 ImplicationChecksByTransitivity, 45.1s TimeCoverageRelationStatistics Valid=73949, Invalid=80107, Unknown=0, NotChecked=0, Total=154056 [2023-12-02 20:07:26,770 INFO L413 NwaCegarLoop]: 25 mSDtfsCounter, 8 mSDsluCounter, 1214 mSDsCounter, 0 mSdLazyCounter, 2315 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 16 SdHoareTripleChecker+Valid, 1239 SdHoareTripleChecker+Invalid, 2317 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 2315 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.8s IncrementalHoareTripleChecker+Time [2023-12-02 20:07:26,770 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [16 Valid, 1239 Invalid, 2317 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 2315 Invalid, 0 Unknown, 0 Unchecked, 2.8s Time] [2023-12-02 20:07:26,775 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 3455 states. [2023-12-02 20:07:26,970 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 3455 to 3455. [2023-12-02 20:07:26,977 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 3455 states, 1920 states have (on average 1.0005208333333333) internal successors, (1921), 1920 states have internal predecessors, (1921), 1532 states have call successors, (1532), 2 states have call predecessors, (1532), 2 states have return successors, (1532), 1532 states have call predecessors, (1532), 1532 states have call successors, (1532) [2023-12-02 20:07:26,999 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3455 states to 3455 states and 4985 transitions. [2023-12-02 20:07:26,999 INFO L78 Accepts]: Start accepts. Automaton has 3455 states and 4985 transitions. Word has length 3250 [2023-12-02 20:07:27,005 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 20:07:27,006 INFO L495 AbstractCegarLoop]: Abstraction has 3455 states and 4985 transitions. [2023-12-02 20:07:27,009 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 385 states, 385 states have (on average 4.9818181818181815) internal successors, (1918), 385 states have internal predecessors, (1918), 382 states have call successors, (1528), 1 states have call predecessors, (1528), 1 states have return successors, (1528), 382 states have call predecessors, (1528), 382 states have call successors, (1528) [2023-12-02 20:07:27,009 INFO L276 IsEmpty]: Start isEmpty. Operand 3455 states and 4985 transitions. [2023-12-02 20:07:27,346 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 6515 [2023-12-02 20:07:27,346 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 20:07:27,348 INFO L195 NwaCegarLoop]: trace histogram [766, 766, 382, 382, 382, 382, 382, 382, 382, 382, 382, 382, 382, 382, 382, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 20:07:27,365 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1da6b7e5-f792-4cbb-9349-461660b658ca/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2023-12-02 20:07:27,548 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 8 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1da6b7e5-f792-4cbb-9349-461660b658ca/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable7 [2023-12-02 20:07:27,549 INFO L420 AbstractCegarLoop]: === Iteration 9 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 20:07:27,549 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 20:07:27,550 INFO L85 PathProgramCache]: Analyzing trace with hash 994596383, now seen corresponding path program 8 times [2023-12-02 20:07:27,550 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 20:07:27,550 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1320019484] [2023-12-02 20:07:27,550 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 20:07:27,550 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 20:07:28,554 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat