./Ultimate.py --spec ../../sv-benchmarks/c/properties/unreach-call.prp --file ../../sv-benchmarks/c/array-examples/standard_sentinel-2.i --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 0e0057cc Calling Ultimate with: /usr/lib/jvm/java-1.11.0-openjdk-amd64/bin/java -Dosgi.configuration.area=/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4b135455-3be0-4a46-9000-73ecba14935e/bin/utaipan-verify-nQ1chXbOIh/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4b135455-3be0-4a46-9000-73ecba14935e/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_4b135455-3be0-4a46-9000-73ecba14935e/bin/utaipan-verify-nQ1chXbOIh/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4b135455-3be0-4a46-9000-73ecba14935e/bin/utaipan-verify-nQ1chXbOIh/config/TaipanReach.xml -i ../../sv-benchmarks/c/array-examples/standard_sentinel-2.i -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4b135455-3be0-4a46-9000-73ecba14935e/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_4b135455-3be0-4a46-9000-73ecba14935e/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 590a845a219659d0ad58521e10c3551f2ec7e80ca70e994a8616abe765f6f296 --- Real Ultimate output --- This is Ultimate 0.2.4-dev-0e0057c [2023-12-02 17:12:05,704 INFO L188 SettingsManager]: Resetting all preferences to default values... [2023-12-02 17:12:05,771 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4b135455-3be0-4a46-9000-73ecba14935e/bin/utaipan-verify-nQ1chXbOIh/config/svcomp-Reach-32bit-Taipan_Default.epf [2023-12-02 17:12:05,777 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2023-12-02 17:12:05,778 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2023-12-02 17:12:05,802 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2023-12-02 17:12:05,802 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2023-12-02 17:12:05,803 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2023-12-02 17:12:05,804 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2023-12-02 17:12:05,804 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2023-12-02 17:12:05,805 INFO L153 SettingsManager]: * User list type=DISABLED [2023-12-02 17:12:05,805 INFO L151 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2023-12-02 17:12:05,806 INFO L153 SettingsManager]: * Explicit value domain=true [2023-12-02 17:12:05,806 INFO L153 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2023-12-02 17:12:05,807 INFO L153 SettingsManager]: * Octagon Domain=false [2023-12-02 17:12:05,807 INFO L153 SettingsManager]: * Abstract domain=CompoundDomain [2023-12-02 17:12:05,808 INFO L153 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2023-12-02 17:12:05,808 INFO L153 SettingsManager]: * Use the RCFG-of-the-future interface=true [2023-12-02 17:12:05,809 INFO L153 SettingsManager]: * Interval Domain=false [2023-12-02 17:12:05,809 INFO L151 SettingsManager]: Preferences of Sifa differ from their defaults: [2023-12-02 17:12:05,810 INFO L153 SettingsManager]: * Call Summarizer=TopInputCallSummarizer [2023-12-02 17:12:05,811 INFO L153 SettingsManager]: * Simplification Technique=POLY_PAC [2023-12-02 17:12:05,811 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2023-12-02 17:12:05,812 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2023-12-02 17:12:05,812 INFO L153 SettingsManager]: * sizeof long=4 [2023-12-02 17:12:05,813 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2023-12-02 17:12:05,813 INFO L153 SettingsManager]: * sizeof POINTER=4 [2023-12-02 17:12:05,813 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2023-12-02 17:12:05,814 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2023-12-02 17:12:05,814 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2023-12-02 17:12:05,814 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2023-12-02 17:12:05,815 INFO L153 SettingsManager]: * sizeof long double=12 [2023-12-02 17:12:05,815 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2023-12-02 17:12:05,815 INFO L153 SettingsManager]: * Use constant arrays=true [2023-12-02 17:12:05,816 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2023-12-02 17:12:05,816 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2023-12-02 17:12:05,816 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2023-12-02 17:12:05,816 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-12-02 17:12:05,817 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2023-12-02 17:12:05,817 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2023-12-02 17:12:05,817 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2023-12-02 17:12:05,817 INFO L153 SettingsManager]: * Trace refinement strategy=SIFA_TAIPAN [2023-12-02 17:12:05,818 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2023-12-02 17:12:05,818 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2023-12-02 17:12:05,818 INFO L153 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2023-12-02 17:12:05,818 INFO L153 SettingsManager]: * Trace refinement exception blacklist=NONE [2023-12-02 17:12:05,818 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2023-12-02 17:12:05,819 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_4b135455-3be0-4a46-9000-73ecba14935e/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_4b135455-3be0-4a46-9000-73ecba14935e/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 -> 590a845a219659d0ad58521e10c3551f2ec7e80ca70e994a8616abe765f6f296 [2023-12-02 17:12:06,048 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2023-12-02 17:12:06,070 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2023-12-02 17:12:06,073 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2023-12-02 17:12:06,074 INFO L270 PluginConnector]: Initializing CDTParser... [2023-12-02 17:12:06,074 INFO L274 PluginConnector]: CDTParser initialized [2023-12-02 17:12:06,076 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4b135455-3be0-4a46-9000-73ecba14935e/bin/utaipan-verify-nQ1chXbOIh/../../sv-benchmarks/c/array-examples/standard_sentinel-2.i [2023-12-02 17:12:08,847 INFO L533 CDTParser]: Created temporary CDT project at NULL [2023-12-02 17:12:09,027 INFO L384 CDTParser]: Found 1 translation units. [2023-12-02 17:12:09,027 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4b135455-3be0-4a46-9000-73ecba14935e/sv-benchmarks/c/array-examples/standard_sentinel-2.i [2023-12-02 17:12:09,035 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4b135455-3be0-4a46-9000-73ecba14935e/bin/utaipan-verify-nQ1chXbOIh/data/4a2b41102/0757cb3c7a2147998805401177ac425f/FLAG6c800b5d4 [2023-12-02 17:12:09,048 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4b135455-3be0-4a46-9000-73ecba14935e/bin/utaipan-verify-nQ1chXbOIh/data/4a2b41102/0757cb3c7a2147998805401177ac425f [2023-12-02 17:12:09,050 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2023-12-02 17:12:09,052 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2023-12-02 17:12:09,053 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2023-12-02 17:12:09,053 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2023-12-02 17:12:09,058 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2023-12-02 17:12:09,059 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 02.12 05:12:09" (1/1) ... [2023-12-02 17:12:09,060 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@cb130c3 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 05:12:09, skipping insertion in model container [2023-12-02 17:12:09,060 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 02.12 05:12:09" (1/1) ... [2023-12-02 17:12:09,079 INFO L177 MainTranslator]: Built tables and reachable declarations [2023-12-02 17:12:09,207 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_4b135455-3be0-4a46-9000-73ecba14935e/sv-benchmarks/c/array-examples/standard_sentinel-2.i[852,865] [2023-12-02 17:12:09,222 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-12-02 17:12:09,230 INFO L202 MainTranslator]: Completed pre-run [2023-12-02 17:12:09,241 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_4b135455-3be0-4a46-9000-73ecba14935e/sv-benchmarks/c/array-examples/standard_sentinel-2.i[852,865] [2023-12-02 17:12:09,247 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-12-02 17:12:09,260 INFO L206 MainTranslator]: Completed translation [2023-12-02 17:12:09,261 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 05:12:09 WrapperNode [2023-12-02 17:12:09,261 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2023-12-02 17:12:09,262 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2023-12-02 17:12:09,262 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2023-12-02 17:12:09,262 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2023-12-02 17:12:09,269 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 05:12:09" (1/1) ... [2023-12-02 17:12:09,276 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 05:12:09" (1/1) ... [2023-12-02 17:12:09,291 INFO L138 Inliner]: procedures = 16, calls = 13, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 54 [2023-12-02 17:12:09,292 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2023-12-02 17:12:09,292 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2023-12-02 17:12:09,293 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2023-12-02 17:12:09,293 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2023-12-02 17:12:09,300 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 05:12:09" (1/1) ... [2023-12-02 17:12:09,300 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 05:12:09" (1/1) ... [2023-12-02 17:12:09,302 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 05:12:09" (1/1) ... [2023-12-02 17:12:09,302 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 05:12:09" (1/1) ... [2023-12-02 17:12:09,307 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 05:12:09" (1/1) ... [2023-12-02 17:12:09,311 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 05:12:09" (1/1) ... [2023-12-02 17:12:09,312 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 05:12:09" (1/1) ... [2023-12-02 17:12:09,313 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 05:12:09" (1/1) ... [2023-12-02 17:12:09,315 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2023-12-02 17:12:09,316 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2023-12-02 17:12:09,316 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2023-12-02 17:12:09,316 INFO L274 PluginConnector]: RCFGBuilder initialized [2023-12-02 17:12:09,317 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 05:12:09" (1/1) ... [2023-12-02 17:12:09,325 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-12-02 17:12:09,334 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4b135455-3be0-4a46-9000-73ecba14935e/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 17:12:09,346 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4b135455-3be0-4a46-9000-73ecba14935e/bin/utaipan-verify-nQ1chXbOIh/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2023-12-02 17:12:09,353 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4b135455-3be0-4a46-9000-73ecba14935e/bin/utaipan-verify-nQ1chXbOIh/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2023-12-02 17:12:09,381 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2023-12-02 17:12:09,381 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2023-12-02 17:12:09,382 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2023-12-02 17:12:09,382 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2023-12-02 17:12:09,382 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2023-12-02 17:12:09,382 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2023-12-02 17:12:09,383 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2023-12-02 17:12:09,383 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2023-12-02 17:12:09,448 INFO L241 CfgBuilder]: Building ICFG [2023-12-02 17:12:09,450 INFO L267 CfgBuilder]: Building CFG for each procedure with an implementation [2023-12-02 17:12:09,567 INFO L282 CfgBuilder]: Performing block encoding [2023-12-02 17:12:09,603 INFO L304 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2023-12-02 17:12:09,603 INFO L309 CfgBuilder]: Removed 2 assume(true) statements. [2023-12-02 17:12:09,605 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 02.12 05:12:09 BoogieIcfgContainer [2023-12-02 17:12:09,605 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2023-12-02 17:12:09,608 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2023-12-02 17:12:09,608 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2023-12-02 17:12:09,611 INFO L274 PluginConnector]: TraceAbstraction initialized [2023-12-02 17:12:09,611 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 02.12 05:12:09" (1/3) ... [2023-12-02 17:12:09,612 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6047c25d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 02.12 05:12:09, skipping insertion in model container [2023-12-02 17:12:09,612 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 05:12:09" (2/3) ... [2023-12-02 17:12:09,613 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6047c25d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 02.12 05:12:09, skipping insertion in model container [2023-12-02 17:12:09,613 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 02.12 05:12:09" (3/3) ... [2023-12-02 17:12:09,614 INFO L112 eAbstractionObserver]: Analyzing ICFG standard_sentinel-2.i [2023-12-02 17:12:09,631 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2023-12-02 17:12:09,631 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2023-12-02 17:12:09,674 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-12-02 17:12:09,681 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;@64a50a11, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2023-12-02 17:12:09,681 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2023-12-02 17:12:09,685 INFO L276 IsEmpty]: Start isEmpty. Operand has 12 states, 10 states have (on average 1.6) internal successors, (16), 11 states have internal predecessors, (16), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 17:12:09,690 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 8 [2023-12-02 17:12:09,690 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 17:12:09,691 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2023-12-02 17:12:09,691 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 17:12:09,696 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 17:12:09,696 INFO L85 PathProgramCache]: Analyzing trace with hash -2024870062, now seen corresponding path program 1 times [2023-12-02 17:12:09,704 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 17:12:09,705 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1311337178] [2023-12-02 17:12:09,705 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 17:12:09,705 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 17:12:09,793 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 17:12:09,877 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-02 17:12:09,878 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 17:12:09,878 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1311337178] [2023-12-02 17:12:09,879 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1311337178] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-02 17:12:09,880 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-12-02 17:12:09,880 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2023-12-02 17:12:09,882 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2120148291] [2023-12-02 17:12:09,883 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-02 17:12:09,887 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-12-02 17:12:09,887 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 17:12:09,917 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-12-02 17:12:09,918 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2023-12-02 17:12:09,920 INFO L87 Difference]: Start difference. First operand has 12 states, 10 states have (on average 1.6) internal successors, (16), 11 states have internal predecessors, (16), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Second operand has 3 states, 3 states have (on average 2.3333333333333335) internal successors, (7), 2 states have internal predecessors, (7), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 17:12:09,948 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 17:12:09,948 INFO L93 Difference]: Finished difference Result 23 states and 31 transitions. [2023-12-02 17:12:09,950 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-12-02 17:12:09,951 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 2.3333333333333335) internal successors, (7), 2 states have internal predecessors, (7), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 7 [2023-12-02 17:12:09,951 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 17:12:09,959 INFO L225 Difference]: With dead ends: 23 [2023-12-02 17:12:09,960 INFO L226 Difference]: Without dead ends: 10 [2023-12-02 17:12:09,963 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 1 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 17:12:09,967 INFO L413 NwaCegarLoop]: 10 mSDtfsCounter, 0 mSDsluCounter, 10 mSDsCounter, 0 mSdLazyCounter, 7 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 20 SdHoareTripleChecker+Invalid, 7 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 7 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-12-02 17:12:09,968 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 20 Invalid, 7 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 7 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-12-02 17:12:09,988 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 10 states. [2023-12-02 17:12:10,000 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 10 to 10. [2023-12-02 17:12:10,001 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 10 states, 9 states have (on average 1.2222222222222223) internal successors, (11), 9 states have internal predecessors, (11), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 17:12:10,002 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 11 transitions. [2023-12-02 17:12:10,003 INFO L78 Accepts]: Start accepts. Automaton has 10 states and 11 transitions. Word has length 7 [2023-12-02 17:12:10,004 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 17:12:10,004 INFO L495 AbstractCegarLoop]: Abstraction has 10 states and 11 transitions. [2023-12-02 17:12:10,004 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 2.3333333333333335) internal successors, (7), 2 states have internal predecessors, (7), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 17:12:10,004 INFO L276 IsEmpty]: Start isEmpty. Operand 10 states and 11 transitions. [2023-12-02 17:12:10,005 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 10 [2023-12-02 17:12:10,005 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 17:12:10,005 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 17:12:10,005 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2023-12-02 17:12:10,006 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 17:12:10,006 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 17:12:10,007 INFO L85 PathProgramCache]: Analyzing trace with hash -1344833310, now seen corresponding path program 1 times [2023-12-02 17:12:10,007 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 17:12:10,007 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [913753252] [2023-12-02 17:12:10,007 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 17:12:10,008 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 17:12:10,029 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 17:12:10,101 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-02 17:12:10,101 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 17:12:10,101 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [913753252] [2023-12-02 17:12:10,101 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [913753252] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-02 17:12:10,102 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1319415899] [2023-12-02 17:12:10,102 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 17:12:10,102 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 17:12:10,120 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4b135455-3be0-4a46-9000-73ecba14935e/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 17:12:10,126 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4b135455-3be0-4a46-9000-73ecba14935e/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 17:12:10,131 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4b135455-3be0-4a46-9000-73ecba14935e/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2023-12-02 17:12:10,224 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 17:12:10,226 INFO L262 TraceCheckSpWp]: Trace formula consists of 64 conjuncts, 3 conjunts are in the unsatisfiable core [2023-12-02 17:12:10,230 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 17:12:10,263 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-02 17:12:10,263 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 17:12:10,288 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-02 17:12:10,289 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1319415899] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-02 17:12:10,289 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1384569819] [2023-12-02 17:12:10,311 INFO L159 IcfgInterpreter]: Started Sifa with 9 locations of interest [2023-12-02 17:12:10,312 INFO L166 IcfgInterpreter]: Building call graph [2023-12-02 17:12:10,316 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-12-02 17:12:10,321 INFO L176 IcfgInterpreter]: Starting interpretation [2023-12-02 17:12:10,322 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-12-02 17:12:10,732 INFO L180 IcfgInterpreter]: Interpretation finished [2023-12-02 17:12:11,000 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSifa [1384569819] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-02 17:12:11,000 INFO L185 FreeRefinementEngine]: Found 1 perfect and 3 imperfect interpolant sequences. [2023-12-02 17:12:11,000 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [3, 3, 3] total 11 [2023-12-02 17:12:11,001 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [288232890] [2023-12-02 17:12:11,001 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-02 17:12:11,002 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2023-12-02 17:12:11,002 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 17:12:11,003 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2023-12-02 17:12:11,003 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=36, Invalid=96, Unknown=0, NotChecked=0, Total=132 [2023-12-02 17:12:11,004 INFO L87 Difference]: Start difference. First operand 10 states and 11 transitions. Second operand has 8 states, 8 states have (on average 1.125) internal successors, (9), 7 states have internal predecessors, (9), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 17:12:11,081 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 17:12:11,081 INFO L93 Difference]: Finished difference Result 16 states and 17 transitions. [2023-12-02 17:12:11,082 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2023-12-02 17:12:11,082 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 1.125) internal successors, (9), 7 states have internal predecessors, (9), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 9 [2023-12-02 17:12:11,083 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 17:12:11,083 INFO L225 Difference]: With dead ends: 16 [2023-12-02 17:12:11,083 INFO L226 Difference]: Without dead ends: 12 [2023-12-02 17:12:11,084 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 28 GetRequests, 18 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 28 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=36, Invalid=96, Unknown=0, NotChecked=0, Total=132 [2023-12-02 17:12:11,085 INFO L413 NwaCegarLoop]: 2 mSDtfsCounter, 7 mSDsluCounter, 8 mSDsCounter, 0 mSdLazyCounter, 38 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 10 SdHoareTripleChecker+Invalid, 38 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 38 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-12-02 17:12:11,086 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 10 Invalid, 38 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 38 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-12-02 17:12:11,087 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 12 states. [2023-12-02 17:12:11,090 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 12 to 12. [2023-12-02 17:12:11,090 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 12 states, 11 states have (on average 1.1818181818181819) internal successors, (13), 11 states have internal predecessors, (13), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 17:12:11,091 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 12 states to 12 states and 13 transitions. [2023-12-02 17:12:11,091 INFO L78 Accepts]: Start accepts. Automaton has 12 states and 13 transitions. Word has length 9 [2023-12-02 17:12:11,091 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 17:12:11,091 INFO L495 AbstractCegarLoop]: Abstraction has 12 states and 13 transitions. [2023-12-02 17:12:11,092 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 1.125) internal successors, (9), 7 states have internal predecessors, (9), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 17:12:11,092 INFO L276 IsEmpty]: Start isEmpty. Operand 12 states and 13 transitions. [2023-12-02 17:12:11,092 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2023-12-02 17:12:11,092 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 17:12:11,092 INFO L195 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 17:12:11,099 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4b135455-3be0-4a46-9000-73ecba14935e/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2023-12-02 17:12:11,293 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4b135455-3be0-4a46-9000-73ecba14935e/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 17:12:11,293 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 17:12:11,294 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 17:12:11,294 INFO L85 PathProgramCache]: Analyzing trace with hash 449020029, now seen corresponding path program 1 times [2023-12-02 17:12:11,294 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 17:12:11,294 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [154869106] [2023-12-02 17:12:11,294 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 17:12:11,294 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 17:12:11,308 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 17:12:11,359 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2023-12-02 17:12:11,359 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 17:12:11,359 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [154869106] [2023-12-02 17:12:11,360 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [154869106] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-02 17:12:11,360 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [552512001] [2023-12-02 17:12:11,360 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 17:12:11,360 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 17:12:11,360 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4b135455-3be0-4a46-9000-73ecba14935e/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 17:12:11,363 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4b135455-3be0-4a46-9000-73ecba14935e/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 17:12:11,367 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4b135455-3be0-4a46-9000-73ecba14935e/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2023-12-02 17:12:11,424 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 17:12:11,425 INFO L262 TraceCheckSpWp]: Trace formula consists of 69 conjuncts, 3 conjunts are in the unsatisfiable core [2023-12-02 17:12:11,426 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 17:12:11,432 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2023-12-02 17:12:11,432 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 17:12:11,449 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2023-12-02 17:12:11,449 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [552512001] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-02 17:12:11,449 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [2100679928] [2023-12-02 17:12:11,452 INFO L159 IcfgInterpreter]: Started Sifa with 9 locations of interest [2023-12-02 17:12:11,452 INFO L166 IcfgInterpreter]: Building call graph [2023-12-02 17:12:11,452 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-12-02 17:12:11,453 INFO L176 IcfgInterpreter]: Starting interpretation [2023-12-02 17:12:11,453 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-12-02 17:12:11,726 INFO L180 IcfgInterpreter]: Interpretation finished [2023-12-02 17:12:11,982 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '220#(and (<= 1 |#StackHeapBarrier|) (= |ULTIMATE.start_main_~marker~0#1| (select (select |#memory_int| |ULTIMATE.start_main_~#a~0#1.base|) (* |ULTIMATE.start_main_~i~1#1| 4))) (<= 0 (+ |ULTIMATE.start_main_~marker~0#1| 2147483648)) (= |ULTIMATE.start___VERIFIER_assert_~cond#1| 0) (<= 0 |ULTIMATE.start_main_~pos~0#1|) (<= 2 |ULTIMATE.start_main_~#a~0#1.base|) (= |ULTIMATE.start_main_~#a~0#1.offset| 0) (<= (+ |ULTIMATE.start_main_~pos~0#1| 1) |ULTIMATE.start_main_~i~1#1|) (<= |ULTIMATE.start_main_~marker~0#1| 2147483647) (= |ULTIMATE.start___VERIFIER_assert_#in~cond#1| 0) (<= |ULTIMATE.start_main_~pos~0#1| 99999))' at error location [2023-12-02 17:12:11,983 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-12-02 17:12:11,983 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-12-02 17:12:11,983 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [3, 3, 3] total 5 [2023-12-02 17:12:11,983 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [882739980] [2023-12-02 17:12:11,983 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-12-02 17:12:11,984 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2023-12-02 17:12:11,984 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 17:12:11,985 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2023-12-02 17:12:11,985 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=42, Invalid=114, Unknown=0, NotChecked=0, Total=156 [2023-12-02 17:12:11,985 INFO L87 Difference]: Start difference. First operand 12 states and 13 transitions. Second operand has 6 states, 6 states have (on average 2.1666666666666665) internal successors, (13), 5 states have internal predecessors, (13), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 17:12:12,004 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 17:12:12,004 INFO L93 Difference]: Finished difference Result 24 states and 28 transitions. [2023-12-02 17:12:12,005 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-12-02 17:12:12,005 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.1666666666666665) internal successors, (13), 5 states have internal predecessors, (13), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 11 [2023-12-02 17:12:12,005 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 17:12:12,006 INFO L225 Difference]: With dead ends: 24 [2023-12-02 17:12:12,006 INFO L226 Difference]: Without dead ends: 15 [2023-12-02 17:12:12,006 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 34 GetRequests, 23 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 33 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=42, Invalid=114, Unknown=0, NotChecked=0, Total=156 [2023-12-02 17:12:12,008 INFO L413 NwaCegarLoop]: 7 mSDtfsCounter, 0 mSDsluCounter, 21 mSDsCounter, 0 mSdLazyCounter, 10 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 28 SdHoareTripleChecker+Invalid, 11 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 10 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-12-02 17:12:12,008 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 28 Invalid, 11 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 10 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-12-02 17:12:12,009 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 15 states. [2023-12-02 17:12:12,013 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 15 to 15. [2023-12-02 17:12:12,014 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 15 states, 14 states have (on average 1.1428571428571428) internal successors, (16), 14 states have internal predecessors, (16), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 17:12:12,014 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 15 states to 15 states and 16 transitions. [2023-12-02 17:12:12,015 INFO L78 Accepts]: Start accepts. Automaton has 15 states and 16 transitions. Word has length 11 [2023-12-02 17:12:12,015 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 17:12:12,015 INFO L495 AbstractCegarLoop]: Abstraction has 15 states and 16 transitions. [2023-12-02 17:12:12,015 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.1666666666666665) internal successors, (13), 5 states have internal predecessors, (13), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 17:12:12,015 INFO L276 IsEmpty]: Start isEmpty. Operand 15 states and 16 transitions. [2023-12-02 17:12:12,016 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2023-12-02 17:12:12,016 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 17:12:12,016 INFO L195 NwaCegarLoop]: trace histogram [4, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 17:12:12,021 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4b135455-3be0-4a46-9000-73ecba14935e/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2023-12-02 17:12:12,221 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4b135455-3be0-4a46-9000-73ecba14935e/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 17:12:12,222 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 17:12:12,222 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 17:12:12,222 INFO L85 PathProgramCache]: Analyzing trace with hash 1725948013, now seen corresponding path program 2 times [2023-12-02 17:12:12,222 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 17:12:12,222 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1534995642] [2023-12-02 17:12:12,223 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 17:12:12,223 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 17:12:12,246 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 17:12:12,333 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2023-12-02 17:12:12,333 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 17:12:12,334 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1534995642] [2023-12-02 17:12:12,334 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1534995642] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-02 17:12:12,334 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [893714730] [2023-12-02 17:12:12,334 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-12-02 17:12:12,334 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 17:12:12,334 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4b135455-3be0-4a46-9000-73ecba14935e/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 17:12:12,335 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4b135455-3be0-4a46-9000-73ecba14935e/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 17:12:12,339 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4b135455-3be0-4a46-9000-73ecba14935e/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2023-12-02 17:12:12,397 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 2 check-sat command(s) [2023-12-02 17:12:12,397 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-02 17:12:12,398 INFO L262 TraceCheckSpWp]: Trace formula consists of 78 conjuncts, 14 conjunts are in the unsatisfiable core [2023-12-02 17:12:12,400 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 17:12:12,428 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2023-12-02 17:12:12,469 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-12-02 17:12:12,470 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 23 treesize of output 15 [2023-12-02 17:12:12,544 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2023-12-02 17:12:12,544 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 17:12:12,639 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2023-12-02 17:12:12,640 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [893714730] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-02 17:12:12,641 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [2026451451] [2023-12-02 17:12:12,644 INFO L159 IcfgInterpreter]: Started Sifa with 9 locations of interest [2023-12-02 17:12:12,644 INFO L166 IcfgInterpreter]: Building call graph [2023-12-02 17:12:12,644 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-12-02 17:12:12,645 INFO L176 IcfgInterpreter]: Starting interpretation [2023-12-02 17:12:12,645 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-12-02 17:12:12,950 INFO L180 IcfgInterpreter]: Interpretation finished [2023-12-02 17:12:13,256 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '375#(and (<= 1 |#StackHeapBarrier|) (= |ULTIMATE.start_main_~marker~0#1| (select (select |#memory_int| |ULTIMATE.start_main_~#a~0#1.base|) (* |ULTIMATE.start_main_~i~1#1| 4))) (<= 0 (+ |ULTIMATE.start_main_~marker~0#1| 2147483648)) (= |ULTIMATE.start___VERIFIER_assert_~cond#1| 0) (<= 0 |ULTIMATE.start_main_~pos~0#1|) (<= 2 |ULTIMATE.start_main_~#a~0#1.base|) (= |ULTIMATE.start_main_~#a~0#1.offset| 0) (<= (+ |ULTIMATE.start_main_~pos~0#1| 1) |ULTIMATE.start_main_~i~1#1|) (<= |ULTIMATE.start_main_~marker~0#1| 2147483647) (= |ULTIMATE.start___VERIFIER_assert_#in~cond#1| 0) (<= |ULTIMATE.start_main_~pos~0#1| 99999))' at error location [2023-12-02 17:12:13,257 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-12-02 17:12:13,257 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-12-02 17:12:13,257 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6, 6] total 15 [2023-12-02 17:12:13,257 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [342998700] [2023-12-02 17:12:13,257 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-12-02 17:12:13,258 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2023-12-02 17:12:13,258 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 17:12:13,259 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2023-12-02 17:12:13,259 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=75, Invalid=387, Unknown=0, NotChecked=0, Total=462 [2023-12-02 17:12:13,259 INFO L87 Difference]: Start difference. First operand 15 states and 16 transitions. Second operand has 15 states, 15 states have (on average 2.0) internal successors, (30), 15 states have internal predecessors, (30), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 17:12:13,442 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 17:12:13,442 INFO L93 Difference]: Finished difference Result 33 states and 37 transitions. [2023-12-02 17:12:13,443 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2023-12-02 17:12:13,443 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 15 states have (on average 2.0) internal successors, (30), 15 states have internal predecessors, (30), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 14 [2023-12-02 17:12:13,443 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 17:12:13,444 INFO L225 Difference]: With dead ends: 33 [2023-12-02 17:12:13,444 INFO L226 Difference]: Without dead ends: 20 [2023-12-02 17:12:13,445 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 51 GetRequests, 26 SyntacticMatches, 0 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 144 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=112, Invalid=590, Unknown=0, NotChecked=0, Total=702 [2023-12-02 17:12:13,446 INFO L413 NwaCegarLoop]: 3 mSDtfsCounter, 6 mSDsluCounter, 19 mSDsCounter, 0 mSdLazyCounter, 67 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 22 SdHoareTripleChecker+Invalid, 69 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 67 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-12-02 17:12:13,446 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 22 Invalid, 69 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 67 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-12-02 17:12:13,447 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 20 states. [2023-12-02 17:12:13,452 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 20 to 20. [2023-12-02 17:12:13,453 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 20 states, 19 states have (on average 1.105263157894737) internal successors, (21), 19 states have internal predecessors, (21), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 17:12:13,453 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 20 states to 20 states and 21 transitions. [2023-12-02 17:12:13,453 INFO L78 Accepts]: Start accepts. Automaton has 20 states and 21 transitions. Word has length 14 [2023-12-02 17:12:13,453 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 17:12:13,454 INFO L495 AbstractCegarLoop]: Abstraction has 20 states and 21 transitions. [2023-12-02 17:12:13,454 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 2.0) internal successors, (30), 15 states have internal predecessors, (30), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 17:12:13,454 INFO L276 IsEmpty]: Start isEmpty. Operand 20 states and 21 transitions. [2023-12-02 17:12:13,455 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2023-12-02 17:12:13,455 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 17:12:13,455 INFO L195 NwaCegarLoop]: trace histogram [5, 4, 3, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 17:12:13,460 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4b135455-3be0-4a46-9000-73ecba14935e/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2023-12-02 17:12:13,660 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4b135455-3be0-4a46-9000-73ecba14935e/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 17:12:13,660 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 17:12:13,660 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 17:12:13,660 INFO L85 PathProgramCache]: Analyzing trace with hash -1968780429, now seen corresponding path program 3 times [2023-12-02 17:12:13,661 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 17:12:13,661 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1483774044] [2023-12-02 17:12:13,661 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 17:12:13,661 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 17:12:13,680 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 17:12:13,778 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2023-12-02 17:12:13,779 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 17:12:13,779 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1483774044] [2023-12-02 17:12:13,779 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1483774044] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-02 17:12:13,779 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [607667369] [2023-12-02 17:12:13,779 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2023-12-02 17:12:13,779 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 17:12:13,779 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4b135455-3be0-4a46-9000-73ecba14935e/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 17:12:13,780 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4b135455-3be0-4a46-9000-73ecba14935e/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 17:12:13,791 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4b135455-3be0-4a46-9000-73ecba14935e/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2023-12-02 17:12:13,849 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2023-12-02 17:12:13,849 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-02 17:12:13,850 INFO L262 TraceCheckSpWp]: Trace formula consists of 115 conjuncts, 7 conjunts are in the unsatisfiable core [2023-12-02 17:12:13,851 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 17:12:13,863 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2023-12-02 17:12:13,863 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 17:12:13,934 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2023-12-02 17:12:13,934 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [607667369] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-02 17:12:13,935 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1948637177] [2023-12-02 17:12:13,937 INFO L159 IcfgInterpreter]: Started Sifa with 9 locations of interest [2023-12-02 17:12:13,937 INFO L166 IcfgInterpreter]: Building call graph [2023-12-02 17:12:13,937 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-12-02 17:12:13,938 INFO L176 IcfgInterpreter]: Starting interpretation [2023-12-02 17:12:13,938 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-12-02 17:12:14,106 INFO L180 IcfgInterpreter]: Interpretation finished [2023-12-02 17:12:14,346 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '589#(and (<= 1 |#StackHeapBarrier|) (= |ULTIMATE.start_main_~marker~0#1| (select (select |#memory_int| |ULTIMATE.start_main_~#a~0#1.base|) (* |ULTIMATE.start_main_~i~1#1| 4))) (<= 0 (+ |ULTIMATE.start_main_~marker~0#1| 2147483648)) (= |ULTIMATE.start___VERIFIER_assert_~cond#1| 0) (<= 0 |ULTIMATE.start_main_~pos~0#1|) (<= 2 |ULTIMATE.start_main_~#a~0#1.base|) (= |ULTIMATE.start_main_~#a~0#1.offset| 0) (<= (+ |ULTIMATE.start_main_~pos~0#1| 1) |ULTIMATE.start_main_~i~1#1|) (<= |ULTIMATE.start_main_~marker~0#1| 2147483647) (= |ULTIMATE.start___VERIFIER_assert_#in~cond#1| 0) (<= |ULTIMATE.start_main_~pos~0#1| 99999))' at error location [2023-12-02 17:12:14,346 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-12-02 17:12:14,346 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-12-02 17:12:14,346 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 13 [2023-12-02 17:12:14,346 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1966075985] [2023-12-02 17:12:14,346 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-12-02 17:12:14,347 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2023-12-02 17:12:14,347 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 17:12:14,348 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2023-12-02 17:12:14,348 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=118, Invalid=302, Unknown=0, NotChecked=0, Total=420 [2023-12-02 17:12:14,348 INFO L87 Difference]: Start difference. First operand 20 states and 21 transitions. Second operand has 14 states, 14 states have (on average 1.5) internal successors, (21), 13 states have internal predecessors, (21), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 17:12:14,376 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 17:12:14,376 INFO L93 Difference]: Finished difference Result 40 states and 48 transitions. [2023-12-02 17:12:14,377 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2023-12-02 17:12:14,377 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 1.5) internal successors, (21), 13 states have internal predecessors, (21), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 19 [2023-12-02 17:12:14,377 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 17:12:14,378 INFO L225 Difference]: With dead ends: 40 [2023-12-02 17:12:14,378 INFO L226 Difference]: Without dead ends: 27 [2023-12-02 17:12:14,378 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 62 GetRequests, 43 SyntacticMatches, 0 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 117 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=118, Invalid=302, Unknown=0, NotChecked=0, Total=420 [2023-12-02 17:12:14,379 INFO L413 NwaCegarLoop]: 7 mSDtfsCounter, 0 mSDsluCounter, 14 mSDsCounter, 0 mSdLazyCounter, 17 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 21 SdHoareTripleChecker+Invalid, 18 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 17 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-12-02 17:12:14,379 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 21 Invalid, 18 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 17 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-12-02 17:12:14,380 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 27 states. [2023-12-02 17:12:14,386 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 27 to 27. [2023-12-02 17:12:14,387 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 27 states, 26 states have (on average 1.0769230769230769) internal successors, (28), 26 states have internal predecessors, (28), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 17:12:14,387 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 27 states to 27 states and 28 transitions. [2023-12-02 17:12:14,388 INFO L78 Accepts]: Start accepts. Automaton has 27 states and 28 transitions. Word has length 19 [2023-12-02 17:12:14,388 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 17:12:14,388 INFO L495 AbstractCegarLoop]: Abstraction has 27 states and 28 transitions. [2023-12-02 17:12:14,388 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 1.5) internal successors, (21), 13 states have internal predecessors, (21), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 17:12:14,388 INFO L276 IsEmpty]: Start isEmpty. Operand 27 states and 28 transitions. [2023-12-02 17:12:14,389 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2023-12-02 17:12:14,389 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 17:12:14,389 INFO L195 NwaCegarLoop]: trace histogram [12, 4, 3, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 17:12:14,394 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4b135455-3be0-4a46-9000-73ecba14935e/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2023-12-02 17:12:14,594 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4b135455-3be0-4a46-9000-73ecba14935e/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 17:12:14,595 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 17:12:14,595 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 17:12:14,595 INFO L85 PathProgramCache]: Analyzing trace with hash 1835450211, now seen corresponding path program 4 times [2023-12-02 17:12:14,595 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 17:12:14,595 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1861149510] [2023-12-02 17:12:14,595 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 17:12:14,595 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 17:12:14,619 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 17:12:14,834 INFO L134 CoverageAnalysis]: Checked inductivity of 90 backedges. 0 proven. 78 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2023-12-02 17:12:14,834 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 17:12:14,834 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1861149510] [2023-12-02 17:12:14,834 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1861149510] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-02 17:12:14,834 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1173377281] [2023-12-02 17:12:14,835 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2023-12-02 17:12:14,835 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 17:12:14,835 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4b135455-3be0-4a46-9000-73ecba14935e/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 17:12:14,836 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4b135455-3be0-4a46-9000-73ecba14935e/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 17:12:14,839 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4b135455-3be0-4a46-9000-73ecba14935e/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2023-12-02 17:12:14,915 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 17:12:14,917 INFO L262 TraceCheckSpWp]: Trace formula consists of 178 conjuncts, 14 conjunts are in the unsatisfiable core [2023-12-02 17:12:14,919 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 17:12:14,945 INFO L134 CoverageAnalysis]: Checked inductivity of 90 backedges. 0 proven. 78 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2023-12-02 17:12:14,945 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 17:12:15,225 INFO L134 CoverageAnalysis]: Checked inductivity of 90 backedges. 0 proven. 78 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2023-12-02 17:12:15,225 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1173377281] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-02 17:12:15,225 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1524409458] [2023-12-02 17:12:15,227 INFO L159 IcfgInterpreter]: Started Sifa with 9 locations of interest [2023-12-02 17:12:15,227 INFO L166 IcfgInterpreter]: Building call graph [2023-12-02 17:12:15,228 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-12-02 17:12:15,228 INFO L176 IcfgInterpreter]: Starting interpretation [2023-12-02 17:12:15,228 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-12-02 17:12:15,354 INFO L180 IcfgInterpreter]: Interpretation finished [2023-12-02 17:12:15,624 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '879#(and (<= 1 |#StackHeapBarrier|) (= |ULTIMATE.start_main_~marker~0#1| (select (select |#memory_int| |ULTIMATE.start_main_~#a~0#1.base|) (* |ULTIMATE.start_main_~i~1#1| 4))) (<= 0 (+ |ULTIMATE.start_main_~marker~0#1| 2147483648)) (= |ULTIMATE.start___VERIFIER_assert_~cond#1| 0) (<= 0 |ULTIMATE.start_main_~pos~0#1|) (<= 2 |ULTIMATE.start_main_~#a~0#1.base|) (= |ULTIMATE.start_main_~#a~0#1.offset| 0) (<= (+ |ULTIMATE.start_main_~pos~0#1| 1) |ULTIMATE.start_main_~i~1#1|) (<= |ULTIMATE.start_main_~marker~0#1| 2147483647) (= |ULTIMATE.start___VERIFIER_assert_#in~cond#1| 0) (<= |ULTIMATE.start_main_~pos~0#1| 99999))' at error location [2023-12-02 17:12:15,624 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-12-02 17:12:15,624 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-12-02 17:12:15,625 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 14, 14] total 27 [2023-12-02 17:12:15,625 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1793365365] [2023-12-02 17:12:15,625 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-12-02 17:12:15,625 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 28 states [2023-12-02 17:12:15,626 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 17:12:15,626 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 28 interpolants. [2023-12-02 17:12:15,627 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=405, Invalid=785, Unknown=0, NotChecked=0, Total=1190 [2023-12-02 17:12:15,627 INFO L87 Difference]: Start difference. First operand 27 states and 28 transitions. Second operand has 28 states, 28 states have (on average 1.25) internal successors, (35), 27 states have internal predecessors, (35), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 17:12:15,672 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 17:12:15,672 INFO L93 Difference]: Finished difference Result 54 states and 69 transitions. [2023-12-02 17:12:15,672 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 28 states. [2023-12-02 17:12:15,673 INFO L78 Accepts]: Start accepts. Automaton has has 28 states, 28 states have (on average 1.25) internal successors, (35), 27 states have internal predecessors, (35), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 26 [2023-12-02 17:12:15,673 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 17:12:15,674 INFO L225 Difference]: With dead ends: 54 [2023-12-02 17:12:15,674 INFO L226 Difference]: Without dead ends: 41 [2023-12-02 17:12:15,675 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 90 GetRequests, 57 SyntacticMatches, 0 SemanticMatches, 33 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 264 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=405, Invalid=785, Unknown=0, NotChecked=0, Total=1190 [2023-12-02 17:12:15,676 INFO L413 NwaCegarLoop]: 7 mSDtfsCounter, 0 mSDsluCounter, 28 mSDsCounter, 0 mSdLazyCounter, 33 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 35 SdHoareTripleChecker+Invalid, 34 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 33 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-12-02 17:12:15,676 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 35 Invalid, 34 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 33 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-12-02 17:12:15,677 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 41 states. [2023-12-02 17:12:15,686 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 41 to 41. [2023-12-02 17:12:15,687 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 41 states, 40 states have (on average 1.05) internal successors, (42), 40 states have internal predecessors, (42), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 17:12:15,688 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 41 states to 41 states and 42 transitions. [2023-12-02 17:12:15,688 INFO L78 Accepts]: Start accepts. Automaton has 41 states and 42 transitions. Word has length 26 [2023-12-02 17:12:15,692 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 17:12:15,692 INFO L495 AbstractCegarLoop]: Abstraction has 41 states and 42 transitions. [2023-12-02 17:12:15,693 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 28 states, 28 states have (on average 1.25) internal successors, (35), 27 states have internal predecessors, (35), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 17:12:15,693 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 42 transitions. [2023-12-02 17:12:15,694 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2023-12-02 17:12:15,694 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 17:12:15,694 INFO L195 NwaCegarLoop]: trace histogram [26, 4, 3, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 17:12:15,700 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4b135455-3be0-4a46-9000-73ecba14935e/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2023-12-02 17:12:15,899 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4b135455-3be0-4a46-9000-73ecba14935e/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable5 [2023-12-02 17:12:15,900 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 17:12:15,900 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 17:12:15,901 INFO L85 PathProgramCache]: Analyzing trace with hash 310889827, now seen corresponding path program 5 times [2023-12-02 17:12:15,901 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 17:12:15,901 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1026426515] [2023-12-02 17:12:15,901 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 17:12:15,901 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 17:12:15,946 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 17:12:16,554 INFO L134 CoverageAnalysis]: Checked inductivity of 363 backedges. 0 proven. 351 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2023-12-02 17:12:16,554 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 17:12:16,554 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1026426515] [2023-12-02 17:12:16,554 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1026426515] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-02 17:12:16,554 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [248382936] [2023-12-02 17:12:16,554 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-12-02 17:12:16,555 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 17:12:16,555 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4b135455-3be0-4a46-9000-73ecba14935e/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 17:12:16,556 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4b135455-3be0-4a46-9000-73ecba14935e/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 17:12:16,559 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4b135455-3be0-4a46-9000-73ecba14935e/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2023-12-02 17:12:16,664 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2023-12-02 17:12:16,664 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-02 17:12:16,666 INFO L262 TraceCheckSpWp]: Trace formula consists of 124 conjuncts, 25 conjunts are in the unsatisfiable core [2023-12-02 17:12:16,672 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 17:12:16,679 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2023-12-02 17:12:16,890 INFO L349 Elim1Store]: treesize reduction 8, result has 81.4 percent of original size [2023-12-02 17:12:16,890 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 0 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 44 treesize of output 49 [2023-12-02 17:12:17,101 INFO L134 CoverageAnalysis]: Checked inductivity of 363 backedges. 0 proven. 12 refuted. 0 times theorem prover too weak. 351 trivial. 0 not checked. [2023-12-02 17:12:17,101 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 17:12:17,538 INFO L134 CoverageAnalysis]: Checked inductivity of 363 backedges. 0 proven. 12 refuted. 0 times theorem prover too weak. 351 trivial. 0 not checked. [2023-12-02 17:12:17,538 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [248382936] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-02 17:12:17,538 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [107354616] [2023-12-02 17:12:17,540 INFO L159 IcfgInterpreter]: Started Sifa with 9 locations of interest [2023-12-02 17:12:17,540 INFO L166 IcfgInterpreter]: Building call graph [2023-12-02 17:12:17,540 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-12-02 17:12:17,540 INFO L176 IcfgInterpreter]: Starting interpretation [2023-12-02 17:12:17,540 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-12-02 17:12:17,712 INFO L180 IcfgInterpreter]: Interpretation finished [2023-12-02 17:12:18,160 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1326#(and (<= 1 |#StackHeapBarrier|) (= |ULTIMATE.start_main_~marker~0#1| (select (select |#memory_int| |ULTIMATE.start_main_~#a~0#1.base|) (* |ULTIMATE.start_main_~i~1#1| 4))) (<= 0 (+ |ULTIMATE.start_main_~marker~0#1| 2147483648)) (= |ULTIMATE.start___VERIFIER_assert_~cond#1| 0) (<= 0 |ULTIMATE.start_main_~pos~0#1|) (<= 2 |ULTIMATE.start_main_~#a~0#1.base|) (= |ULTIMATE.start_main_~#a~0#1.offset| 0) (<= (+ |ULTIMATE.start_main_~pos~0#1| 1) |ULTIMATE.start_main_~i~1#1|) (<= |ULTIMATE.start_main_~marker~0#1| 2147483647) (= |ULTIMATE.start___VERIFIER_assert_#in~cond#1| 0) (<= |ULTIMATE.start_main_~pos~0#1| 99999))' at error location [2023-12-02 17:12:18,160 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-12-02 17:12:18,160 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-12-02 17:12:18,160 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [28, 10, 10] total 45 [2023-12-02 17:12:18,161 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1273683227] [2023-12-02 17:12:18,161 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-12-02 17:12:18,161 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 45 states [2023-12-02 17:12:18,162 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 17:12:18,163 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 45 interpolants. [2023-12-02 17:12:18,164 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=512, Invalid=2140, Unknown=0, NotChecked=0, Total=2652 [2023-12-02 17:12:18,165 INFO L87 Difference]: Start difference. First operand 41 states and 42 transitions. Second operand has 45 states, 45 states have (on average 1.3333333333333333) internal successors, (60), 45 states have internal predecessors, (60), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 17:12:19,047 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 17:12:19,047 INFO L93 Difference]: Finished difference Result 71 states and 77 transitions. [2023-12-02 17:12:19,047 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 46 states. [2023-12-02 17:12:19,048 INFO L78 Accepts]: Start accepts. Automaton has has 45 states, 45 states have (on average 1.3333333333333333) internal successors, (60), 45 states have internal predecessors, (60), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 40 [2023-12-02 17:12:19,048 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 17:12:19,049 INFO L225 Difference]: With dead ends: 71 [2023-12-02 17:12:19,049 INFO L226 Difference]: Without dead ends: 50 [2023-12-02 17:12:19,051 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 159 GetRequests, 96 SyntacticMatches, 0 SemanticMatches, 63 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 940 ImplicationChecksByTransitivity, 2.1s TimeCoverageRelationStatistics Valid=671, Invalid=3489, Unknown=0, NotChecked=0, Total=4160 [2023-12-02 17:12:19,052 INFO L413 NwaCegarLoop]: 3 mSDtfsCounter, 24 mSDsluCounter, 38 mSDsCounter, 0 mSdLazyCounter, 178 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 24 SdHoareTripleChecker+Valid, 41 SdHoareTripleChecker+Invalid, 183 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 178 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-12-02 17:12:19,052 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [24 Valid, 41 Invalid, 183 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 178 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-12-02 17:12:19,053 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 50 states. [2023-12-02 17:12:19,064 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 50 to 50. [2023-12-02 17:12:19,064 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 50 states, 49 states have (on average 1.0408163265306123) internal successors, (51), 49 states have internal predecessors, (51), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 17:12:19,065 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 50 states to 50 states and 51 transitions. [2023-12-02 17:12:19,065 INFO L78 Accepts]: Start accepts. Automaton has 50 states and 51 transitions. Word has length 40 [2023-12-02 17:12:19,066 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 17:12:19,066 INFO L495 AbstractCegarLoop]: Abstraction has 50 states and 51 transitions. [2023-12-02 17:12:19,066 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 45 states, 45 states have (on average 1.3333333333333333) internal successors, (60), 45 states have internal predecessors, (60), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 17:12:19,066 INFO L276 IsEmpty]: Start isEmpty. Operand 50 states and 51 transitions. [2023-12-02 17:12:19,067 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 50 [2023-12-02 17:12:19,067 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 17:12:19,068 INFO L195 NwaCegarLoop]: trace histogram [27, 8, 7, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 17:12:19,072 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4b135455-3be0-4a46-9000-73ecba14935e/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2023-12-02 17:12:19,270 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,7 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4b135455-3be0-4a46-9000-73ecba14935e/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 17:12:19,271 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 17:12:19,271 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 17:12:19,271 INFO L85 PathProgramCache]: Analyzing trace with hash 51794527, now seen corresponding path program 6 times [2023-12-02 17:12:19,271 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 17:12:19,272 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [122047390] [2023-12-02 17:12:19,272 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 17:12:19,272 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 17:12:19,316 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 17:12:20,114 INFO L134 CoverageAnalysis]: Checked inductivity of 434 backedges. 0 proven. 378 refuted. 0 times theorem prover too weak. 56 trivial. 0 not checked. [2023-12-02 17:12:20,114 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 17:12:20,114 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [122047390] [2023-12-02 17:12:20,114 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [122047390] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-02 17:12:20,114 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [219892510] [2023-12-02 17:12:20,114 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2023-12-02 17:12:20,114 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 17:12:20,114 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4b135455-3be0-4a46-9000-73ecba14935e/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 17:12:20,115 INFO L229 MonitoredProcess]: Starting monitored process 8 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4b135455-3be0-4a46-9000-73ecba14935e/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 17:12:20,116 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4b135455-3be0-4a46-9000-73ecba14935e/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2023-12-02 17:12:20,217 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2023-12-02 17:12:20,217 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-02 17:12:20,219 INFO L262 TraceCheckSpWp]: Trace formula consists of 333 conjuncts, 29 conjunts are in the unsatisfiable core [2023-12-02 17:12:20,221 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 17:12:20,264 INFO L134 CoverageAnalysis]: Checked inductivity of 434 backedges. 0 proven. 378 refuted. 0 times theorem prover too weak. 56 trivial. 0 not checked. [2023-12-02 17:12:20,265 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 17:12:21,194 INFO L134 CoverageAnalysis]: Checked inductivity of 434 backedges. 0 proven. 378 refuted. 0 times theorem prover too weak. 56 trivial. 0 not checked. [2023-12-02 17:12:21,194 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [219892510] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-02 17:12:21,194 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1582331682] [2023-12-02 17:12:21,196 INFO L159 IcfgInterpreter]: Started Sifa with 9 locations of interest [2023-12-02 17:12:21,197 INFO L166 IcfgInterpreter]: Building call graph [2023-12-02 17:12:21,197 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-12-02 17:12:21,197 INFO L176 IcfgInterpreter]: Starting interpretation [2023-12-02 17:12:21,197 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-12-02 17:12:21,345 INFO L180 IcfgInterpreter]: Interpretation finished [2023-12-02 17:12:21,675 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1902#(and (<= 1 |#StackHeapBarrier|) (= |ULTIMATE.start_main_~marker~0#1| (select (select |#memory_int| |ULTIMATE.start_main_~#a~0#1.base|) (* |ULTIMATE.start_main_~i~1#1| 4))) (<= 0 (+ |ULTIMATE.start_main_~marker~0#1| 2147483648)) (= |ULTIMATE.start___VERIFIER_assert_~cond#1| 0) (<= 0 |ULTIMATE.start_main_~pos~0#1|) (<= 2 |ULTIMATE.start_main_~#a~0#1.base|) (= |ULTIMATE.start_main_~#a~0#1.offset| 0) (<= (+ |ULTIMATE.start_main_~pos~0#1| 1) |ULTIMATE.start_main_~i~1#1|) (<= |ULTIMATE.start_main_~marker~0#1| 2147483647) (= |ULTIMATE.start___VERIFIER_assert_#in~cond#1| 0) (<= |ULTIMATE.start_main_~pos~0#1| 99999))' at error location [2023-12-02 17:12:21,675 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-12-02 17:12:21,675 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-12-02 17:12:21,675 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [29, 29, 29] total 57 [2023-12-02 17:12:21,675 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [523053938] [2023-12-02 17:12:21,675 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-12-02 17:12:21,676 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 58 states [2023-12-02 17:12:21,676 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 17:12:21,677 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 58 interpolants. [2023-12-02 17:12:21,679 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1680, Invalid=2480, Unknown=0, NotChecked=0, Total=4160 [2023-12-02 17:12:21,679 INFO L87 Difference]: Start difference. First operand 50 states and 51 transitions. Second operand has 58 states, 58 states have (on average 1.1206896551724137) internal successors, (65), 57 states have internal predecessors, (65), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 17:12:21,767 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 17:12:21,767 INFO L93 Difference]: Finished difference Result 100 states and 130 transitions. [2023-12-02 17:12:21,767 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 58 states. [2023-12-02 17:12:21,767 INFO L78 Accepts]: Start accepts. Automaton has has 58 states, 58 states have (on average 1.1206896551724137) internal successors, (65), 57 states have internal predecessors, (65), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 49 [2023-12-02 17:12:21,768 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 17:12:21,769 INFO L225 Difference]: With dead ends: 100 [2023-12-02 17:12:21,769 INFO L226 Difference]: Without dead ends: 79 [2023-12-02 17:12:21,770 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 174 GetRequests, 111 SyntacticMatches, 0 SemanticMatches, 63 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 579 ImplicationChecksByTransitivity, 1.5s TimeCoverageRelationStatistics Valid=1680, Invalid=2480, Unknown=0, NotChecked=0, Total=4160 [2023-12-02 17:12:21,771 INFO L413 NwaCegarLoop]: 7 mSDtfsCounter, 0 mSDsluCounter, 28 mSDsCounter, 0 mSdLazyCounter, 63 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 35 SdHoareTripleChecker+Invalid, 64 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 63 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-12-02 17:12:21,772 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 35 Invalid, 64 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 63 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-12-02 17:12:21,772 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 79 states. [2023-12-02 17:12:21,791 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 79 to 79. [2023-12-02 17:12:21,791 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 79 states, 78 states have (on average 1.0256410256410255) internal successors, (80), 78 states have internal predecessors, (80), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 17:12:21,792 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 79 states to 79 states and 80 transitions. [2023-12-02 17:12:21,792 INFO L78 Accepts]: Start accepts. Automaton has 79 states and 80 transitions. Word has length 49 [2023-12-02 17:12:21,792 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 17:12:21,793 INFO L495 AbstractCegarLoop]: Abstraction has 79 states and 80 transitions. [2023-12-02 17:12:21,793 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 58 states, 58 states have (on average 1.1206896551724137) internal successors, (65), 57 states have internal predecessors, (65), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 17:12:21,793 INFO L276 IsEmpty]: Start isEmpty. Operand 79 states and 80 transitions. [2023-12-02 17:12:21,794 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 79 [2023-12-02 17:12:21,794 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 17:12:21,794 INFO L195 NwaCegarLoop]: trace histogram [56, 8, 7, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 17:12:21,800 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4b135455-3be0-4a46-9000-73ecba14935e/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2023-12-02 17:12:21,995 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 8 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4b135455-3be0-4a46-9000-73ecba14935e/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable7 [2023-12-02 17:12:21,996 INFO L420 AbstractCegarLoop]: === Iteration 9 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 17:12:21,996 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 17:12:21,996 INFO L85 PathProgramCache]: Analyzing trace with hash 1925077071, now seen corresponding path program 7 times [2023-12-02 17:12:21,996 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 17:12:21,996 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [418627763] [2023-12-02 17:12:21,996 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 17:12:21,996 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 17:12:22,061 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 17:12:24,040 INFO L134 CoverageAnalysis]: Checked inductivity of 1652 backedges. 0 proven. 1596 refuted. 0 times theorem prover too weak. 56 trivial. 0 not checked. [2023-12-02 17:12:24,040 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 17:12:24,041 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [418627763] [2023-12-02 17:12:24,041 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [418627763] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-02 17:12:24,041 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [577838121] [2023-12-02 17:12:24,041 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2023-12-02 17:12:24,041 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 17:12:24,041 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4b135455-3be0-4a46-9000-73ecba14935e/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 17:12:24,042 INFO L229 MonitoredProcess]: Starting monitored process 9 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4b135455-3be0-4a46-9000-73ecba14935e/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 17:12:24,043 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4b135455-3be0-4a46-9000-73ecba14935e/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2023-12-02 17:12:24,229 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 17:12:24,233 INFO L262 TraceCheckSpWp]: Trace formula consists of 594 conjuncts, 58 conjunts are in the unsatisfiable core [2023-12-02 17:12:24,237 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 17:12:24,328 INFO L134 CoverageAnalysis]: Checked inductivity of 1652 backedges. 0 proven. 1596 refuted. 0 times theorem prover too weak. 56 trivial. 0 not checked. [2023-12-02 17:12:24,328 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 17:12:27,397 INFO L134 CoverageAnalysis]: Checked inductivity of 1652 backedges. 0 proven. 1596 refuted. 0 times theorem prover too weak. 56 trivial. 0 not checked. [2023-12-02 17:12:27,397 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [577838121] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-02 17:12:27,397 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [412262464] [2023-12-02 17:12:27,399 INFO L159 IcfgInterpreter]: Started Sifa with 9 locations of interest [2023-12-02 17:12:27,399 INFO L166 IcfgInterpreter]: Building call graph [2023-12-02 17:12:27,400 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-12-02 17:12:27,400 INFO L176 IcfgInterpreter]: Starting interpretation [2023-12-02 17:12:27,400 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-12-02 17:12:27,534 INFO L180 IcfgInterpreter]: Interpretation finished [2023-12-02 17:12:27,916 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '2804#(and (<= 1 |#StackHeapBarrier|) (= |ULTIMATE.start_main_~marker~0#1| (select (select |#memory_int| |ULTIMATE.start_main_~#a~0#1.base|) (* |ULTIMATE.start_main_~i~1#1| 4))) (<= 0 (+ |ULTIMATE.start_main_~marker~0#1| 2147483648)) (= |ULTIMATE.start___VERIFIER_assert_~cond#1| 0) (<= 0 |ULTIMATE.start_main_~pos~0#1|) (<= 2 |ULTIMATE.start_main_~#a~0#1.base|) (= |ULTIMATE.start_main_~#a~0#1.offset| 0) (<= (+ |ULTIMATE.start_main_~pos~0#1| 1) |ULTIMATE.start_main_~i~1#1|) (<= |ULTIMATE.start_main_~marker~0#1| 2147483647) (= |ULTIMATE.start___VERIFIER_assert_#in~cond#1| 0) (<= |ULTIMATE.start_main_~pos~0#1| 99999))' at error location [2023-12-02 17:12:27,916 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-12-02 17:12:27,916 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-12-02 17:12:27,916 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [58, 58, 58] total 115 [2023-12-02 17:12:27,916 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1894893030] [2023-12-02 17:12:27,917 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-12-02 17:12:27,917 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 116 states [2023-12-02 17:12:27,917 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 17:12:27,920 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 116 interpolants. [2023-12-02 17:12:27,926 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=6697, Invalid=8309, Unknown=0, NotChecked=0, Total=15006 [2023-12-02 17:12:27,926 INFO L87 Difference]: Start difference. First operand 79 states and 80 transitions. Second operand has 116 states, 116 states have (on average 1.0603448275862069) internal successors, (123), 115 states have internal predecessors, (123), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 17:12:28,112 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 17:12:28,112 INFO L93 Difference]: Finished difference Result 158 states and 217 transitions. [2023-12-02 17:12:28,112 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 116 states. [2023-12-02 17:12:28,113 INFO L78 Accepts]: Start accepts. Automaton has has 116 states, 116 states have (on average 1.0603448275862069) internal successors, (123), 115 states have internal predecessors, (123), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 78 [2023-12-02 17:12:28,113 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 17:12:28,114 INFO L225 Difference]: With dead ends: 158 [2023-12-02 17:12:28,114 INFO L226 Difference]: Without dead ends: 137 [2023-12-02 17:12:28,118 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 290 GetRequests, 169 SyntacticMatches, 0 SemanticMatches, 121 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1188 ImplicationChecksByTransitivity, 4.6s TimeCoverageRelationStatistics Valid=6697, Invalid=8309, Unknown=0, NotChecked=0, Total=15006 [2023-12-02 17:12:28,119 INFO L413 NwaCegarLoop]: 7 mSDtfsCounter, 0 mSDsluCounter, 49 mSDsCounter, 0 mSdLazyCounter, 124 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 56 SdHoareTripleChecker+Invalid, 125 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 124 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-12-02 17:12:28,119 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 56 Invalid, 125 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 124 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-12-02 17:12:28,120 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 137 states. [2023-12-02 17:12:28,143 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 137 to 137. [2023-12-02 17:12:28,143 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 137 states, 136 states have (on average 1.0147058823529411) internal successors, (138), 136 states have internal predecessors, (138), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 17:12:28,144 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 137 states to 137 states and 138 transitions. [2023-12-02 17:12:28,144 INFO L78 Accepts]: Start accepts. Automaton has 137 states and 138 transitions. Word has length 78 [2023-12-02 17:12:28,144 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 17:12:28,145 INFO L495 AbstractCegarLoop]: Abstraction has 137 states and 138 transitions. [2023-12-02 17:12:28,145 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 116 states, 116 states have (on average 1.0603448275862069) internal successors, (123), 115 states have internal predecessors, (123), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 17:12:28,145 INFO L276 IsEmpty]: Start isEmpty. Operand 137 states and 138 transitions. [2023-12-02 17:12:28,147 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 137 [2023-12-02 17:12:28,147 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 17:12:28,147 INFO L195 NwaCegarLoop]: trace histogram [114, 8, 7, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 17:12:28,152 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4b135455-3be0-4a46-9000-73ecba14935e/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2023-12-02 17:12:28,347 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4b135455-3be0-4a46-9000-73ecba14935e/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable8 [2023-12-02 17:12:28,348 INFO L420 AbstractCegarLoop]: === Iteration 10 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 17:12:28,348 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 17:12:28,348 INFO L85 PathProgramCache]: Analyzing trace with hash 1248399951, now seen corresponding path program 8 times [2023-12-02 17:12:28,348 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 17:12:28,348 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1559467251] [2023-12-02 17:12:28,349 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 17:12:28,349 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 17:12:28,485 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 17:12:35,300 INFO L134 CoverageAnalysis]: Checked inductivity of 6611 backedges. 0 proven. 6555 refuted. 0 times theorem prover too weak. 56 trivial. 0 not checked. [2023-12-02 17:12:35,300 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 17:12:35,300 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1559467251] [2023-12-02 17:12:35,300 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1559467251] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-02 17:12:35,301 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1200568564] [2023-12-02 17:12:35,301 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-12-02 17:12:35,301 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 17:12:35,301 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4b135455-3be0-4a46-9000-73ecba14935e/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 17:12:35,302 INFO L229 MonitoredProcess]: Starting monitored process 10 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4b135455-3be0-4a46-9000-73ecba14935e/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 17:12:35,302 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4b135455-3be0-4a46-9000-73ecba14935e/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2023-12-02 17:12:35,786 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 8 check-sat command(s) [2023-12-02 17:12:35,787 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-02 17:12:35,790 INFO L262 TraceCheckSpWp]: Trace formula consists of 216 conjuncts, 52 conjunts are in the unsatisfiable core [2023-12-02 17:12:35,794 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 17:12:35,944 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 13 treesize of output 9 [2023-12-02 17:12:37,384 INFO L349 Elim1Store]: treesize reduction 24, result has 77.1 percent of original size [2023-12-02 17:12:37,384 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 8 select indices, 8 select index equivalence classes, 15 disjoint index pairs (out of 28 index pairs), introduced 8 new quantified variables, introduced 28 case distinctions, treesize of input 67 treesize of output 111 [2023-12-02 17:12:37,813 INFO L134 CoverageAnalysis]: Checked inductivity of 6611 backedges. 0 proven. 283 refuted. 0 times theorem prover too weak. 6328 trivial. 0 not checked. [2023-12-02 17:12:37,813 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 17:12:40,117 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 113 treesize of output 99 [2023-12-02 17:12:40,129 INFO L349 Elim1Store]: treesize reduction 48, result has 2.0 percent of original size [2023-12-02 17:12:40,129 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 7 select indices, 7 select index equivalence classes, 0 disjoint index pairs (out of 21 index pairs), introduced 7 new quantified variables, introduced 21 case distinctions, treesize of input 106 treesize of output 1 [2023-12-02 17:12:40,135 INFO L134 CoverageAnalysis]: Checked inductivity of 6611 backedges. 0 proven. 56 refuted. 0 times theorem prover too weak. 6555 trivial. 0 not checked. [2023-12-02 17:12:40,136 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1200568564] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-02 17:12:40,136 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [146233298] [2023-12-02 17:12:40,138 INFO L159 IcfgInterpreter]: Started Sifa with 9 locations of interest [2023-12-02 17:12:40,138 INFO L166 IcfgInterpreter]: Building call graph [2023-12-02 17:12:40,138 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-12-02 17:12:40,138 INFO L176 IcfgInterpreter]: Starting interpretation [2023-12-02 17:12:40,138 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-12-02 17:12:40,248 INFO L180 IcfgInterpreter]: Interpretation finished [2023-12-02 17:12:41,066 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '4322#(and (<= 1 |#StackHeapBarrier|) (= |ULTIMATE.start_main_~marker~0#1| (select (select |#memory_int| |ULTIMATE.start_main_~#a~0#1.base|) (* |ULTIMATE.start_main_~i~1#1| 4))) (<= 0 (+ |ULTIMATE.start_main_~marker~0#1| 2147483648)) (= |ULTIMATE.start___VERIFIER_assert_~cond#1| 0) (<= 0 |ULTIMATE.start_main_~pos~0#1|) (<= 2 |ULTIMATE.start_main_~#a~0#1.base|) (= |ULTIMATE.start_main_~#a~0#1.offset| 0) (<= (+ |ULTIMATE.start_main_~pos~0#1| 1) |ULTIMATE.start_main_~i~1#1|) (<= |ULTIMATE.start_main_~marker~0#1| 2147483647) (= |ULTIMATE.start___VERIFIER_assert_#in~cond#1| 0) (<= |ULTIMATE.start_main_~pos~0#1| 99999))' at error location [2023-12-02 17:12:41,066 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-12-02 17:12:41,066 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-12-02 17:12:41,067 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [116, 20, 18] total 152 [2023-12-02 17:12:41,067 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [758313502] [2023-12-02 17:12:41,067 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-12-02 17:12:41,067 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 152 states [2023-12-02 17:12:41,067 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 17:12:41,069 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 152 interpolants. [2023-12-02 17:12:41,073 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7314, Invalid=17808, Unknown=0, NotChecked=0, Total=25122 [2023-12-02 17:12:41,074 INFO L87 Difference]: Start difference. First operand 137 states and 138 transitions. Second operand has 152 states, 152 states have (on average 1.111842105263158) internal successors, (169), 152 states have internal predecessors, (169), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 17:12:55,128 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 17:12:55,128 INFO L93 Difference]: Finished difference Result 191 states and 201 transitions. [2023-12-02 17:12:55,129 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 155 states. [2023-12-02 17:12:55,129 INFO L78 Accepts]: Start accepts. Automaton has has 152 states, 152 states have (on average 1.111842105263158) internal successors, (169), 152 states have internal predecessors, (169), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 136 [2023-12-02 17:12:55,130 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 17:12:55,131 INFO L225 Difference]: With dead ends: 191 [2023-12-02 17:12:55,131 INFO L226 Difference]: Without dead ends: 154 [2023-12-02 17:12:55,136 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 659 GetRequests, 365 SyntacticMatches, 0 SemanticMatches, 294 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 17021 ImplicationChecksByTransitivity, 21.8s TimeCoverageRelationStatistics Valid=21183, Invalid=66137, Unknown=0, NotChecked=0, Total=87320 [2023-12-02 17:12:55,136 INFO L413 NwaCegarLoop]: 2 mSDtfsCounter, 118 mSDsluCounter, 46 mSDsCounter, 0 mSdLazyCounter, 574 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 118 SdHoareTripleChecker+Valid, 48 SdHoareTripleChecker+Invalid, 582 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 574 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2023-12-02 17:12:55,137 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [118 Valid, 48 Invalid, 582 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 574 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2023-12-02 17:12:55,137 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 154 states. [2023-12-02 17:12:55,161 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 154 to 154. [2023-12-02 17:12:55,161 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 154 states, 153 states have (on average 1.0130718954248366) internal successors, (155), 153 states have internal predecessors, (155), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 17:12:55,162 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 154 states to 154 states and 155 transitions. [2023-12-02 17:12:55,162 INFO L78 Accepts]: Start accepts. Automaton has 154 states and 155 transitions. Word has length 136 [2023-12-02 17:12:55,162 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 17:12:55,162 INFO L495 AbstractCegarLoop]: Abstraction has 154 states and 155 transitions. [2023-12-02 17:12:55,163 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 152 states, 152 states have (on average 1.111842105263158) internal successors, (169), 152 states have internal predecessors, (169), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 17:12:55,163 INFO L276 IsEmpty]: Start isEmpty. Operand 154 states and 155 transitions. [2023-12-02 17:12:55,164 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 154 [2023-12-02 17:12:55,164 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 17:12:55,165 INFO L195 NwaCegarLoop]: trace histogram [115, 16, 15, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 17:12:55,170 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4b135455-3be0-4a46-9000-73ecba14935e/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2023-12-02 17:12:55,365 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4b135455-3be0-4a46-9000-73ecba14935e/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2023-12-02 17:12:55,365 INFO L420 AbstractCegarLoop]: === Iteration 11 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 17:12:55,366 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 17:12:55,366 INFO L85 PathProgramCache]: Analyzing trace with hash 1092268087, now seen corresponding path program 9 times [2023-12-02 17:12:55,366 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 17:12:55,366 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [629098748] [2023-12-02 17:12:55,366 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 17:12:55,366 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 17:12:55,500 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 17:13:02,056 INFO L134 CoverageAnalysis]: Checked inductivity of 6910 backedges. 0 proven. 6670 refuted. 0 times theorem prover too weak. 240 trivial. 0 not checked. [2023-12-02 17:13:02,056 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 17:13:02,057 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [629098748] [2023-12-02 17:13:02,057 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [629098748] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-02 17:13:02,057 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1032681836] [2023-12-02 17:13:02,057 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2023-12-02 17:13:02,057 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 17:13:02,057 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4b135455-3be0-4a46-9000-73ecba14935e/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 17:13:02,058 INFO L229 MonitoredProcess]: Starting monitored process 11 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4b135455-3be0-4a46-9000-73ecba14935e/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 17:13:02,059 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4b135455-3be0-4a46-9000-73ecba14935e/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2023-12-02 17:13:02,354 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2023-12-02 17:13:02,354 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-02 17:13:02,360 INFO L262 TraceCheckSpWp]: Trace formula consists of 1165 conjuncts, 117 conjunts are in the unsatisfiable core [2023-12-02 17:13:02,365 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 17:13:02,517 INFO L134 CoverageAnalysis]: Checked inductivity of 6910 backedges. 0 proven. 6670 refuted. 0 times theorem prover too weak. 240 trivial. 0 not checked. [2023-12-02 17:13:02,517 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 17:13:15,010 INFO L134 CoverageAnalysis]: Checked inductivity of 6910 backedges. 0 proven. 6670 refuted. 0 times theorem prover too weak. 240 trivial. 0 not checked. [2023-12-02 17:13:15,010 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1032681836] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-02 17:13:15,010 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1239192116] [2023-12-02 17:13:15,012 INFO L159 IcfgInterpreter]: Started Sifa with 9 locations of interest [2023-12-02 17:13:15,012 INFO L166 IcfgInterpreter]: Building call graph [2023-12-02 17:13:15,012 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-12-02 17:13:15,012 INFO L176 IcfgInterpreter]: Starting interpretation [2023-12-02 17:13:15,012 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-12-02 17:13:15,133 INFO L180 IcfgInterpreter]: Interpretation finished [2023-12-02 17:13:15,810 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '6366#(and (<= 1 |#StackHeapBarrier|) (= |ULTIMATE.start_main_~marker~0#1| (select (select |#memory_int| |ULTIMATE.start_main_~#a~0#1.base|) (* |ULTIMATE.start_main_~i~1#1| 4))) (<= 0 (+ |ULTIMATE.start_main_~marker~0#1| 2147483648)) (= |ULTIMATE.start___VERIFIER_assert_~cond#1| 0) (<= 0 |ULTIMATE.start_main_~pos~0#1|) (<= 2 |ULTIMATE.start_main_~#a~0#1.base|) (= |ULTIMATE.start_main_~#a~0#1.offset| 0) (<= (+ |ULTIMATE.start_main_~pos~0#1| 1) |ULTIMATE.start_main_~i~1#1|) (<= |ULTIMATE.start_main_~marker~0#1| 2147483647) (= |ULTIMATE.start___VERIFIER_assert_#in~cond#1| 0) (<= |ULTIMATE.start_main_~pos~0#1| 99999))' at error location [2023-12-02 17:13:15,810 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-12-02 17:13:15,810 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-12-02 17:13:15,810 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [117, 117, 117] total 233 [2023-12-02 17:13:15,811 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1848024411] [2023-12-02 17:13:15,811 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-12-02 17:13:15,811 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 234 states [2023-12-02 17:13:15,811 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 17:13:15,816 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 234 interpolants. [2023-12-02 17:13:15,818 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=27288, Invalid=30552, Unknown=0, NotChecked=0, Total=57840 [2023-12-02 17:13:15,819 INFO L87 Difference]: Start difference. First operand 154 states and 155 transitions. Second operand has 234 states, 234 states have (on average 1.0299145299145298) internal successors, (241), 233 states have internal predecessors, (241), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 17:13:16,437 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 17:13:16,437 INFO L93 Difference]: Finished difference Result 308 states and 426 transitions. [2023-12-02 17:13:16,437 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 234 states. [2023-12-02 17:13:16,438 INFO L78 Accepts]: Start accepts. Automaton has has 234 states, 234 states have (on average 1.0299145299145298) internal successors, (241), 233 states have internal predecessors, (241), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 153 [2023-12-02 17:13:16,439 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 17:13:16,440 INFO L225 Difference]: With dead ends: 308 [2023-12-02 17:13:16,440 INFO L226 Difference]: Without dead ends: 271 [2023-12-02 17:13:16,443 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 574 GetRequests, 335 SyntacticMatches, 0 SemanticMatches, 239 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2427 ImplicationChecksByTransitivity, 17.3s TimeCoverageRelationStatistics Valid=27288, Invalid=30552, Unknown=0, NotChecked=0, Total=57840 [2023-12-02 17:13:16,443 INFO L413 NwaCegarLoop]: 7 mSDtfsCounter, 0 mSDsluCounter, 42 mSDsCounter, 0 mSdLazyCounter, 241 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 49 SdHoareTripleChecker+Invalid, 242 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 241 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-12-02 17:13:16,444 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 49 Invalid, 242 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 241 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-12-02 17:13:16,444 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 271 states. [2023-12-02 17:13:16,487 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 271 to 271. [2023-12-02 17:13:16,487 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 271 states, 270 states have (on average 1.0074074074074073) internal successors, (272), 270 states have internal predecessors, (272), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 17:13:16,507 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 271 states to 271 states and 272 transitions. [2023-12-02 17:13:16,508 INFO L78 Accepts]: Start accepts. Automaton has 271 states and 272 transitions. Word has length 153 [2023-12-02 17:13:16,508 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 17:13:16,508 INFO L495 AbstractCegarLoop]: Abstraction has 271 states and 272 transitions. [2023-12-02 17:13:16,509 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 234 states, 234 states have (on average 1.0299145299145298) internal successors, (241), 233 states have internal predecessors, (241), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 17:13:16,509 INFO L276 IsEmpty]: Start isEmpty. Operand 271 states and 272 transitions. [2023-12-02 17:13:16,513 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 271 [2023-12-02 17:13:16,513 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 17:13:16,514 INFO L195 NwaCegarLoop]: trace histogram [232, 16, 15, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 17:13:16,519 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4b135455-3be0-4a46-9000-73ecba14935e/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Ended with exit code 0 [2023-12-02 17:13:16,714 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4b135455-3be0-4a46-9000-73ecba14935e/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2023-12-02 17:13:16,714 INFO L420 AbstractCegarLoop]: === Iteration 12 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 17:13:16,715 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 17:13:16,715 INFO L85 PathProgramCache]: Analyzing trace with hash -2118918617, now seen corresponding path program 10 times [2023-12-02 17:13:16,715 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 17:13:16,715 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [20834575] [2023-12-02 17:13:16,715 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 17:13:16,715 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 17:13:17,092 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 17:13:43,205 INFO L134 CoverageAnalysis]: Checked inductivity of 27268 backedges. 0 proven. 27028 refuted. 0 times theorem prover too weak. 240 trivial. 0 not checked. [2023-12-02 17:13:43,206 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 17:13:43,206 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [20834575] [2023-12-02 17:13:43,206 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [20834575] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-02 17:13:43,206 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [386858233] [2023-12-02 17:13:43,206 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2023-12-02 17:13:43,206 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 17:13:43,206 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4b135455-3be0-4a46-9000-73ecba14935e/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 17:13:43,207 INFO L229 MonitoredProcess]: Starting monitored process 12 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4b135455-3be0-4a46-9000-73ecba14935e/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 17:13:43,208 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4b135455-3be0-4a46-9000-73ecba14935e/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2023-12-02 17:13:43,745 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 17:13:43,759 INFO L262 TraceCheckSpWp]: Trace formula consists of 2218 conjuncts, 234 conjunts are in the unsatisfiable core [2023-12-02 17:13:43,768 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 17:13:44,024 INFO L134 CoverageAnalysis]: Checked inductivity of 27268 backedges. 0 proven. 27028 refuted. 0 times theorem prover too weak. 240 trivial. 0 not checked. [2023-12-02 17:13:44,024 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 17:14:35,276 INFO L134 CoverageAnalysis]: Checked inductivity of 27268 backedges. 0 proven. 27028 refuted. 0 times theorem prover too weak. 240 trivial. 0 not checked. [2023-12-02 17:14:35,276 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [386858233] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-02 17:14:35,276 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [559445354] [2023-12-02 17:14:35,278 INFO L159 IcfgInterpreter]: Started Sifa with 9 locations of interest [2023-12-02 17:14:35,278 INFO L166 IcfgInterpreter]: Building call graph [2023-12-02 17:14:35,278 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-12-02 17:14:35,278 INFO L176 IcfgInterpreter]: Starting interpretation [2023-12-02 17:14:35,279 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-12-02 17:14:35,392 INFO L180 IcfgInterpreter]: Interpretation finished [2023-12-02 17:14:36,600 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '9548#(and (<= 1 |#StackHeapBarrier|) (= |ULTIMATE.start_main_~marker~0#1| (select (select |#memory_int| |ULTIMATE.start_main_~#a~0#1.base|) (* |ULTIMATE.start_main_~i~1#1| 4))) (<= 0 (+ |ULTIMATE.start_main_~marker~0#1| 2147483648)) (= |ULTIMATE.start___VERIFIER_assert_~cond#1| 0) (<= 0 |ULTIMATE.start_main_~pos~0#1|) (<= 2 |ULTIMATE.start_main_~#a~0#1.base|) (= |ULTIMATE.start_main_~#a~0#1.offset| 0) (<= (+ |ULTIMATE.start_main_~pos~0#1| 1) |ULTIMATE.start_main_~i~1#1|) (<= |ULTIMATE.start_main_~marker~0#1| 2147483647) (= |ULTIMATE.start___VERIFIER_assert_#in~cond#1| 0) (<= |ULTIMATE.start_main_~pos~0#1| 99999))' at error location [2023-12-02 17:14:36,600 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-12-02 17:14:36,601 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-12-02 17:14:36,601 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [234, 234, 234] total 467 [2023-12-02 17:14:36,601 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1529629641] [2023-12-02 17:14:36,601 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-12-02 17:14:36,602 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 468 states [2023-12-02 17:14:36,603 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 17:14:36,623 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 468 interpolants. [2023-12-02 17:14:36,633 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=109305, Invalid=115845, Unknown=0, NotChecked=0, Total=225150 [2023-12-02 17:14:36,634 INFO L87 Difference]: Start difference. First operand 271 states and 272 transitions. Second operand has 468 states, 468 states have (on average 1.014957264957265) internal successors, (475), 467 states have internal predecessors, (475), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 17:14:41,653 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 17:14:41,653 INFO L93 Difference]: Finished difference Result 542 states and 777 transitions. [2023-12-02 17:14:41,654 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 468 states. [2023-12-02 17:14:41,654 INFO L78 Accepts]: Start accepts. Automaton has has 468 states, 468 states have (on average 1.014957264957265) internal successors, (475), 467 states have internal predecessors, (475), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 270 [2023-12-02 17:14:41,655 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 17:14:41,657 INFO L225 Difference]: With dead ends: 542 [2023-12-02 17:14:41,657 INFO L226 Difference]: Without dead ends: 505 [2023-12-02 17:14:41,665 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 1042 GetRequests, 569 SyntacticMatches, 0 SemanticMatches, 473 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4884 ImplicationChecksByTransitivity, 68.5s TimeCoverageRelationStatistics Valid=109305, Invalid=115845, Unknown=0, NotChecked=0, Total=225150 [2023-12-02 17:14:41,666 INFO L413 NwaCegarLoop]: 7 mSDtfsCounter, 0 mSDsluCounter, 63 mSDsCounter, 0 mSdLazyCounter, 478 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 70 SdHoareTripleChecker+Invalid, 479 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 478 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2023-12-02 17:14:41,666 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 70 Invalid, 479 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 478 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2023-12-02 17:14:41,667 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 505 states. [2023-12-02 17:14:41,730 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 505 to 505. [2023-12-02 17:14:41,731 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 505 states, 504 states have (on average 1.003968253968254) internal successors, (506), 504 states have internal predecessors, (506), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 17:14:41,732 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 505 states to 505 states and 506 transitions. [2023-12-02 17:14:41,732 INFO L78 Accepts]: Start accepts. Automaton has 505 states and 506 transitions. Word has length 270 [2023-12-02 17:14:41,733 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 17:14:41,733 INFO L495 AbstractCegarLoop]: Abstraction has 505 states and 506 transitions. [2023-12-02 17:14:41,733 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 468 states, 468 states have (on average 1.014957264957265) internal successors, (475), 467 states have internal predecessors, (475), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 17:14:41,733 INFO L276 IsEmpty]: Start isEmpty. Operand 505 states and 506 transitions. [2023-12-02 17:14:41,740 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 505 [2023-12-02 17:14:41,740 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 17:14:41,740 INFO L195 NwaCegarLoop]: trace histogram [466, 16, 15, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 17:14:41,748 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4b135455-3be0-4a46-9000-73ecba14935e/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Ended with exit code 0 [2023-12-02 17:14:41,941 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11,12 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4b135455-3be0-4a46-9000-73ecba14935e/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 17:14:41,941 INFO L420 AbstractCegarLoop]: === Iteration 13 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 17:14:41,941 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 17:14:41,942 INFO L85 PathProgramCache]: Analyzing trace with hash -1836234713, now seen corresponding path program 11 times [2023-12-02 17:14:41,942 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 17:14:41,942 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1957242437] [2023-12-02 17:14:41,942 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 17:14:41,942 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 17:14:43,020 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 17:16:40,519 INFO L134 CoverageAnalysis]: Checked inductivity of 109051 backedges. 0 proven. 108811 refuted. 0 times theorem prover too weak. 240 trivial. 0 not checked. [2023-12-02 17:16:40,519 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 17:16:40,519 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1957242437] [2023-12-02 17:16:40,519 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1957242437] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-02 17:16:40,519 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [629046782] [2023-12-02 17:16:40,519 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-12-02 17:16:40,519 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 17:16:40,520 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4b135455-3be0-4a46-9000-73ecba14935e/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 17:16:40,521 INFO L229 MonitoredProcess]: Starting monitored process 13 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4b135455-3be0-4a46-9000-73ecba14935e/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 17:16:40,523 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4b135455-3be0-4a46-9000-73ecba14935e/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2023-12-02 17:16:52,310 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 16 check-sat command(s) [2023-12-02 17:16:52,311 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-02 17:16:52,324 INFO L262 TraceCheckSpWp]: Trace formula consists of 400 conjuncts, 106 conjunts are in the unsatisfiable core [2023-12-02 17:16:52,333 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 17:16:52,922 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 13 treesize of output 9 [2023-12-02 17:17:04,417 INFO L349 Elim1Store]: treesize reduction 56, result has 53.7 percent of original size [2023-12-02 17:17:04,418 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 16 select indices, 16 select index equivalence classes, 105 disjoint index pairs (out of 120 index pairs), introduced 16 new quantified variables, introduced 120 case distinctions, treesize of input 129 treesize of output 127 [2023-12-02 17:17:05,632 WARN L667 sPolynomialRelations]: Constructing 32768(two to the power of 15 dual juncts. [2023-12-02 17:17:07,379 INFO L134 CoverageAnalysis]: Checked inductivity of 109051 backedges. 0 proven. 3021 refuted. 0 times theorem prover too weak. 106030 trivial. 0 not checked. [2023-12-02 17:17:07,379 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 17:17:22,731 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 239 treesize of output 209 [2023-12-02 17:17:22,748 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-12-02 17:17:22,749 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 15 select indices, 15 select index equivalence classes, 0 disjoint index pairs (out of 105 index pairs), introduced 15 new quantified variables, introduced 105 case distinctions, treesize of input 224 treesize of output 1 [2023-12-02 17:17:22,764 INFO L134 CoverageAnalysis]: Checked inductivity of 109051 backedges. 0 proven. 240 refuted. 0 times theorem prover too weak. 108811 trivial. 0 not checked. [2023-12-02 17:17:22,764 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [629046782] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-02 17:17:22,764 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1801501882] [2023-12-02 17:17:22,766 INFO L159 IcfgInterpreter]: Started Sifa with 9 locations of interest [2023-12-02 17:17:22,766 INFO L166 IcfgInterpreter]: Building call graph [2023-12-02 17:17:22,767 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-12-02 17:17:22,767 INFO L176 IcfgInterpreter]: Starting interpretation [2023-12-02 17:17:22,767 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-12-02 17:17:22,902 INFO L180 IcfgInterpreter]: Interpretation finished [2023-12-02 17:17:25,535 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '15142#(and (<= 1 |#StackHeapBarrier|) (= |ULTIMATE.start_main_~marker~0#1| (select (select |#memory_int| |ULTIMATE.start_main_~#a~0#1.base|) (* |ULTIMATE.start_main_~i~1#1| 4))) (<= 0 (+ |ULTIMATE.start_main_~marker~0#1| 2147483648)) (= |ULTIMATE.start___VERIFIER_assert_~cond#1| 0) (<= 0 |ULTIMATE.start_main_~pos~0#1|) (<= 2 |ULTIMATE.start_main_~#a~0#1.base|) (= |ULTIMATE.start_main_~#a~0#1.offset| 0) (<= (+ |ULTIMATE.start_main_~pos~0#1| 1) |ULTIMATE.start_main_~i~1#1|) (<= |ULTIMATE.start_main_~marker~0#1| 2147483647) (= |ULTIMATE.start___VERIFIER_assert_#in~cond#1| 0) (<= |ULTIMATE.start_main_~pos~0#1| 99999))' at error location [2023-12-02 17:17:25,535 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-12-02 17:17:25,535 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-12-02 17:17:25,536 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [468, 40, 34] total 540 [2023-12-02 17:17:25,536 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2060530132] [2023-12-02 17:17:25,536 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-12-02 17:17:25,538 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 540 states [2023-12-02 17:17:25,538 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 17:17:25,561 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 540 interpolants. [2023-12-02 17:17:25,575 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=113481, Invalid=185181, Unknown=0, NotChecked=0, Total=298662 [2023-12-02 17:17:25,576 INFO L87 Difference]: Start difference. First operand 505 states and 506 transitions. Second operand has 540 states, 540 states have (on average 1.0314814814814814) internal successors, (557), 540 states have internal predecessors, (557), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 17:19:57,624 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 17:19:57,625 INFO L93 Difference]: Finished difference Result 607 states and 625 transitions. [2023-12-02 17:19:57,625 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 547 states. [2023-12-02 17:19:57,626 INFO L78 Accepts]: Start accepts. Automaton has has 540 states, 540 states have (on average 1.0314814814814814) internal successors, (557), 540 states have internal predecessors, (557), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 504 [2023-12-02 17:19:57,627 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 17:19:57,629 INFO L225 Difference]: With dead ends: 607 [2023-12-02 17:19:57,629 INFO L226 Difference]: Without dead ends: 538 [2023-12-02 17:19:57,680 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 2487 GetRequests, 1433 SyntacticMatches, 0 SemanticMatches, 1054 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 184034 ImplicationChecksByTransitivity, 244.4s TimeCoverageRelationStatistics Valid=332166, Invalid=781914, Unknown=0, NotChecked=0, Total=1114080 [2023-12-02 17:19:57,680 INFO L413 NwaCegarLoop]: 2 mSDtfsCounter, 459 mSDsluCounter, 81 mSDsCounter, 0 mSdLazyCounter, 2174 mSolverCounterSat, 16 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 459 SdHoareTripleChecker+Valid, 83 SdHoareTripleChecker+Invalid, 2190 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 16 IncrementalHoareTripleChecker+Valid, 2174 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.8s IncrementalHoareTripleChecker+Time [2023-12-02 17:19:57,680 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [459 Valid, 83 Invalid, 2190 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [16 Valid, 2174 Invalid, 0 Unknown, 0 Unchecked, 1.8s Time] [2023-12-02 17:19:57,681 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 538 states. [2023-12-02 17:19:57,753 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 538 to 538. [2023-12-02 17:19:57,754 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 538 states, 537 states have (on average 1.0037243947858474) internal successors, (539), 537 states have internal predecessors, (539), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 17:19:57,755 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 538 states to 538 states and 539 transitions. [2023-12-02 17:19:57,755 INFO L78 Accepts]: Start accepts. Automaton has 538 states and 539 transitions. Word has length 504 [2023-12-02 17:19:57,756 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 17:19:57,756 INFO L495 AbstractCegarLoop]: Abstraction has 538 states and 539 transitions. [2023-12-02 17:19:57,756 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 540 states, 540 states have (on average 1.0314814814814814) internal successors, (557), 540 states have internal predecessors, (557), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 17:19:57,756 INFO L276 IsEmpty]: Start isEmpty. Operand 538 states and 539 transitions. [2023-12-02 17:19:57,759 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 538 [2023-12-02 17:19:57,759 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 17:19:57,759 INFO L195 NwaCegarLoop]: trace histogram [467, 32, 31, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 17:19:57,769 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4b135455-3be0-4a46-9000-73ecba14935e/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Ended with exit code 0 [2023-12-02 17:19:57,959 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4b135455-3be0-4a46-9000-73ecba14935e/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2023-12-02 17:19:57,960 INFO L420 AbstractCegarLoop]: === Iteration 14 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 17:19:57,960 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 17:19:57,960 INFO L85 PathProgramCache]: Analyzing trace with hash 1615768551, now seen corresponding path program 12 times [2023-12-02 17:19:57,960 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 17:19:57,960 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1425177039] [2023-12-02 17:19:57,960 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 17:19:57,960 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 17:19:58,848 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 17:21:55,467 INFO L134 CoverageAnalysis]: Checked inductivity of 110270 backedges. 0 proven. 109278 refuted. 0 times theorem prover too weak. 992 trivial. 0 not checked. [2023-12-02 17:21:55,467 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 17:21:55,467 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1425177039] [2023-12-02 17:21:55,467 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1425177039] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-02 17:21:55,467 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [686487080] [2023-12-02 17:21:55,467 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2023-12-02 17:21:55,468 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 17:21:55,468 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4b135455-3be0-4a46-9000-73ecba14935e/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 17:21:55,469 INFO L229 MonitoredProcess]: Starting monitored process 14 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4b135455-3be0-4a46-9000-73ecba14935e/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 17:21:55,469 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4b135455-3be0-4a46-9000-73ecba14935e/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2023-12-02 17:21:56,509 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2023-12-02 17:21:56,509 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-02 17:21:56,539 INFO L262 TraceCheckSpWp]: Trace formula consists of 4413 conjuncts, 469 conjunts are in the unsatisfiable core [2023-12-02 17:21:56,553 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 17:21:57,055 INFO L134 CoverageAnalysis]: Checked inductivity of 110270 backedges. 0 proven. 109278 refuted. 0 times theorem prover too weak. 992 trivial. 0 not checked. [2023-12-02 17:21:57,056 INFO L327 TraceCheckSpWp]: Computing backward predicates...