./Ultimate.py --spec ../../sv-benchmarks/c/properties/unreach-call.prp --file ../../sv-benchmarks/c/array-patterns/array24_pattern.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 826ab2ba Calling Ultimate with: /usr/bin/java -Dosgi.configuration.area=/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a55227d7-7e76-4ee9-9ae9-d9948a0c4017/bin/utaipan-verify-sOmjnqqW8E/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a55227d7-7e76-4ee9-9ae9-d9948a0c4017/bin/utaipan-verify-sOmjnqqW8E/plugins/org.eclipse.equinox.launcher_1.6.800.v20240513-1750.jar -data @noDefault -ultimatedata /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a55227d7-7e76-4ee9-9ae9-d9948a0c4017/bin/utaipan-verify-sOmjnqqW8E/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a55227d7-7e76-4ee9-9ae9-d9948a0c4017/bin/utaipan-verify-sOmjnqqW8E/config/TaipanReach.xml -i ../../sv-benchmarks/c/array-patterns/array24_pattern.c -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a55227d7-7e76-4ee9-9ae9-d9948a0c4017/bin/utaipan-verify-sOmjnqqW8E/config/svcomp-Reach-32bit-Taipan_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a55227d7-7e76-4ee9-9ae9-d9948a0c4017/bin/utaipan-verify-sOmjnqqW8E --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 b41c571dabcbc4670dde65107f8da5b879f13435b678b4e9a9cdcc7ef0066cf6 --- Real Ultimate output --- This is Ultimate 0.3.0-dev-826ab2b [2024-11-14 03:02:58,617 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-14 03:02:58,678 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a55227d7-7e76-4ee9-9ae9-d9948a0c4017/bin/utaipan-verify-sOmjnqqW8E/config/svcomp-Reach-32bit-Taipan_Default.epf [2024-11-14 03:02:58,683 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-14 03:02:58,683 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-14 03:02:58,706 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-14 03:02:58,706 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-14 03:02:58,707 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-14 03:02:58,707 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-14 03:02:58,707 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-14 03:02:58,707 INFO L153 SettingsManager]: * User list type=DISABLED [2024-11-14 03:02:58,707 INFO L151 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2024-11-14 03:02:58,707 INFO L153 SettingsManager]: * Explicit value domain=true [2024-11-14 03:02:58,708 INFO L153 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2024-11-14 03:02:58,708 INFO L153 SettingsManager]: * Octagon Domain=false [2024-11-14 03:02:58,708 INFO L153 SettingsManager]: * Abstract domain=CompoundDomain [2024-11-14 03:02:58,708 INFO L153 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2024-11-14 03:02:58,708 INFO L153 SettingsManager]: * Use the RCFG-of-the-future interface=true [2024-11-14 03:02:58,708 INFO L153 SettingsManager]: * Interval Domain=false [2024-11-14 03:02:58,708 INFO L151 SettingsManager]: Preferences of Sifa differ from their defaults: [2024-11-14 03:02:58,708 INFO L153 SettingsManager]: * Call Summarizer=TopInputCallSummarizer [2024-11-14 03:02:58,709 INFO L153 SettingsManager]: * Simplification Technique=POLY_PAC [2024-11-14 03:02:58,709 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-14 03:02:58,709 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-14 03:02:58,709 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-14 03:02:58,709 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-14 03:02:58,709 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-14 03:02:58,709 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-14 03:02:58,710 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-14 03:02:58,710 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-14 03:02:58,710 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-14 03:02:58,710 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-14 03:02:58,710 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-14 03:02:58,710 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-14 03:02:58,710 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-14 03:02:58,710 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-14 03:02:58,711 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-14 03:02:58,711 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-14 03:02:58,711 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2024-11-14 03:02:58,711 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-14 03:02:58,711 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-14 03:02:58,711 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-14 03:02:58,711 INFO L153 SettingsManager]: * Trace refinement strategy=SIFA_TAIPAN [2024-11-14 03:02:58,711 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-14 03:02:58,711 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-14 03:02:58,712 INFO L153 SettingsManager]: * Trace refinement exception blacklist=NONE [2024-11-14 03:02:58,712 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-14 03:02:58,712 INFO L153 SettingsManager]: * Abstract interpretation Mode=USE_PREDICATES 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_a55227d7-7e76-4ee9-9ae9-d9948a0c4017/bin/utaipan-verify-sOmjnqqW8E 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 -> b41c571dabcbc4670dde65107f8da5b879f13435b678b4e9a9cdcc7ef0066cf6 [2024-11-14 03:02:59,026 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-14 03:02:59,037 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-14 03:02:59,041 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-14 03:02:59,044 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-14 03:02:59,044 INFO L274 PluginConnector]: CDTParser initialized [2024-11-14 03:02:59,045 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a55227d7-7e76-4ee9-9ae9-d9948a0c4017/bin/utaipan-verify-sOmjnqqW8E/../../sv-benchmarks/c/array-patterns/array24_pattern.c Unable to find full path for "g++" [2024-11-14 03:03:01,052 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-14 03:03:01,360 INFO L384 CDTParser]: Found 1 translation units. [2024-11-14 03:03:01,367 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a55227d7-7e76-4ee9-9ae9-d9948a0c4017/sv-benchmarks/c/array-patterns/array24_pattern.c [2024-11-14 03:03:01,390 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a55227d7-7e76-4ee9-9ae9-d9948a0c4017/bin/utaipan-verify-sOmjnqqW8E/data/231112635/5057e15e35434010968dbc81f77b1cac/FLAGe7ba50133 [2024-11-14 03:03:01,622 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a55227d7-7e76-4ee9-9ae9-d9948a0c4017/bin/utaipan-verify-sOmjnqqW8E/data/231112635/5057e15e35434010968dbc81f77b1cac [2024-11-14 03:03:01,624 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-14 03:03:01,626 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-14 03:03:01,627 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-14 03:03:01,628 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-14 03:03:01,632 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-14 03:03:01,633 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 14.11 03:03:01" (1/1) ... [2024-11-14 03:03:01,634 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@4d541a70 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 03:03:01, skipping insertion in model container [2024-11-14 03:03:01,634 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 14.11 03:03:01" (1/1) ... [2024-11-14 03:03:01,650 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-14 03:03:01,830 WARN L250 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_a55227d7-7e76-4ee9-9ae9-d9948a0c4017/sv-benchmarks/c/array-patterns/array24_pattern.c[1359,1372] [2024-11-14 03:03:01,863 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-14 03:03:01,875 INFO L200 MainTranslator]: Completed pre-run [2024-11-14 03:03:01,887 WARN L250 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_a55227d7-7e76-4ee9-9ae9-d9948a0c4017/sv-benchmarks/c/array-patterns/array24_pattern.c[1359,1372] [2024-11-14 03:03:01,909 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-14 03:03:01,926 INFO L204 MainTranslator]: Completed translation [2024-11-14 03:03:01,927 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 03:03:01 WrapperNode [2024-11-14 03:03:01,927 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-14 03:03:01,928 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-14 03:03:01,928 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-14 03:03:01,929 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-14 03:03:01,935 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 03:03:01" (1/1) ... [2024-11-14 03:03:01,947 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 03:03:01" (1/1) ... [2024-11-14 03:03:01,971 INFO L138 Inliner]: procedures = 17, calls = 20, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 102 [2024-11-14 03:03:01,971 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-14 03:03:01,972 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-14 03:03:01,972 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-14 03:03:01,972 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-14 03:03:01,981 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 03:03:01" (1/1) ... [2024-11-14 03:03:01,982 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 03:03:01" (1/1) ... [2024-11-14 03:03:01,985 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 03:03:01" (1/1) ... [2024-11-14 03:03:01,985 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 03:03:01" (1/1) ... [2024-11-14 03:03:01,996 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 03:03:01" (1/1) ... [2024-11-14 03:03:02,000 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 03:03:01" (1/1) ... [2024-11-14 03:03:02,004 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 03:03:01" (1/1) ... [2024-11-14 03:03:02,006 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 03:03:01" (1/1) ... [2024-11-14 03:03:02,008 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-14 03:03:02,013 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-14 03:03:02,013 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-14 03:03:02,013 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-14 03:03:02,016 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 03:03:01" (1/1) ... [2024-11-14 03:03:02,025 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2024-11-14 03:03:02,041 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a55227d7-7e76-4ee9-9ae9-d9948a0c4017/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 03:03:02,053 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a55227d7-7e76-4ee9-9ae9-d9948a0c4017/bin/utaipan-verify-sOmjnqqW8E/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2024-11-14 03:03:02,055 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a55227d7-7e76-4ee9-9ae9-d9948a0c4017/bin/utaipan-verify-sOmjnqqW8E/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2024-11-14 03:03:02,075 INFO L130 BoogieDeclarations]: Found specification of procedure outerBoundaryPatternCheck [2024-11-14 03:03:02,076 INFO L138 BoogieDeclarations]: Found implementation of procedure outerBoundaryPatternCheck [2024-11-14 03:03:02,076 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-14 03:03:02,076 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2024-11-14 03:03:02,076 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2024-11-14 03:03:02,076 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2024-11-14 03:03:02,076 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2024-11-14 03:03:02,076 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2024-11-14 03:03:02,076 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-14 03:03:02,076 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-14 03:03:02,076 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2024-11-14 03:03:02,076 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2024-11-14 03:03:02,161 INFO L238 CfgBuilder]: Building ICFG [2024-11-14 03:03:02,163 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-14 03:03:02,386 INFO L? ?]: Removed 25 outVars from TransFormulas that were not future-live. [2024-11-14 03:03:02,386 INFO L287 CfgBuilder]: Performing block encoding [2024-11-14 03:03:02,478 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-14 03:03:02,478 INFO L316 CfgBuilder]: Removed 5 assume(true) statements. [2024-11-14 03:03:02,479 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 14.11 03:03:02 BoogieIcfgContainer [2024-11-14 03:03:02,479 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-14 03:03:02,483 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-14 03:03:02,483 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-14 03:03:02,492 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-14 03:03:02,493 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 14.11 03:03:01" (1/3) ... [2024-11-14 03:03:02,494 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@176b8d97 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 14.11 03:03:02, skipping insertion in model container [2024-11-14 03:03:02,494 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 03:03:01" (2/3) ... [2024-11-14 03:03:02,495 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@176b8d97 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 14.11 03:03:02, skipping insertion in model container [2024-11-14 03:03:02,495 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 14.11 03:03:02" (3/3) ... [2024-11-14 03:03:02,496 INFO L112 eAbstractionObserver]: Analyzing ICFG array24_pattern.c [2024-11-14 03:03:02,513 INFO L217 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-14 03:03:02,516 INFO L154 ceAbstractionStarter]: Applying trace abstraction to ICFG array24_pattern.c that has 3 procedures, 27 locations, 1 initial locations, 5 loop locations, and 1 error locations. [2024-11-14 03:03:02,579 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-14 03:03:02,596 INFO L333 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, 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;@574b47e7, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-14 03:03:02,597 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-14 03:03:02,601 INFO L276 IsEmpty]: Start isEmpty. Operand has 27 states, 18 states have (on average 1.5) internal successors, (27), 19 states have internal predecessors, (27), 5 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2024-11-14 03:03:02,611 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2024-11-14 03:03:02,611 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 03:03:02,612 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 03:03:02,613 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 03:03:02,618 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 03:03:02,619 INFO L85 PathProgramCache]: Analyzing trace with hash -331043645, now seen corresponding path program 1 times [2024-11-14 03:03:02,625 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 03:03:02,626 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [658069202] [2024-11-14 03:03:02,626 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 03:03:02,626 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 03:03:02,737 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 03:03:02,805 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 03:03:02,806 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 03:03:02,806 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [658069202] [2024-11-14 03:03:02,809 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [658069202] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 03:03:02,809 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 03:03:02,810 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-11-14 03:03:02,811 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [792807015] [2024-11-14 03:03:02,812 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 03:03:02,815 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-11-14 03:03:02,815 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 03:03:02,837 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-11-14 03:03:02,837 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-14 03:03:02,839 INFO L87 Difference]: Start difference. First operand has 27 states, 18 states have (on average 1.5) internal successors, (27), 19 states have internal predecessors, (27), 5 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) Second operand has 2 states, 2 states have (on average 4.5) internal successors, (9), 2 states have internal predecessors, (9), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-14 03:03:02,894 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 03:03:02,894 INFO L93 Difference]: Finished difference Result 35 states and 47 transitions. [2024-11-14 03:03:02,896 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-14 03:03:02,897 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 4.5) internal successors, (9), 2 states have internal predecessors, (9), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 11 [2024-11-14 03:03:02,898 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 03:03:02,905 INFO L225 Difference]: With dead ends: 35 [2024-11-14 03:03:02,905 INFO L226 Difference]: Without dead ends: 25 [2024-11-14 03:03:02,908 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-14 03:03:02,913 INFO L432 NwaCegarLoop]: 26 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 9 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 26 SdHoareTripleChecker+Invalid, 9 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 9 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-14 03:03:02,913 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 26 Invalid, 9 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 9 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-14 03:03:02,925 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 25 states. [2024-11-14 03:03:02,943 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 25 to 25. [2024-11-14 03:03:02,944 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 25 states, 17 states have (on average 1.3529411764705883) internal successors, (23), 17 states have internal predecessors, (23), 5 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2024-11-14 03:03:02,951 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 25 states to 25 states and 33 transitions. [2024-11-14 03:03:02,953 INFO L78 Accepts]: Start accepts. Automaton has 25 states and 33 transitions. Word has length 11 [2024-11-14 03:03:02,955 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 03:03:02,955 INFO L471 AbstractCegarLoop]: Abstraction has 25 states and 33 transitions. [2024-11-14 03:03:02,955 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 4.5) internal successors, (9), 2 states have internal predecessors, (9), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-14 03:03:02,955 INFO L276 IsEmpty]: Start isEmpty. Operand 25 states and 33 transitions. [2024-11-14 03:03:02,957 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2024-11-14 03:03:02,957 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 03:03:02,957 INFO L215 NwaCegarLoop]: trace histogram [3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 03:03:02,957 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-14 03:03:02,957 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 03:03:02,958 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 03:03:02,958 INFO L85 PathProgramCache]: Analyzing trace with hash -920436763, now seen corresponding path program 1 times [2024-11-14 03:03:02,958 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 03:03:02,958 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [297780179] [2024-11-14 03:03:02,958 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 03:03:02,961 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 03:03:03,041 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 03:03:03,337 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-14 03:03:03,338 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 03:03:03,338 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [297780179] [2024-11-14 03:03:03,338 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [297780179] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 03:03:03,338 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [258704785] [2024-11-14 03:03:03,338 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 03:03:03,338 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 03:03:03,339 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a55227d7-7e76-4ee9-9ae9-d9948a0c4017/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 03:03:03,343 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a55227d7-7e76-4ee9-9ae9-d9948a0c4017/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 03:03:03,345 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a55227d7-7e76-4ee9-9ae9-d9948a0c4017/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-11-14 03:03:03,436 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 03:03:03,438 INFO L255 TraceCheckSpWp]: Trace formula consists of 94 conjuncts, 5 conjuncts are in the unsatisfiable core [2024-11-14 03:03:03,442 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 03:03:03,496 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-14 03:03:03,496 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-14 03:03:03,496 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [258704785] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 03:03:03,497 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-14 03:03:03,497 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [5] total 6 [2024-11-14 03:03:03,497 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [740845795] [2024-11-14 03:03:03,498 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 03:03:03,498 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-14 03:03:03,498 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 03:03:03,499 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-14 03:03:03,499 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=12, Invalid=18, Unknown=0, NotChecked=0, Total=30 [2024-11-14 03:03:03,499 INFO L87 Difference]: Start difference. First operand 25 states and 33 transitions. Second operand has 5 states, 4 states have (on average 3.75) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-14 03:03:03,633 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 03:03:03,633 INFO L93 Difference]: Finished difference Result 51 states and 67 transitions. [2024-11-14 03:03:03,633 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-14 03:03:03,634 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 3.75) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 24 [2024-11-14 03:03:03,634 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 03:03:03,635 INFO L225 Difference]: With dead ends: 51 [2024-11-14 03:03:03,636 INFO L226 Difference]: Without dead ends: 31 [2024-11-14 03:03:03,636 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 29 GetRequests, 24 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=16, Invalid=26, Unknown=0, NotChecked=0, Total=42 [2024-11-14 03:03:03,638 INFO L432 NwaCegarLoop]: 17 mSDtfsCounter, 37 mSDsluCounter, 23 mSDsCounter, 0 mSdLazyCounter, 58 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 39 SdHoareTripleChecker+Valid, 40 SdHoareTripleChecker+Invalid, 60 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 58 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-14 03:03:03,638 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [39 Valid, 40 Invalid, 60 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 58 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-14 03:03:03,640 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 31 states. [2024-11-14 03:03:03,648 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 31 to 29. [2024-11-14 03:03:03,649 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 29 states, 20 states have (on average 1.3) internal successors, (26), 20 states have internal predecessors, (26), 5 states have call successors, (5), 3 states have call predecessors, (5), 3 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2024-11-14 03:03:03,650 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 29 states to 29 states and 36 transitions. [2024-11-14 03:03:03,650 INFO L78 Accepts]: Start accepts. Automaton has 29 states and 36 transitions. Word has length 24 [2024-11-14 03:03:03,651 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 03:03:03,651 INFO L471 AbstractCegarLoop]: Abstraction has 29 states and 36 transitions. [2024-11-14 03:03:03,651 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 3.75) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-14 03:03:03,651 INFO L276 IsEmpty]: Start isEmpty. Operand 29 states and 36 transitions. [2024-11-14 03:03:03,652 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2024-11-14 03:03:03,652 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 03:03:03,652 INFO L215 NwaCegarLoop]: trace histogram [3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 03:03:03,672 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a55227d7-7e76-4ee9-9ae9-d9948a0c4017/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2024-11-14 03:03:03,852 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a55227d7-7e76-4ee9-9ae9-d9948a0c4017/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 03:03:03,853 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 03:03:03,853 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 03:03:03,853 INFO L85 PathProgramCache]: Analyzing trace with hash -1117586259, now seen corresponding path program 1 times [2024-11-14 03:03:03,853 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 03:03:03,853 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1912013421] [2024-11-14 03:03:03,853 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 03:03:03,854 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 03:03:03,893 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 03:03:04,052 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2024-11-14 03:03:04,053 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 03:03:04,053 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1912013421] [2024-11-14 03:03:04,053 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1912013421] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 03:03:04,053 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 03:03:04,053 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2024-11-14 03:03:04,053 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1067272246] [2024-11-14 03:03:04,053 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 03:03:04,054 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-11-14 03:03:04,054 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 03:03:04,054 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-11-14 03:03:04,054 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2024-11-14 03:03:04,055 INFO L87 Difference]: Start difference. First operand 29 states and 36 transitions. Second operand has 4 states, 4 states have (on average 4.5) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (4), 1 states have call predecessors, (4), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-14 03:03:04,106 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 03:03:04,106 INFO L93 Difference]: Finished difference Result 56 states and 74 transitions. [2024-11-14 03:03:04,106 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-11-14 03:03:04,106 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 4.5) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (4), 1 states have call predecessors, (4), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 28 [2024-11-14 03:03:04,107 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 03:03:04,107 INFO L225 Difference]: With dead ends: 56 [2024-11-14 03:03:04,107 INFO L226 Difference]: Without dead ends: 33 [2024-11-14 03:03:04,108 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2024-11-14 03:03:04,108 INFO L432 NwaCegarLoop]: 21 mSDtfsCounter, 5 mSDsluCounter, 19 mSDsCounter, 0 mSdLazyCounter, 28 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 40 SdHoareTripleChecker+Invalid, 31 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 28 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-14 03:03:04,109 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [5 Valid, 40 Invalid, 31 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 28 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-14 03:03:04,109 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 33 states. [2024-11-14 03:03:04,115 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 33 to 31. [2024-11-14 03:03:04,115 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 31 states, 22 states have (on average 1.2727272727272727) internal successors, (28), 22 states have internal predecessors, (28), 5 states have call successors, (5), 3 states have call predecessors, (5), 3 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2024-11-14 03:03:04,116 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 31 states to 31 states and 38 transitions. [2024-11-14 03:03:04,116 INFO L78 Accepts]: Start accepts. Automaton has 31 states and 38 transitions. Word has length 28 [2024-11-14 03:03:04,116 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 03:03:04,116 INFO L471 AbstractCegarLoop]: Abstraction has 31 states and 38 transitions. [2024-11-14 03:03:04,117 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 4.5) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (4), 1 states have call predecessors, (4), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-14 03:03:04,117 INFO L276 IsEmpty]: Start isEmpty. Operand 31 states and 38 transitions. [2024-11-14 03:03:04,117 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2024-11-14 03:03:04,118 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 03:03:04,118 INFO L215 NwaCegarLoop]: trace histogram [3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 03:03:04,118 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2024-11-14 03:03:04,118 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 03:03:04,118 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 03:03:04,119 INFO L85 PathProgramCache]: Analyzing trace with hash -948260595, now seen corresponding path program 1 times [2024-11-14 03:03:04,119 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 03:03:04,119 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [498656065] [2024-11-14 03:03:04,119 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 03:03:04,119 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 03:03:04,148 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 03:03:04,345 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 1 proven. 3 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2024-11-14 03:03:04,345 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 03:03:04,345 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [498656065] [2024-11-14 03:03:04,345 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [498656065] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 03:03:04,345 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1926465199] [2024-11-14 03:03:04,345 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 03:03:04,346 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 03:03:04,346 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a55227d7-7e76-4ee9-9ae9-d9948a0c4017/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 03:03:04,348 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a55227d7-7e76-4ee9-9ae9-d9948a0c4017/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 03:03:04,351 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a55227d7-7e76-4ee9-9ae9-d9948a0c4017/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-11-14 03:03:04,451 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 03:03:04,453 INFO L255 TraceCheckSpWp]: Trace formula consists of 120 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-11-14 03:03:04,456 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 03:03:04,534 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 5 proven. 1 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-14 03:03:04,538 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 03:03:04,664 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 1 proven. 3 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2024-11-14 03:03:04,664 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1926465199] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 03:03:04,664 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1986591788] [2024-11-14 03:03:04,688 INFO L159 IcfgInterpreter]: Started Sifa with 23 locations of interest [2024-11-14 03:03:04,690 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 03:03:04,693 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 03:03:04,697 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 03:03:04,698 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 03:03:07,221 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 1 for LOIs [2024-11-14 03:03:07,225 INFO L197 IcfgInterpreter]: Interpreting procedure outerBoundaryPatternCheck with input of size 83 for LOIs [2024-11-14 03:03:07,278 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 03:03:09,226 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '661#(exists ((|v_ULTIMATE.start_main_~row~0#1_48| Int)) (and (<= ~ARR_SIZE~0 |v_ULTIMATE.start_main_~row~0#1_48|) (<= 1 ~ARR_SIZE~0)))' at error location [2024-11-14 03:03:09,226 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 03:03:09,226 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-14 03:03:09,226 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6, 6] total 10 [2024-11-14 03:03:09,227 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [144196503] [2024-11-14 03:03:09,227 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-14 03:03:09,227 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-11-14 03:03:09,227 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 03:03:09,228 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-11-14 03:03:09,228 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=125, Invalid=631, Unknown=0, NotChecked=0, Total=756 [2024-11-14 03:03:09,229 INFO L87 Difference]: Start difference. First operand 31 states and 38 transitions. Second operand has 10 states, 8 states have (on average 3.625) internal successors, (29), 10 states have internal predecessors, (29), 2 states have call successors, (7), 2 states have call predecessors, (7), 4 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2024-11-14 03:03:09,355 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 03:03:09,355 INFO L93 Difference]: Finished difference Result 59 states and 77 transitions. [2024-11-14 03:03:09,355 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-11-14 03:03:09,356 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 8 states have (on average 3.625) internal successors, (29), 10 states have internal predecessors, (29), 2 states have call successors, (7), 2 states have call predecessors, (7), 4 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) Word has length 30 [2024-11-14 03:03:09,356 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 03:03:09,356 INFO L225 Difference]: With dead ends: 59 [2024-11-14 03:03:09,357 INFO L226 Difference]: Without dead ends: 35 [2024-11-14 03:03:09,357 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 95 GetRequests, 65 SyntacticMatches, 3 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 347 ImplicationChecksByTransitivity, 2.1s TimeCoverageRelationStatistics Valid=131, Invalid=681, Unknown=0, NotChecked=0, Total=812 [2024-11-14 03:03:09,358 INFO L432 NwaCegarLoop]: 17 mSDtfsCounter, 48 mSDsluCounter, 34 mSDsCounter, 0 mSdLazyCounter, 82 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 50 SdHoareTripleChecker+Valid, 51 SdHoareTripleChecker+Invalid, 95 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 82 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-14 03:03:09,358 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [50 Valid, 51 Invalid, 95 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 82 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-14 03:03:09,359 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 35 states. [2024-11-14 03:03:09,363 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 35 to 33. [2024-11-14 03:03:09,364 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 33 states, 24 states have (on average 1.25) internal successors, (30), 24 states have internal predecessors, (30), 5 states have call successors, (5), 3 states have call predecessors, (5), 3 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2024-11-14 03:03:09,364 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 33 states to 33 states and 40 transitions. [2024-11-14 03:03:09,365 INFO L78 Accepts]: Start accepts. Automaton has 33 states and 40 transitions. Word has length 30 [2024-11-14 03:03:09,365 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 03:03:09,365 INFO L471 AbstractCegarLoop]: Abstraction has 33 states and 40 transitions. [2024-11-14 03:03:09,365 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 8 states have (on average 3.625) internal successors, (29), 10 states have internal predecessors, (29), 2 states have call successors, (7), 2 states have call predecessors, (7), 4 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2024-11-14 03:03:09,365 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 40 transitions. [2024-11-14 03:03:09,366 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2024-11-14 03:03:09,366 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 03:03:09,366 INFO L215 NwaCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 03:03:09,387 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a55227d7-7e76-4ee9-9ae9-d9948a0c4017/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2024-11-14 03:03:09,567 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a55227d7-7e76-4ee9-9ae9-d9948a0c4017/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 03:03:09,567 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 03:03:09,567 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 03:03:09,567 INFO L85 PathProgramCache]: Analyzing trace with hash -1886593235, now seen corresponding path program 2 times [2024-11-14 03:03:09,567 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 03:03:09,567 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1177542530] [2024-11-14 03:03:09,567 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 03:03:09,567 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 03:03:09,599 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 03:03:09,769 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2024-11-14 03:03:09,769 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 03:03:09,769 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1177542530] [2024-11-14 03:03:09,769 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1177542530] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 03:03:09,769 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1144570366] [2024-11-14 03:03:09,770 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-14 03:03:09,770 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 03:03:09,770 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a55227d7-7e76-4ee9-9ae9-d9948a0c4017/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 03:03:09,772 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a55227d7-7e76-4ee9-9ae9-d9948a0c4017/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 03:03:09,774 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a55227d7-7e76-4ee9-9ae9-d9948a0c4017/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-11-14 03:03:09,853 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 2 check-sat command(s) [2024-11-14 03:03:09,853 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-14 03:03:09,855 INFO L255 TraceCheckSpWp]: Trace formula consists of 69 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-11-14 03:03:09,859 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 03:03:09,977 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 2 proven. 3 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2024-11-14 03:03:09,977 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 03:03:10,095 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2024-11-14 03:03:10,095 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1144570366] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 03:03:10,095 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [146747775] [2024-11-14 03:03:10,097 INFO L159 IcfgInterpreter]: Started Sifa with 23 locations of interest [2024-11-14 03:03:10,098 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 03:03:10,098 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 03:03:10,098 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 03:03:10,102 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 03:03:11,273 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 1 for LOIs [2024-11-14 03:03:11,274 INFO L197 IcfgInterpreter]: Interpreting procedure outerBoundaryPatternCheck with input of size 83 for LOIs [2024-11-14 03:03:11,310 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 03:03:12,779 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '834#true' at error location [2024-11-14 03:03:12,779 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 03:03:12,779 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-14 03:03:12,780 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 6, 6] total 13 [2024-11-14 03:03:12,780 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2096309543] [2024-11-14 03:03:12,780 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-14 03:03:12,781 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2024-11-14 03:03:12,781 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 03:03:12,781 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2024-11-14 03:03:12,782 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=123, Invalid=689, Unknown=0, NotChecked=0, Total=812 [2024-11-14 03:03:12,783 INFO L87 Difference]: Start difference. First operand 33 states and 40 transitions. Second operand has 13 states, 11 states have (on average 4.090909090909091) internal successors, (45), 13 states have internal predecessors, (45), 3 states have call successors, (10), 2 states have call predecessors, (10), 4 states have return successors, (12), 3 states have call predecessors, (12), 3 states have call successors, (12) [2024-11-14 03:03:13,006 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 03:03:13,006 INFO L93 Difference]: Finished difference Result 70 states and 88 transitions. [2024-11-14 03:03:13,007 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-14 03:03:13,008 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 11 states have (on average 4.090909090909091) internal successors, (45), 13 states have internal predecessors, (45), 3 states have call successors, (10), 2 states have call predecessors, (10), 4 states have return successors, (12), 3 states have call predecessors, (12), 3 states have call successors, (12) Word has length 32 [2024-11-14 03:03:13,008 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 03:03:13,008 INFO L225 Difference]: With dead ends: 70 [2024-11-14 03:03:13,008 INFO L226 Difference]: Without dead ends: 47 [2024-11-14 03:03:13,009 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 105 GetRequests, 72 SyntacticMatches, 2 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 376 ImplicationChecksByTransitivity, 1.7s TimeCoverageRelationStatistics Valid=164, Invalid=892, Unknown=0, NotChecked=0, Total=1056 [2024-11-14 03:03:13,010 INFO L432 NwaCegarLoop]: 17 mSDtfsCounter, 35 mSDsluCounter, 74 mSDsCounter, 0 mSdLazyCounter, 160 mSolverCounterSat, 12 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 35 SdHoareTripleChecker+Valid, 91 SdHoareTripleChecker+Invalid, 172 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 160 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-14 03:03:13,010 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [35 Valid, 91 Invalid, 172 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 160 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-14 03:03:13,011 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2024-11-14 03:03:13,016 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 41. [2024-11-14 03:03:13,017 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 41 states, 32 states have (on average 1.25) internal successors, (40), 32 states have internal predecessors, (40), 5 states have call successors, (5), 3 states have call predecessors, (5), 3 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2024-11-14 03:03:13,017 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 41 states to 41 states and 50 transitions. [2024-11-14 03:03:13,018 INFO L78 Accepts]: Start accepts. Automaton has 41 states and 50 transitions. Word has length 32 [2024-11-14 03:03:13,018 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 03:03:13,018 INFO L471 AbstractCegarLoop]: Abstraction has 41 states and 50 transitions. [2024-11-14 03:03:13,018 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 11 states have (on average 4.090909090909091) internal successors, (45), 13 states have internal predecessors, (45), 3 states have call successors, (10), 2 states have call predecessors, (10), 4 states have return successors, (12), 3 states have call predecessors, (12), 3 states have call successors, (12) [2024-11-14 03:03:13,018 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 50 transitions. [2024-11-14 03:03:13,019 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2024-11-14 03:03:13,019 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 03:03:13,019 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 03:03:13,037 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a55227d7-7e76-4ee9-9ae9-d9948a0c4017/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2024-11-14 03:03:13,223 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a55227d7-7e76-4ee9-9ae9-d9948a0c4017/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 03:03:13,224 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 03:03:13,224 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 03:03:13,224 INFO L85 PathProgramCache]: Analyzing trace with hash -1634871691, now seen corresponding path program 3 times [2024-11-14 03:03:13,224 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 03:03:13,224 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [315546805] [2024-11-14 03:03:13,224 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 03:03:13,224 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 03:03:13,269 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 03:03:13,272 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [334157681] [2024-11-14 03:03:13,272 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-14 03:03:13,272 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 03:03:13,272 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a55227d7-7e76-4ee9-9ae9-d9948a0c4017/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 03:03:13,278 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a55227d7-7e76-4ee9-9ae9-d9948a0c4017/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 03:03:13,280 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a55227d7-7e76-4ee9-9ae9-d9948a0c4017/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-11-14 03:03:13,509 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-14 03:03:13,509 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-14 03:03:13,511 INFO L255 TraceCheckSpWp]: Trace formula consists of 174 conjuncts, 74 conjuncts are in the unsatisfiable core [2024-11-14 03:03:13,517 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 03:03:13,615 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 11 treesize of output 7 [2024-11-14 03:03:13,655 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 18 [2024-11-14 03:03:13,807 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-14 03:03:13,807 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 26 treesize of output 28 [2024-11-14 03:03:13,872 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-14 03:03:13,872 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 6 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 33 treesize of output 38 [2024-11-14 03:03:14,812 INFO L349 Elim1Store]: treesize reduction 368, result has 13.4 percent of original size [2024-11-14 03:03:14,813 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 9 select indices, 9 select index equivalence classes, 6 disjoint index pairs (out of 36 index pairs), introduced 9 new quantified variables, introduced 44 case distinctions, treesize of input 84 treesize of output 94 [2024-11-14 03:03:15,327 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 4 proven. 36 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-14 03:03:15,327 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 03:03:19,053 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 227 treesize of output 219 [2024-11-14 03:03:19,097 INFO L349 Elim1Store]: treesize reduction 27, result has 22.9 percent of original size [2024-11-14 03:03:19,098 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 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 1486421 treesize of output 1408605 [2024-11-14 03:03:56,978 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 234 treesize of output 226 [2024-11-14 03:03:57,034 INFO L349 Elim1Store]: treesize reduction 27, result has 22.9 percent of original size [2024-11-14 03:03:57,035 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 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 1988626 treesize of output 1910810 [2024-11-14 03:04:02,939 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 2 proven. 36 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-14 03:04:02,940 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 03:04:02,940 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [315546805] [2024-11-14 03:04:02,940 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-14 03:04:02,940 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [334157681] [2024-11-14 03:04:02,940 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [334157681] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 03:04:02,940 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [563602606] [2024-11-14 03:04:02,943 INFO L159 IcfgInterpreter]: Started Sifa with 23 locations of interest [2024-11-14 03:04:02,943 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 03:04:02,944 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 03:04:02,944 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 03:04:02,944 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 03:04:03,865 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 1 for LOIs [2024-11-14 03:04:03,867 INFO L197 IcfgInterpreter]: Interpreting procedure outerBoundaryPatternCheck with input of size 83 for LOIs [2024-11-14 03:04:03,902 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 03:04:10,578 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1526#(exists ((|v_ULTIMATE.start_main_~row~0#1_83| Int)) (and (<= 1 ~ARR_SIZE~0) (<= ~ARR_SIZE~0 |v_ULTIMATE.start_main_~row~0#1_83|)))' at error location [2024-11-14 03:04:10,578 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 03:04:10,578 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-14 03:04:10,578 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [23, 22] total 44 [2024-11-14 03:04:10,579 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [274082218] [2024-11-14 03:04:10,579 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-14 03:04:10,579 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 44 states [2024-11-14 03:04:10,579 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 03:04:10,580 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 44 interpolants. [2024-11-14 03:04:10,585 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=467, Invalid=3439, Unknown=0, NotChecked=0, Total=3906 [2024-11-14 03:04:10,585 INFO L87 Difference]: Start difference. First operand 41 states and 50 transitions. Second operand has 44 states, 41 states have (on average 1.4878048780487805) internal successors, (61), 43 states have internal predecessors, (61), 7 states have call successors, (8), 3 states have call predecessors, (8), 5 states have return successors, (8), 6 states have call predecessors, (8), 7 states have call successors, (8) [2024-11-14 03:04:21,169 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 03:04:21,169 INFO L93 Difference]: Finished difference Result 145 states and 191 transitions. [2024-11-14 03:04:21,172 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 56 states. [2024-11-14 03:04:21,172 INFO L78 Accepts]: Start accepts. Automaton has has 44 states, 41 states have (on average 1.4878048780487805) internal successors, (61), 43 states have internal predecessors, (61), 7 states have call successors, (8), 3 states have call predecessors, (8), 5 states have return successors, (8), 6 states have call predecessors, (8), 7 states have call successors, (8) Word has length 40 [2024-11-14 03:04:21,172 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 03:04:21,175 INFO L225 Difference]: With dead ends: 145 [2024-11-14 03:04:21,175 INFO L226 Difference]: Without dead ends: 141 [2024-11-14 03:04:21,177 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 155 GetRequests, 53 SyntacticMatches, 5 SemanticMatches, 97 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3531 ImplicationChecksByTransitivity, 17.9s TimeCoverageRelationStatistics Valid=1235, Invalid=8466, Unknown=1, NotChecked=0, Total=9702 [2024-11-14 03:04:21,178 INFO L432 NwaCegarLoop]: 28 mSDtfsCounter, 193 mSDsluCounter, 484 mSDsCounter, 0 mSdLazyCounter, 1525 mSolverCounterSat, 93 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 3.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 198 SdHoareTripleChecker+Valid, 512 SdHoareTripleChecker+Invalid, 1618 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 93 IncrementalHoareTripleChecker+Valid, 1525 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 3.2s IncrementalHoareTripleChecker+Time [2024-11-14 03:04:21,178 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [198 Valid, 512 Invalid, 1618 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [93 Valid, 1525 Invalid, 0 Unknown, 0 Unchecked, 3.2s Time] [2024-11-14 03:04:21,179 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 141 states. [2024-11-14 03:04:21,211 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 141 to 102. [2024-11-14 03:04:21,211 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 102 states, 79 states have (on average 1.3164556962025316) internal successors, (104), 80 states have internal predecessors, (104), 16 states have call successors, (16), 6 states have call predecessors, (16), 6 states have return successors, (16), 15 states have call predecessors, (16), 16 states have call successors, (16) [2024-11-14 03:04:21,213 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 102 states to 102 states and 136 transitions. [2024-11-14 03:04:21,213 INFO L78 Accepts]: Start accepts. Automaton has 102 states and 136 transitions. Word has length 40 [2024-11-14 03:04:21,213 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 03:04:21,213 INFO L471 AbstractCegarLoop]: Abstraction has 102 states and 136 transitions. [2024-11-14 03:04:21,214 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 44 states, 41 states have (on average 1.4878048780487805) internal successors, (61), 43 states have internal predecessors, (61), 7 states have call successors, (8), 3 states have call predecessors, (8), 5 states have return successors, (8), 6 states have call predecessors, (8), 7 states have call successors, (8) [2024-11-14 03:04:21,214 INFO L276 IsEmpty]: Start isEmpty. Operand 102 states and 136 transitions. [2024-11-14 03:04:21,216 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 42 [2024-11-14 03:04:21,216 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 03:04:21,216 INFO L215 NwaCegarLoop]: trace histogram [5, 4, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 03:04:21,230 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a55227d7-7e76-4ee9-9ae9-d9948a0c4017/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2024-11-14 03:04:21,417 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a55227d7-7e76-4ee9-9ae9-d9948a0c4017/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 03:04:21,417 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 03:04:21,417 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 03:04:21,417 INFO L85 PathProgramCache]: Analyzing trace with hash 810659135, now seen corresponding path program 4 times [2024-11-14 03:04:21,417 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 03:04:21,418 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [638860560] [2024-11-14 03:04:21,418 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 03:04:21,418 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 03:04:21,442 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 03:04:21,609 INFO L134 CoverageAnalysis]: Checked inductivity of 48 backedges. 14 proven. 20 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2024-11-14 03:04:21,609 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 03:04:21,609 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [638860560] [2024-11-14 03:04:21,609 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [638860560] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 03:04:21,609 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [879764979] [2024-11-14 03:04:21,610 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2024-11-14 03:04:21,610 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 03:04:21,610 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a55227d7-7e76-4ee9-9ae9-d9948a0c4017/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 03:04:21,612 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a55227d7-7e76-4ee9-9ae9-d9948a0c4017/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 03:04:21,615 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a55227d7-7e76-4ee9-9ae9-d9948a0c4017/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2024-11-14 03:04:21,705 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 03:04:21,707 INFO L255 TraceCheckSpWp]: Trace formula consists of 181 conjuncts, 8 conjuncts are in the unsatisfiable core [2024-11-14 03:04:21,708 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 03:04:21,814 INFO L134 CoverageAnalysis]: Checked inductivity of 48 backedges. 26 proven. 12 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2024-11-14 03:04:21,814 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 03:04:21,896 INFO L134 CoverageAnalysis]: Checked inductivity of 48 backedges. 13 proven. 21 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2024-11-14 03:04:21,896 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [879764979] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 03:04:21,896 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [889067904] [2024-11-14 03:04:21,898 INFO L159 IcfgInterpreter]: Started Sifa with 23 locations of interest [2024-11-14 03:04:21,898 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 03:04:21,899 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 03:04:21,899 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 03:04:21,899 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 03:04:22,673 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 1 for LOIs [2024-11-14 03:04:22,675 INFO L197 IcfgInterpreter]: Interpreting procedure outerBoundaryPatternCheck with input of size 83 for LOIs [2024-11-14 03:04:22,696 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 03:04:24,039 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '2048#true' at error location [2024-11-14 03:04:24,040 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 03:04:24,040 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-14 03:04:24,040 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9, 9] total 14 [2024-11-14 03:04:24,040 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1951137193] [2024-11-14 03:04:24,040 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-14 03:04:24,040 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2024-11-14 03:04:24,041 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 03:04:24,041 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2024-11-14 03:04:24,041 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=113, Invalid=817, Unknown=0, NotChecked=0, Total=930 [2024-11-14 03:04:24,042 INFO L87 Difference]: Start difference. First operand 102 states and 136 transitions. Second operand has 14 states, 14 states have (on average 2.7857142857142856) internal successors, (39), 14 states have internal predecessors, (39), 2 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2024-11-14 03:04:24,237 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 03:04:24,237 INFO L93 Difference]: Finished difference Result 206 states and 273 transitions. [2024-11-14 03:04:24,239 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-14 03:04:24,240 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 2.7857142857142856) internal successors, (39), 14 states have internal predecessors, (39), 2 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 41 [2024-11-14 03:04:24,240 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 03:04:24,241 INFO L225 Difference]: With dead ends: 206 [2024-11-14 03:04:24,241 INFO L226 Difference]: Without dead ends: 135 [2024-11-14 03:04:24,242 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 132 GetRequests, 96 SyntacticMatches, 5 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 355 ImplicationChecksByTransitivity, 1.5s TimeCoverageRelationStatistics Valid=132, Invalid=924, Unknown=0, NotChecked=0, Total=1056 [2024-11-14 03:04:24,242 INFO L432 NwaCegarLoop]: 20 mSDtfsCounter, 8 mSDsluCounter, 78 mSDsCounter, 0 mSdLazyCounter, 163 mSolverCounterSat, 16 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 98 SdHoareTripleChecker+Invalid, 179 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 16 IncrementalHoareTripleChecker+Valid, 163 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-14 03:04:24,243 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 98 Invalid, 179 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [16 Valid, 163 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-14 03:04:24,247 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 135 states. [2024-11-14 03:04:24,296 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 135 to 123. [2024-11-14 03:04:24,297 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 123 states, 94 states have (on average 1.2872340425531914) internal successors, (121), 95 states have internal predecessors, (121), 20 states have call successors, (20), 8 states have call predecessors, (20), 8 states have return successors, (20), 19 states have call predecessors, (20), 20 states have call successors, (20) [2024-11-14 03:04:24,298 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 123 states to 123 states and 161 transitions. [2024-11-14 03:04:24,299 INFO L78 Accepts]: Start accepts. Automaton has 123 states and 161 transitions. Word has length 41 [2024-11-14 03:04:24,299 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 03:04:24,299 INFO L471 AbstractCegarLoop]: Abstraction has 123 states and 161 transitions. [2024-11-14 03:04:24,299 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 2.7857142857142856) internal successors, (39), 14 states have internal predecessors, (39), 2 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2024-11-14 03:04:24,300 INFO L276 IsEmpty]: Start isEmpty. Operand 123 states and 161 transitions. [2024-11-14 03:04:24,302 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 43 [2024-11-14 03:04:24,302 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 03:04:24,302 INFO L215 NwaCegarLoop]: trace histogram [6, 4, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 03:04:24,316 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a55227d7-7e76-4ee9-9ae9-d9948a0c4017/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2024-11-14 03:04:24,503 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a55227d7-7e76-4ee9-9ae9-d9948a0c4017/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 03:04:24,503 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 03:04:24,503 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 03:04:24,504 INFO L85 PathProgramCache]: Analyzing trace with hash -657850323, now seen corresponding path program 5 times [2024-11-14 03:04:24,504 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 03:04:24,504 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1307097772] [2024-11-14 03:04:24,504 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 03:04:24,504 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 03:04:24,526 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 03:04:24,686 INFO L134 CoverageAnalysis]: Checked inductivity of 55 backedges. 1 proven. 24 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2024-11-14 03:04:24,686 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 03:04:24,686 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1307097772] [2024-11-14 03:04:24,686 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1307097772] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 03:04:24,687 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1993514235] [2024-11-14 03:04:24,687 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-14 03:04:24,687 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 03:04:24,687 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a55227d7-7e76-4ee9-9ae9-d9948a0c4017/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 03:04:24,688 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a55227d7-7e76-4ee9-9ae9-d9948a0c4017/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 03:04:24,690 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a55227d7-7e76-4ee9-9ae9-d9948a0c4017/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2024-11-14 03:04:24,867 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 7 check-sat command(s) [2024-11-14 03:04:24,867 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-14 03:04:24,868 INFO L255 TraceCheckSpWp]: Trace formula consists of 182 conjuncts, 8 conjuncts are in the unsatisfiable core [2024-11-14 03:04:24,870 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 03:04:24,975 INFO L134 CoverageAnalysis]: Checked inductivity of 55 backedges. 9 proven. 27 refuted. 0 times theorem prover too weak. 19 trivial. 0 not checked. [2024-11-14 03:04:24,975 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 03:04:25,064 INFO L134 CoverageAnalysis]: Checked inductivity of 55 backedges. 5 proven. 27 refuted. 0 times theorem prover too weak. 23 trivial. 0 not checked. [2024-11-14 03:04:25,064 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1993514235] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 03:04:25,064 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [894629010] [2024-11-14 03:04:25,066 INFO L159 IcfgInterpreter]: Started Sifa with 23 locations of interest [2024-11-14 03:04:25,066 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 03:04:25,067 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 03:04:25,067 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 03:04:25,067 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 03:04:25,775 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 1 for LOIs [2024-11-14 03:04:25,776 INFO L197 IcfgInterpreter]: Interpreting procedure outerBoundaryPatternCheck with input of size 83 for LOIs [2024-11-14 03:04:25,800 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 03:04:27,054 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '2896#true' at error location [2024-11-14 03:04:27,054 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 03:04:27,054 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-14 03:04:27,054 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9, 9] total 17 [2024-11-14 03:04:27,054 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [426587957] [2024-11-14 03:04:27,054 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-14 03:04:27,055 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2024-11-14 03:04:27,055 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 03:04:27,055 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2024-11-14 03:04:27,055 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=133, Invalid=989, Unknown=0, NotChecked=0, Total=1122 [2024-11-14 03:04:27,056 INFO L87 Difference]: Start difference. First operand 123 states and 161 transitions. Second operand has 17 states, 17 states have (on average 3.3529411764705883) internal successors, (57), 17 states have internal predecessors, (57), 3 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (10), 3 states have call predecessors, (10), 3 states have call successors, (10) [2024-11-14 03:04:27,739 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 03:04:27,739 INFO L93 Difference]: Finished difference Result 230 states and 292 transitions. [2024-11-14 03:04:27,740 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 26 states. [2024-11-14 03:04:27,740 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 17 states have (on average 3.3529411764705883) internal successors, (57), 17 states have internal predecessors, (57), 3 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (10), 3 states have call predecessors, (10), 3 states have call successors, (10) Word has length 42 [2024-11-14 03:04:27,740 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 03:04:27,741 INFO L225 Difference]: With dead ends: 230 [2024-11-14 03:04:27,741 INFO L226 Difference]: Without dead ends: 164 [2024-11-14 03:04:27,742 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 151 GetRequests, 95 SyntacticMatches, 6 SemanticMatches, 50 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 931 ImplicationChecksByTransitivity, 1.7s TimeCoverageRelationStatistics Valid=379, Invalid=2273, Unknown=0, NotChecked=0, Total=2652 [2024-11-14 03:04:27,743 INFO L432 NwaCegarLoop]: 37 mSDtfsCounter, 29 mSDsluCounter, 276 mSDsCounter, 0 mSdLazyCounter, 408 mSolverCounterSat, 20 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 29 SdHoareTripleChecker+Valid, 313 SdHoareTripleChecker+Invalid, 428 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 20 IncrementalHoareTripleChecker+Valid, 408 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-11-14 03:04:27,745 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [29 Valid, 313 Invalid, 428 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [20 Valid, 408 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-11-14 03:04:27,745 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 164 states. [2024-11-14 03:04:27,787 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 164 to 121. [2024-11-14 03:04:27,788 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 121 states, 94 states have (on average 1.2659574468085106) internal successors, (119), 95 states have internal predecessors, (119), 17 states have call successors, (17), 9 states have call predecessors, (17), 9 states have return successors, (17), 16 states have call predecessors, (17), 17 states have call successors, (17) [2024-11-14 03:04:27,789 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 121 states to 121 states and 153 transitions. [2024-11-14 03:04:27,789 INFO L78 Accepts]: Start accepts. Automaton has 121 states and 153 transitions. Word has length 42 [2024-11-14 03:04:27,789 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 03:04:27,789 INFO L471 AbstractCegarLoop]: Abstraction has 121 states and 153 transitions. [2024-11-14 03:04:27,789 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 17 states have (on average 3.3529411764705883) internal successors, (57), 17 states have internal predecessors, (57), 3 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (10), 3 states have call predecessors, (10), 3 states have call successors, (10) [2024-11-14 03:04:27,789 INFO L276 IsEmpty]: Start isEmpty. Operand 121 states and 153 transitions. [2024-11-14 03:04:27,790 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 45 [2024-11-14 03:04:27,791 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 03:04:27,791 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 03:04:27,796 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a55227d7-7e76-4ee9-9ae9-d9948a0c4017/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2024-11-14 03:04:27,991 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,7 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a55227d7-7e76-4ee9-9ae9-d9948a0c4017/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 03:04:27,991 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 03:04:27,992 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 03:04:27,992 INFO L85 PathProgramCache]: Analyzing trace with hash -1762521255, now seen corresponding path program 1 times [2024-11-14 03:04:27,992 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 03:04:27,992 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [216029970] [2024-11-14 03:04:27,992 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 03:04:27,992 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 03:04:28,024 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 03:04:28,461 INFO L134 CoverageAnalysis]: Checked inductivity of 44 backedges. 3 proven. 14 refuted. 0 times theorem prover too weak. 27 trivial. 0 not checked. [2024-11-14 03:04:28,461 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 03:04:28,461 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [216029970] [2024-11-14 03:04:28,461 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [216029970] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 03:04:28,461 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1021222310] [2024-11-14 03:04:28,462 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 03:04:28,462 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 03:04:28,462 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a55227d7-7e76-4ee9-9ae9-d9948a0c4017/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 03:04:28,464 INFO L229 MonitoredProcess]: Starting monitored process 8 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a55227d7-7e76-4ee9-9ae9-d9948a0c4017/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 03:04:28,465 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a55227d7-7e76-4ee9-9ae9-d9948a0c4017/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2024-11-14 03:04:28,549 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 03:04:28,551 INFO L255 TraceCheckSpWp]: Trace formula consists of 184 conjuncts, 20 conjuncts are in the unsatisfiable core [2024-11-14 03:04:28,553 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 03:04:28,752 INFO L134 CoverageAnalysis]: Checked inductivity of 44 backedges. 7 proven. 14 refuted. 0 times theorem prover too weak. 23 trivial. 0 not checked. [2024-11-14 03:04:28,752 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 03:04:29,055 INFO L134 CoverageAnalysis]: Checked inductivity of 44 backedges. 12 proven. 5 refuted. 0 times theorem prover too weak. 27 trivial. 0 not checked. [2024-11-14 03:04:29,055 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1021222310] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 03:04:29,055 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [929039421] [2024-11-14 03:04:29,057 INFO L159 IcfgInterpreter]: Started Sifa with 25 locations of interest [2024-11-14 03:04:29,057 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 03:04:29,057 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 03:04:29,057 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 03:04:29,057 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 03:04:29,918 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 1 for LOIs [2024-11-14 03:04:29,919 INFO L197 IcfgInterpreter]: Interpreting procedure outerBoundaryPatternCheck with input of size 9 for LOIs [2024-11-14 03:04:29,922 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 03:04:32,083 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '3836#true' at error location [2024-11-14 03:04:32,083 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 03:04:32,083 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-14 03:04:32,083 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 13, 11] total 27 [2024-11-14 03:04:32,083 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [851818438] [2024-11-14 03:04:32,083 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-14 03:04:32,084 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 27 states [2024-11-14 03:04:32,084 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 03:04:32,084 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 27 interpolants. [2024-11-14 03:04:32,085 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=183, Invalid=1686, Unknown=23, NotChecked=0, Total=1892 [2024-11-14 03:04:32,085 INFO L87 Difference]: Start difference. First operand 121 states and 153 transitions. Second operand has 27 states, 17 states have (on average 2.8823529411764706) internal successors, (49), 22 states have internal predecessors, (49), 8 states have call successors, (12), 3 states have call predecessors, (12), 9 states have return successors, (13), 8 states have call predecessors, (13), 8 states have call successors, (13) [2024-11-14 03:04:32,632 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 03:04:32,632 INFO L93 Difference]: Finished difference Result 156 states and 189 transitions. [2024-11-14 03:04:32,633 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2024-11-14 03:04:32,633 INFO L78 Accepts]: Start accepts. Automaton has has 27 states, 17 states have (on average 2.8823529411764706) internal successors, (49), 22 states have internal predecessors, (49), 8 states have call successors, (12), 3 states have call predecessors, (12), 9 states have return successors, (13), 8 states have call predecessors, (13), 8 states have call successors, (13) Word has length 44 [2024-11-14 03:04:32,633 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 03:04:32,634 INFO L225 Difference]: With dead ends: 156 [2024-11-14 03:04:32,634 INFO L226 Difference]: Without dead ends: 107 [2024-11-14 03:04:32,635 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 150 GetRequests, 98 SyntacticMatches, 2 SemanticMatches, 50 ConstructedPredicates, 0 IntricatePredicates, 1 DeprecatedPredicates, 784 ImplicationChecksByTransitivity, 2.7s TimeCoverageRelationStatistics Valid=267, Invalid=2354, Unknown=31, NotChecked=0, Total=2652 [2024-11-14 03:04:32,636 INFO L432 NwaCegarLoop]: 13 mSDtfsCounter, 78 mSDsluCounter, 132 mSDsCounter, 0 mSdLazyCounter, 430 mSolverCounterSat, 27 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 83 SdHoareTripleChecker+Valid, 145 SdHoareTripleChecker+Invalid, 457 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 27 IncrementalHoareTripleChecker+Valid, 430 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-11-14 03:04:32,636 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [83 Valid, 145 Invalid, 457 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [27 Valid, 430 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-11-14 03:04:32,637 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 107 states. [2024-11-14 03:04:32,670 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 107 to 86. [2024-11-14 03:04:32,670 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 86 states, 72 states have (on average 1.2638888888888888) internal successors, (91), 72 states have internal predecessors, (91), 8 states have call successors, (8), 5 states have call predecessors, (8), 5 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2024-11-14 03:04:32,671 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 86 states to 86 states and 107 transitions. [2024-11-14 03:04:32,671 INFO L78 Accepts]: Start accepts. Automaton has 86 states and 107 transitions. Word has length 44 [2024-11-14 03:04:32,671 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 03:04:32,671 INFO L471 AbstractCegarLoop]: Abstraction has 86 states and 107 transitions. [2024-11-14 03:04:32,672 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 27 states, 17 states have (on average 2.8823529411764706) internal successors, (49), 22 states have internal predecessors, (49), 8 states have call successors, (12), 3 states have call predecessors, (12), 9 states have return successors, (13), 8 states have call predecessors, (13), 8 states have call successors, (13) [2024-11-14 03:04:32,672 INFO L276 IsEmpty]: Start isEmpty. Operand 86 states and 107 transitions. [2024-11-14 03:04:32,673 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 45 [2024-11-14 03:04:32,673 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 03:04:32,673 INFO L215 NwaCegarLoop]: trace histogram [6, 4, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 03:04:32,689 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a55227d7-7e76-4ee9-9ae9-d9948a0c4017/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2024-11-14 03:04:32,873 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,8 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a55227d7-7e76-4ee9-9ae9-d9948a0c4017/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 03:04:32,873 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 03:04:32,874 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 03:04:32,874 INFO L85 PathProgramCache]: Analyzing trace with hash 1321040953, now seen corresponding path program 6 times [2024-11-14 03:04:32,874 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 03:04:32,874 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [783848332] [2024-11-14 03:04:32,874 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 03:04:32,874 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 03:04:32,897 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 03:04:33,064 INFO L134 CoverageAnalysis]: Checked inductivity of 66 backedges. 24 proven. 23 refuted. 0 times theorem prover too weak. 19 trivial. 0 not checked. [2024-11-14 03:04:33,064 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 03:04:33,065 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [783848332] [2024-11-14 03:04:33,065 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [783848332] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 03:04:33,065 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2076326326] [2024-11-14 03:04:33,066 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-14 03:04:33,066 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 03:04:33,066 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a55227d7-7e76-4ee9-9ae9-d9948a0c4017/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 03:04:33,068 INFO L229 MonitoredProcess]: Starting monitored process 9 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a55227d7-7e76-4ee9-9ae9-d9948a0c4017/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 03:04:33,070 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a55227d7-7e76-4ee9-9ae9-d9948a0c4017/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2024-11-14 03:04:33,155 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-14 03:04:33,155 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-14 03:04:33,156 INFO L255 TraceCheckSpWp]: Trace formula consists of 139 conjuncts, 8 conjuncts are in the unsatisfiable core [2024-11-14 03:04:33,158 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 03:04:33,258 INFO L134 CoverageAnalysis]: Checked inductivity of 66 backedges. 39 proven. 12 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2024-11-14 03:04:33,258 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 03:04:33,334 INFO L134 CoverageAnalysis]: Checked inductivity of 66 backedges. 35 proven. 12 refuted. 0 times theorem prover too weak. 19 trivial. 0 not checked. [2024-11-14 03:04:33,334 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2076326326] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 03:04:33,334 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1824649239] [2024-11-14 03:04:33,336 INFO L159 IcfgInterpreter]: Started Sifa with 23 locations of interest [2024-11-14 03:04:33,336 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 03:04:33,336 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 03:04:33,336 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 03:04:33,336 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 03:04:34,053 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 1 for LOIs [2024-11-14 03:04:34,054 INFO L197 IcfgInterpreter]: Interpreting procedure outerBoundaryPatternCheck with input of size 83 for LOIs [2024-11-14 03:04:34,077 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 03:04:35,605 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '4855#(exists ((|v_ULTIMATE.start_main_~row~0#1_153| Int)) (and (<= ~ARR_SIZE~0 |v_ULTIMATE.start_main_~row~0#1_153|) (<= 1 ~ARR_SIZE~0)))' at error location [2024-11-14 03:04:35,605 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 03:04:35,605 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-14 03:04:35,605 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9, 9] total 14 [2024-11-14 03:04:35,605 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2022932308] [2024-11-14 03:04:35,606 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-14 03:04:35,606 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2024-11-14 03:04:35,606 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 03:04:35,606 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2024-11-14 03:04:35,607 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=120, Invalid=936, Unknown=0, NotChecked=0, Total=1056 [2024-11-14 03:04:35,607 INFO L87 Difference]: Start difference. First operand 86 states and 107 transitions. Second operand has 14 states, 14 states have (on average 3.2857142857142856) internal successors, (46), 14 states have internal predecessors, (46), 2 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2024-11-14 03:04:35,947 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 03:04:35,948 INFO L93 Difference]: Finished difference Result 101 states and 121 transitions. [2024-11-14 03:04:35,948 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2024-11-14 03:04:35,948 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 3.2857142857142856) internal successors, (46), 14 states have internal predecessors, (46), 2 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 44 [2024-11-14 03:04:35,949 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 03:04:35,949 INFO L225 Difference]: With dead ends: 101 [2024-11-14 03:04:35,949 INFO L226 Difference]: Without dead ends: 67 [2024-11-14 03:04:35,950 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 148 GetRequests, 102 SyntacticMatches, 6 SemanticMatches, 40 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 578 ImplicationChecksByTransitivity, 1.7s TimeCoverageRelationStatistics Valid=210, Invalid=1512, Unknown=0, NotChecked=0, Total=1722 [2024-11-14 03:04:35,951 INFO L432 NwaCegarLoop]: 20 mSDtfsCounter, 7 mSDsluCounter, 94 mSDsCounter, 0 mSdLazyCounter, 183 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 114 SdHoareTripleChecker+Invalid, 196 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 183 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-14 03:04:35,951 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 114 Invalid, 196 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 183 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-14 03:04:35,952 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 67 states. [2024-11-14 03:04:35,986 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 67 to 64. [2024-11-14 03:04:35,986 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 64 states, 55 states have (on average 1.2545454545454546) internal successors, (69), 55 states have internal predecessors, (69), 5 states have call successors, (5), 3 states have call predecessors, (5), 3 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2024-11-14 03:04:35,987 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 64 states to 64 states and 79 transitions. [2024-11-14 03:04:35,987 INFO L78 Accepts]: Start accepts. Automaton has 64 states and 79 transitions. Word has length 44 [2024-11-14 03:04:35,987 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 03:04:35,987 INFO L471 AbstractCegarLoop]: Abstraction has 64 states and 79 transitions. [2024-11-14 03:04:35,988 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 3.2857142857142856) internal successors, (46), 14 states have internal predecessors, (46), 2 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2024-11-14 03:04:35,988 INFO L276 IsEmpty]: Start isEmpty. Operand 64 states and 79 transitions. [2024-11-14 03:04:35,988 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 52 [2024-11-14 03:04:35,988 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 03:04:35,989 INFO L215 NwaCegarLoop]: trace histogram [9, 6, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 03:04:36,009 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a55227d7-7e76-4ee9-9ae9-d9948a0c4017/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2024-11-14 03:04:36,189 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a55227d7-7e76-4ee9-9ae9-d9948a0c4017/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2024-11-14 03:04:36,189 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 03:04:36,190 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 03:04:36,190 INFO L85 PathProgramCache]: Analyzing trace with hash -68206801, now seen corresponding path program 7 times [2024-11-14 03:04:36,190 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 03:04:36,190 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1025808767] [2024-11-14 03:04:36,190 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 03:04:36,190 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 03:04:36,220 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 03:04:36,413 INFO L134 CoverageAnalysis]: Checked inductivity of 120 backedges. 25 proven. 32 refuted. 0 times theorem prover too weak. 63 trivial. 0 not checked. [2024-11-14 03:04:36,414 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 03:04:36,414 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1025808767] [2024-11-14 03:04:36,414 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1025808767] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 03:04:36,414 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [520746066] [2024-11-14 03:04:36,414 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2024-11-14 03:04:36,414 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 03:04:36,414 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a55227d7-7e76-4ee9-9ae9-d9948a0c4017/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 03:04:36,416 INFO L229 MonitoredProcess]: Starting monitored process 10 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a55227d7-7e76-4ee9-9ae9-d9948a0c4017/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 03:04:36,420 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a55227d7-7e76-4ee9-9ae9-d9948a0c4017/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2024-11-14 03:04:36,524 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 03:04:36,525 INFO L255 TraceCheckSpWp]: Trace formula consists of 235 conjuncts, 8 conjuncts are in the unsatisfiable core [2024-11-14 03:04:36,527 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 03:04:36,636 INFO L134 CoverageAnalysis]: Checked inductivity of 120 backedges. 31 proven. 30 refuted. 0 times theorem prover too weak. 59 trivial. 0 not checked. [2024-11-14 03:04:36,636 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 03:04:36,749 INFO L134 CoverageAnalysis]: Checked inductivity of 120 backedges. 27 proven. 30 refuted. 0 times theorem prover too weak. 63 trivial. 0 not checked. [2024-11-14 03:04:36,750 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [520746066] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 03:04:36,750 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1150932378] [2024-11-14 03:04:36,752 INFO L159 IcfgInterpreter]: Started Sifa with 23 locations of interest [2024-11-14 03:04:36,752 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 03:04:36,752 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 03:04:36,752 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 03:04:36,752 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 03:04:37,524 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 1 for LOIs [2024-11-14 03:04:37,525 INFO L197 IcfgInterpreter]: Interpreting procedure outerBoundaryPatternCheck with input of size 83 for LOIs [2024-11-14 03:04:37,541 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 03:04:38,877 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '5189#true' at error location [2024-11-14 03:04:38,877 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 03:04:38,877 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-14 03:04:38,877 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9, 9] total 14 [2024-11-14 03:04:38,877 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1546458040] [2024-11-14 03:04:38,877 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-14 03:04:38,878 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2024-11-14 03:04:38,878 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 03:04:38,878 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2024-11-14 03:04:38,879 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=119, Invalid=811, Unknown=0, NotChecked=0, Total=930 [2024-11-14 03:04:38,879 INFO L87 Difference]: Start difference. First operand 64 states and 79 transitions. Second operand has 14 states, 14 states have (on average 2.7142857142857144) internal successors, (38), 14 states have internal predecessors, (38), 2 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2024-11-14 03:04:39,062 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 03:04:39,062 INFO L93 Difference]: Finished difference Result 67 states and 81 transitions. [2024-11-14 03:04:39,063 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-14 03:04:39,063 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 2.7142857142857144) internal successors, (38), 14 states have internal predecessors, (38), 2 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 51 [2024-11-14 03:04:39,063 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 03:04:39,064 INFO L225 Difference]: With dead ends: 67 [2024-11-14 03:04:39,064 INFO L226 Difference]: Without dead ends: 55 [2024-11-14 03:04:39,064 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 163 GetRequests, 125 SyntacticMatches, 6 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 405 ImplicationChecksByTransitivity, 1.5s TimeCoverageRelationStatistics Valid=146, Invalid=976, Unknown=0, NotChecked=0, Total=1122 [2024-11-14 03:04:39,065 INFO L432 NwaCegarLoop]: 20 mSDtfsCounter, 11 mSDsluCounter, 95 mSDsCounter, 0 mSdLazyCounter, 190 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 115 SdHoareTripleChecker+Invalid, 203 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 190 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-14 03:04:39,065 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 115 Invalid, 203 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 190 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-14 03:04:39,065 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 55 states. [2024-11-14 03:04:39,080 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 55 to 55. [2024-11-14 03:04:39,080 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 55 states, 46 states have (on average 1.2173913043478262) internal successors, (56), 46 states have internal predecessors, (56), 5 states have call successors, (5), 3 states have call predecessors, (5), 3 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2024-11-14 03:04:39,081 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 55 states to 55 states and 66 transitions. [2024-11-14 03:04:39,081 INFO L78 Accepts]: Start accepts. Automaton has 55 states and 66 transitions. Word has length 51 [2024-11-14 03:04:39,081 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 03:04:39,081 INFO L471 AbstractCegarLoop]: Abstraction has 55 states and 66 transitions. [2024-11-14 03:04:39,081 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 2.7142857142857144) internal successors, (38), 14 states have internal predecessors, (38), 2 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2024-11-14 03:04:39,082 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 66 transitions. [2024-11-14 03:04:39,082 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 55 [2024-11-14 03:04:39,082 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 03:04:39,082 INFO L215 NwaCegarLoop]: trace histogram [9, 9, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 03:04:39,103 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a55227d7-7e76-4ee9-9ae9-d9948a0c4017/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2024-11-14 03:04:39,283 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a55227d7-7e76-4ee9-9ae9-d9948a0c4017/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2024-11-14 03:04:39,283 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 03:04:39,283 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 03:04:39,284 INFO L85 PathProgramCache]: Analyzing trace with hash 1339160589, now seen corresponding path program 8 times [2024-11-14 03:04:39,284 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 03:04:39,284 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1638417297] [2024-11-14 03:04:39,284 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 03:04:39,284 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 03:04:39,314 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 03:04:39,316 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [182765330] [2024-11-14 03:04:39,316 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-14 03:04:39,316 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 03:04:39,317 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a55227d7-7e76-4ee9-9ae9-d9948a0c4017/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 03:04:39,319 INFO L229 MonitoredProcess]: Starting monitored process 11 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a55227d7-7e76-4ee9-9ae9-d9948a0c4017/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 03:04:39,321 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a55227d7-7e76-4ee9-9ae9-d9948a0c4017/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2024-11-14 03:04:41,156 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 11 check-sat command(s) [2024-11-14 03:04:41,156 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-14 03:04:41,160 WARN L253 TraceCheckSpWp]: Trace formula consists of 256 conjuncts, 134 conjuncts are in the unsatisfiable core [2024-11-14 03:04:41,166 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 03:04:41,220 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 11 treesize of output 7 [2024-11-14 03:04:41,245 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 18 [2024-11-14 03:04:41,287 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-14 03:04:41,287 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 26 treesize of output 28 [2024-11-14 03:04:41,424 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:41,425 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:41,426 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:41,429 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-14 03:04:41,430 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 6 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 35 treesize of output 40 [2024-11-14 03:04:41,493 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:41,495 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:41,496 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:41,500 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:41,504 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:41,505 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:41,507 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-14 03:04:41,507 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 4 select indices, 4 select index equivalence classes, 10 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 46 treesize of output 54 [2024-11-14 03:04:41,579 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:41,580 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:41,581 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:41,583 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:41,584 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:41,586 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:41,587 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:41,588 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:41,589 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:41,591 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-14 03:04:41,592 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 5 select indices, 5 select index equivalence classes, 15 disjoint index pairs (out of 10 index pairs), introduced 5 new quantified variables, introduced 10 case distinctions, treesize of input 57 treesize of output 68 [2024-11-14 03:04:41,810 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:41,811 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:41,812 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:41,813 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:41,814 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:41,816 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:41,817 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:41,818 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:41,819 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:41,820 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:41,822 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:41,823 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:41,824 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:41,824 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:41,830 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-14 03:04:41,830 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 6 select indices, 6 select index equivalence classes, 21 disjoint index pairs (out of 15 index pairs), introduced 6 new quantified variables, introduced 15 case distinctions, treesize of input 66 treesize of output 80 [2024-11-14 03:04:41,926 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:41,928 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:41,930 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:41,931 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:41,932 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:41,933 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:41,935 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:41,936 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:41,937 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:41,938 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:41,940 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:41,941 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:41,942 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:41,944 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:41,945 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:41,946 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:41,948 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:41,949 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:41,952 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-14 03:04:41,953 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 7 select indices, 7 select index equivalence classes, 28 disjoint index pairs (out of 21 index pairs), introduced 7 new quantified variables, introduced 21 case distinctions, treesize of input 77 treesize of output 94 [2024-11-14 03:04:42,062 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:42,063 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:42,065 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:42,066 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:42,067 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:42,069 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:42,070 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:42,071 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:42,073 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:42,074 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:42,075 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:42,076 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:42,078 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:42,079 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:42,080 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:42,081 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:42,083 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:42,084 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:42,085 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:42,087 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:42,088 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:42,089 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:42,090 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:42,094 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-14 03:04:42,094 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 8 select indices, 8 select index equivalence classes, 36 disjoint index pairs (out of 28 index pairs), introduced 8 new quantified variables, introduced 28 case distinctions, treesize of input 88 treesize of output 108 [2024-11-14 03:04:43,878 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:43,885 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:43,888 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:43,896 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:43,897 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:43,898 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:43,900 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:43,901 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:43,902 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:43,903 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:43,904 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:43,905 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:43,906 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:43,908 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:43,909 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:43,910 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:43,911 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:43,912 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:43,913 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:43,915 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:43,916 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:43,917 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:43,918 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:43,919 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:43,920 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:43,924 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:44,198 INFO L349 Elim1Store]: treesize reduction 656, result has 13.8 percent of original size [2024-11-14 03:04:44,198 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 19 select indices, 19 select index equivalence classes, 39 disjoint index pairs (out of 171 index pairs), introduced 19 new quantified variables, introduced 183 case distinctions, treesize of input 198 treesize of output 236 [2024-11-14 03:04:45,986 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:45,988 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:45,989 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:45,990 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:45,992 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:45,993 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:45,994 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:45,996 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:45,997 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:45,998 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:45,999 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:46,001 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:46,002 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:46,003 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:46,005 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:46,006 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:46,007 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:46,008 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:46,009 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:46,011 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:46,012 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:46,013 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:46,014 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 03:04:46,017 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-14 03:04:46,017 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 9 select indices, 9 select index equivalence classes, 36 disjoint index pairs (out of 36 index pairs), introduced 9 new quantified variables, introduced 36 case distinctions, treesize of input 84 treesize of output 28 [2024-11-14 03:04:46,164 INFO L134 CoverageAnalysis]: Checked inductivity of 150 backedges. 5 proven. 144 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-14 03:04:46,164 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 03:04:54,593 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 785 treesize of output 767 [2024-11-14 03:04:55,258 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-14 03:04:55,275 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 9 select indices, 9 select index equivalence classes, 0 disjoint index pairs (out of 36 index pairs), introduced 9 new quantified variables, introduced 36 case distinctions, treesize of input 750359092232751 treesize of output 712975696888367