./Ultimate.py --spec ../../sv-benchmarks/c/properties/unreach-call.prp --file ../../sv-benchmarks/c/aws-c-common/aws_priority_queue_clean_up_harness.i --full-output --architecture 64bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 0e0057cc Calling Ultimate with: /usr/lib/jvm/java-11-openjdk-amd64/bin/java -Dosgi.configuration.area=/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5b71d6ca-f486-4540-8cb5-b6662b7dbd5f/bin/utaipan-verify-SwPr7d2a91/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5b71d6ca-f486-4540-8cb5-b6662b7dbd5f/bin/utaipan-verify-SwPr7d2a91/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5b71d6ca-f486-4540-8cb5-b6662b7dbd5f/bin/utaipan-verify-SwPr7d2a91/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5b71d6ca-f486-4540-8cb5-b6662b7dbd5f/bin/utaipan-verify-SwPr7d2a91/config/TaipanReach.xml -i ../../sv-benchmarks/c/aws-c-common/aws_priority_queue_clean_up_harness.i -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5b71d6ca-f486-4540-8cb5-b6662b7dbd5f/bin/utaipan-verify-SwPr7d2a91/config/svcomp-Reach-64bit-Taipan_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5b71d6ca-f486-4540-8cb5-b6662b7dbd5f/bin/utaipan-verify-SwPr7d2a91 --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 efb3bc3d53d5de978717fadeb26804aec5f97721ade955fc2d1463ef24ff6010 --- Real Ultimate output --- This is Ultimate 0.2.4-dev-0e0057c [2023-11-24 23:57:21,823 INFO L188 SettingsManager]: Resetting all preferences to default values... [2023-11-24 23:57:21,920 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5b71d6ca-f486-4540-8cb5-b6662b7dbd5f/bin/utaipan-verify-SwPr7d2a91/config/svcomp-Reach-64bit-Taipan_Default.epf [2023-11-24 23:57:21,927 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2023-11-24 23:57:21,927 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2023-11-24 23:57:21,977 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2023-11-24 23:57:21,978 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2023-11-24 23:57:21,979 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2023-11-24 23:57:21,980 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2023-11-24 23:57:21,980 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2023-11-24 23:57:21,981 INFO L153 SettingsManager]: * User list type=DISABLED [2023-11-24 23:57:21,985 INFO L151 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2023-11-24 23:57:21,986 INFO L153 SettingsManager]: * Explicit value domain=true [2023-11-24 23:57:21,991 INFO L153 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2023-11-24 23:57:21,992 INFO L153 SettingsManager]: * Octagon Domain=false [2023-11-24 23:57:21,992 INFO L153 SettingsManager]: * Abstract domain=CompoundDomain [2023-11-24 23:57:21,993 INFO L153 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2023-11-24 23:57:21,994 INFO L153 SettingsManager]: * Use the RCFG-of-the-future interface=true [2023-11-24 23:57:21,994 INFO L153 SettingsManager]: * Interval Domain=false [2023-11-24 23:57:21,995 INFO L151 SettingsManager]: Preferences of Sifa differ from their defaults: [2023-11-24 23:57:21,995 INFO L153 SettingsManager]: * Call Summarizer=TopInputCallSummarizer [2023-11-24 23:57:21,996 INFO L153 SettingsManager]: * Simplification Technique=POLY_PAC [2023-11-24 23:57:21,997 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2023-11-24 23:57:21,998 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2023-11-24 23:57:21,998 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2023-11-24 23:57:21,999 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2023-11-24 23:57:21,999 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2023-11-24 23:57:21,999 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2023-11-24 23:57:22,000 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2023-11-24 23:57:22,001 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2023-11-24 23:57:22,002 INFO L153 SettingsManager]: * Use constant arrays=true [2023-11-24 23:57:22,003 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2023-11-24 23:57:22,003 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2023-11-24 23:57:22,003 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2023-11-24 23:57:22,003 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-11-24 23:57:22,004 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2023-11-24 23:57:22,004 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2023-11-24 23:57:22,004 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2023-11-24 23:57:22,004 INFO L153 SettingsManager]: * Trace refinement strategy=SIFA_TAIPAN [2023-11-24 23:57:22,005 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2023-11-24 23:57:22,005 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2023-11-24 23:57:22,005 INFO L153 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2023-11-24 23:57:22,006 INFO L153 SettingsManager]: * Trace refinement exception blacklist=NONE [2023-11-24 23:57:22,006 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2023-11-24 23:57:22,006 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_5b71d6ca-f486-4540-8cb5-b6662b7dbd5f/bin/utaipan-verify-SwPr7d2a91/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_5b71d6ca-f486-4540-8cb5-b6662b7dbd5f/bin/utaipan-verify-SwPr7d2a91 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 -> efb3bc3d53d5de978717fadeb26804aec5f97721ade955fc2d1463ef24ff6010 [2023-11-24 23:57:22,320 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2023-11-24 23:57:22,366 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2023-11-24 23:57:22,369 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2023-11-24 23:57:22,370 INFO L270 PluginConnector]: Initializing CDTParser... [2023-11-24 23:57:22,370 INFO L274 PluginConnector]: CDTParser initialized [2023-11-24 23:57:22,372 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5b71d6ca-f486-4540-8cb5-b6662b7dbd5f/bin/utaipan-verify-SwPr7d2a91/../../sv-benchmarks/c/aws-c-common/aws_priority_queue_clean_up_harness.i [2023-11-24 23:57:25,548 INFO L533 CDTParser]: Created temporary CDT project at NULL [2023-11-24 23:57:26,144 INFO L384 CDTParser]: Found 1 translation units. [2023-11-24 23:57:26,145 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5b71d6ca-f486-4540-8cb5-b6662b7dbd5f/sv-benchmarks/c/aws-c-common/aws_priority_queue_clean_up_harness.i [2023-11-24 23:57:26,181 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5b71d6ca-f486-4540-8cb5-b6662b7dbd5f/bin/utaipan-verify-SwPr7d2a91/data/c18fadcd1/d5a75765b8714e98b82afc0a404bc314/FLAG62953f805 [2023-11-24 23:57:26,197 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5b71d6ca-f486-4540-8cb5-b6662b7dbd5f/bin/utaipan-verify-SwPr7d2a91/data/c18fadcd1/d5a75765b8714e98b82afc0a404bc314 [2023-11-24 23:57:26,202 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2023-11-24 23:57:26,205 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2023-11-24 23:57:26,210 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2023-11-24 23:57:26,210 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2023-11-24 23:57:26,216 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2023-11-24 23:57:26,217 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 24.11 11:57:26" (1/1) ... [2023-11-24 23:57:26,218 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@2996e051 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.11 11:57:26, skipping insertion in model container [2023-11-24 23:57:26,218 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 24.11 11:57:26" (1/1) ... [2023-11-24 23:57:26,354 INFO L177 MainTranslator]: Built tables and reachable declarations [2023-11-24 23:57:26,634 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_5b71d6ca-f486-4540-8cb5-b6662b7dbd5f/sv-benchmarks/c/aws-c-common/aws_priority_queue_clean_up_harness.i[4501,4514] [2023-11-24 23:57:26,643 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_5b71d6ca-f486-4540-8cb5-b6662b7dbd5f/sv-benchmarks/c/aws-c-common/aws_priority_queue_clean_up_harness.i[4561,4574] [2023-11-24 23:57:27,785 WARN L1590 CHandler]: Possible shadowing of function index [2023-11-24 23:57:27,786 WARN L1590 CHandler]: Possible shadowing of function index [2023-11-24 23:57:27,787 WARN L1590 CHandler]: Possible shadowing of function index [2023-11-24 23:57:27,792 WARN L1590 CHandler]: Possible shadowing of function index [2023-11-24 23:57:27,793 WARN L1590 CHandler]: Possible shadowing of function index [2023-11-24 23:57:27,808 WARN L1590 CHandler]: Possible shadowing of function index [2023-11-24 23:57:27,809 WARN L1590 CHandler]: Possible shadowing of function index [2023-11-24 23:57:27,811 WARN L1590 CHandler]: Possible shadowing of function index [2023-11-24 23:57:27,812 WARN L1590 CHandler]: Possible shadowing of function index [2023-11-24 23:57:28,318 WARN L638 FunctionHandler]: implicit declaration of function __atomic_load_n [2023-11-24 23:57:28,320 WARN L638 FunctionHandler]: implicit declaration of function __atomic_store_n [2023-11-24 23:57:28,321 WARN L638 FunctionHandler]: implicit declaration of function __atomic_exchange_n [2023-11-24 23:57:28,325 WARN L638 FunctionHandler]: implicit declaration of function __atomic_compare_exchange_n [2023-11-24 23:57:28,336 WARN L638 FunctionHandler]: implicit declaration of function __atomic_fetch_add [2023-11-24 23:57:28,336 WARN L638 FunctionHandler]: implicit declaration of function __atomic_fetch_sub [2023-11-24 23:57:28,337 WARN L638 FunctionHandler]: implicit declaration of function __atomic_fetch_or [2023-11-24 23:57:28,337 WARN L638 FunctionHandler]: implicit declaration of function __atomic_fetch_and [2023-11-24 23:57:28,338 WARN L638 FunctionHandler]: implicit declaration of function __atomic_fetch_xor [2023-11-24 23:57:28,339 WARN L638 FunctionHandler]: implicit declaration of function __atomic_thread_fence [2023-11-24 23:57:28,523 WARN L1590 CHandler]: Possible shadowing of function index [2023-11-24 23:57:28,523 WARN L1590 CHandler]: Possible shadowing of function index [2023-11-24 23:57:28,584 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-24 23:57:28,630 INFO L202 MainTranslator]: Completed pre-run [2023-11-24 23:57:28,652 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_5b71d6ca-f486-4540-8cb5-b6662b7dbd5f/sv-benchmarks/c/aws-c-common/aws_priority_queue_clean_up_harness.i[4501,4514] [2023-11-24 23:57:28,661 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_5b71d6ca-f486-4540-8cb5-b6662b7dbd5f/sv-benchmarks/c/aws-c-common/aws_priority_queue_clean_up_harness.i[4561,4574] [2023-11-24 23:57:28,730 WARN L1590 CHandler]: Possible shadowing of function index [2023-11-24 23:57:28,730 WARN L1590 CHandler]: Possible shadowing of function index [2023-11-24 23:57:28,731 WARN L1590 CHandler]: Possible shadowing of function index [2023-11-24 23:57:28,731 WARN L1590 CHandler]: Possible shadowing of function index [2023-11-24 23:57:28,732 WARN L1590 CHandler]: Possible shadowing of function index [2023-11-24 23:57:28,740 WARN L1590 CHandler]: Possible shadowing of function index [2023-11-24 23:57:28,740 WARN L1590 CHandler]: Possible shadowing of function index [2023-11-24 23:57:28,742 WARN L1590 CHandler]: Possible shadowing of function index [2023-11-24 23:57:28,742 WARN L1590 CHandler]: Possible shadowing of function index [2023-11-24 23:57:28,782 WARN L638 FunctionHandler]: implicit declaration of function __atomic_load_n [2023-11-24 23:57:28,783 WARN L638 FunctionHandler]: implicit declaration of function __atomic_store_n [2023-11-24 23:57:28,784 WARN L638 FunctionHandler]: implicit declaration of function __atomic_exchange_n [2023-11-24 23:57:28,785 WARN L638 FunctionHandler]: implicit declaration of function __atomic_compare_exchange_n [2023-11-24 23:57:28,786 WARN L638 FunctionHandler]: implicit declaration of function __atomic_fetch_add [2023-11-24 23:57:28,787 WARN L638 FunctionHandler]: implicit declaration of function __atomic_fetch_sub [2023-11-24 23:57:28,788 WARN L638 FunctionHandler]: implicit declaration of function __atomic_fetch_or [2023-11-24 23:57:28,788 WARN L638 FunctionHandler]: implicit declaration of function __atomic_fetch_and [2023-11-24 23:57:28,789 WARN L638 FunctionHandler]: implicit declaration of function __atomic_fetch_xor [2023-11-24 23:57:28,789 WARN L638 FunctionHandler]: implicit declaration of function __atomic_thread_fence [2023-11-24 23:57:28,825 WARN L1590 CHandler]: Possible shadowing of function index [2023-11-24 23:57:28,825 WARN L1590 CHandler]: Possible shadowing of function index [2023-11-24 23:57:28,834 WARN L75 lationResultReporter]: Unsoundness Warning: Ignoring inline assembler instruction C: __asm__ __volatile__("" : : "r"(pBuf) : "memory"); [7703-7714] [2023-11-24 23:57:28,857 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-24 23:57:29,191 WARN L675 CHandler]: The function __atomic_fetch_or is called, but not defined or handled by StandardFunctionHandler. [2023-11-24 23:57:29,191 WARN L675 CHandler]: The function __atomic_fetch_sub is called, but not defined or handled by StandardFunctionHandler. [2023-11-24 23:57:29,192 WARN L675 CHandler]: The function __atomic_exchange_n is called, but not defined or handled by StandardFunctionHandler. [2023-11-24 23:57:29,192 WARN L675 CHandler]: The function __atomic_fetch_xor is called, but not defined or handled by StandardFunctionHandler. [2023-11-24 23:57:29,192 WARN L675 CHandler]: The function htons is called, but not defined or handled by StandardFunctionHandler. [2023-11-24 23:57:29,193 WARN L675 CHandler]: The function ntohl is called, but not defined or handled by StandardFunctionHandler. [2023-11-24 23:57:29,193 WARN L675 CHandler]: The function __atomic_compare_exchange_n is called, but not defined or handled by StandardFunctionHandler. [2023-11-24 23:57:29,194 WARN L675 CHandler]: The function __atomic_fetch_add is called, but not defined or handled by StandardFunctionHandler. [2023-11-24 23:57:29,194 WARN L675 CHandler]: The function fprintf is called, but not defined or handled by StandardFunctionHandler. [2023-11-24 23:57:29,194 WARN L675 CHandler]: The function htonl is called, but not defined or handled by StandardFunctionHandler. [2023-11-24 23:57:29,195 WARN L675 CHandler]: The function __atomic_store_n is called, but not defined or handled by StandardFunctionHandler. [2023-11-24 23:57:29,195 WARN L675 CHandler]: The function ntohs is called, but not defined or handled by StandardFunctionHandler. [2023-11-24 23:57:29,196 WARN L675 CHandler]: The function __atomic_load_n is called, but not defined or handled by StandardFunctionHandler. [2023-11-24 23:57:29,196 WARN L675 CHandler]: The function __atomic_thread_fence is called, but not defined or handled by StandardFunctionHandler. [2023-11-24 23:57:29,198 WARN L675 CHandler]: The function __atomic_fetch_and is called, but not defined or handled by StandardFunctionHandler. [2023-11-24 23:57:29,207 INFO L206 MainTranslator]: Completed translation [2023-11-24 23:57:29,208 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.11 11:57:29 WrapperNode [2023-11-24 23:57:29,209 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2023-11-24 23:57:29,210 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2023-11-24 23:57:29,210 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2023-11-24 23:57:29,211 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2023-11-24 23:57:29,219 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.11 11:57:29" (1/1) ... [2023-11-24 23:57:29,329 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.11 11:57:29" (1/1) ... [2023-11-24 23:57:29,420 INFO L138 Inliner]: procedures = 688, calls = 1498, calls flagged for inlining = 55, calls inlined = 9, statements flattened = 596 [2023-11-24 23:57:29,420 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2023-11-24 23:57:29,421 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2023-11-24 23:57:29,421 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2023-11-24 23:57:29,422 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2023-11-24 23:57:29,432 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.11 11:57:29" (1/1) ... [2023-11-24 23:57:29,432 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.11 11:57:29" (1/1) ... [2023-11-24 23:57:29,446 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.11 11:57:29" (1/1) ... [2023-11-24 23:57:29,447 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.11 11:57:29" (1/1) ... [2023-11-24 23:57:29,512 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.11 11:57:29" (1/1) ... [2023-11-24 23:57:29,521 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.11 11:57:29" (1/1) ... [2023-11-24 23:57:29,549 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.11 11:57:29" (1/1) ... [2023-11-24 23:57:29,554 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.11 11:57:29" (1/1) ... [2023-11-24 23:57:29,563 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2023-11-24 23:57:29,564 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2023-11-24 23:57:29,564 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2023-11-24 23:57:29,564 INFO L274 PluginConnector]: RCFGBuilder initialized [2023-11-24 23:57:29,594 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.11 11:57:29" (1/1) ... [2023-11-24 23:57:29,600 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-11-24 23:57:29,629 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5b71d6ca-f486-4540-8cb5-b6662b7dbd5f/bin/utaipan-verify-SwPr7d2a91/z3 [2023-11-24 23:57:29,663 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5b71d6ca-f486-4540-8cb5-b6662b7dbd5f/bin/utaipan-verify-SwPr7d2a91/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2023-11-24 23:57:29,734 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5b71d6ca-f486-4540-8cb5-b6662b7dbd5f/bin/utaipan-verify-SwPr7d2a91/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2023-11-24 23:57:29,786 INFO L130 BoogieDeclarations]: Found specification of procedure aws_is_mem_zeroed [2023-11-24 23:57:29,786 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_is_mem_zeroed [2023-11-24 23:57:29,786 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2023-11-24 23:57:29,787 INFO L130 BoogieDeclarations]: Found specification of procedure aws_array_list_is_bounded [2023-11-24 23:57:29,787 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_array_list_is_bounded [2023-11-24 23:57:29,787 INFO L130 BoogieDeclarations]: Found specification of procedure aws_array_list_is_valid [2023-11-24 23:57:29,787 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_array_list_is_valid [2023-11-24 23:57:29,788 INFO L130 BoogieDeclarations]: Found specification of procedure nondet_bool [2023-11-24 23:57:29,788 INFO L138 BoogieDeclarations]: Found implementation of procedure nondet_bool [2023-11-24 23:57:29,788 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2023-11-24 23:57:29,788 INFO L130 BoogieDeclarations]: Found specification of procedure aws_raise_error [2023-11-24 23:57:29,788 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_raise_error [2023-11-24 23:57:29,788 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2023-11-24 23:57:29,789 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2023-11-24 23:57:29,789 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnHeap [2023-11-24 23:57:29,789 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2023-11-24 23:57:29,789 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$ [2023-11-24 23:57:29,789 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2023-11-24 23:57:29,790 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2023-11-24 23:57:29,790 INFO L130 BoogieDeclarations]: Found specification of procedure aws_array_list_clean_up [2023-11-24 23:57:29,790 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_array_list_clean_up [2023-11-24 23:57:29,790 INFO L130 BoogieDeclarations]: Found specification of procedure bounded_malloc [2023-11-24 23:57:29,790 INFO L138 BoogieDeclarations]: Found implementation of procedure bounded_malloc [2023-11-24 23:57:29,791 INFO L130 BoogieDeclarations]: Found specification of procedure aws_mul_size_checked [2023-11-24 23:57:29,791 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_mul_size_checked [2023-11-24 23:57:29,791 INFO L130 BoogieDeclarations]: Found specification of procedure aws_priority_queue_is_valid [2023-11-24 23:57:29,791 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_priority_queue_is_valid [2023-11-24 23:57:29,791 INFO L130 BoogieDeclarations]: Found specification of procedure aws_mem_release [2023-11-24 23:57:29,791 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_mem_release [2023-11-24 23:57:29,792 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2023-11-24 23:57:29,792 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2023-11-24 23:57:29,792 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2023-11-24 23:57:29,792 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$ [2023-11-24 23:57:29,792 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$ [2023-11-24 23:57:29,793 INFO L130 BoogieDeclarations]: Found specification of procedure can_fail_allocator [2023-11-24 23:57:29,793 INFO L138 BoogieDeclarations]: Found implementation of procedure can_fail_allocator [2023-11-24 23:57:29,793 INFO L130 BoogieDeclarations]: Found specification of procedure __CPROVER_overflow_mult [2023-11-24 23:57:29,793 INFO L138 BoogieDeclarations]: Found implementation of procedure __CPROVER_overflow_mult [2023-11-24 23:57:29,795 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2023-11-24 23:57:29,796 INFO L130 BoogieDeclarations]: Found specification of procedure memset_impl [2023-11-24 23:57:29,796 INFO L138 BoogieDeclarations]: Found implementation of procedure memset_impl [2023-11-24 23:57:29,796 INFO L130 BoogieDeclarations]: Found specification of procedure my_memset [2023-11-24 23:57:29,796 INFO L138 BoogieDeclarations]: Found implementation of procedure my_memset [2023-11-24 23:57:29,796 INFO L130 BoogieDeclarations]: Found specification of procedure ensure_array_list_has_allocated_data_member [2023-11-24 23:57:29,796 INFO L138 BoogieDeclarations]: Found implementation of procedure ensure_array_list_has_allocated_data_member [2023-11-24 23:57:29,797 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2023-11-24 23:57:30,159 INFO L241 CfgBuilder]: Building ICFG [2023-11-24 23:57:30,161 INFO L267 CfgBuilder]: Building CFG for each procedure with an implementation [2023-11-24 23:57:31,175 INFO L282 CfgBuilder]: Performing block encoding [2023-11-24 23:57:31,403 INFO L304 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2023-11-24 23:57:31,403 INFO L309 CfgBuilder]: Removed 4 assume(true) statements. [2023-11-24 23:57:31,405 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 24.11 11:57:31 BoogieIcfgContainer [2023-11-24 23:57:31,405 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2023-11-24 23:57:31,408 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2023-11-24 23:57:31,408 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2023-11-24 23:57:31,411 INFO L274 PluginConnector]: TraceAbstraction initialized [2023-11-24 23:57:31,412 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 24.11 11:57:26" (1/3) ... [2023-11-24 23:57:31,413 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@476f6c97 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 24.11 11:57:31, skipping insertion in model container [2023-11-24 23:57:31,413 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.11 11:57:29" (2/3) ... [2023-11-24 23:57:31,413 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@476f6c97 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 24.11 11:57:31, skipping insertion in model container [2023-11-24 23:57:31,414 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 24.11 11:57:31" (3/3) ... [2023-11-24 23:57:31,415 INFO L112 eAbstractionObserver]: Analyzing ICFG aws_priority_queue_clean_up_harness.i [2023-11-24 23:57:31,436 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2023-11-24 23:57:31,436 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2023-11-24 23:57:31,490 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-11-24 23:57:31,498 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;@5808df91, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2023-11-24 23:57:31,498 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2023-11-24 23:57:31,503 INFO L276 IsEmpty]: Start isEmpty. Operand has 126 states, 73 states have (on average 1.2328767123287672) internal successors, (90), 74 states have internal predecessors, (90), 35 states have call successors, (35), 17 states have call predecessors, (35), 17 states have return successors, (35), 35 states have call predecessors, (35), 35 states have call successors, (35) [2023-11-24 23:57:31,518 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 83 [2023-11-24 23:57:31,518 INFO L187 NwaCegarLoop]: Found error trace [2023-11-24 23:57:31,519 INFO L195 NwaCegarLoop]: trace histogram [5, 3, 3, 3, 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] [2023-11-24 23:57:31,520 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-24 23:57:31,525 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-24 23:57:31,526 INFO L85 PathProgramCache]: Analyzing trace with hash -1188117460, now seen corresponding path program 1 times [2023-11-24 23:57:31,536 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-24 23:57:31,536 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1362874565] [2023-11-24 23:57:31,537 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-24 23:57:31,537 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-24 23:57:32,135 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-24 23:57:32,408 INFO L134 CoverageAnalysis]: Checked inductivity of 44 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 44 trivial. 0 not checked. [2023-11-24 23:57:32,409 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-24 23:57:32,409 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1362874565] [2023-11-24 23:57:32,411 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1362874565] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-24 23:57:32,411 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-24 23:57:32,412 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2023-11-24 23:57:32,413 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1969569985] [2023-11-24 23:57:32,418 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-24 23:57:32,425 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2023-11-24 23:57:32,429 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-24 23:57:32,469 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2023-11-24 23:57:32,470 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2023-11-24 23:57:32,473 INFO L87 Difference]: Start difference. First operand has 126 states, 73 states have (on average 1.2328767123287672) internal successors, (90), 74 states have internal predecessors, (90), 35 states have call successors, (35), 17 states have call predecessors, (35), 17 states have return successors, (35), 35 states have call predecessors, (35), 35 states have call successors, (35) Second operand has 2 states, 2 states have (on average 16.0) internal successors, (32), 2 states have internal predecessors, (32), 2 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (14), 2 states have call predecessors, (14), 2 states have call successors, (14) [2023-11-24 23:57:32,648 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-24 23:57:32,649 INFO L93 Difference]: Finished difference Result 199 states and 255 transitions. [2023-11-24 23:57:32,650 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2023-11-24 23:57:32,652 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 16.0) internal successors, (32), 2 states have internal predecessors, (32), 2 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (14), 2 states have call predecessors, (14), 2 states have call successors, (14) Word has length 82 [2023-11-24 23:57:32,653 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-24 23:57:32,663 INFO L225 Difference]: With dead ends: 199 [2023-11-24 23:57:32,663 INFO L226 Difference]: Without dead ends: 124 [2023-11-24 23:57:32,667 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2023-11-24 23:57:32,671 INFO L413 NwaCegarLoop]: 134 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 23 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 134 SdHoareTripleChecker+Invalid, 23 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 23 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-24 23:57:32,672 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 134 Invalid, 23 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 23 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-24 23:57:32,690 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 124 states. [2023-11-24 23:57:32,719 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 124 to 124. [2023-11-24 23:57:32,721 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 124 states, 71 states have (on average 1.2112676056338028) internal successors, (86), 73 states have internal predecessors, (86), 35 states have call successors, (35), 17 states have call predecessors, (35), 17 states have return successors, (34), 34 states have call predecessors, (34), 34 states have call successors, (34) [2023-11-24 23:57:32,724 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 124 states to 124 states and 155 transitions. [2023-11-24 23:57:32,726 INFO L78 Accepts]: Start accepts. Automaton has 124 states and 155 transitions. Word has length 82 [2023-11-24 23:57:32,728 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-24 23:57:32,728 INFO L495 AbstractCegarLoop]: Abstraction has 124 states and 155 transitions. [2023-11-24 23:57:32,728 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 16.0) internal successors, (32), 2 states have internal predecessors, (32), 2 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (14), 2 states have call predecessors, (14), 2 states have call successors, (14) [2023-11-24 23:57:32,729 INFO L276 IsEmpty]: Start isEmpty. Operand 124 states and 155 transitions. [2023-11-24 23:57:32,734 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 96 [2023-11-24 23:57:32,735 INFO L187 NwaCegarLoop]: Found error trace [2023-11-24 23:57:32,735 INFO L195 NwaCegarLoop]: trace histogram [6, 3, 3, 3, 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] [2023-11-24 23:57:32,735 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2023-11-24 23:57:32,736 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-24 23:57:32,738 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-24 23:57:32,738 INFO L85 PathProgramCache]: Analyzing trace with hash -1843381692, now seen corresponding path program 1 times [2023-11-24 23:57:32,738 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-24 23:57:32,738 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [266264382] [2023-11-24 23:57:32,739 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-24 23:57:32,739 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-24 23:57:32,905 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-24 23:57:33,547 INFO L134 CoverageAnalysis]: Checked inductivity of 54 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 54 trivial. 0 not checked. [2023-11-24 23:57:33,548 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-24 23:57:33,548 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [266264382] [2023-11-24 23:57:33,548 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [266264382] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-24 23:57:33,548 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-24 23:57:33,548 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2023-11-24 23:57:33,549 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2005532842] [2023-11-24 23:57:33,549 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-24 23:57:33,550 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-11-24 23:57:33,550 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-24 23:57:33,551 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-11-24 23:57:33,551 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2023-11-24 23:57:33,552 INFO L87 Difference]: Start difference. First operand 124 states and 155 transitions. Second operand has 5 states, 5 states have (on average 7.6) internal successors, (38), 5 states have internal predecessors, (38), 3 states have call successors, (18), 2 states have call predecessors, (18), 2 states have return successors, (17), 3 states have call predecessors, (17), 3 states have call successors, (17) [2023-11-24 23:57:33,936 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-24 23:57:33,940 INFO L93 Difference]: Finished difference Result 200 states and 248 transitions. [2023-11-24 23:57:33,941 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2023-11-24 23:57:33,941 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 7.6) internal successors, (38), 5 states have internal predecessors, (38), 3 states have call successors, (18), 2 states have call predecessors, (18), 2 states have return successors, (17), 3 states have call predecessors, (17), 3 states have call successors, (17) Word has length 95 [2023-11-24 23:57:33,942 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-24 23:57:33,944 INFO L225 Difference]: With dead ends: 200 [2023-11-24 23:57:33,946 INFO L226 Difference]: Without dead ends: 124 [2023-11-24 23:57:33,948 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2023-11-24 23:57:33,951 INFO L413 NwaCegarLoop]: 127 mSDtfsCounter, 18 mSDsluCounter, 346 mSDsCounter, 0 mSdLazyCounter, 107 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 29 SdHoareTripleChecker+Valid, 473 SdHoareTripleChecker+Invalid, 107 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 107 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2023-11-24 23:57:33,952 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [29 Valid, 473 Invalid, 107 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 107 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2023-11-24 23:57:33,959 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 124 states. [2023-11-24 23:57:33,974 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 124 to 124. [2023-11-24 23:57:33,986 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 124 states, 71 states have (on average 1.1971830985915493) internal successors, (85), 73 states have internal predecessors, (85), 35 states have call successors, (35), 17 states have call predecessors, (35), 17 states have return successors, (34), 34 states have call predecessors, (34), 34 states have call successors, (34) [2023-11-24 23:57:33,989 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 124 states to 124 states and 154 transitions. [2023-11-24 23:57:33,993 INFO L78 Accepts]: Start accepts. Automaton has 124 states and 154 transitions. Word has length 95 [2023-11-24 23:57:33,994 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-24 23:57:33,994 INFO L495 AbstractCegarLoop]: Abstraction has 124 states and 154 transitions. [2023-11-24 23:57:33,994 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 7.6) internal successors, (38), 5 states have internal predecessors, (38), 3 states have call successors, (18), 2 states have call predecessors, (18), 2 states have return successors, (17), 3 states have call predecessors, (17), 3 states have call successors, (17) [2023-11-24 23:57:33,994 INFO L276 IsEmpty]: Start isEmpty. Operand 124 states and 154 transitions. [2023-11-24 23:57:33,999 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 104 [2023-11-24 23:57:34,005 INFO L187 NwaCegarLoop]: Found error trace [2023-11-24 23:57:34,005 INFO L195 NwaCegarLoop]: trace histogram [6, 3, 3, 3, 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] [2023-11-24 23:57:34,006 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2023-11-24 23:57:34,006 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-24 23:57:34,007 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-24 23:57:34,007 INFO L85 PathProgramCache]: Analyzing trace with hash 138453490, now seen corresponding path program 1 times [2023-11-24 23:57:34,008 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-24 23:57:34,008 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1057293857] [2023-11-24 23:57:34,010 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-24 23:57:34,010 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-24 23:57:34,176 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-24 23:57:34,861 INFO L134 CoverageAnalysis]: Checked inductivity of 54 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 54 trivial. 0 not checked. [2023-11-24 23:57:34,862 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-24 23:57:34,862 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1057293857] [2023-11-24 23:57:34,862 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1057293857] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-24 23:57:34,862 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-24 23:57:34,863 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2023-11-24 23:57:34,863 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [104484438] [2023-11-24 23:57:34,863 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-24 23:57:34,864 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2023-11-24 23:57:34,864 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-24 23:57:34,865 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2023-11-24 23:57:34,865 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2023-11-24 23:57:34,866 INFO L87 Difference]: Start difference. First operand 124 states and 154 transitions. Second operand has 7 states, 7 states have (on average 6.285714285714286) internal successors, (44), 7 states have internal predecessors, (44), 4 states have call successors, (19), 2 states have call predecessors, (19), 3 states have return successors, (18), 4 states have call predecessors, (18), 4 states have call successors, (18) [2023-11-24 23:57:35,437 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-24 23:57:35,440 INFO L93 Difference]: Finished difference Result 211 states and 265 transitions. [2023-11-24 23:57:35,440 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2023-11-24 23:57:35,441 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 6.285714285714286) internal successors, (44), 7 states have internal predecessors, (44), 4 states have call successors, (19), 2 states have call predecessors, (19), 3 states have return successors, (18), 4 states have call predecessors, (18), 4 states have call successors, (18) Word has length 103 [2023-11-24 23:57:35,441 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-24 23:57:35,444 INFO L225 Difference]: With dead ends: 211 [2023-11-24 23:57:35,445 INFO L226 Difference]: Without dead ends: 126 [2023-11-24 23:57:35,446 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 9 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=19, Invalid=53, Unknown=0, NotChecked=0, Total=72 [2023-11-24 23:57:35,447 INFO L413 NwaCegarLoop]: 126 mSDtfsCounter, 32 mSDsluCounter, 582 mSDsCounter, 0 mSdLazyCounter, 197 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 46 SdHoareTripleChecker+Valid, 708 SdHoareTripleChecker+Invalid, 201 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 197 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2023-11-24 23:57:35,448 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [46 Valid, 708 Invalid, 201 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 197 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2023-11-24 23:57:35,449 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 126 states. [2023-11-24 23:57:35,463 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 126 to 126. [2023-11-24 23:57:35,464 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 126 states, 72 states have (on average 1.1944444444444444) internal successors, (86), 75 states have internal predecessors, (86), 35 states have call successors, (35), 17 states have call predecessors, (35), 18 states have return successors, (36), 34 states have call predecessors, (36), 34 states have call successors, (36) [2023-11-24 23:57:35,466 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 126 states to 126 states and 157 transitions. [2023-11-24 23:57:35,466 INFO L78 Accepts]: Start accepts. Automaton has 126 states and 157 transitions. Word has length 103 [2023-11-24 23:57:35,467 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-24 23:57:35,467 INFO L495 AbstractCegarLoop]: Abstraction has 126 states and 157 transitions. [2023-11-24 23:57:35,467 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 6.285714285714286) internal successors, (44), 7 states have internal predecessors, (44), 4 states have call successors, (19), 2 states have call predecessors, (19), 3 states have return successors, (18), 4 states have call predecessors, (18), 4 states have call successors, (18) [2023-11-24 23:57:35,467 INFO L276 IsEmpty]: Start isEmpty. Operand 126 states and 157 transitions. [2023-11-24 23:57:35,471 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 113 [2023-11-24 23:57:35,472 INFO L187 NwaCegarLoop]: Found error trace [2023-11-24 23:57:35,472 INFO L195 NwaCegarLoop]: trace histogram [6, 3, 3, 3, 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-24 23:57:35,472 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2023-11-24 23:57:35,472 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-24 23:57:35,473 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-24 23:57:35,473 INFO L85 PathProgramCache]: Analyzing trace with hash 2062453710, now seen corresponding path program 1 times [2023-11-24 23:57:35,473 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-24 23:57:35,474 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [184186078] [2023-11-24 23:57:35,474 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-24 23:57:35,474 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-24 23:57:35,579 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-24 23:57:35,579 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1401071185] [2023-11-24 23:57:35,579 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-24 23:57:35,580 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-24 23:57:35,580 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5b71d6ca-f486-4540-8cb5-b6662b7dbd5f/bin/utaipan-verify-SwPr7d2a91/z3 [2023-11-24 23:57:35,583 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5b71d6ca-f486-4540-8cb5-b6662b7dbd5f/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-24 23:57:35,621 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5b71d6ca-f486-4540-8cb5-b6662b7dbd5f/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2023-11-24 23:57:36,219 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-24 23:57:36,231 INFO L262 TraceCheckSpWp]: Trace formula consists of 2385 conjuncts, 7 conjunts are in the unsatisfiable core [2023-11-24 23:57:36,244 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-24 23:57:36,354 INFO L134 CoverageAnalysis]: Checked inductivity of 54 backedges. 18 proven. 0 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2023-11-24 23:57:36,354 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-11-24 23:57:36,355 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-24 23:57:36,355 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [184186078] [2023-11-24 23:57:36,355 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-24 23:57:36,355 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1401071185] [2023-11-24 23:57:36,356 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1401071185] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-24 23:57:36,356 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-24 23:57:36,356 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2023-11-24 23:57:36,356 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [451119593] [2023-11-24 23:57:36,356 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-24 23:57:36,357 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2023-11-24 23:57:36,357 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-24 23:57:36,358 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2023-11-24 23:57:36,358 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2023-11-24 23:57:36,359 INFO L87 Difference]: Start difference. First operand 126 states and 157 transitions. Second operand has 6 states, 6 states have (on average 8.333333333333334) internal successors, (50), 6 states have internal predecessors, (50), 4 states have call successors, (21), 2 states have call predecessors, (21), 3 states have return successors, (20), 4 states have call predecessors, (20), 4 states have call successors, (20) [2023-11-24 23:57:37,035 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-24 23:57:37,039 INFO L93 Difference]: Finished difference Result 205 states and 253 transitions. [2023-11-24 23:57:37,040 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2023-11-24 23:57:37,040 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 8.333333333333334) internal successors, (50), 6 states have internal predecessors, (50), 4 states have call successors, (21), 2 states have call predecessors, (21), 3 states have return successors, (20), 4 states have call predecessors, (20), 4 states have call successors, (20) Word has length 112 [2023-11-24 23:57:37,041 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-24 23:57:37,044 INFO L225 Difference]: With dead ends: 205 [2023-11-24 23:57:37,044 INFO L226 Difference]: Without dead ends: 126 [2023-11-24 23:57:37,045 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 114 GetRequests, 107 SyntacticMatches, 0 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=24, Invalid=48, Unknown=0, NotChecked=0, Total=72 [2023-11-24 23:57:37,046 INFO L413 NwaCegarLoop]: 125 mSDtfsCounter, 24 mSDsluCounter, 457 mSDsCounter, 0 mSdLazyCounter, 139 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 32 SdHoareTripleChecker+Valid, 582 SdHoareTripleChecker+Invalid, 143 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 139 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2023-11-24 23:57:37,047 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [32 Valid, 582 Invalid, 143 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 139 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2023-11-24 23:57:37,048 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 126 states. [2023-11-24 23:57:37,061 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 126 to 126. [2023-11-24 23:57:37,062 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 126 states, 72 states have (on average 1.1805555555555556) internal successors, (85), 75 states have internal predecessors, (85), 35 states have call successors, (35), 17 states have call predecessors, (35), 18 states have return successors, (36), 34 states have call predecessors, (36), 34 states have call successors, (36) [2023-11-24 23:57:37,064 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 126 states to 126 states and 156 transitions. [2023-11-24 23:57:37,064 INFO L78 Accepts]: Start accepts. Automaton has 126 states and 156 transitions. Word has length 112 [2023-11-24 23:57:37,065 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-24 23:57:37,065 INFO L495 AbstractCegarLoop]: Abstraction has 126 states and 156 transitions. [2023-11-24 23:57:37,065 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 8.333333333333334) internal successors, (50), 6 states have internal predecessors, (50), 4 states have call successors, (21), 2 states have call predecessors, (21), 3 states have return successors, (20), 4 states have call predecessors, (20), 4 states have call successors, (20) [2023-11-24 23:57:37,066 INFO L276 IsEmpty]: Start isEmpty. Operand 126 states and 156 transitions. [2023-11-24 23:57:37,068 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 121 [2023-11-24 23:57:37,068 INFO L187 NwaCegarLoop]: Found error trace [2023-11-24 23:57:37,069 INFO L195 NwaCegarLoop]: trace histogram [6, 3, 3, 3, 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, 1, 1, 1] [2023-11-24 23:57:37,086 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5b71d6ca-f486-4540-8cb5-b6662b7dbd5f/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2023-11-24 23:57:37,279 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5b71d6ca-f486-4540-8cb5-b6662b7dbd5f/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-24 23:57:37,279 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-24 23:57:37,279 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-24 23:57:37,280 INFO L85 PathProgramCache]: Analyzing trace with hash 1168644479, now seen corresponding path program 1 times [2023-11-24 23:57:37,280 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-24 23:57:37,280 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2048859133] [2023-11-24 23:57:37,280 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-24 23:57:37,280 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-24 23:57:37,412 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-24 23:57:37,412 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1598443200] [2023-11-24 23:57:37,412 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-24 23:57:37,413 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-24 23:57:37,413 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5b71d6ca-f486-4540-8cb5-b6662b7dbd5f/bin/utaipan-verify-SwPr7d2a91/z3 [2023-11-24 23:57:37,414 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5b71d6ca-f486-4540-8cb5-b6662b7dbd5f/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-24 23:57:37,437 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5b71d6ca-f486-4540-8cb5-b6662b7dbd5f/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2023-11-24 23:57:38,089 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-24 23:57:38,103 INFO L262 TraceCheckSpWp]: Trace formula consists of 2439 conjuncts, 9 conjunts are in the unsatisfiable core [2023-11-24 23:57:38,111 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-24 23:57:38,281 INFO L134 CoverageAnalysis]: Checked inductivity of 58 backedges. 21 proven. 0 refuted. 0 times theorem prover too weak. 37 trivial. 0 not checked. [2023-11-24 23:57:38,282 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-11-24 23:57:38,282 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-24 23:57:38,282 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2048859133] [2023-11-24 23:57:38,282 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-24 23:57:38,282 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1598443200] [2023-11-24 23:57:38,283 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1598443200] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-24 23:57:38,283 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-24 23:57:38,283 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2023-11-24 23:57:38,283 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2137290952] [2023-11-24 23:57:38,283 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-24 23:57:38,290 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2023-11-24 23:57:38,290 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-24 23:57:38,291 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2023-11-24 23:57:38,291 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=43, Unknown=0, NotChecked=0, Total=56 [2023-11-24 23:57:38,292 INFO L87 Difference]: Start difference. First operand 126 states and 156 transitions. Second operand has 8 states, 8 states have (on average 7.0) internal successors, (56), 8 states have internal predecessors, (56), 5 states have call successors, (22), 2 states have call predecessors, (22), 4 states have return successors, (21), 5 states have call predecessors, (21), 5 states have call successors, (21) [2023-11-24 23:57:39,066 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-24 23:57:39,066 INFO L93 Difference]: Finished difference Result 210 states and 259 transitions. [2023-11-24 23:57:39,067 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2023-11-24 23:57:39,067 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 7.0) internal successors, (56), 8 states have internal predecessors, (56), 5 states have call successors, (22), 2 states have call predecessors, (22), 4 states have return successors, (21), 5 states have call predecessors, (21), 5 states have call successors, (21) Word has length 120 [2023-11-24 23:57:39,068 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-24 23:57:39,069 INFO L225 Difference]: With dead ends: 210 [2023-11-24 23:57:39,069 INFO L226 Difference]: Without dead ends: 126 [2023-11-24 23:57:39,070 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 124 GetRequests, 114 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=32, Invalid=100, Unknown=0, NotChecked=0, Total=132 [2023-11-24 23:57:39,071 INFO L413 NwaCegarLoop]: 120 mSDtfsCounter, 38 mSDsluCounter, 672 mSDsCounter, 0 mSdLazyCounter, 226 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 47 SdHoareTripleChecker+Valid, 792 SdHoareTripleChecker+Invalid, 235 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 226 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.7s IncrementalHoareTripleChecker+Time [2023-11-24 23:57:39,071 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [47 Valid, 792 Invalid, 235 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 226 Invalid, 0 Unknown, 0 Unchecked, 0.7s Time] [2023-11-24 23:57:39,072 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 126 states. [2023-11-24 23:57:39,083 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 126 to 126. [2023-11-24 23:57:39,084 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 126 states, 72 states have (on average 1.1805555555555556) internal successors, (85), 75 states have internal predecessors, (85), 35 states have call successors, (35), 17 states have call predecessors, (35), 18 states have return successors, (35), 34 states have call predecessors, (35), 34 states have call successors, (35) [2023-11-24 23:57:39,086 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 126 states to 126 states and 155 transitions. [2023-11-24 23:57:39,086 INFO L78 Accepts]: Start accepts. Automaton has 126 states and 155 transitions. Word has length 120 [2023-11-24 23:57:39,086 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-24 23:57:39,087 INFO L495 AbstractCegarLoop]: Abstraction has 126 states and 155 transitions. [2023-11-24 23:57:39,087 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 7.0) internal successors, (56), 8 states have internal predecessors, (56), 5 states have call successors, (22), 2 states have call predecessors, (22), 4 states have return successors, (21), 5 states have call predecessors, (21), 5 states have call successors, (21) [2023-11-24 23:57:39,087 INFO L276 IsEmpty]: Start isEmpty. Operand 126 states and 155 transitions. [2023-11-24 23:57:39,089 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 130 [2023-11-24 23:57:39,089 INFO L187 NwaCegarLoop]: Found error trace [2023-11-24 23:57:39,090 INFO L195 NwaCegarLoop]: trace histogram [6, 3, 3, 3, 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] [2023-11-24 23:57:39,101 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5b71d6ca-f486-4540-8cb5-b6662b7dbd5f/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2023-11-24 23:57:39,300 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5b71d6ca-f486-4540-8cb5-b6662b7dbd5f/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-24 23:57:39,300 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-24 23:57:39,300 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-24 23:57:39,301 INFO L85 PathProgramCache]: Analyzing trace with hash 1288177461, now seen corresponding path program 1 times [2023-11-24 23:57:39,301 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-24 23:57:39,301 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1232286824] [2023-11-24 23:57:39,301 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-24 23:57:39,301 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-24 23:57:39,429 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-24 23:57:39,429 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [245184722] [2023-11-24 23:57:39,429 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-24 23:57:39,430 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-24 23:57:39,430 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5b71d6ca-f486-4540-8cb5-b6662b7dbd5f/bin/utaipan-verify-SwPr7d2a91/z3 [2023-11-24 23:57:39,431 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5b71d6ca-f486-4540-8cb5-b6662b7dbd5f/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-24 23:57:39,473 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5b71d6ca-f486-4540-8cb5-b6662b7dbd5f/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2023-11-24 23:57:40,146 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-24 23:57:40,160 INFO L262 TraceCheckSpWp]: Trace formula consists of 2571 conjuncts, 17 conjunts are in the unsatisfiable core [2023-11-24 23:57:40,169 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-24 23:57:40,240 INFO L134 CoverageAnalysis]: Checked inductivity of 67 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 63 trivial. 0 not checked. [2023-11-24 23:57:40,240 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-24 23:57:40,557 INFO L134 CoverageAnalysis]: Checked inductivity of 67 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 63 trivial. 0 not checked. [2023-11-24 23:57:40,557 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-24 23:57:40,558 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1232286824] [2023-11-24 23:57:40,558 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-24 23:57:40,559 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [245184722] [2023-11-24 23:57:40,559 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [245184722] provided 1 perfect and 1 imperfect interpolant sequences [2023-11-24 23:57:40,559 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-11-24 23:57:40,559 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [8] total 12 [2023-11-24 23:57:40,559 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1731969050] [2023-11-24 23:57:40,559 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-24 23:57:40,560 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2023-11-24 23:57:40,560 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-24 23:57:40,561 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2023-11-24 23:57:40,562 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=25, Invalid=107, Unknown=0, NotChecked=0, Total=132 [2023-11-24 23:57:40,562 INFO L87 Difference]: Start difference. First operand 126 states and 155 transitions. Second operand has 6 states, 5 states have (on average 10.8) internal successors, (54), 4 states have internal predecessors, (54), 2 states have call successors, (22), 2 states have call predecessors, (22), 2 states have return successors, (21), 2 states have call predecessors, (21), 1 states have call successors, (21) [2023-11-24 23:57:41,022 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-24 23:57:41,022 INFO L93 Difference]: Finished difference Result 136 states and 169 transitions. [2023-11-24 23:57:41,030 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2023-11-24 23:57:41,031 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 10.8) internal successors, (54), 4 states have internal predecessors, (54), 2 states have call successors, (22), 2 states have call predecessors, (22), 2 states have return successors, (21), 2 states have call predecessors, (21), 1 states have call successors, (21) Word has length 129 [2023-11-24 23:57:41,032 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-24 23:57:41,033 INFO L225 Difference]: With dead ends: 136 [2023-11-24 23:57:41,033 INFO L226 Difference]: Without dead ends: 134 [2023-11-24 23:57:41,034 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 257 GetRequests, 246 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=29, Invalid=127, Unknown=0, NotChecked=0, Total=156 [2023-11-24 23:57:41,034 INFO L413 NwaCegarLoop]: 128 mSDtfsCounter, 6 mSDsluCounter, 508 mSDsCounter, 0 mSdLazyCounter, 126 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 636 SdHoareTripleChecker+Invalid, 127 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 126 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2023-11-24 23:57:41,035 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 636 Invalid, 127 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 126 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2023-11-24 23:57:41,036 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 134 states. [2023-11-24 23:57:41,047 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 134 to 133. [2023-11-24 23:57:41,057 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 133 states, 76 states have (on average 1.1710526315789473) internal successors, (89), 80 states have internal predecessors, (89), 36 states have call successors, (36), 18 states have call predecessors, (36), 20 states have return successors, (41), 35 states have call predecessors, (41), 35 states have call successors, (41) [2023-11-24 23:57:41,061 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 133 states to 133 states and 166 transitions. [2023-11-24 23:57:41,063 INFO L78 Accepts]: Start accepts. Automaton has 133 states and 166 transitions. Word has length 129 [2023-11-24 23:57:41,064 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-24 23:57:41,064 INFO L495 AbstractCegarLoop]: Abstraction has 133 states and 166 transitions. [2023-11-24 23:57:41,064 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 10.8) internal successors, (54), 4 states have internal predecessors, (54), 2 states have call successors, (22), 2 states have call predecessors, (22), 2 states have return successors, (21), 2 states have call predecessors, (21), 1 states have call successors, (21) [2023-11-24 23:57:41,065 INFO L276 IsEmpty]: Start isEmpty. Operand 133 states and 166 transitions. [2023-11-24 23:57:41,067 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 131 [2023-11-24 23:57:41,068 INFO L187 NwaCegarLoop]: Found error trace [2023-11-24 23:57:41,069 INFO L195 NwaCegarLoop]: trace histogram [6, 3, 3, 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] [2023-11-24 23:57:41,086 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5b71d6ca-f486-4540-8cb5-b6662b7dbd5f/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2023-11-24 23:57:41,279 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5b71d6ca-f486-4540-8cb5-b6662b7dbd5f/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable5 [2023-11-24 23:57:41,279 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-24 23:57:41,280 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-24 23:57:41,280 INFO L85 PathProgramCache]: Analyzing trace with hash -1533142051, now seen corresponding path program 1 times [2023-11-24 23:57:41,280 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-24 23:57:41,280 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [515710951] [2023-11-24 23:57:41,280 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-24 23:57:41,280 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-24 23:57:41,408 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-24 23:57:41,408 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [322779886] [2023-11-24 23:57:41,408 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-24 23:57:41,408 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-24 23:57:41,408 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5b71d6ca-f486-4540-8cb5-b6662b7dbd5f/bin/utaipan-verify-SwPr7d2a91/z3 [2023-11-24 23:57:41,410 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5b71d6ca-f486-4540-8cb5-b6662b7dbd5f/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-24 23:57:41,437 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5b71d6ca-f486-4540-8cb5-b6662b7dbd5f/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2023-11-24 23:57:42,110 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-24 23:57:42,124 INFO L262 TraceCheckSpWp]: Trace formula consists of 2574 conjuncts, 14 conjunts are in the unsatisfiable core [2023-11-24 23:57:42,131 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-24 23:57:42,177 INFO L134 CoverageAnalysis]: Checked inductivity of 67 backedges. 8 proven. 0 refuted. 0 times theorem prover too weak. 59 trivial. 0 not checked. [2023-11-24 23:57:42,177 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-11-24 23:57:42,178 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-24 23:57:42,178 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [515710951] [2023-11-24 23:57:42,178 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-24 23:57:42,178 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [322779886] [2023-11-24 23:57:42,178 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [322779886] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-24 23:57:42,179 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-24 23:57:42,179 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2023-11-24 23:57:42,179 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1308067992] [2023-11-24 23:57:42,179 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-24 23:57:42,180 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2023-11-24 23:57:42,180 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-24 23:57:42,181 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2023-11-24 23:57:42,181 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2023-11-24 23:57:42,181 INFO L87 Difference]: Start difference. First operand 133 states and 166 transitions. Second operand has 6 states, 5 states have (on average 11.4) internal successors, (57), 6 states have internal predecessors, (57), 4 states have call successors, (22), 2 states have call predecessors, (22), 4 states have return successors, (21), 4 states have call predecessors, (21), 4 states have call successors, (21) [2023-11-24 23:57:42,654 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-24 23:57:42,655 INFO L93 Difference]: Finished difference Result 217 states and 270 transitions. [2023-11-24 23:57:42,655 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-11-24 23:57:42,655 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 11.4) internal successors, (57), 6 states have internal predecessors, (57), 4 states have call successors, (22), 2 states have call predecessors, (22), 4 states have return successors, (21), 4 states have call predecessors, (21), 4 states have call successors, (21) Word has length 130 [2023-11-24 23:57:42,656 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-24 23:57:42,658 INFO L225 Difference]: With dead ends: 217 [2023-11-24 23:57:42,658 INFO L226 Difference]: Without dead ends: 133 [2023-11-24 23:57:42,658 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 131 GetRequests, 125 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2023-11-24 23:57:42,659 INFO L413 NwaCegarLoop]: 127 mSDtfsCounter, 8 mSDsluCounter, 498 mSDsCounter, 0 mSdLazyCounter, 129 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 625 SdHoareTripleChecker+Invalid, 129 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 129 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2023-11-24 23:57:42,660 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 625 Invalid, 129 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 129 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2023-11-24 23:57:42,661 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 133 states. [2023-11-24 23:57:42,685 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 133 to 133. [2023-11-24 23:57:42,690 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 133 states, 76 states have (on average 1.1578947368421053) internal successors, (88), 80 states have internal predecessors, (88), 36 states have call successors, (36), 18 states have call predecessors, (36), 20 states have return successors, (41), 35 states have call predecessors, (41), 35 states have call successors, (41) [2023-11-24 23:57:42,692 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 133 states to 133 states and 165 transitions. [2023-11-24 23:57:42,692 INFO L78 Accepts]: Start accepts. Automaton has 133 states and 165 transitions. Word has length 130 [2023-11-24 23:57:42,694 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-24 23:57:42,694 INFO L495 AbstractCegarLoop]: Abstraction has 133 states and 165 transitions. [2023-11-24 23:57:42,694 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 11.4) internal successors, (57), 6 states have internal predecessors, (57), 4 states have call successors, (22), 2 states have call predecessors, (22), 4 states have return successors, (21), 4 states have call predecessors, (21), 4 states have call successors, (21) [2023-11-24 23:57:42,695 INFO L276 IsEmpty]: Start isEmpty. Operand 133 states and 165 transitions. [2023-11-24 23:57:42,701 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 132 [2023-11-24 23:57:42,702 INFO L187 NwaCegarLoop]: Found error trace [2023-11-24 23:57:42,702 INFO L195 NwaCegarLoop]: trace histogram [6, 3, 3, 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] [2023-11-24 23:57:42,717 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5b71d6ca-f486-4540-8cb5-b6662b7dbd5f/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2023-11-24 23:57:42,913 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5b71d6ca-f486-4540-8cb5-b6662b7dbd5f/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-24 23:57:42,913 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-24 23:57:42,913 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-24 23:57:42,913 INFO L85 PathProgramCache]: Analyzing trace with hash -460980485, now seen corresponding path program 1 times [2023-11-24 23:57:42,914 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-24 23:57:42,914 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1844208882] [2023-11-24 23:57:42,914 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-24 23:57:42,914 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-24 23:57:43,031 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-24 23:57:43,032 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1668138674] [2023-11-24 23:57:43,032 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-24 23:57:43,032 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-24 23:57:43,033 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5b71d6ca-f486-4540-8cb5-b6662b7dbd5f/bin/utaipan-verify-SwPr7d2a91/z3 [2023-11-24 23:57:43,034 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5b71d6ca-f486-4540-8cb5-b6662b7dbd5f/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-24 23:57:43,057 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5b71d6ca-f486-4540-8cb5-b6662b7dbd5f/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2023-11-24 23:57:43,765 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-24 23:57:43,778 INFO L262 TraceCheckSpWp]: Trace formula consists of 2581 conjuncts, 20 conjunts are in the unsatisfiable core [2023-11-24 23:57:43,784 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-24 23:57:43,859 INFO L134 CoverageAnalysis]: Checked inductivity of 67 backedges. 8 proven. 0 refuted. 0 times theorem prover too weak. 59 trivial. 0 not checked. [2023-11-24 23:57:43,859 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-11-24 23:57:43,859 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-24 23:57:43,860 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1844208882] [2023-11-24 23:57:43,860 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-24 23:57:43,860 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1668138674] [2023-11-24 23:57:43,860 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1668138674] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-24 23:57:43,860 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-24 23:57:43,860 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2023-11-24 23:57:43,861 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2110139624] [2023-11-24 23:57:43,861 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-24 23:57:43,861 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2023-11-24 23:57:43,862 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-24 23:57:43,862 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2023-11-24 23:57:43,862 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=12, Invalid=30, Unknown=0, NotChecked=0, Total=42 [2023-11-24 23:57:43,863 INFO L87 Difference]: Start difference. First operand 133 states and 165 transitions. Second operand has 7 states, 6 states have (on average 9.666666666666666) internal successors, (58), 7 states have internal predecessors, (58), 4 states have call successors, (22), 2 states have call predecessors, (22), 4 states have return successors, (21), 4 states have call predecessors, (21), 4 states have call successors, (21) [2023-11-24 23:57:44,664 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-24 23:57:44,665 INFO L93 Difference]: Finished difference Result 218 states and 270 transitions. [2023-11-24 23:57:44,665 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2023-11-24 23:57:44,665 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 6 states have (on average 9.666666666666666) internal successors, (58), 7 states have internal predecessors, (58), 4 states have call successors, (22), 2 states have call predecessors, (22), 4 states have return successors, (21), 4 states have call predecessors, (21), 4 states have call successors, (21) Word has length 131 [2023-11-24 23:57:44,666 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-24 23:57:44,667 INFO L225 Difference]: With dead ends: 218 [2023-11-24 23:57:44,668 INFO L226 Difference]: Without dead ends: 134 [2023-11-24 23:57:44,668 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 132 GetRequests, 125 SyntacticMatches, 0 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=20, Invalid=52, Unknown=0, NotChecked=0, Total=72 [2023-11-24 23:57:44,669 INFO L413 NwaCegarLoop]: 127 mSDtfsCounter, 8 mSDsluCounter, 498 mSDsCounter, 0 mSdLazyCounter, 131 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 625 SdHoareTripleChecker+Invalid, 131 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 131 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.8s IncrementalHoareTripleChecker+Time [2023-11-24 23:57:44,670 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 625 Invalid, 131 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 131 Invalid, 0 Unknown, 0 Unchecked, 0.8s Time] [2023-11-24 23:57:44,670 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 134 states. [2023-11-24 23:57:44,680 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 134 to 134. [2023-11-24 23:57:44,680 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 134 states, 77 states have (on average 1.155844155844156) internal successors, (89), 81 states have internal predecessors, (89), 36 states have call successors, (36), 18 states have call predecessors, (36), 20 states have return successors, (41), 35 states have call predecessors, (41), 35 states have call successors, (41) [2023-11-24 23:57:44,682 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 134 states to 134 states and 166 transitions. [2023-11-24 23:57:44,682 INFO L78 Accepts]: Start accepts. Automaton has 134 states and 166 transitions. Word has length 131 [2023-11-24 23:57:44,683 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-24 23:57:44,683 INFO L495 AbstractCegarLoop]: Abstraction has 134 states and 166 transitions. [2023-11-24 23:57:44,683 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 6 states have (on average 9.666666666666666) internal successors, (58), 7 states have internal predecessors, (58), 4 states have call successors, (22), 2 states have call predecessors, (22), 4 states have return successors, (21), 4 states have call predecessors, (21), 4 states have call successors, (21) [2023-11-24 23:57:44,684 INFO L276 IsEmpty]: Start isEmpty. Operand 134 states and 166 transitions. [2023-11-24 23:57:44,685 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 133 [2023-11-24 23:57:44,686 INFO L187 NwaCegarLoop]: Found error trace [2023-11-24 23:57:44,686 INFO L195 NwaCegarLoop]: trace histogram [6, 3, 3, 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] [2023-11-24 23:57:44,702 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5b71d6ca-f486-4540-8cb5-b6662b7dbd5f/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2023-11-24 23:57:44,897 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5b71d6ca-f486-4540-8cb5-b6662b7dbd5f/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable7 [2023-11-24 23:57:44,897 INFO L420 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-24 23:57:44,898 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-24 23:57:44,898 INFO L85 PathProgramCache]: Analyzing trace with hash 1107357061, now seen corresponding path program 1 times [2023-11-24 23:57:44,898 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-24 23:57:44,898 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [121706853] [2023-11-24 23:57:44,898 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-24 23:57:44,899 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-24 23:57:45,004 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-24 23:57:45,005 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [43961900] [2023-11-24 23:57:45,005 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-24 23:57:45,005 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-24 23:57:45,005 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5b71d6ca-f486-4540-8cb5-b6662b7dbd5f/bin/utaipan-verify-SwPr7d2a91/z3 [2023-11-24 23:57:45,006 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5b71d6ca-f486-4540-8cb5-b6662b7dbd5f/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-24 23:57:45,027 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5b71d6ca-f486-4540-8cb5-b6662b7dbd5f/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2023-11-24 23:57:45,683 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-24 23:57:45,696 INFO L262 TraceCheckSpWp]: Trace formula consists of 2600 conjuncts, 18 conjunts are in the unsatisfiable core [2023-11-24 23:57:45,702 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-24 23:57:45,731 INFO L134 CoverageAnalysis]: Checked inductivity of 68 backedges. 24 proven. 0 refuted. 0 times theorem prover too weak. 44 trivial. 0 not checked. [2023-11-24 23:57:45,732 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-11-24 23:57:45,732 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-24 23:57:45,732 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [121706853] [2023-11-24 23:57:45,732 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-24 23:57:45,732 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [43961900] [2023-11-24 23:57:45,732 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [43961900] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-24 23:57:45,732 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-24 23:57:45,732 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2023-11-24 23:57:45,733 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1483538503] [2023-11-24 23:57:45,733 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-24 23:57:45,733 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2023-11-24 23:57:45,733 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-24 23:57:45,734 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2023-11-24 23:57:45,734 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2023-11-24 23:57:45,734 INFO L87 Difference]: Start difference. First operand 134 states and 166 transitions. Second operand has 4 states, 4 states have (on average 15.0) internal successors, (60), 4 states have internal predecessors, (60), 2 states have call successors, (22), 2 states have call predecessors, (22), 3 states have return successors, (21), 2 states have call predecessors, (21), 2 states have call successors, (21) [2023-11-24 23:57:46,338 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-24 23:57:46,338 INFO L93 Difference]: Finished difference Result 229 states and 292 transitions. [2023-11-24 23:57:46,338 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2023-11-24 23:57:46,339 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 15.0) internal successors, (60), 4 states have internal predecessors, (60), 2 states have call successors, (22), 2 states have call predecessors, (22), 3 states have return successors, (21), 2 states have call predecessors, (21), 2 states have call successors, (21) Word has length 132 [2023-11-24 23:57:46,339 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-24 23:57:46,340 INFO L225 Difference]: With dead ends: 229 [2023-11-24 23:57:46,341 INFO L226 Difference]: Without dead ends: 138 [2023-11-24 23:57:46,341 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 132 GetRequests, 129 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2023-11-24 23:57:46,342 INFO L413 NwaCegarLoop]: 124 mSDtfsCounter, 5 mSDsluCounter, 236 mSDsCounter, 0 mSdLazyCounter, 95 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 360 SdHoareTripleChecker+Invalid, 99 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 95 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2023-11-24 23:57:46,342 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [5 Valid, 360 Invalid, 99 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 95 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2023-11-24 23:57:46,344 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 138 states. [2023-11-24 23:57:46,388 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 138 to 135. [2023-11-24 23:57:46,394 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 135 states, 78 states have (on average 1.1538461538461537) internal successors, (90), 82 states have internal predecessors, (90), 36 states have call successors, (36), 18 states have call predecessors, (36), 20 states have return successors, (41), 35 states have call predecessors, (41), 35 states have call successors, (41) [2023-11-24 23:57:46,397 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 135 states to 135 states and 167 transitions. [2023-11-24 23:57:46,397 INFO L78 Accepts]: Start accepts. Automaton has 135 states and 167 transitions. Word has length 132 [2023-11-24 23:57:46,398 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-24 23:57:46,398 INFO L495 AbstractCegarLoop]: Abstraction has 135 states and 167 transitions. [2023-11-24 23:57:46,399 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 15.0) internal successors, (60), 4 states have internal predecessors, (60), 2 states have call successors, (22), 2 states have call predecessors, (22), 3 states have return successors, (21), 2 states have call predecessors, (21), 2 states have call successors, (21) [2023-11-24 23:57:46,399 INFO L276 IsEmpty]: Start isEmpty. Operand 135 states and 167 transitions. [2023-11-24 23:57:46,401 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 135 [2023-11-24 23:57:46,401 INFO L187 NwaCegarLoop]: Found error trace [2023-11-24 23:57:46,402 INFO L195 NwaCegarLoop]: trace histogram [6, 3, 3, 3, 3, 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] [2023-11-24 23:57:46,414 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5b71d6ca-f486-4540-8cb5-b6662b7dbd5f/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2023-11-24 23:57:46,610 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 7 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5b71d6ca-f486-4540-8cb5-b6662b7dbd5f/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable8 [2023-11-24 23:57:46,611 INFO L420 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-24 23:57:46,611 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-24 23:57:46,611 INFO L85 PathProgramCache]: Analyzing trace with hash 1428839579, now seen corresponding path program 1 times [2023-11-24 23:57:46,611 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-24 23:57:46,612 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1505513703] [2023-11-24 23:57:46,612 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-24 23:57:46,612 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-24 23:57:46,744 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-24 23:57:46,744 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [898228624] [2023-11-24 23:57:46,745 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-24 23:57:46,745 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-24 23:57:46,745 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5b71d6ca-f486-4540-8cb5-b6662b7dbd5f/bin/utaipan-verify-SwPr7d2a91/z3 [2023-11-24 23:57:46,746 INFO L229 MonitoredProcess]: Starting monitored process 8 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5b71d6ca-f486-4540-8cb5-b6662b7dbd5f/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-24 23:57:46,761 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_5b71d6ca-f486-4540-8cb5-b6662b7dbd5f/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2023-11-24 23:57:47,623 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-24 23:57:47,636 INFO L262 TraceCheckSpWp]: Trace formula consists of 2606 conjuncts, 134 conjunts are in the unsatisfiable core [2023-11-24 23:57:47,650 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-24 23:57:47,683 INFO L378 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-24 23:57:48,381 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-11-24 23:57:48,381 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 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 38 treesize of output 29 [2023-11-24 23:57:50,554 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 34 treesize of output 25 [2023-11-24 23:58:13,339 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 53 treesize of output 47 [2023-11-24 23:58:13,351 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 47 treesize of output 41 [2023-11-24 23:58:17,421 INFO L134 CoverageAnalysis]: Checked inductivity of 71 backedges. 37 proven. 19 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2023-11-24 23:58:17,421 INFO L327 TraceCheckSpWp]: Computing backward predicates...