./Ultimate.py --spec ../../sv-benchmarks/c/properties/unreach-call.prp --file ../../sv-benchmarks/c/aws-c-common/aws_linked_list_front_harness.i --full-output --architecture 64bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version cf1a7837 Calling Ultimate with: /usr/lib/jvm/java-1.11.0-openjdk-amd64/bin/java -Dosgi.configuration.area=/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89d3aef9-3936-4957-a177-31ac795c3954/bin/utaipan-verify-NcY6lQBIFX/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89d3aef9-3936-4957-a177-31ac795c3954/bin/utaipan-verify-NcY6lQBIFX/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89d3aef9-3936-4957-a177-31ac795c3954/bin/utaipan-verify-NcY6lQBIFX/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89d3aef9-3936-4957-a177-31ac795c3954/bin/utaipan-verify-NcY6lQBIFX/config/TaipanReach.xml -i ../../sv-benchmarks/c/aws-c-common/aws_linked_list_front_harness.i -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89d3aef9-3936-4957-a177-31ac795c3954/bin/utaipan-verify-NcY6lQBIFX/config/svcomp-Reach-64bit-Taipan_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89d3aef9-3936-4957-a177-31ac795c3954/bin/utaipan-verify-NcY6lQBIFX --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 64bit --witnessprinter.graph.data.programhash 61592663790a1842b8bd7e9befeca1c276604b90aee8701db027349608c78395 --- Real Ultimate output --- This is Ultimate 0.2.3-dev-cf1a783 [2023-11-12 00:49:56,948 INFO L188 SettingsManager]: Resetting all preferences to default values... [2023-11-12 00:49:57,080 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89d3aef9-3936-4957-a177-31ac795c3954/bin/utaipan-verify-NcY6lQBIFX/config/svcomp-Reach-64bit-Taipan_Default.epf [2023-11-12 00:49:57,092 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2023-11-12 00:49:57,093 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2023-11-12 00:49:57,132 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2023-11-12 00:49:57,132 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2023-11-12 00:49:57,133 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2023-11-12 00:49:57,134 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2023-11-12 00:49:57,139 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2023-11-12 00:49:57,140 INFO L153 SettingsManager]: * User list type=DISABLED [2023-11-12 00:49:57,141 INFO L151 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2023-11-12 00:49:57,142 INFO L153 SettingsManager]: * Explicit value domain=true [2023-11-12 00:49:57,144 INFO L153 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2023-11-12 00:49:57,144 INFO L153 SettingsManager]: * Octagon Domain=false [2023-11-12 00:49:57,145 INFO L153 SettingsManager]: * Abstract domain=CompoundDomain [2023-11-12 00:49:57,145 INFO L153 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2023-11-12 00:49:57,146 INFO L153 SettingsManager]: * Use the RCFG-of-the-future interface=true [2023-11-12 00:49:57,146 INFO L153 SettingsManager]: * Interval Domain=false [2023-11-12 00:49:57,147 INFO L151 SettingsManager]: Preferences of Sifa differ from their defaults: [2023-11-12 00:49:57,147 INFO L153 SettingsManager]: * Call Summarizer=TopInputCallSummarizer [2023-11-12 00:49:57,148 INFO L153 SettingsManager]: * Simplification Technique=POLY_PAC [2023-11-12 00:49:57,149 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2023-11-12 00:49:57,150 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2023-11-12 00:49:57,150 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2023-11-12 00:49:57,151 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2023-11-12 00:49:57,152 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2023-11-12 00:49:57,152 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2023-11-12 00:49:57,153 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2023-11-12 00:49:57,153 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2023-11-12 00:49:57,154 INFO L153 SettingsManager]: * Use constant arrays=true [2023-11-12 00:49:57,155 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2023-11-12 00:49:57,155 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2023-11-12 00:49:57,156 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-11-12 00:49:57,156 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2023-11-12 00:49:57,156 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2023-11-12 00:49:57,157 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2023-11-12 00:49:57,157 INFO L153 SettingsManager]: * Trace refinement strategy=SIFA_TAIPAN [2023-11-12 00:49:57,157 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2023-11-12 00:49:57,158 INFO L153 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2023-11-12 00:49:57,158 INFO L153 SettingsManager]: * Trace refinement exception blacklist=NONE [2023-11-12 00:49:57,158 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2023-11-12 00:49:57,159 INFO L153 SettingsManager]: * Abstract interpretation Mode=USE_PREDICATES WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89d3aef9-3936-4957-a177-31ac795c3954/bin/utaipan-verify-NcY6lQBIFX/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Entry function -> main Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness directory -> /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89d3aef9-3936-4957-a177-31ac795c3954/bin/utaipan-verify-NcY6lQBIFX 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 -> 64bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> 61592663790a1842b8bd7e9befeca1c276604b90aee8701db027349608c78395 [2023-11-12 00:49:57,484 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2023-11-12 00:49:57,519 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2023-11-12 00:49:57,522 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2023-11-12 00:49:57,524 INFO L270 PluginConnector]: Initializing CDTParser... [2023-11-12 00:49:57,524 INFO L274 PluginConnector]: CDTParser initialized [2023-11-12 00:49:57,526 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89d3aef9-3936-4957-a177-31ac795c3954/bin/utaipan-verify-NcY6lQBIFX/../../sv-benchmarks/c/aws-c-common/aws_linked_list_front_harness.i [2023-11-12 00:50:00,660 INFO L533 CDTParser]: Created temporary CDT project at NULL [2023-11-12 00:50:01,168 INFO L384 CDTParser]: Found 1 translation units. [2023-11-12 00:50:01,169 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89d3aef9-3936-4957-a177-31ac795c3954/sv-benchmarks/c/aws-c-common/aws_linked_list_front_harness.i [2023-11-12 00:50:01,214 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89d3aef9-3936-4957-a177-31ac795c3954/bin/utaipan-verify-NcY6lQBIFX/data/234a58ad1/c171c3ed5ce747b4a172f39fca7320ef/FLAG3ef15c61d [2023-11-12 00:50:01,233 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89d3aef9-3936-4957-a177-31ac795c3954/bin/utaipan-verify-NcY6lQBIFX/data/234a58ad1/c171c3ed5ce747b4a172f39fca7320ef [2023-11-12 00:50:01,239 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2023-11-12 00:50:01,241 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2023-11-12 00:50:01,244 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2023-11-12 00:50:01,245 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2023-11-12 00:50:01,250 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2023-11-12 00:50:01,251 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 12.11 12:50:01" (1/1) ... [2023-11-12 00:50:01,253 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@12d9febd and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:50:01, skipping insertion in model container [2023-11-12 00:50:01,253 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 12.11 12:50:01" (1/1) ... [2023-11-12 00:50:01,412 INFO L177 MainTranslator]: Built tables and reachable declarations [2023-11-12 00:50:01,716 WARN L240 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89d3aef9-3936-4957-a177-31ac795c3954/sv-benchmarks/c/aws-c-common/aws_linked_list_front_harness.i[4495,4508] [2023-11-12 00:50:01,727 WARN L240 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89d3aef9-3936-4957-a177-31ac795c3954/sv-benchmarks/c/aws-c-common/aws_linked_list_front_harness.i[4555,4568] [2023-11-12 00:50:02,723 WARN L1577 CHandler]: Possible shadowing of function index [2023-11-12 00:50:02,724 WARN L1577 CHandler]: Possible shadowing of function index [2023-11-12 00:50:02,725 WARN L1577 CHandler]: Possible shadowing of function index [2023-11-12 00:50:02,727 WARN L1577 CHandler]: Possible shadowing of function index [2023-11-12 00:50:02,730 WARN L1577 CHandler]: Possible shadowing of function index [2023-11-12 00:50:02,759 WARN L1577 CHandler]: Possible shadowing of function index [2023-11-12 00:50:02,769 WARN L1577 CHandler]: Possible shadowing of function index [2023-11-12 00:50:02,772 WARN L1577 CHandler]: Possible shadowing of function index [2023-11-12 00:50:02,774 WARN L1577 CHandler]: Possible shadowing of function index [2023-11-12 00:50:02,776 WARN L1577 CHandler]: Possible shadowing of function index [2023-11-12 00:50:02,779 WARN L1577 CHandler]: Possible shadowing of function index [2023-11-12 00:50:02,781 WARN L1577 CHandler]: Possible shadowing of function index [2023-11-12 00:50:02,782 WARN L1577 CHandler]: Possible shadowing of function index [2023-11-12 00:50:03,106 WARN L635 FunctionHandler]: implicit declaration of function __atomic_load_n [2023-11-12 00:50:03,108 WARN L635 FunctionHandler]: implicit declaration of function __atomic_store_n [2023-11-12 00:50:03,109 WARN L635 FunctionHandler]: implicit declaration of function __atomic_exchange_n [2023-11-12 00:50:03,110 WARN L635 FunctionHandler]: implicit declaration of function __atomic_compare_exchange_n [2023-11-12 00:50:03,112 WARN L635 FunctionHandler]: implicit declaration of function __atomic_fetch_add [2023-11-12 00:50:03,113 WARN L635 FunctionHandler]: implicit declaration of function __atomic_fetch_sub [2023-11-12 00:50:03,113 WARN L635 FunctionHandler]: implicit declaration of function __atomic_fetch_or [2023-11-12 00:50:03,114 WARN L635 FunctionHandler]: implicit declaration of function __atomic_fetch_and [2023-11-12 00:50:03,115 WARN L635 FunctionHandler]: implicit declaration of function __atomic_fetch_xor [2023-11-12 00:50:03,115 WARN L635 FunctionHandler]: implicit declaration of function __atomic_thread_fence [2023-11-12 00:50:03,337 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-12 00:50:03,358 INFO L202 MainTranslator]: Completed pre-run [2023-11-12 00:50:03,385 WARN L240 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89d3aef9-3936-4957-a177-31ac795c3954/sv-benchmarks/c/aws-c-common/aws_linked_list_front_harness.i[4495,4508] [2023-11-12 00:50:03,387 WARN L240 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89d3aef9-3936-4957-a177-31ac795c3954/sv-benchmarks/c/aws-c-common/aws_linked_list_front_harness.i[4555,4568] [2023-11-12 00:50:03,476 WARN L1577 CHandler]: Possible shadowing of function index [2023-11-12 00:50:03,477 WARN L1577 CHandler]: Possible shadowing of function index [2023-11-12 00:50:03,481 WARN L1577 CHandler]: Possible shadowing of function index [2023-11-12 00:50:03,486 WARN L1577 CHandler]: Possible shadowing of function index [2023-11-12 00:50:03,487 WARN L1577 CHandler]: Possible shadowing of function index [2023-11-12 00:50:03,496 WARN L1577 CHandler]: Possible shadowing of function index [2023-11-12 00:50:03,507 WARN L1577 CHandler]: Possible shadowing of function index [2023-11-12 00:50:03,508 WARN L1577 CHandler]: Possible shadowing of function index [2023-11-12 00:50:03,509 WARN L1577 CHandler]: Possible shadowing of function index [2023-11-12 00:50:03,510 WARN L1577 CHandler]: Possible shadowing of function index [2023-11-12 00:50:03,516 WARN L1577 CHandler]: Possible shadowing of function index [2023-11-12 00:50:03,517 WARN L1577 CHandler]: Possible shadowing of function index [2023-11-12 00:50:03,517 WARN L1577 CHandler]: Possible shadowing of function index [2023-11-12 00:50:03,552 WARN L635 FunctionHandler]: implicit declaration of function __atomic_load_n [2023-11-12 00:50:03,553 WARN L635 FunctionHandler]: implicit declaration of function __atomic_store_n [2023-11-12 00:50:03,554 WARN L635 FunctionHandler]: implicit declaration of function __atomic_exchange_n [2023-11-12 00:50:03,555 WARN L635 FunctionHandler]: implicit declaration of function __atomic_compare_exchange_n [2023-11-12 00:50:03,556 WARN L635 FunctionHandler]: implicit declaration of function __atomic_fetch_add [2023-11-12 00:50:03,557 WARN L635 FunctionHandler]: implicit declaration of function __atomic_fetch_sub [2023-11-12 00:50:03,557 WARN L635 FunctionHandler]: implicit declaration of function __atomic_fetch_or [2023-11-12 00:50:03,558 WARN L635 FunctionHandler]: implicit declaration of function __atomic_fetch_and [2023-11-12 00:50:03,558 WARN L635 FunctionHandler]: implicit declaration of function __atomic_fetch_xor [2023-11-12 00:50:03,559 WARN L635 FunctionHandler]: implicit declaration of function __atomic_thread_fence [2023-11-12 00:50:03,602 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-12 00:50:03,842 WARN L672 CHandler]: The function __atomic_fetch_or is called, but not defined or handled by StandardFunctionHandler. [2023-11-12 00:50:03,842 WARN L672 CHandler]: The function __atomic_fetch_sub is called, but not defined or handled by StandardFunctionHandler. [2023-11-12 00:50:03,843 WARN L672 CHandler]: The function __atomic_exchange_n is called, but not defined or handled by StandardFunctionHandler. [2023-11-12 00:50:03,843 WARN L672 CHandler]: The function __atomic_fetch_xor is called, but not defined or handled by StandardFunctionHandler. [2023-11-12 00:50:03,843 WARN L672 CHandler]: The function htons is called, but not defined or handled by StandardFunctionHandler. [2023-11-12 00:50:03,843 WARN L672 CHandler]: The function ntohl is called, but not defined or handled by StandardFunctionHandler. [2023-11-12 00:50:03,843 WARN L672 CHandler]: The function __atomic_compare_exchange_n is called, but not defined or handled by StandardFunctionHandler. [2023-11-12 00:50:03,844 WARN L672 CHandler]: The function __atomic_fetch_add is called, but not defined or handled by StandardFunctionHandler. [2023-11-12 00:50:03,844 WARN L672 CHandler]: The function htonl is called, but not defined or handled by StandardFunctionHandler. [2023-11-12 00:50:03,844 WARN L672 CHandler]: The function __atomic_store_n is called, but not defined or handled by StandardFunctionHandler. [2023-11-12 00:50:03,844 WARN L672 CHandler]: The function ntohs is called, but not defined or handled by StandardFunctionHandler. [2023-11-12 00:50:03,844 WARN L672 CHandler]: The function __atomic_load_n is called, but not defined or handled by StandardFunctionHandler. [2023-11-12 00:50:03,845 WARN L672 CHandler]: The function memcmp is called, but not defined or handled by StandardFunctionHandler. [2023-11-12 00:50:03,845 WARN L672 CHandler]: The function __atomic_thread_fence is called, but not defined or handled by StandardFunctionHandler. [2023-11-12 00:50:03,845 WARN L672 CHandler]: The function __atomic_fetch_and is called, but not defined or handled by StandardFunctionHandler. [2023-11-12 00:50:03,845 WARN L672 CHandler]: The function aws_array_list_ensure_capacity is called, but not defined or handled by StandardFunctionHandler. [2023-11-12 00:50:03,852 INFO L206 MainTranslator]: Completed translation [2023-11-12 00:50:03,853 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:50:03 WrapperNode [2023-11-12 00:50:03,853 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2023-11-12 00:50:03,854 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2023-11-12 00:50:03,854 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2023-11-12 00:50:03,854 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2023-11-12 00:50:03,860 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:50:03" (1/1) ... [2023-11-12 00:50:03,958 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:50:03" (1/1) ... [2023-11-12 00:50:04,000 INFO L138 Inliner]: procedures = 678, calls = 1045, calls flagged for inlining = 50, calls inlined = 5, statements flattened = 133 [2023-11-12 00:50:04,001 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2023-11-12 00:50:04,002 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2023-11-12 00:50:04,002 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2023-11-12 00:50:04,002 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2023-11-12 00:50:04,012 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:50:03" (1/1) ... [2023-11-12 00:50:04,012 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:50:03" (1/1) ... [2023-11-12 00:50:04,017 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:50:03" (1/1) ... [2023-11-12 00:50:04,017 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:50:03" (1/1) ... [2023-11-12 00:50:04,034 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:50:03" (1/1) ... [2023-11-12 00:50:04,039 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:50:03" (1/1) ... [2023-11-12 00:50:04,043 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:50:03" (1/1) ... [2023-11-12 00:50:04,046 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:50:03" (1/1) ... [2023-11-12 00:50:04,076 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2023-11-12 00:50:04,077 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2023-11-12 00:50:04,077 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2023-11-12 00:50:04,078 INFO L274 PluginConnector]: RCFGBuilder initialized [2023-11-12 00:50:04,078 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:50:03" (1/1) ... [2023-11-12 00:50:04,085 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-11-12 00:50:04,100 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89d3aef9-3936-4957-a177-31ac795c3954/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:50:04,114 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89d3aef9-3936-4957-a177-31ac795c3954/bin/utaipan-verify-NcY6lQBIFX/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2023-11-12 00:50:04,149 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89d3aef9-3936-4957-a177-31ac795c3954/bin/utaipan-verify-NcY6lQBIFX/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2023-11-12 00:50:04,159 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2023-11-12 00:50:04,160 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2023-11-12 00:50:04,160 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2023-11-12 00:50:04,161 INFO L130 BoogieDeclarations]: Found specification of procedure aws_linked_list_node_next_is_valid [2023-11-12 00:50:04,161 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_linked_list_node_next_is_valid [2023-11-12 00:50:04,161 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnHeap [2023-11-12 00:50:04,161 INFO L130 BoogieDeclarations]: Found specification of procedure aws_linked_list_is_valid [2023-11-12 00:50:04,161 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_linked_list_is_valid [2023-11-12 00:50:04,161 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2023-11-12 00:50:04,162 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$ [2023-11-12 00:50:04,162 INFO L130 BoogieDeclarations]: Found specification of procedure aws_linked_list_front [2023-11-12 00:50:04,163 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_linked_list_front [2023-11-12 00:50:04,163 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2023-11-12 00:50:04,163 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2023-11-12 00:50:04,163 INFO L130 BoogieDeclarations]: Found specification of procedure aws_linked_list_empty [2023-11-12 00:50:04,163 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_linked_list_empty [2023-11-12 00:50:04,163 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2023-11-12 00:50:04,165 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2023-11-12 00:50:04,165 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2023-11-12 00:50:04,165 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$ [2023-11-12 00:50:04,165 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$ [2023-11-12 00:50:04,166 INFO L130 BoogieDeclarations]: Found specification of procedure nondet_uint64_t [2023-11-12 00:50:04,166 INFO L138 BoogieDeclarations]: Found implementation of procedure nondet_uint64_t [2023-11-12 00:50:04,166 INFO L130 BoogieDeclarations]: Found specification of procedure aws_linked_list_node_prev_is_valid [2023-11-12 00:50:04,167 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_linked_list_node_prev_is_valid [2023-11-12 00:50:04,167 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2023-11-12 00:50:04,522 INFO L236 CfgBuilder]: Building ICFG [2023-11-12 00:50:04,526 INFO L262 CfgBuilder]: Building CFG for each procedure with an implementation [2023-11-12 00:50:04,884 INFO L277 CfgBuilder]: Performing block encoding [2023-11-12 00:50:05,086 INFO L297 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2023-11-12 00:50:05,087 INFO L302 CfgBuilder]: Removed 2 assume(true) statements. [2023-11-12 00:50:05,090 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 12.11 12:50:05 BoogieIcfgContainer [2023-11-12 00:50:05,090 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2023-11-12 00:50:05,093 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2023-11-12 00:50:05,093 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2023-11-12 00:50:05,097 INFO L274 PluginConnector]: TraceAbstraction initialized [2023-11-12 00:50:05,097 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 12.11 12:50:01" (1/3) ... [2023-11-12 00:50:05,098 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@2c83b852 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 12.11 12:50:05, skipping insertion in model container [2023-11-12 00:50:05,098 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:50:03" (2/3) ... [2023-11-12 00:50:05,099 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@2c83b852 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 12.11 12:50:05, skipping insertion in model container [2023-11-12 00:50:05,099 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 12.11 12:50:05" (3/3) ... [2023-11-12 00:50:05,101 INFO L112 eAbstractionObserver]: Analyzing ICFG aws_linked_list_front_harness.i [2023-11-12 00:50:05,121 INFO L204 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2023-11-12 00:50:05,122 INFO L163 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2023-11-12 00:50:05,197 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-11-12 00:50:05,210 INFO L357 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=FPandBP, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mHoare=true, mAutomataTypeConcurrency=FINITE_AUTOMATA, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=LoopHeads, mDumpOnlyReuseAutomata=false, mLimitTraceHistogram=0, mErrorLocTimeLimit=0, mLimitPathProgramCount=0, mCollectInterpolantStatistics=true, mHeuristicEmptinessCheck=false, mHeuristicEmptinessCheckAStarHeuristic=ZERO, mHeuristicEmptinessCheckAStarHeuristicRandomSeed=1337, mHeuristicEmptinessCheckSmtFeatureScoringMethod=DAGSIZE, mSMTFeatureExtraction=false, mSMTFeatureExtractionDumpPath=., mOverrideInterpolantAutomaton=false, mMcrInterpolantMethod=WP, mPorIndependenceSettings=[Lde.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings;@2ea08654, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2023-11-12 00:50:05,210 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2023-11-12 00:50:05,216 INFO L276 IsEmpty]: Start isEmpty. Operand has 69 states, 35 states have (on average 1.2285714285714286) internal successors, (43), 36 states have internal predecessors, (43), 24 states have call successors, (24), 8 states have call predecessors, (24), 8 states have return successors, (24), 24 states have call predecessors, (24), 24 states have call successors, (24) [2023-11-12 00:50:05,228 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 53 [2023-11-12 00:50:05,228 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:50:05,229 INFO L195 NwaCegarLoop]: trace histogram [6, 2, 2, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 00:50:05,230 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:50:05,238 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:50:05,238 INFO L85 PathProgramCache]: Analyzing trace with hash 1481258301, now seen corresponding path program 1 times [2023-11-12 00:50:05,251 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:50:05,251 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [478395837] [2023-11-12 00:50:05,251 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:50:05,252 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:50:05,662 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:50:06,268 INFO L134 CoverageAnalysis]: Checked inductivity of 38 backedges. 3 proven. 4 refuted. 0 times theorem prover too weak. 31 trivial. 0 not checked. [2023-11-12 00:50:06,268 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:50:06,268 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [478395837] [2023-11-12 00:50:06,269 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [478395837] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-12 00:50:06,269 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [465543047] [2023-11-12 00:50:06,269 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:50:06,270 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:50:06,270 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89d3aef9-3936-4957-a177-31ac795c3954/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:50:06,277 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89d3aef9-3936-4957-a177-31ac795c3954/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:50:06,313 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89d3aef9-3936-4957-a177-31ac795c3954/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2023-11-12 00:50:06,578 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:50:06,582 INFO L262 TraceCheckSpWp]: Trace formula consists of 301 conjuncts, 58 conjunts are in the unsatisfiable core [2023-11-12 00:50:06,595 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:50:06,780 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 15 [2023-11-12 00:50:06,800 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 15 [2023-11-12 00:50:06,940 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 6 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 28 [2023-11-12 00:50:06,970 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 6 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 28 [2023-11-12 00:50:10,608 INFO L134 CoverageAnalysis]: Checked inductivity of 38 backedges. 13 proven. 0 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2023-11-12 00:50:10,608 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-11-12 00:50:10,608 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [465543047] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-12 00:50:10,609 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-11-12 00:50:10,609 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [10] imperfect sequences [5] total 13 [2023-11-12 00:50:10,611 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1416506191] [2023-11-12 00:50:10,613 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-12 00:50:10,617 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2023-11-12 00:50:10,618 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:50:10,649 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2023-11-12 00:50:10,650 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=29, Invalid=127, Unknown=0, NotChecked=0, Total=156 [2023-11-12 00:50:10,653 INFO L87 Difference]: Start difference. First operand has 69 states, 35 states have (on average 1.2285714285714286) internal successors, (43), 36 states have internal predecessors, (43), 24 states have call successors, (24), 8 states have call predecessors, (24), 8 states have return successors, (24), 24 states have call predecessors, (24), 24 states have call successors, (24) Second operand has 10 states, 10 states have (on average 2.2) internal successors, (22), 9 states have internal predecessors, (22), 5 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (10), 5 states have call predecessors, (10), 4 states have call successors, (10) [2023-11-12 00:50:11,836 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:50:11,836 INFO L93 Difference]: Finished difference Result 188 states and 265 transitions. [2023-11-12 00:50:11,838 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2023-11-12 00:50:11,839 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 2.2) internal successors, (22), 9 states have internal predecessors, (22), 5 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (10), 5 states have call predecessors, (10), 4 states have call successors, (10) Word has length 52 [2023-11-12 00:50:11,840 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:50:11,851 INFO L225 Difference]: With dead ends: 188 [2023-11-12 00:50:11,851 INFO L226 Difference]: Without dead ends: 127 [2023-11-12 00:50:11,857 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 57 GetRequests, 33 SyntacticMatches, 12 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 39 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=34, Invalid=148, Unknown=0, NotChecked=0, Total=182 [2023-11-12 00:50:11,865 INFO L413 NwaCegarLoop]: 89 mSDtfsCounter, 56 mSDsluCounter, 266 mSDsCounter, 0 mSdLazyCounter, 350 mSolverCounterSat, 31 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 64 SdHoareTripleChecker+Valid, 355 SdHoareTripleChecker+Invalid, 381 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 31 IncrementalHoareTripleChecker+Valid, 350 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.0s IncrementalHoareTripleChecker+Time [2023-11-12 00:50:11,869 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [64 Valid, 355 Invalid, 381 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [31 Valid, 350 Invalid, 0 Unknown, 0 Unchecked, 1.0s Time] [2023-11-12 00:50:11,890 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 127 states. [2023-11-12 00:50:11,970 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 127 to 125. [2023-11-12 00:50:11,972 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 125 states, 63 states have (on average 1.2063492063492063) internal successors, (76), 65 states have internal predecessors, (76), 46 states have call successors, (46), 15 states have call predecessors, (46), 15 states have return successors, (44), 44 states have call predecessors, (44), 44 states have call successors, (44) [2023-11-12 00:50:11,986 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 125 states to 125 states and 166 transitions. [2023-11-12 00:50:11,987 INFO L78 Accepts]: Start accepts. Automaton has 125 states and 166 transitions. Word has length 52 [2023-11-12 00:50:11,988 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:50:11,989 INFO L495 AbstractCegarLoop]: Abstraction has 125 states and 166 transitions. [2023-11-12 00:50:11,989 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 2.2) internal successors, (22), 9 states have internal predecessors, (22), 5 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (10), 5 states have call predecessors, (10), 4 states have call successors, (10) [2023-11-12 00:50:11,989 INFO L276 IsEmpty]: Start isEmpty. Operand 125 states and 166 transitions. [2023-11-12 00:50:11,994 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 54 [2023-11-12 00:50:11,994 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:50:11,995 INFO L195 NwaCegarLoop]: trace histogram [6, 2, 2, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 00:50:12,007 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89d3aef9-3936-4957-a177-31ac795c3954/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2023-11-12 00:50:12,201 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0,2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89d3aef9-3936-4957-a177-31ac795c3954/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:50:12,201 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:50:12,202 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:50:12,202 INFO L85 PathProgramCache]: Analyzing trace with hash 12802211, now seen corresponding path program 1 times [2023-11-12 00:50:12,202 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:50:12,202 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1217074216] [2023-11-12 00:50:12,202 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:50:12,202 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:50:12,302 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:50:12,630 INFO L134 CoverageAnalysis]: Checked inductivity of 39 backedges. 3 proven. 4 refuted. 0 times theorem prover too weak. 32 trivial. 0 not checked. [2023-11-12 00:50:12,631 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:50:12,631 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1217074216] [2023-11-12 00:50:12,631 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1217074216] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-12 00:50:12,631 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1142744500] [2023-11-12 00:50:12,631 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:50:12,631 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:50:12,632 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89d3aef9-3936-4957-a177-31ac795c3954/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:50:12,633 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89d3aef9-3936-4957-a177-31ac795c3954/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:50:12,661 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_89d3aef9-3936-4957-a177-31ac795c3954/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2023-11-12 00:50:12,849 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:50:12,854 INFO L262 TraceCheckSpWp]: Trace formula consists of 350 conjuncts, 80 conjunts are in the unsatisfiable core [2023-11-12 00:50:12,869 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:50:12,893 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 1, 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 6 treesize of output 5 [2023-11-12 00:50:13,121 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 15 [2023-11-12 00:50:13,139 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 15 [2023-11-12 00:50:13,218 INFO L351 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 3 new quantified variables, introduced 0 case distinctions, treesize of input 31 treesize of output 36 [2023-11-12 00:50:13,245 INFO L322 Elim1Store]: treesize reduction 13, result has 40.9 percent of original size [2023-11-12 00:50:13,245 INFO L351 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 1 case distinctions, treesize of input 23 treesize of output 20 [2023-11-12 00:50:13,269 INFO L322 Elim1Store]: treesize reduction 4, result has 50.0 percent of original size [2023-11-12 00:50:13,271 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 11 treesize of output 11 [2023-11-12 00:50:13,287 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 5 disjoint index pairs (out of 1 index pairs), introduced 3 new quantified variables, introduced 0 case distinctions, treesize of input 31 treesize of output 36 [2023-11-12 00:50:13,294 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 30 treesize of output 21 [2023-11-12 00:50:13,415 INFO L322 Elim1Store]: treesize reduction 96, result has 23.2 percent of original size [2023-11-12 00:50:13,416 INFO L351 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 4 new quantified variables, introduced 4 case distinctions, treesize of input 107 treesize of output 74 [2023-11-12 00:50:13,426 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-11-12 00:50:13,438 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 37 treesize of output 32 [2023-11-12 00:50:13,446 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 1, 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 0 case distinctions, treesize of input 23 treesize of output 21 [2023-11-12 00:50:15,785 INFO L134 CoverageAnalysis]: Checked inductivity of 39 backedges. 26 proven. 5 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2023-11-12 00:50:15,785 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 00:50:21,573 INFO L322 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-11-12 00:50:21,573 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 1, 4 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 4 new quantified variables, introduced 4 case distinctions, treesize of input 364 treesize of output 449 [2023-11-12 00:50:22,375 INFO L322 Elim1Store]: treesize reduction 24, result has 4.0 percent of original size [2023-11-12 00:50:22,375 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 1, 2 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 4 case distinctions, treesize of input 35 treesize of output 24 [2023-11-12 00:50:22,405 INFO L322 Elim1Store]: treesize reduction 24, result has 4.0 percent of original size [2023-11-12 00:50:22,405 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 1, 2 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 4 case distinctions, treesize of input 35 treesize of output 24 [2023-11-12 00:50:22,440 INFO L322 Elim1Store]: treesize reduction 24, result has 4.0 percent of original size [2023-11-12 00:50:22,441 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 1, 2 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 4 case distinctions, treesize of input 35 treesize of output 24 [2023-11-12 00:50:22,489 INFO L322 Elim1Store]: treesize reduction 36, result has 2.7 percent of original size [2023-11-12 00:50:22,489 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 1, 3 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 6 case distinctions, treesize of input 49 treesize of output 62 [2023-11-12 00:50:22,566 INFO L322 Elim1Store]: treesize reduction 24, result has 4.0 percent of original size [2023-11-12 00:50:22,567 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 1, 2 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 4 case distinctions, treesize of input 35 treesize of output 24 [2023-11-12 00:50:22,602 INFO L322 Elim1Store]: treesize reduction 24, result has 4.0 percent of original size [2023-11-12 00:50:22,603 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 1, 2 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 4 case distinctions, treesize of input 35 treesize of output 24 [2023-11-12 00:50:22,804 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 1, 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 20 treesize of output 18 [2023-11-12 00:50:22,848 INFO L322 Elim1Store]: treesize reduction 11, result has 8.3 percent of original size [2023-11-12 00:50:22,848 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 2 case distinctions, treesize of input 21 treesize of output 4 [2023-11-12 00:50:22,911 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 1, 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 20 treesize of output 18 [2023-11-12 00:50:22,988 INFO L322 Elim1Store]: treesize reduction 72, result has 17.2 percent of original size [2023-11-12 00:50:22,988 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 1, 2 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 3 new quantified variables, introduced 7 case distinctions, treesize of input 130 treesize of output 121 [2023-11-12 00:50:23,070 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 1, 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 20 treesize of output 18 [2023-11-12 00:50:24,001 INFO L322 Elim1Store]: treesize reduction 78, result has 46.9 percent of original size [2023-11-12 00:50:24,002 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 3 disjoint index pairs (out of 0 index pairs), introduced 2 new quantified variables, introduced 4 case distinctions, treesize of input 234 treesize of output 223 [2023-11-12 00:50:24,051 INFO L322 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-11-12 00:50:24,055 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 169 treesize of output 167 [2023-11-12 00:50:24,077 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 1, 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 130 treesize of output 124 [2023-11-12 00:50:24,199 INFO L322 Elim1Store]: treesize reduction 78, result has 46.9 percent of original size [2023-11-12 00:50:24,200 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 4 disjoint index pairs (out of 0 index pairs), introduced 2 new quantified variables, introduced 4 case distinctions, treesize of input 234 treesize of output 223 [2023-11-12 00:50:24,293 INFO L322 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-11-12 00:50:24,296 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 390 treesize of output 344 [2023-11-12 00:50:24,344 INFO L322 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-11-12 00:50:24,344 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 161 treesize of output 161 [2023-11-12 00:50:24,769 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 1, 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 6 treesize of output 4 [2023-11-12 00:50:24,831 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 1, 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 6 treesize of output 4 [2023-11-12 00:50:24,855 INFO L322 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-11-12 00:50:24,857 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 1 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 2 case distinctions, treesize of input 50 treesize of output 60 [2023-11-12 00:50:24,913 INFO L322 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-11-12 00:50:24,914 INFO L351 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 71 treesize of output 81 [2023-11-12 00:50:25,079 INFO L322 Elim1Store]: treesize reduction 108, result has 32.1 percent of original size [2023-11-12 00:50:25,080 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 4 disjoint index pairs (out of 0 index pairs), introduced 2 new quantified variables, introduced 4 case distinctions, treesize of input 242 treesize of output 208 [2023-11-12 00:50:25,108 INFO L322 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-11-12 00:50:25,109 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 219 treesize of output 189 [2023-11-12 00:50:25,440 INFO L322 Elim1Store]: treesize reduction 326, result has 20.5 percent of original size [2023-11-12 00:50:25,440 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 1, 4 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 6 new quantified variables, introduced 18 case distinctions, treesize of input 410 treesize of output 458 [2023-11-12 00:50:25,826 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 1, 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 7 treesize of output 3 [2023-11-12 00:50:26,098 INFO L322 Elim1Store]: treesize reduction 104, result has 33.8 percent of original size [2023-11-12 00:50:26,098 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 4 select indices, 4 select index equivalence classes, 0 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 8 case distinctions, treesize of input 209 treesize of output 221 [2023-11-12 00:50:26,201 INFO L322 Elim1Store]: treesize reduction 8, result has 72.4 percent of original size [2023-11-12 00:50:26,202 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 34 treesize of output 46 [2023-11-12 00:50:26,285 INFO L322 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-11-12 00:50:26,285 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 3 case distinctions, treesize of input 66 treesize of output 74 [2023-11-12 00:50:26,435 INFO L322 Elim1Store]: treesize reduction 108, result has 32.1 percent of original size [2023-11-12 00:50:26,436 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 3 disjoint index pairs (out of 0 index pairs), introduced 2 new quantified variables, introduced 4 case distinctions, treesize of input 116 treesize of output 124 [2023-11-12 00:50:26,444 INFO L173 IndexEqualityManager]: detected equality via solver [2023-11-12 00:50:26,455 INFO L322 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-11-12 00:50:26,456 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 110 treesize of output 108 [2023-11-12 00:50:26,469 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 1, 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 33 treesize of output 29 [2023-11-12 00:50:26,509 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 1, 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 8 treesize of output 4 [2023-11-12 00:50:26,582 INFO L322 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-11-12 00:50:26,583 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 1 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 2 case distinctions, treesize of input 45 treesize of output 51 [2023-11-12 00:50:26,865 INFO L322 Elim1Store]: treesize reduction 101, result has 38.0 percent of original size [2023-11-12 00:50:26,865 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 3 disjoint index pairs (out of 0 index pairs), introduced 2 new quantified variables, introduced 4 case distinctions, treesize of input 120 treesize of output 140 [2023-11-12 00:50:26,880 INFO L173 IndexEqualityManager]: detected equality via solver [2023-11-12 00:50:26,909 INFO L322 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-11-12 00:50:26,910 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 126 treesize of output 124 [2023-11-12 00:50:26,926 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 1, 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 68 treesize of output 64 [2023-11-12 00:50:27,026 INFO L322 Elim1Store]: treesize reduction 101, result has 38.0 percent of original size [2023-11-12 00:50:27,027 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 4 disjoint index pairs (out of 0 index pairs), introduced 2 new quantified variables, introduced 4 case distinctions, treesize of input 250 treesize of output 228 [2023-11-12 00:50:27,063 INFO L322 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-11-12 00:50:27,064 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 309 treesize of output 275 [2023-11-12 00:50:27,094 INFO L322 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-11-12 00:50:27,095 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 176 treesize of output 172 [2023-11-12 00:50:27,413 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 1, 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 8 treesize of output 4 [2023-11-12 00:50:27,432 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 1, 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 8 treesize of output 4 [2023-11-12 00:50:27,460 INFO L322 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-11-12 00:50:27,461 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 1 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 2 case distinctions, treesize of input 60 treesize of output 68 [2023-11-12 00:50:27,511 INFO L322 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-11-12 00:50:27,511 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 3 case distinctions, treesize of input 57 treesize of output 69 [2023-11-12 00:50:27,635 INFO L322 Elim1Store]: treesize reduction 106, result has 32.5 percent of original size [2023-11-12 00:50:27,635 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 4 disjoint index pairs (out of 0 index pairs), introduced 2 new quantified variables, introduced 4 case distinctions, treesize of input 116 treesize of output 124 [2023-11-12 00:50:27,652 INFO L322 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-11-12 00:50:27,653 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 211 treesize of output 185 [2023-11-12 00:50:27,675 INFO L322 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-11-12 00:50:27,678 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 158 treesize of output 154 [2023-11-12 00:50:27,754 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 1, 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 7 treesize of output 3 [2023-11-12 00:50:27,802 INFO L322 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-11-12 00:50:27,802 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 3 case distinctions, treesize of input 60 treesize of output 70 [2023-11-12 00:50:27,922 INFO L322 Elim1Store]: treesize reduction 106, result has 32.5 percent of original size [2023-11-12 00:50:27,923 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 3 disjoint index pairs (out of 0 index pairs), introduced 2 new quantified variables, introduced 4 case distinctions, treesize of input 116 treesize of output 124 [2023-11-12 00:50:27,930 INFO L173 IndexEqualityManager]: detected equality via solver [2023-11-12 00:50:27,940 INFO L322 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-11-12 00:50:27,940 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 110 treesize of output 108 [2023-11-12 00:50:27,951 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 1, 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 33 treesize of output 29 [2023-11-12 00:50:27,984 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 1, 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 8 treesize of output 4 [2023-11-12 00:50:28,052 INFO L322 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-11-12 00:50:28,052 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 1 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 2 case distinctions, treesize of input 45 treesize of output 51 [2023-11-12 00:50:33,784 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1142744500] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-12 00:50:33,784 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [163670819] [2023-11-12 00:50:33,817 INFO L159 IcfgInterpreter]: Started Sifa with 35 locations of interest [2023-11-12 00:50:33,817 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 00:50:33,823 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 00:50:33,830 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 00:50:33,831 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-12 00:50:40,918 INFO L197 IcfgInterpreter]: Interpreting procedure aws_linked_list_front with input of size 1 for LOIs [2023-11-12 00:50:40,999 INFO L197 IcfgInterpreter]: Interpreting procedure aws_linked_list_empty with input of size 68 for LOIs [2023-11-12 00:50:41,075 INFO L197 IcfgInterpreter]: Interpreting procedure aws_linked_list_is_valid with input of size 1 for LOIs [2023-11-12 00:50:41,131 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 1 for LOIs [2023-11-12 00:50:41,133 INFO L197 IcfgInterpreter]: Interpreting procedure nondet_uint64_t with input of size 94 for LOIs [2023-11-12 00:50:41,153 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-12 00:50:42,910 WARN L876 $PredicateComparison]: unable to prove that (and (exists ((|v_#memory_$Pointer$.offset_84| (Array Int (Array Int Int))) (|v_#memory_int_30| (Array Int (Array Int Int))) (|v_#memory_real_47| (Array Int (Array Int Real))) (|v_#memory_$Pointer$.base_84| (Array Int (Array Int Int))) (|v_#memory_real_27| (Array Int (Array Int Real))) (|v_ULTIMATE.start_ensure_linked_list_is_allocated_~list#1.offset_18| Int) (|v_ULTIMATE.start_ensure_linked_list_is_allocated_~list#1.base_18| Int) (|v_#memory_int_50| (Array Int (Array Int Int)))) (let ((.cse1 (+ |v_ULTIMATE.start_ensure_linked_list_is_allocated_~list#1.offset_18| 24))) (let ((.cse2 (select (select |c_#memory_$Pointer$.base| |v_ULTIMATE.start_ensure_linked_list_is_allocated_~list#1.base_18|) .cse1)) (.cse3 (select (select |c_#memory_$Pointer$.offset| |v_ULTIMATE.start_ensure_linked_list_is_allocated_~list#1.base_18|) .cse1))) (and (= |c_#memory_$Pointer$.base| (let ((.cse0 (store |v_#memory_$Pointer$.base_84| .cse2 (store (select |v_#memory_$Pointer$.base_84| .cse2) .cse3 |v_ULTIMATE.start_ensure_linked_list_is_allocated_~list#1.base_18|)))) (store .cse0 |v_ULTIMATE.start_ensure_linked_list_is_allocated_~list#1.base_18| (store (select .cse0 |v_ULTIMATE.start_ensure_linked_list_is_allocated_~list#1.base_18|) .cse1 .cse2)))) (= |c_#memory_real| (store |v_#memory_real_27| |v_ULTIMATE.start_ensure_linked_list_is_allocated_~list#1.base_18| (store (select |v_#memory_real_27| |v_ULTIMATE.start_ensure_linked_list_is_allocated_~list#1.base_18|) .cse1 (select (select |c_#memory_real| |v_ULTIMATE.start_ensure_linked_list_is_allocated_~list#1.base_18|) .cse1)))) (= (store |v_#memory_int_50| .cse2 (store (select |v_#memory_int_50| .cse2) .cse3 (select (select |v_#memory_int_30| .cse2) .cse3))) |v_#memory_int_30|) (= (let ((.cse4 (store |v_#memory_$Pointer$.offset_84| .cse2 (store (select |v_#memory_$Pointer$.offset_84| .cse2) .cse3 (+ 16 |v_ULTIMATE.start_ensure_linked_list_is_allocated_~list#1.offset_18|))))) (store .cse4 |v_ULTIMATE.start_ensure_linked_list_is_allocated_~list#1.base_18| (store (select .cse4 |v_ULTIMATE.start_ensure_linked_list_is_allocated_~list#1.base_18|) .cse1 .cse3))) |c_#memory_$Pointer$.offset|) (= |c_#memory_int| (store |v_#memory_int_30| |v_ULTIMATE.start_ensure_linked_list_is_allocated_~list#1.base_18| (store (select |v_#memory_int_30| |v_ULTIMATE.start_ensure_linked_list_is_allocated_~list#1.base_18|) .cse1 (select (select |c_#memory_int| |v_ULTIMATE.start_ensure_linked_list_is_allocated_~list#1.base_18|) .cse1)))) (= |v_#memory_real_27| (store |v_#memory_real_47| .cse2 (store (select |v_#memory_real_47| .cse2) .cse3 (select (select |v_#memory_real_27| .cse2) .cse3)))))))) (exists ((|v_ULTIMATE.start_ensure_linked_list_is_allocated_~length~1#1_18| Int) (|v_ULTIMATE.start_ensure_linked_list_is_allocated_~i~1#1_27| Int)) (<= (mod |v_ULTIMATE.start_ensure_linked_list_is_allocated_~length~1#1_18| 18446744073709551616) (mod |v_ULTIMATE.start_ensure_linked_list_is_allocated_~i~1#1_27| 18446744073709551616)))) is different from true [2023-11-12 00:50:45,348 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSifa [163670819] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-12 00:50:45,349 INFO L185 FreeRefinementEngine]: Found 1 perfect and 2 imperfect interpolant sequences. [2023-11-12 00:50:45,349 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [15] imperfect sequences [5, 11] total 27 [2023-11-12 00:50:45,349 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1808802565] [2023-11-12 00:50:45,349 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-12 00:50:45,350 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2023-11-12 00:50:45,351 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:50:45,351 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2023-11-12 00:50:45,352 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=103, Invalid=1021, Unknown=2, NotChecked=64, Total=1190 [2023-11-12 00:50:45,353 INFO L87 Difference]: Start difference. First operand 125 states and 166 transitions. Second operand has 15 states, 8 states have (on average 2.375) internal successors, (19), 10 states have internal predecessors, (19), 8 states have call successors, (12), 4 states have call predecessors, (12), 4 states have return successors, (10), 7 states have call predecessors, (10), 7 states have call successors, (10) [2023-11-12 00:50:47,264 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.07s for a HTC check with result INVALID. Formula has sorts [Array, Bool, Real, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0]