./Ultimate.py --spec ../../sv-benchmarks/c/properties/no-overflow.prp --file ../../sv-benchmarks/c/aws-c-common/aws_ring_buffer_acquire_harness.i --full-output --architecture 64bit -------------------------------------------------------------------------------- Checking for overflows Using default analysis Version 30e01a73 Calling Ultimate with: /usr/lib/jvm/java-11-openjdk-amd64/bin/java -Dosgi.configuration.area=/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_46ae7aed-a01c-40ac-a605-40d62c69fa2a/bin/utaipan-verify-mE87zJ7Ire/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_46ae7aed-a01c-40ac-a605-40d62c69fa2a/bin/utaipan-verify-mE87zJ7Ire/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_46ae7aed-a01c-40ac-a605-40d62c69fa2a/bin/utaipan-verify-mE87zJ7Ire/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_46ae7aed-a01c-40ac-a605-40d62c69fa2a/bin/utaipan-verify-mE87zJ7Ire/config/TaipanReach.xml -i ../../sv-benchmarks/c/aws-c-common/aws_ring_buffer_acquire_harness.i -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_46ae7aed-a01c-40ac-a605-40d62c69fa2a/bin/utaipan-verify-mE87zJ7Ire/config/svcomp-Overflow-64bit-Taipan_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_46ae7aed-a01c-40ac-a605-40d62c69fa2a/bin/utaipan-verify-mE87zJ7Ire --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(G ! overflow) ) --witnessprinter.graph.data.producer Taipan --witnessprinter.graph.data.architecture 64bit --witnessprinter.graph.data.programhash 29d7fb95278c2cc136033d841944b6b6554a35073619295af30129693cec9c54 --- Real Ultimate output --- This is Ultimate 0.2.3-dev-30e01a7 [2023-11-23 21:30:21,999 INFO L188 SettingsManager]: Resetting all preferences to default values... [2023-11-23 21:30:22,140 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_46ae7aed-a01c-40ac-a605-40d62c69fa2a/bin/utaipan-verify-mE87zJ7Ire/config/svcomp-Overflow-64bit-Taipan_Default.epf [2023-11-23 21:30:22,148 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2023-11-23 21:30:22,148 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2023-11-23 21:30:22,189 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2023-11-23 21:30:22,189 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2023-11-23 21:30:22,190 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2023-11-23 21:30:22,191 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2023-11-23 21:30:22,196 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2023-11-23 21:30:22,196 INFO L153 SettingsManager]: * User list type=DISABLED [2023-11-23 21:30:22,197 INFO L151 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2023-11-23 21:30:22,198 INFO L153 SettingsManager]: * Explicit value domain=true [2023-11-23 21:30:22,199 INFO L153 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2023-11-23 21:30:22,200 INFO L153 SettingsManager]: * Octagon Domain=false [2023-11-23 21:30:22,200 INFO L153 SettingsManager]: * Abstract domain=CompoundDomain [2023-11-23 21:30:22,200 INFO L153 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2023-11-23 21:30:22,201 INFO L153 SettingsManager]: * Use the RCFG-of-the-future interface=true [2023-11-23 21:30:22,201 INFO L153 SettingsManager]: * Interval Domain=false [2023-11-23 21:30:22,202 INFO L151 SettingsManager]: Preferences of Sifa differ from their defaults: [2023-11-23 21:30:22,202 INFO L153 SettingsManager]: * Call Summarizer=TopInputCallSummarizer [2023-11-23 21:30:22,203 INFO L153 SettingsManager]: * Simplification Technique=POLY_PAC [2023-11-23 21:30:22,204 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2023-11-23 21:30:22,204 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2023-11-23 21:30:22,205 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2023-11-23 21:30:22,205 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2023-11-23 21:30:22,206 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2023-11-23 21:30:22,206 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2023-11-23 21:30:22,206 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2023-11-23 21:30:22,207 INFO L153 SettingsManager]: * Check absence of signed integer overflows=true [2023-11-23 21:30:22,208 INFO L153 SettingsManager]: * Check unreachability of reach_error function=false [2023-11-23 21:30:22,208 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2023-11-23 21:30:22,208 INFO L153 SettingsManager]: * Use constant arrays=true [2023-11-23 21:30:22,209 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2023-11-23 21:30:22,209 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2023-11-23 21:30:22,209 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2023-11-23 21:30:22,209 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-11-23 21:30:22,210 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2023-11-23 21:30:22,210 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2023-11-23 21:30:22,210 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2023-11-23 21:30:22,210 INFO L153 SettingsManager]: * Trace refinement strategy=SIFA_TAIPAN [2023-11-23 21:30:22,211 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2023-11-23 21:30:22,211 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2023-11-23 21:30:22,211 INFO L153 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2023-11-23 21:30:22,211 INFO L153 SettingsManager]: * Trace refinement exception blacklist=NONE [2023-11-23 21:30:22,212 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2023-11-23 21:30:22,212 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_46ae7aed-a01c-40ac-a605-40d62c69fa2a/bin/utaipan-verify-mE87zJ7Ire/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_46ae7aed-a01c-40ac-a605-40d62c69fa2a/bin/utaipan-verify-mE87zJ7Ire 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 ! overflow) ) 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 -> 29d7fb95278c2cc136033d841944b6b6554a35073619295af30129693cec9c54 [2023-11-23 21:30:22,564 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2023-11-23 21:30:22,597 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2023-11-23 21:30:22,600 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2023-11-23 21:30:22,601 INFO L270 PluginConnector]: Initializing CDTParser... [2023-11-23 21:30:22,602 INFO L274 PluginConnector]: CDTParser initialized [2023-11-23 21:30:22,604 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_46ae7aed-a01c-40ac-a605-40d62c69fa2a/bin/utaipan-verify-mE87zJ7Ire/../../sv-benchmarks/c/aws-c-common/aws_ring_buffer_acquire_harness.i [2023-11-23 21:30:25,678 INFO L533 CDTParser]: Created temporary CDT project at NULL [2023-11-23 21:30:26,462 INFO L384 CDTParser]: Found 1 translation units. [2023-11-23 21:30:26,463 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_46ae7aed-a01c-40ac-a605-40d62c69fa2a/sv-benchmarks/c/aws-c-common/aws_ring_buffer_acquire_harness.i [2023-11-23 21:30:26,525 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_46ae7aed-a01c-40ac-a605-40d62c69fa2a/bin/utaipan-verify-mE87zJ7Ire/data/85addf5f8/404558cff39b4f5eb1e4ffa9f5c52124/FLAGb4be4f2ba [2023-11-23 21:30:26,548 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_46ae7aed-a01c-40ac-a605-40d62c69fa2a/bin/utaipan-verify-mE87zJ7Ire/data/85addf5f8/404558cff39b4f5eb1e4ffa9f5c52124 [2023-11-23 21:30:26,555 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2023-11-23 21:30:26,557 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2023-11-23 21:30:26,563 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2023-11-23 21:30:26,563 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2023-11-23 21:30:26,568 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2023-11-23 21:30:26,569 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 23.11 09:30:26" (1/1) ... [2023-11-23 21:30:26,570 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@1ba7ba43 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 09:30:26, skipping insertion in model container [2023-11-23 21:30:26,571 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 23.11 09:30:26" (1/1) ... [2023-11-23 21:30:26,708 INFO L177 MainTranslator]: Built tables and reachable declarations [2023-11-23 21:30:28,263 WARN L1590 CHandler]: Possible shadowing of function index [2023-11-23 21:30:28,264 WARN L1590 CHandler]: Possible shadowing of function index [2023-11-23 21:30:28,265 WARN L1590 CHandler]: Possible shadowing of function index [2023-11-23 21:30:28,266 WARN L1590 CHandler]: Possible shadowing of function index [2023-11-23 21:30:28,267 WARN L1590 CHandler]: Possible shadowing of function index [2023-11-23 21:30:28,282 WARN L1590 CHandler]: Possible shadowing of function index [2023-11-23 21:30:28,283 WARN L1590 CHandler]: Possible shadowing of function index [2023-11-23 21:30:28,285 WARN L1590 CHandler]: Possible shadowing of function index [2023-11-23 21:30:28,285 WARN L1590 CHandler]: Possible shadowing of function index [2023-11-23 21:30:28,714 WARN L635 FunctionHandler]: implicit declaration of function __atomic_load_n [2023-11-23 21:30:28,715 WARN L635 FunctionHandler]: implicit declaration of function __atomic_store_n [2023-11-23 21:30:28,729 WARN L635 FunctionHandler]: implicit declaration of function __atomic_exchange_n [2023-11-23 21:30:28,731 WARN L635 FunctionHandler]: implicit declaration of function __atomic_compare_exchange_n [2023-11-23 21:30:28,735 WARN L635 FunctionHandler]: implicit declaration of function __atomic_fetch_add [2023-11-23 21:30:28,736 WARN L635 FunctionHandler]: implicit declaration of function __atomic_fetch_sub [2023-11-23 21:30:28,743 WARN L635 FunctionHandler]: implicit declaration of function __atomic_fetch_or [2023-11-23 21:30:28,744 WARN L635 FunctionHandler]: implicit declaration of function __atomic_fetch_and [2023-11-23 21:30:28,745 WARN L635 FunctionHandler]: implicit declaration of function __atomic_fetch_xor [2023-11-23 21:30:28,745 WARN L635 FunctionHandler]: implicit declaration of function __atomic_thread_fence [2023-11-23 21:30:29,056 WARN L1590 CHandler]: Possible shadowing of function index [2023-11-23 21:30:29,064 WARN L1590 CHandler]: Possible shadowing of function index [2023-11-23 21:30:29,216 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-23 21:30:29,291 INFO L202 MainTranslator]: Completed pre-run [2023-11-23 21:30:29,373 WARN L1590 CHandler]: Possible shadowing of function index [2023-11-23 21:30:29,374 WARN L1590 CHandler]: Possible shadowing of function index [2023-11-23 21:30:29,374 WARN L1590 CHandler]: Possible shadowing of function index [2023-11-23 21:30:29,375 WARN L1590 CHandler]: Possible shadowing of function index [2023-11-23 21:30:29,376 WARN L1590 CHandler]: Possible shadowing of function index [2023-11-23 21:30:29,389 WARN L1590 CHandler]: Possible shadowing of function index [2023-11-23 21:30:29,389 WARN L1590 CHandler]: Possible shadowing of function index [2023-11-23 21:30:29,390 WARN L1590 CHandler]: Possible shadowing of function index [2023-11-23 21:30:29,391 WARN L1590 CHandler]: Possible shadowing of function index [2023-11-23 21:30:29,439 WARN L635 FunctionHandler]: implicit declaration of function __atomic_load_n [2023-11-23 21:30:29,440 WARN L635 FunctionHandler]: implicit declaration of function __atomic_store_n [2023-11-23 21:30:29,440 WARN L635 FunctionHandler]: implicit declaration of function __atomic_exchange_n [2023-11-23 21:30:29,449 WARN L635 FunctionHandler]: implicit declaration of function __atomic_compare_exchange_n [2023-11-23 21:30:29,491 WARN L635 FunctionHandler]: implicit declaration of function __atomic_fetch_add [2023-11-23 21:30:29,491 WARN L635 FunctionHandler]: implicit declaration of function __atomic_fetch_sub [2023-11-23 21:30:29,492 WARN L635 FunctionHandler]: implicit declaration of function __atomic_fetch_or [2023-11-23 21:30:29,492 WARN L635 FunctionHandler]: implicit declaration of function __atomic_fetch_and [2023-11-23 21:30:29,496 WARN L635 FunctionHandler]: implicit declaration of function __atomic_fetch_xor [2023-11-23 21:30:29,496 WARN L635 FunctionHandler]: implicit declaration of function __atomic_thread_fence [2023-11-23 21:30:29,641 WARN L75 lationResultReporter]: Unsoundness Warning: Ignoring inline assembler instruction C: __asm__ __volatile__("" : "+r"(index)); [8269] [2023-11-23 21:30:29,643 WARN L1590 CHandler]: Possible shadowing of function index [2023-11-23 21:30:29,644 WARN L1590 CHandler]: Possible shadowing of function index [2023-11-23 21:30:29,690 WARN L75 lationResultReporter]: Unsoundness Warning: Ignoring inline assembler instruction C: __asm__ __volatile__("" : : "r"(pBuf) : "memory"); [8989-9000] [2023-11-23 21:30:29,722 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-23 21:30:29,995 WARN L675 CHandler]: The function __atomic_fetch_or is called, but not defined or handled by StandardFunctionHandler. [2023-11-23 21:30:29,996 WARN L675 CHandler]: The function __atomic_fetch_sub is called, but not defined or handled by StandardFunctionHandler. [2023-11-23 21:30:29,996 WARN L675 CHandler]: The function __atomic_exchange_n is called, but not defined or handled by StandardFunctionHandler. [2023-11-23 21:30:29,996 WARN L675 CHandler]: The function __atomic_fetch_xor is called, but not defined or handled by StandardFunctionHandler. [2023-11-23 21:30:29,996 WARN L675 CHandler]: The function htons is called, but not defined or handled by StandardFunctionHandler. [2023-11-23 21:30:29,997 WARN L675 CHandler]: The function ntohl is called, but not defined or handled by StandardFunctionHandler. [2023-11-23 21:30:29,997 WARN L675 CHandler]: The function __atomic_compare_exchange_n is called, but not defined or handled by StandardFunctionHandler. [2023-11-23 21:30:29,998 WARN L675 CHandler]: The function __atomic_fetch_add is called, but not defined or handled by StandardFunctionHandler. [2023-11-23 21:30:29,998 WARN L675 CHandler]: The function fprintf is called, but not defined or handled by StandardFunctionHandler. [2023-11-23 21:30:29,998 WARN L675 CHandler]: The function htonl is called, but not defined or handled by StandardFunctionHandler. [2023-11-23 21:30:29,998 WARN L675 CHandler]: The function __atomic_store_n is called, but not defined or handled by StandardFunctionHandler. [2023-11-23 21:30:29,999 WARN L675 CHandler]: The function ntohs is called, but not defined or handled by StandardFunctionHandler. [2023-11-23 21:30:29,999 WARN L675 CHandler]: The function predicate is called, but not defined or handled by StandardFunctionHandler. [2023-11-23 21:30:29,999 WARN L675 CHandler]: The function __atomic_load_n is called, but not defined or handled by StandardFunctionHandler. [2023-11-23 21:30:29,999 WARN L675 CHandler]: The function memcmp is called, but not defined or handled by StandardFunctionHandler. [2023-11-23 21:30:30,000 WARN L675 CHandler]: The function __atomic_thread_fence is called, but not defined or handled by StandardFunctionHandler. [2023-11-23 21:30:30,000 WARN L675 CHandler]: The function __atomic_fetch_and is called, but not defined or handled by StandardFunctionHandler. [2023-11-23 21:30:30,001 WARN L675 CHandler]: The function memchr is called, but not defined or handled by StandardFunctionHandler. [2023-11-23 21:30:30,008 INFO L206 MainTranslator]: Completed translation [2023-11-23 21:30:30,009 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 09:30:30 WrapperNode [2023-11-23 21:30:30,010 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2023-11-23 21:30:30,012 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2023-11-23 21:30:30,012 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2023-11-23 21:30:30,012 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2023-11-23 21:30:30,019 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 09:30:30" (1/1) ... [2023-11-23 21:30:30,127 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 09:30:30" (1/1) ... [2023-11-23 21:30:30,214 INFO L138 Inliner]: procedures = 694, calls = 2941, calls flagged for inlining = 62, calls inlined = 12, statements flattened = 1181 [2023-11-23 21:30:30,215 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2023-11-23 21:30:30,216 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2023-11-23 21:30:30,216 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2023-11-23 21:30:30,216 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2023-11-23 21:30:30,226 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 09:30:30" (1/1) ... [2023-11-23 21:30:30,226 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 09:30:30" (1/1) ... [2023-11-23 21:30:30,236 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 09:30:30" (1/1) ... [2023-11-23 21:30:30,240 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 09:30:30" (1/1) ... [2023-11-23 21:30:30,318 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 09:30:30" (1/1) ... [2023-11-23 21:30:30,336 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 09:30:30" (1/1) ... [2023-11-23 21:30:30,357 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 09:30:30" (1/1) ... [2023-11-23 21:30:30,365 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 09:30:30" (1/1) ... [2023-11-23 21:30:30,400 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2023-11-23 21:30:30,403 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2023-11-23 21:30:30,404 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2023-11-23 21:30:30,404 INFO L274 PluginConnector]: RCFGBuilder initialized [2023-11-23 21:30:30,405 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 09:30:30" (1/1) ... [2023-11-23 21:30:30,411 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-11-23 21:30:30,423 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_46ae7aed-a01c-40ac-a605-40d62c69fa2a/bin/utaipan-verify-mE87zJ7Ire/z3 [2023-11-23 21:30:30,439 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_46ae7aed-a01c-40ac-a605-40d62c69fa2a/bin/utaipan-verify-mE87zJ7Ire/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2023-11-23 21:30:30,462 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_46ae7aed-a01c-40ac-a605-40d62c69fa2a/bin/utaipan-verify-mE87zJ7Ire/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2023-11-23 21:30:30,480 INFO L130 BoogieDeclarations]: Found specification of procedure aws_byte_buf_is_valid [2023-11-23 21:30:30,480 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_byte_buf_is_valid [2023-11-23 21:30:30,480 INFO L130 BoogieDeclarations]: Found specification of procedure __atomic_store_n [2023-11-23 21:30:30,480 INFO L130 BoogieDeclarations]: Found specification of procedure __atomic_load_n [2023-11-23 21:30:30,481 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2023-11-23 21:30:30,481 INFO L130 BoogieDeclarations]: Found specification of procedure nondet_bool [2023-11-23 21:30:30,481 INFO L138 BoogieDeclarations]: Found implementation of procedure nondet_bool [2023-11-23 21:30:30,481 INFO L130 BoogieDeclarations]: Found specification of procedure aws_atomic_load_ptr [2023-11-23 21:30:30,481 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_atomic_load_ptr [2023-11-23 21:30:30,481 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2023-11-23 21:30:30,481 INFO L130 BoogieDeclarations]: Found specification of procedure aws_raise_error [2023-11-23 21:30:30,481 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_raise_error [2023-11-23 21:30:30,481 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2023-11-23 21:30:30,481 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2023-11-23 21:30:30,482 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnHeap [2023-11-23 21:30:30,482 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2023-11-23 21:30:30,482 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$ [2023-11-23 21:30:30,482 INFO L130 BoogieDeclarations]: Found specification of procedure aws_atomic_priv_xlate_order [2023-11-23 21:30:30,482 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_atomic_priv_xlate_order [2023-11-23 21:30:30,482 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2023-11-23 21:30:30,482 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2023-11-23 21:30:30,482 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2023-11-23 21:30:30,482 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2023-11-23 21:30:30,483 INFO L130 BoogieDeclarations]: Found specification of procedure bounded_malloc [2023-11-23 21:30:30,483 INFO L138 BoogieDeclarations]: Found implementation of procedure bounded_malloc [2023-11-23 21:30:30,483 INFO L130 BoogieDeclarations]: Found specification of procedure aws_atomic_store_ptr [2023-11-23 21:30:30,483 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_atomic_store_ptr [2023-11-23 21:30:30,483 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2023-11-23 21:30:30,483 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2023-11-23 21:30:30,483 INFO L130 BoogieDeclarations]: Found specification of procedure aws_byte_buf_from_empty_array [2023-11-23 21:30:30,483 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_byte_buf_from_empty_array [2023-11-23 21:30:30,483 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2023-11-23 21:30:30,484 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$ [2023-11-23 21:30:30,484 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$ [2023-11-23 21:30:30,484 INFO L130 BoogieDeclarations]: Found specification of procedure aws_ring_buffer_check_atomic_ptr [2023-11-23 21:30:30,484 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_ring_buffer_check_atomic_ptr [2023-11-23 21:30:30,484 INFO L130 BoogieDeclarations]: Found specification of procedure is_front_valid_state [2023-11-23 21:30:30,484 INFO L138 BoogieDeclarations]: Found implementation of procedure is_front_valid_state [2023-11-23 21:30:30,484 INFO L130 BoogieDeclarations]: Found specification of procedure can_fail_allocator [2023-11-23 21:30:30,484 INFO L138 BoogieDeclarations]: Found implementation of procedure can_fail_allocator [2023-11-23 21:30:30,485 INFO L130 BoogieDeclarations]: Found specification of procedure is_ends_valid_state [2023-11-23 21:30:30,485 INFO L138 BoogieDeclarations]: Found implementation of procedure is_ends_valid_state [2023-11-23 21:30:30,485 INFO L130 BoogieDeclarations]: Found specification of procedure s_buf_belongs_to_pool [2023-11-23 21:30:30,485 INFO L138 BoogieDeclarations]: Found implementation of procedure s_buf_belongs_to_pool [2023-11-23 21:30:30,485 INFO L130 BoogieDeclarations]: Found specification of procedure nondet_uint64_t [2023-11-23 21:30:30,485 INFO L138 BoogieDeclarations]: Found implementation of procedure nondet_uint64_t [2023-11-23 21:30:30,485 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2023-11-23 21:30:30,485 INFO L130 BoogieDeclarations]: Found specification of procedure aws_atomic_store_ptr_explicit [2023-11-23 21:30:30,485 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_atomic_store_ptr_explicit [2023-11-23 21:30:30,485 INFO L130 BoogieDeclarations]: Found specification of procedure aws_ring_buffer_is_valid [2023-11-23 21:30:30,486 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_ring_buffer_is_valid [2023-11-23 21:30:30,486 INFO L130 BoogieDeclarations]: Found specification of procedure is_middle_valid_state [2023-11-23 21:30:30,486 INFO L138 BoogieDeclarations]: Found implementation of procedure is_middle_valid_state [2023-11-23 21:30:30,486 INFO L130 BoogieDeclarations]: Found specification of procedure aws_atomic_load_ptr_explicit [2023-11-23 21:30:30,486 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_atomic_load_ptr_explicit [2023-11-23 21:30:30,486 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2023-11-23 21:30:30,908 INFO L241 CfgBuilder]: Building ICFG [2023-11-23 21:30:30,913 INFO L267 CfgBuilder]: Building CFG for each procedure with an implementation [2023-11-23 21:30:32,783 INFO L282 CfgBuilder]: Performing block encoding [2023-11-23 21:30:33,236 INFO L304 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2023-11-23 21:30:33,237 INFO L309 CfgBuilder]: Removed 2 assume(true) statements. [2023-11-23 21:30:33,238 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 23.11 09:30:33 BoogieIcfgContainer [2023-11-23 21:30:33,239 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2023-11-23 21:30:33,241 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2023-11-23 21:30:33,241 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2023-11-23 21:30:33,245 INFO L274 PluginConnector]: TraceAbstraction initialized [2023-11-23 21:30:33,245 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 23.11 09:30:26" (1/3) ... [2023-11-23 21:30:33,246 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@2fd11f2a and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 23.11 09:30:33, skipping insertion in model container [2023-11-23 21:30:33,246 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 09:30:30" (2/3) ... [2023-11-23 21:30:33,246 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@2fd11f2a and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 23.11 09:30:33, skipping insertion in model container [2023-11-23 21:30:33,247 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 23.11 09:30:33" (3/3) ... [2023-11-23 21:30:33,248 INFO L112 eAbstractionObserver]: Analyzing ICFG aws_ring_buffer_acquire_harness.i [2023-11-23 21:30:33,268 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2023-11-23 21:30:33,268 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 2 error locations. [2023-11-23 21:30:33,329 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-11-23 21:30:33,336 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;@4fe4712f, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2023-11-23 21:30:33,337 INFO L358 AbstractCegarLoop]: Starting to check reachability of 2 error locations. [2023-11-23 21:30:33,342 INFO L276 IsEmpty]: Start isEmpty. Operand has 335 states, 167 states have (on average 1.1736526946107784) internal successors, (196), 170 states have internal predecessors, (196), 144 states have call successors, (144), 21 states have call predecessors, (144), 21 states have return successors, (144), 144 states have call predecessors, (144), 144 states have call successors, (144) [2023-11-23 21:30:33,361 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 213 [2023-11-23 21:30:33,361 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 21:30:33,362 INFO L195 NwaCegarLoop]: trace histogram [8, 8, 8, 8, 6, 6, 6, 6, 6, 4, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 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, 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, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-23 21:30:33,363 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [ULTIMATE.startErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, ULTIMATE.startErr1ASSERT_VIOLATIONINTEGER_OVERFLOW] === [2023-11-23 21:30:33,368 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 21:30:33,368 INFO L85 PathProgramCache]: Analyzing trace with hash 1498542966, now seen corresponding path program 1 times [2023-11-23 21:30:33,379 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-23 21:30:33,379 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1853824339] [2023-11-23 21:30:33,380 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 21:30:33,380 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 21:30:33,970 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 21:30:35,322 INFO L134 CoverageAnalysis]: Checked inductivity of 312 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 286 trivial. 0 not checked. [2023-11-23 21:30:35,323 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-23 21:30:35,323 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1853824339] [2023-11-23 21:30:35,325 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1853824339] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-23 21:30:35,325 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [801799957] [2023-11-23 21:30:35,325 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 21:30:35,332 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 21:30:35,332 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_46ae7aed-a01c-40ac-a605-40d62c69fa2a/bin/utaipan-verify-mE87zJ7Ire/z3 [2023-11-23 21:30:35,334 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_46ae7aed-a01c-40ac-a605-40d62c69fa2a/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-23 21:30:35,378 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_46ae7aed-a01c-40ac-a605-40d62c69fa2a/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2023-11-23 21:30:36,343 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 21:30:36,359 INFO L262 TraceCheckSpWp]: Trace formula consists of 3244 conjuncts, 1 conjunts are in the unsatisfiable core [2023-11-23 21:30:36,376 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-23 21:30:36,415 INFO L134 CoverageAnalysis]: Checked inductivity of 312 backedges. 96 proven. 0 refuted. 0 times theorem prover too weak. 216 trivial. 0 not checked. [2023-11-23 21:30:36,415 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-11-23 21:30:36,416 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [801799957] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-23 21:30:36,416 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-11-23 21:30:36,416 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [6] total 6 [2023-11-23 21:30:36,418 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1042922337] [2023-11-23 21:30:36,419 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-23 21:30:36,424 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2023-11-23 21:30:36,424 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-23 21:30:36,453 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2023-11-23 21:30:36,454 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2023-11-23 21:30:36,458 INFO L87 Difference]: Start difference. First operand has 335 states, 167 states have (on average 1.1736526946107784) internal successors, (196), 170 states have internal predecessors, (196), 144 states have call successors, (144), 21 states have call predecessors, (144), 21 states have return successors, (144), 144 states have call predecessors, (144), 144 states have call successors, (144) Second operand has 2 states, 2 states have (on average 28.5) internal successors, (57), 2 states have internal predecessors, (57), 2 states have call successors, (34), 2 states have call predecessors, (34), 2 states have return successors, (34), 2 states have call predecessors, (34), 2 states have call successors, (34) [2023-11-23 21:30:37,085 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 21:30:37,085 INFO L93 Difference]: Finished difference Result 652 states and 1045 transitions. [2023-11-23 21:30:37,086 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2023-11-23 21:30:37,088 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 28.5) internal successors, (57), 2 states have internal predecessors, (57), 2 states have call successors, (34), 2 states have call predecessors, (34), 2 states have return successors, (34), 2 states have call predecessors, (34), 2 states have call successors, (34) Word has length 212 [2023-11-23 21:30:37,091 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 21:30:37,103 INFO L225 Difference]: With dead ends: 652 [2023-11-23 21:30:37,104 INFO L226 Difference]: Without dead ends: 110 [2023-11-23 21:30:37,114 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 217 GetRequests, 213 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2023-11-23 21:30:37,117 INFO L413 NwaCegarLoop]: 452 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 25 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 452 SdHoareTripleChecker+Invalid, 25 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 25 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2023-11-23 21:30:37,118 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 452 Invalid, 25 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 25 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2023-11-23 21:30:37,136 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 110 states. [2023-11-23 21:30:37,174 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 110 to 110. [2023-11-23 21:30:37,177 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 110 states, 60 states have (on average 1.1166666666666667) internal successors, (67), 61 states have internal predecessors, (67), 34 states have call successors, (34), 14 states have call predecessors, (34), 14 states have return successors, (34), 34 states have call predecessors, (34), 34 states have call successors, (34) [2023-11-23 21:30:37,181 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 110 states to 110 states and 135 transitions. [2023-11-23 21:30:37,183 INFO L78 Accepts]: Start accepts. Automaton has 110 states and 135 transitions. Word has length 212 [2023-11-23 21:30:37,188 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 21:30:37,188 INFO L495 AbstractCegarLoop]: Abstraction has 110 states and 135 transitions. [2023-11-23 21:30:37,188 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 28.5) internal successors, (57), 2 states have internal predecessors, (57), 2 states have call successors, (34), 2 states have call predecessors, (34), 2 states have return successors, (34), 2 states have call predecessors, (34), 2 states have call successors, (34) [2023-11-23 21:30:37,189 INFO L276 IsEmpty]: Start isEmpty. Operand 110 states and 135 transitions. [2023-11-23 21:30:37,205 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 214 [2023-11-23 21:30:37,205 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 21:30:37,206 INFO L195 NwaCegarLoop]: trace histogram [8, 8, 8, 8, 6, 6, 6, 6, 6, 4, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 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, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-23 21:30:37,242 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_46ae7aed-a01c-40ac-a605-40d62c69fa2a/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2023-11-23 21:30:37,421 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_46ae7aed-a01c-40ac-a605-40d62c69fa2a/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable0 [2023-11-23 21:30:37,421 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [ULTIMATE.startErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, ULTIMATE.startErr1ASSERT_VIOLATIONINTEGER_OVERFLOW] === [2023-11-23 21:30:37,422 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 21:30:37,422 INFO L85 PathProgramCache]: Analyzing trace with hash 1997887852, now seen corresponding path program 1 times [2023-11-23 21:30:37,422 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-23 21:30:37,422 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1910804991] [2023-11-23 21:30:37,422 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 21:30:37,422 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 21:30:37,604 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 21:30:38,552 INFO L134 CoverageAnalysis]: Checked inductivity of 312 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 286 trivial. 0 not checked. [2023-11-23 21:30:38,553 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-23 21:30:38,553 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1910804991] [2023-11-23 21:30:38,553 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1910804991] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-23 21:30:38,553 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [822787934] [2023-11-23 21:30:38,553 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 21:30:38,554 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 21:30:38,554 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_46ae7aed-a01c-40ac-a605-40d62c69fa2a/bin/utaipan-verify-mE87zJ7Ire/z3 [2023-11-23 21:30:38,555 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_46ae7aed-a01c-40ac-a605-40d62c69fa2a/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-23 21:30:38,580 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_46ae7aed-a01c-40ac-a605-40d62c69fa2a/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2023-11-23 21:30:39,420 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 21:30:39,435 INFO L262 TraceCheckSpWp]: Trace formula consists of 3245 conjuncts, 2 conjunts are in the unsatisfiable core [2023-11-23 21:30:39,444 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-23 21:30:39,475 INFO L134 CoverageAnalysis]: Checked inductivity of 312 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 312 trivial. 0 not checked. [2023-11-23 21:30:39,475 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-11-23 21:30:39,476 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [822787934] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-23 21:30:39,476 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-11-23 21:30:39,476 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [6] total 7 [2023-11-23 21:30:39,476 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [788634785] [2023-11-23 21:30:39,479 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-23 21:30:39,480 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-11-23 21:30:39,481 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-23 21:30:39,482 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-11-23 21:30:39,482 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=12, Invalid=30, Unknown=0, NotChecked=0, Total=42 [2023-11-23 21:30:39,482 INFO L87 Difference]: Start difference. First operand 110 states and 135 transitions. Second operand has 3 states, 2 states have (on average 26.0) internal successors, (52), 3 states have internal predecessors, (52), 1 states have call successors, (33), 1 states have call predecessors, (33), 1 states have return successors, (33), 1 states have call predecessors, (33), 1 states have call successors, (33) [2023-11-23 21:30:39,830 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 21:30:39,830 INFO L93 Difference]: Finished difference Result 110 states and 135 transitions. [2023-11-23 21:30:39,830 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-11-23 21:30:39,831 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 2 states have (on average 26.0) internal successors, (52), 3 states have internal predecessors, (52), 1 states have call successors, (33), 1 states have call predecessors, (33), 1 states have return successors, (33), 1 states have call predecessors, (33), 1 states have call successors, (33) Word has length 213 [2023-11-23 21:30:39,832 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 21:30:39,834 INFO L225 Difference]: With dead ends: 110 [2023-11-23 21:30:39,834 INFO L226 Difference]: Without dead ends: 109 [2023-11-23 21:30:39,834 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 218 GetRequests, 213 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=12, Invalid=30, Unknown=0, NotChecked=0, Total=42 [2023-11-23 21:30:39,836 INFO L413 NwaCegarLoop]: 118 mSDtfsCounter, 2 mSDsluCounter, 112 mSDsCounter, 0 mSdLazyCounter, 35 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 230 SdHoareTripleChecker+Invalid, 35 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 35 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2023-11-23 21:30:39,836 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [2 Valid, 230 Invalid, 35 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 35 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2023-11-23 21:30:39,837 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 109 states. [2023-11-23 21:30:39,847 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 109 to 109. [2023-11-23 21:30:39,848 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 109 states, 60 states have (on average 1.1) internal successors, (66), 60 states have internal predecessors, (66), 34 states have call successors, (34), 14 states have call predecessors, (34), 14 states have return successors, (34), 34 states have call predecessors, (34), 34 states have call successors, (34) [2023-11-23 21:30:39,849 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 109 states to 109 states and 134 transitions. [2023-11-23 21:30:39,849 INFO L78 Accepts]: Start accepts. Automaton has 109 states and 134 transitions. Word has length 213 [2023-11-23 21:30:39,851 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 21:30:39,851 INFO L495 AbstractCegarLoop]: Abstraction has 109 states and 134 transitions. [2023-11-23 21:30:39,851 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 2 states have (on average 26.0) internal successors, (52), 3 states have internal predecessors, (52), 1 states have call successors, (33), 1 states have call predecessors, (33), 1 states have return successors, (33), 1 states have call predecessors, (33), 1 states have call successors, (33) [2023-11-23 21:30:39,851 INFO L276 IsEmpty]: Start isEmpty. Operand 109 states and 134 transitions. [2023-11-23 21:30:39,855 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 215 [2023-11-23 21:30:39,855 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 21:30:39,855 INFO L195 NwaCegarLoop]: trace histogram [8, 8, 8, 8, 6, 6, 6, 6, 6, 4, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 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, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-23 21:30:39,882 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_46ae7aed-a01c-40ac-a605-40d62c69fa2a/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2023-11-23 21:30:40,081 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_46ae7aed-a01c-40ac-a605-40d62c69fa2a/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable1 [2023-11-23 21:30:40,082 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting ULTIMATE.startErr1ASSERT_VIOLATIONINTEGER_OVERFLOW === [ULTIMATE.startErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, ULTIMATE.startErr1ASSERT_VIOLATIONINTEGER_OVERFLOW] === [2023-11-23 21:30:40,082 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 21:30:40,082 INFO L85 PathProgramCache]: Analyzing trace with hash 1804981633, now seen corresponding path program 1 times [2023-11-23 21:30:40,083 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-23 21:30:40,083 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1828637584] [2023-11-23 21:30:40,083 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 21:30:40,083 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 21:30:40,266 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 21:30:41,189 INFO L134 CoverageAnalysis]: Checked inductivity of 312 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 286 trivial. 0 not checked. [2023-11-23 21:30:41,189 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-23 21:30:41,189 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1828637584] [2023-11-23 21:30:41,190 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1828637584] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-23 21:30:41,190 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [512474372] [2023-11-23 21:30:41,190 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 21:30:41,190 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 21:30:41,191 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_46ae7aed-a01c-40ac-a605-40d62c69fa2a/bin/utaipan-verify-mE87zJ7Ire/z3 [2023-11-23 21:30:41,192 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_46ae7aed-a01c-40ac-a605-40d62c69fa2a/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-23 21:30:41,217 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_46ae7aed-a01c-40ac-a605-40d62c69fa2a/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2023-11-23 21:30:42,126 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 21:30:42,143 INFO L262 TraceCheckSpWp]: Trace formula consists of 3246 conjuncts, 7 conjunts are in the unsatisfiable core [2023-11-23 21:30:42,152 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-23 21:30:42,333 INFO L134 CoverageAnalysis]: Checked inductivity of 312 backedges. 8 proven. 1 refuted. 0 times theorem prover too weak. 303 trivial. 0 not checked. [2023-11-23 21:30:42,333 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-23 21:30:42,738 INFO L134 CoverageAnalysis]: Checked inductivity of 312 backedges. 8 proven. 1 refuted. 0 times theorem prover too weak. 303 trivial. 0 not checked. [2023-11-23 21:30:42,738 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [512474372] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-23 21:30:42,738 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [661143912] [2023-11-23 21:30:42,763 INFO L159 IcfgInterpreter]: Started Sifa with 101 locations of interest [2023-11-23 21:30:42,763 INFO L166 IcfgInterpreter]: Building call graph [2023-11-23 21:30:42,768 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-23 21:30:42,773 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-23 21:30:42,774 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs