./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/aws-c-common/aws_array_list_ensure_capacity_harness.i --full-output --architecture 64bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 6c24879c Calling Ultimate with: /usr/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/aws-c-common/aws_array_list_ensure_capacity_harness.i -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-64bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux --witnessprinter.witness.filename witness.graphml --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(G ! call(reach_error())) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 64bit --witnessprinter.graph.data.programhash c12ad62b7b197015493bfb3c1dd9a5de2922d9b16e39f249961c276d8b82591b --- Real Ultimate output --- This is Ultimate 0.2.2-?-6c24879 [2022-07-12 10:47:11,881 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-07-12 10:47:11,883 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-07-12 10:47:11,900 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-07-12 10:47:11,901 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-07-12 10:47:11,901 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-07-12 10:47:11,902 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-07-12 10:47:11,904 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-07-12 10:47:11,905 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-07-12 10:47:11,905 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-07-12 10:47:11,906 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-07-12 10:47:11,907 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-07-12 10:47:11,907 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-07-12 10:47:11,908 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-07-12 10:47:11,908 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-07-12 10:47:11,909 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-07-12 10:47:11,910 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-07-12 10:47:11,910 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-07-12 10:47:11,911 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-07-12 10:47:11,912 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-07-12 10:47:11,913 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-07-12 10:47:11,924 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-07-12 10:47:11,924 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-07-12 10:47:11,925 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-07-12 10:47:11,926 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-07-12 10:47:11,927 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-07-12 10:47:11,928 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-07-12 10:47:11,928 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-07-12 10:47:11,928 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-07-12 10:47:11,929 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-07-12 10:47:11,929 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-07-12 10:47:11,929 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-07-12 10:47:11,930 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-07-12 10:47:11,930 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-07-12 10:47:11,931 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-07-12 10:47:11,931 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-07-12 10:47:11,932 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-07-12 10:47:11,932 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-07-12 10:47:11,932 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-07-12 10:47:11,933 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-07-12 10:47:11,933 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-07-12 10:47:11,934 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-07-12 10:47:11,934 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-64bit-Automizer_Default.epf [2022-07-12 10:47:11,965 INFO L113 SettingsManager]: Loading preferences was successful [2022-07-12 10:47:11,965 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-07-12 10:47:11,965 INFO L136 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2022-07-12 10:47:11,965 INFO L138 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2022-07-12 10:47:11,966 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2022-07-12 10:47:11,966 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2022-07-12 10:47:11,966 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2022-07-12 10:47:11,966 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2022-07-12 10:47:11,967 INFO L138 SettingsManager]: * Use SBE=true [2022-07-12 10:47:11,967 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-07-12 10:47:11,967 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-07-12 10:47:11,967 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-07-12 10:47:11,967 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-07-12 10:47:11,967 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-07-12 10:47:11,967 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-07-12 10:47:11,968 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-07-12 10:47:11,968 INFO L138 SettingsManager]: * Use constant arrays=true [2022-07-12 10:47:11,968 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-07-12 10:47:11,968 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-07-12 10:47:11,968 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-07-12 10:47:11,968 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-07-12 10:47:11,968 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-07-12 10:47:11,969 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-07-12 10:47:11,969 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2022-07-12 10:47:11,969 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2022-07-12 10:47:11,969 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2022-07-12 10:47:11,969 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2022-07-12 10:47:11,969 INFO L138 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2022-07-12 10:47:11,969 INFO L138 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2022-07-12 10:47:11,969 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-07-12 10:47:11,970 INFO L138 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/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 -> /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness.graphml 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 -> Automizer 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 -> c12ad62b7b197015493bfb3c1dd9a5de2922d9b16e39f249961c276d8b82591b [2022-07-12 10:47:12,130 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-07-12 10:47:12,146 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-07-12 10:47:12,148 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-07-12 10:47:12,149 INFO L271 PluginConnector]: Initializing CDTParser... [2022-07-12 10:47:12,150 INFO L275 PluginConnector]: CDTParser initialized [2022-07-12 10:47:12,151 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/aws-c-common/aws_array_list_ensure_capacity_harness.i [2022-07-12 10:47:12,210 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/20f647745/d24bd507056c4c27a2f41cfaba0a6de5/FLAG93a4895e2 [2022-07-12 10:47:12,791 INFO L306 CDTParser]: Found 1 translation units. [2022-07-12 10:47:12,792 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/aws-c-common/aws_array_list_ensure_capacity_harness.i [2022-07-12 10:47:12,822 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/20f647745/d24bd507056c4c27a2f41cfaba0a6de5/FLAG93a4895e2 [2022-07-12 10:47:13,236 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/20f647745/d24bd507056c4c27a2f41cfaba0a6de5 [2022-07-12 10:47:13,238 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-07-12 10:47:13,239 INFO L131 ToolchainWalker]: Walking toolchain with 6 elements. [2022-07-12 10:47:13,240 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-07-12 10:47:13,240 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-07-12 10:47:13,242 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-07-12 10:47:13,242 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 12.07 10:47:13" (1/1) ... [2022-07-12 10:47:13,243 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@5734e439 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.07 10:47:13, skipping insertion in model container [2022-07-12 10:47:13,243 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 12.07 10:47:13" (1/1) ... [2022-07-12 10:47:13,247 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-07-12 10:47:13,345 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-07-12 10:47:13,530 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/aws-c-common/aws_array_list_ensure_capacity_harness.i[4504,4517] [2022-07-12 10:47:13,534 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/aws-c-common/aws_array_list_ensure_capacity_harness.i[4564,4577] [2022-07-12 10:47:14,037 WARN L611 FunctionHandler]: implicit declaration of function __builtin_va_copy [2022-07-12 10:47:14,088 WARN L1550 CHandler]: Possible shadowing of function index [2022-07-12 10:47:14,091 WARN L1550 CHandler]: Possible shadowing of function index [2022-07-12 10:47:14,092 WARN L1550 CHandler]: Possible shadowing of function index [2022-07-12 10:47:14,095 WARN L1550 CHandler]: Possible shadowing of function index [2022-07-12 10:47:14,097 WARN L1550 CHandler]: Possible shadowing of function index [2022-07-12 10:47:14,103 WARN L1550 CHandler]: Possible shadowing of function index [2022-07-12 10:47:14,105 WARN L1550 CHandler]: Possible shadowing of function index [2022-07-12 10:47:14,109 WARN L1550 CHandler]: Possible shadowing of function index [2022-07-12 10:47:14,109 WARN L1550 CHandler]: Possible shadowing of function index [2022-07-12 10:47:14,111 WARN L1550 CHandler]: Possible shadowing of function index [2022-07-12 10:47:14,111 WARN L1550 CHandler]: Possible shadowing of function index [2022-07-12 10:47:14,113 WARN L1550 CHandler]: Possible shadowing of function index [2022-07-12 10:47:14,113 WARN L1550 CHandler]: Possible shadowing of function index [2022-07-12 10:47:14,278 WARN L611 FunctionHandler]: implicit declaration of function __atomic_load_n [2022-07-12 10:47:14,279 WARN L611 FunctionHandler]: implicit declaration of function __atomic_store_n [2022-07-12 10:47:14,280 WARN L611 FunctionHandler]: implicit declaration of function __atomic_exchange_n [2022-07-12 10:47:14,280 WARN L611 FunctionHandler]: implicit declaration of function __atomic_compare_exchange_n [2022-07-12 10:47:14,281 WARN L611 FunctionHandler]: implicit declaration of function __atomic_fetch_add [2022-07-12 10:47:14,281 WARN L611 FunctionHandler]: implicit declaration of function __atomic_fetch_sub [2022-07-12 10:47:14,282 WARN L611 FunctionHandler]: implicit declaration of function __atomic_fetch_or [2022-07-12 10:47:14,282 WARN L611 FunctionHandler]: implicit declaration of function __atomic_fetch_and [2022-07-12 10:47:14,283 WARN L611 FunctionHandler]: implicit declaration of function __atomic_fetch_xor [2022-07-12 10:47:14,283 WARN L611 FunctionHandler]: implicit declaration of function __atomic_thread_fence [2022-07-12 10:47:14,349 WARN L1550 CHandler]: Possible shadowing of function index [2022-07-12 10:47:14,349 WARN L1550 CHandler]: Possible shadowing of function index [2022-07-12 10:47:14,352 WARN L1550 CHandler]: Possible shadowing of function index [2022-07-12 10:47:14,355 WARN L1550 CHandler]: Possible shadowing of function index [2022-07-12 10:47:14,385 WARN L1550 CHandler]: Possible shadowing of function index [2022-07-12 10:47:14,387 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-07-12 10:47:14,419 INFO L203 MainTranslator]: Completed pre-run [2022-07-12 10:47:14,427 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/aws-c-common/aws_array_list_ensure_capacity_harness.i[4504,4517] [2022-07-12 10:47:14,428 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/aws-c-common/aws_array_list_ensure_capacity_harness.i[4564,4577] [2022-07-12 10:47:14,454 WARN L611 FunctionHandler]: implicit declaration of function __builtin_va_copy [2022-07-12 10:47:14,464 WARN L1550 CHandler]: Possible shadowing of function index [2022-07-12 10:47:14,464 WARN L1550 CHandler]: Possible shadowing of function index [2022-07-12 10:47:14,464 WARN L1550 CHandler]: Possible shadowing of function index [2022-07-12 10:47:14,465 WARN L1550 CHandler]: Possible shadowing of function index [2022-07-12 10:47:14,465 WARN L1550 CHandler]: Possible shadowing of function index [2022-07-12 10:47:14,469 WARN L1550 CHandler]: Possible shadowing of function index [2022-07-12 10:47:14,470 WARN L1550 CHandler]: Possible shadowing of function index [2022-07-12 10:47:14,470 WARN L1550 CHandler]: Possible shadowing of function index [2022-07-12 10:47:14,471 WARN L1550 CHandler]: Possible shadowing of function index [2022-07-12 10:47:14,471 WARN L1550 CHandler]: Possible shadowing of function index [2022-07-12 10:47:14,472 WARN L1550 CHandler]: Possible shadowing of function index [2022-07-12 10:47:14,472 WARN L1550 CHandler]: Possible shadowing of function index [2022-07-12 10:47:14,472 WARN L1550 CHandler]: Possible shadowing of function index [2022-07-12 10:47:14,492 WARN L611 FunctionHandler]: implicit declaration of function __atomic_load_n [2022-07-12 10:47:14,493 WARN L611 FunctionHandler]: implicit declaration of function __atomic_store_n [2022-07-12 10:47:14,493 WARN L611 FunctionHandler]: implicit declaration of function __atomic_exchange_n [2022-07-12 10:47:14,494 WARN L611 FunctionHandler]: implicit declaration of function __atomic_compare_exchange_n [2022-07-12 10:47:14,494 WARN L611 FunctionHandler]: implicit declaration of function __atomic_fetch_add [2022-07-12 10:47:14,494 WARN L611 FunctionHandler]: implicit declaration of function __atomic_fetch_sub [2022-07-12 10:47:14,495 WARN L611 FunctionHandler]: implicit declaration of function __atomic_fetch_or [2022-07-12 10:47:14,495 WARN L611 FunctionHandler]: implicit declaration of function __atomic_fetch_and [2022-07-12 10:47:14,495 WARN L611 FunctionHandler]: implicit declaration of function __atomic_fetch_xor [2022-07-12 10:47:14,496 WARN L611 FunctionHandler]: implicit declaration of function __atomic_thread_fence [2022-07-12 10:47:14,513 WARN L1550 CHandler]: Possible shadowing of function index [2022-07-12 10:47:14,513 WARN L1550 CHandler]: Possible shadowing of function index [2022-07-12 10:47:14,514 WARN L1550 CHandler]: Possible shadowing of function index [2022-07-12 10:47:14,517 WARN L1550 CHandler]: Possible shadowing of function index [2022-07-12 10:47:14,531 WARN L1550 CHandler]: Possible shadowing of function index [2022-07-12 10:47:14,532 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-07-12 10:47:14,656 INFO L208 MainTranslator]: Completed translation [2022-07-12 10:47:14,657 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.07 10:47:14 WrapperNode [2022-07-12 10:47:14,657 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-07-12 10:47:14,658 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2022-07-12 10:47:14,658 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2022-07-12 10:47:14,658 INFO L275 PluginConnector]: Boogie Procedure Inliner initialized [2022-07-12 10:47:14,663 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.07 10:47:14" (1/1) ... [2022-07-12 10:47:14,731 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.07 10:47:14" (1/1) ... [2022-07-12 10:47:14,777 INFO L137 Inliner]: procedures = 691, calls = 1684, calls flagged for inlining = 52, calls inlined = 11, statements flattened = 804 [2022-07-12 10:47:14,777 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2022-07-12 10:47:14,778 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-07-12 10:47:14,778 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-07-12 10:47:14,778 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-07-12 10:47:14,784 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.07 10:47:14" (1/1) ... [2022-07-12 10:47:14,784 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.07 10:47:14" (1/1) ... [2022-07-12 10:47:14,790 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.07 10:47:14" (1/1) ... [2022-07-12 10:47:14,791 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.07 10:47:14" (1/1) ... [2022-07-12 10:47:14,813 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.07 10:47:14" (1/1) ... [2022-07-12 10:47:14,816 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.07 10:47:14" (1/1) ... [2022-07-12 10:47:14,821 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.07 10:47:14" (1/1) ... [2022-07-12 10:47:14,829 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-07-12 10:47:14,830 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-07-12 10:47:14,830 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-07-12 10:47:14,830 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-07-12 10:47:14,831 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.07 10:47:14" (1/1) ... [2022-07-12 10:47:14,845 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-07-12 10:47:14,852 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-12 10:47:14,862 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2022-07-12 10:47:14,868 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2022-07-12 10:47:14,887 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-07-12 10:47:14,887 INFO L130 BoogieDeclarations]: Found specification of procedure aws_array_list_is_bounded [2022-07-12 10:47:14,887 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_array_list_is_bounded [2022-07-12 10:47:14,887 INFO L130 BoogieDeclarations]: Found specification of procedure aws_array_list_is_valid [2022-07-12 10:47:14,887 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_array_list_is_valid [2022-07-12 10:47:14,888 INFO L130 BoogieDeclarations]: Found specification of procedure nondet_bool [2022-07-12 10:47:14,888 INFO L138 BoogieDeclarations]: Found implementation of procedure nondet_bool [2022-07-12 10:47:14,888 INFO L130 BoogieDeclarations]: Found specification of procedure aws_allocator_is_valid [2022-07-12 10:47:14,888 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_allocator_is_valid [2022-07-12 10:47:14,888 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-07-12 10:47:14,888 INFO L130 BoogieDeclarations]: Found specification of procedure aws_raise_error [2022-07-12 10:47:14,888 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_raise_error [2022-07-12 10:47:14,888 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-07-12 10:47:14,889 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-07-12 10:47:14,889 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnHeap [2022-07-12 10:47:14,889 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-07-12 10:47:14,889 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$ [2022-07-12 10:47:14,889 INFO L130 BoogieDeclarations]: Found specification of procedure memcpy_impl [2022-07-12 10:47:14,889 INFO L138 BoogieDeclarations]: Found implementation of procedure memcpy_impl [2022-07-12 10:47:14,889 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-07-12 10:47:14,890 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-07-12 10:47:14,890 INFO L130 BoogieDeclarations]: Found specification of procedure bounded_malloc [2022-07-12 10:47:14,890 INFO L138 BoogieDeclarations]: Found implementation of procedure bounded_malloc [2022-07-12 10:47:14,890 INFO L130 BoogieDeclarations]: Found specification of procedure assert_byte_from_buffer_matches [2022-07-12 10:47:14,890 INFO L138 BoogieDeclarations]: Found implementation of procedure assert_byte_from_buffer_matches [2022-07-12 10:47:14,890 INFO L130 BoogieDeclarations]: Found specification of procedure aws_mul_size_checked [2022-07-12 10:47:14,890 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_mul_size_checked [2022-07-12 10:47:14,891 INFO L130 BoogieDeclarations]: Found specification of procedure can_fail_malloc [2022-07-12 10:47:14,891 INFO L138 BoogieDeclarations]: Found implementation of procedure can_fail_malloc [2022-07-12 10:47:14,891 INFO L130 BoogieDeclarations]: Found specification of procedure aws_mem_release [2022-07-12 10:47:14,891 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_mem_release [2022-07-12 10:47:14,891 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-07-12 10:47:14,891 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-07-12 10:47:14,891 INFO L130 BoogieDeclarations]: Found specification of procedure my_memcpy [2022-07-12 10:47:14,891 INFO L138 BoogieDeclarations]: Found implementation of procedure my_memcpy [2022-07-12 10:47:14,892 INFO L130 BoogieDeclarations]: Found specification of procedure aws_mem_acquire [2022-07-12 10:47:14,892 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_mem_acquire [2022-07-12 10:47:14,892 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2022-07-12 10:47:14,892 INFO L130 BoogieDeclarations]: Found specification of procedure __CPROVER_overflow_plus [2022-07-12 10:47:14,892 INFO L138 BoogieDeclarations]: Found implementation of procedure __CPROVER_overflow_plus [2022-07-12 10:47:14,892 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$ [2022-07-12 10:47:14,892 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$ [2022-07-12 10:47:14,893 INFO L130 BoogieDeclarations]: Found specification of procedure can_fail_allocator [2022-07-12 10:47:14,893 INFO L138 BoogieDeclarations]: Found implementation of procedure can_fail_allocator [2022-07-12 10:47:14,893 INFO L130 BoogieDeclarations]: Found specification of procedure __CPROVER_overflow_mult [2022-07-12 10:47:14,893 INFO L138 BoogieDeclarations]: Found implementation of procedure __CPROVER_overflow_mult [2022-07-12 10:47:14,893 INFO L130 BoogieDeclarations]: Found specification of procedure aws_add_size_checked [2022-07-12 10:47:14,893 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_add_size_checked [2022-07-12 10:47:14,893 INFO L130 BoogieDeclarations]: Found specification of procedure aws_array_list_ensure_capacity [2022-07-12 10:47:14,893 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_array_list_ensure_capacity [2022-07-12 10:47:14,894 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-07-12 10:47:14,894 INFO L130 BoogieDeclarations]: Found specification of procedure ensure_array_list_has_allocated_data_member [2022-07-12 10:47:14,894 INFO L138 BoogieDeclarations]: Found implementation of procedure ensure_array_list_has_allocated_data_member [2022-07-12 10:47:14,894 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-07-12 10:47:15,073 INFO L234 CfgBuilder]: Building ICFG [2022-07-12 10:47:15,074 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-07-12 10:47:15,595 INFO L275 CfgBuilder]: Performing block encoding [2022-07-12 10:47:15,601 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-07-12 10:47:15,601 INFO L299 CfgBuilder]: Removed 0 assume(true) statements. [2022-07-12 10:47:15,602 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 12.07 10:47:15 BoogieIcfgContainer [2022-07-12 10:47:15,602 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-07-12 10:47:15,603 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-07-12 10:47:15,604 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-07-12 10:47:15,606 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-07-12 10:47:15,606 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 12.07 10:47:13" (1/3) ... [2022-07-12 10:47:15,607 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@155e44a5 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 12.07 10:47:15, skipping insertion in model container [2022-07-12 10:47:15,607 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.07 10:47:14" (2/3) ... [2022-07-12 10:47:15,607 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@155e44a5 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 12.07 10:47:15, skipping insertion in model container [2022-07-12 10:47:15,610 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 12.07 10:47:15" (3/3) ... [2022-07-12 10:47:15,611 INFO L111 eAbstractionObserver]: Analyzing ICFG aws_array_list_ensure_capacity_harness.i [2022-07-12 10:47:15,620 INFO L201 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2022-07-12 10:47:15,620 INFO L160 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-07-12 10:47:15,675 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-07-12 10:47:15,680 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=PETRI_NET, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=LoopsAndPotentialCycles, 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=de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings@49c2501a, mLbeIndependenceSettings=de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings@53b15aed [2022-07-12 10:47:15,680 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-07-12 10:47:15,683 INFO L276 IsEmpty]: Start isEmpty. Operand has 241 states, 145 states have (on average 1.206896551724138) internal successors, (175), 146 states have internal predecessors, (175), 73 states have call successors, (73), 21 states have call predecessors, (73), 21 states have return successors, (73), 73 states have call predecessors, (73), 73 states have call successors, (73) [2022-07-12 10:47:15,691 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 88 [2022-07-12 10:47:15,691 INFO L187 NwaCegarLoop]: Found error trace [2022-07-12 10:47:15,692 INFO L195 NwaCegarLoop]: trace histogram [5, 5, 5, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-12 10:47:15,692 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-12 10:47:15,695 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-12 10:47:15,695 INFO L85 PathProgramCache]: Analyzing trace with hash -1087274047, now seen corresponding path program 1 times [2022-07-12 10:47:15,701 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-12 10:47:15,701 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [987509393] [2022-07-12 10:47:15,701 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-12 10:47:15,702 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-12 10:47:15,907 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-12 10:47:16,094 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2022-07-12 10:47:16,098 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-12 10:47:16,112 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-07-12 10:47:16,113 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-12 10:47:16,144 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2022-07-12 10:47:16,149 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-12 10:47:16,159 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2022-07-12 10:47:16,172 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-12 10:47:16,178 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2022-07-12 10:47:16,179 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-12 10:47:16,215 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 29 [2022-07-12 10:47:16,217 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-12 10:47:16,230 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 34 [2022-07-12 10:47:16,231 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-12 10:47:16,235 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 44 [2022-07-12 10:47:16,237 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-12 10:47:16,242 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 49 [2022-07-12 10:47:16,247 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-12 10:47:16,256 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 55 [2022-07-12 10:47:16,261 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-12 10:47:16,271 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 60 [2022-07-12 10:47:16,272 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-12 10:47:16,304 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 66 [2022-07-12 10:47:16,313 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-12 10:47:16,325 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2022-07-12 10:47:16,327 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-12 10:47:16,332 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 78 [2022-07-12 10:47:16,334 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-12 10:47:16,340 INFO L134 CoverageAnalysis]: Checked inductivity of 64 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 64 trivial. 0 not checked. [2022-07-12 10:47:16,340 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-12 10:47:16,340 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [987509393] [2022-07-12 10:47:16,341 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [987509393] provided 1 perfect and 0 imperfect interpolant sequences [2022-07-12 10:47:16,341 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-07-12 10:47:16,341 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-07-12 10:47:16,342 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [155322051] [2022-07-12 10:47:16,342 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-12 10:47:16,345 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-07-12 10:47:16,346 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-12 10:47:16,361 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-07-12 10:47:16,362 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=10, Unknown=0, NotChecked=0, Total=20 [2022-07-12 10:47:16,364 INFO L87 Difference]: Start difference. First operand has 241 states, 145 states have (on average 1.206896551724138) internal successors, (175), 146 states have internal predecessors, (175), 73 states have call successors, (73), 21 states have call predecessors, (73), 21 states have return successors, (73), 73 states have call predecessors, (73), 73 states have call successors, (73) Second operand has 5 states, 5 states have (on average 7.2) internal successors, (36), 2 states have internal predecessors, (36), 2 states have call successors, (16), 5 states have call predecessors, (16), 2 states have return successors, (14), 2 states have call predecessors, (14), 2 states have call successors, (14) [2022-07-12 10:47:16,794 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-12 10:47:16,795 INFO L93 Difference]: Finished difference Result 502 states and 720 transitions. [2022-07-12 10:47:16,808 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-07-12 10:47:16,809 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 7.2) internal successors, (36), 2 states have internal predecessors, (36), 2 states have call successors, (16), 5 states have call predecessors, (16), 2 states have return successors, (14), 2 states have call predecessors, (14), 2 states have call successors, (14) Word has length 87 [2022-07-12 10:47:16,809 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-12 10:47:16,817 INFO L225 Difference]: With dead ends: 502 [2022-07-12 10:47:16,817 INFO L226 Difference]: Without dead ends: 257 [2022-07-12 10:47:16,822 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 36 GetRequests, 33 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=10, Invalid=10, Unknown=0, NotChecked=0, Total=20 [2022-07-12 10:47:16,824 INFO L413 NwaCegarLoop]: 288 mSDtfsCounter, 78 mSDsluCounter, 154 mSDsCounter, 0 mSdLazyCounter, 248 mSolverCounterSat, 83 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 94 SdHoareTripleChecker+Valid, 442 SdHoareTripleChecker+Invalid, 331 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 83 IncrementalHoareTripleChecker+Valid, 248 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2022-07-12 10:47:16,825 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [94 Valid, 442 Invalid, 331 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [83 Valid, 248 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2022-07-12 10:47:16,836 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 257 states. [2022-07-12 10:47:16,880 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 257 to 230. [2022-07-12 10:47:16,881 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 230 states, 136 states have (on average 1.1838235294117647) internal successors, (161), 138 states have internal predecessors, (161), 73 states have call successors, (73), 21 states have call predecessors, (73), 20 states have return successors, (70), 70 states have call predecessors, (70), 70 states have call successors, (70) [2022-07-12 10:47:16,884 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 230 states to 230 states and 304 transitions. [2022-07-12 10:47:16,885 INFO L78 Accepts]: Start accepts. Automaton has 230 states and 304 transitions. Word has length 87 [2022-07-12 10:47:16,885 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-12 10:47:16,885 INFO L495 AbstractCegarLoop]: Abstraction has 230 states and 304 transitions. [2022-07-12 10:47:16,885 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 7.2) internal successors, (36), 2 states have internal predecessors, (36), 2 states have call successors, (16), 5 states have call predecessors, (16), 2 states have return successors, (14), 2 states have call predecessors, (14), 2 states have call successors, (14) [2022-07-12 10:47:16,886 INFO L276 IsEmpty]: Start isEmpty. Operand 230 states and 304 transitions. [2022-07-12 10:47:16,888 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 88 [2022-07-12 10:47:16,888 INFO L187 NwaCegarLoop]: Found error trace [2022-07-12 10:47:16,889 INFO L195 NwaCegarLoop]: trace histogram [5, 5, 5, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-12 10:47:16,889 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-07-12 10:47:16,889 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-12 10:47:16,890 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-12 10:47:16,890 INFO L85 PathProgramCache]: Analyzing trace with hash 672902535, now seen corresponding path program 1 times [2022-07-12 10:47:16,890 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-12 10:47:16,890 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1187193621] [2022-07-12 10:47:16,890 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-12 10:47:16,890 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-12 10:47:16,965 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-12 10:47:17,022 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2022-07-12 10:47:17,026 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-12 10:47:17,034 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-07-12 10:47:17,036 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-12 10:47:17,051 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2022-07-12 10:47:17,057 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-12 10:47:17,066 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2022-07-12 10:47:17,067 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-12 10:47:17,073 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2022-07-12 10:47:17,074 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-12 10:47:17,089 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 29 [2022-07-12 10:47:17,091 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-12 10:47:17,108 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 34 [2022-07-12 10:47:17,110 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-12 10:47:17,115 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 44 [2022-07-12 10:47:17,116 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-12 10:47:17,121 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 49 [2022-07-12 10:47:17,122 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-12 10:47:17,127 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 55 [2022-07-12 10:47:17,129 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-12 10:47:17,133 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 60 [2022-07-12 10:47:17,135 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-12 10:47:17,139 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 66 [2022-07-12 10:47:17,143 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-12 10:47:17,155 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2022-07-12 10:47:17,156 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-12 10:47:17,161 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 78 [2022-07-12 10:47:17,162 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-12 10:47:17,167 INFO L134 CoverageAnalysis]: Checked inductivity of 64 backedges. 0 proven. 9 refuted. 0 times theorem prover too weak. 55 trivial. 0 not checked. [2022-07-12 10:47:17,167 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-12 10:47:17,168 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1187193621] [2022-07-12 10:47:17,168 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1187193621] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-12 10:47:17,168 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [160969973] [2022-07-12 10:47:17,168 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-12 10:47:17,168 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-12 10:47:17,168 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-12 10:47:17,199 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-12 10:47:17,230 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2022-07-12 10:47:17,542 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-12 10:47:17,550 INFO L263 TraceCheckSpWp]: Trace formula consists of 2243 conjuncts, 5 conjunts are in the unsatisfiable core [2022-07-12 10:47:17,556 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-12 10:47:17,619 INFO L134 CoverageAnalysis]: Checked inductivity of 64 backedges. 36 proven. 0 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2022-07-12 10:47:17,619 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-07-12 10:47:17,619 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [160969973] provided 1 perfect and 0 imperfect interpolant sequences [2022-07-12 10:47:17,620 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-07-12 10:47:17,620 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [8] total 12 [2022-07-12 10:47:17,623 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [451103424] [2022-07-12 10:47:17,624 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-12 10:47:17,624 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-07-12 10:47:17,624 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-12 10:47:17,625 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-07-12 10:47:17,625 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=105, Unknown=0, NotChecked=0, Total=132 [2022-07-12 10:47:17,625 INFO L87 Difference]: Start difference. First operand 230 states and 304 transitions. Second operand has 6 states, 6 states have (on average 7.0) internal successors, (42), 6 states have internal predecessors, (42), 3 states have call successors, (16), 2 states have call predecessors, (16), 3 states have return successors, (14), 3 states have call predecessors, (14), 3 states have call successors, (14) [2022-07-12 10:47:17,837 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-12 10:47:17,837 INFO L93 Difference]: Finished difference Result 436 states and 585 transitions. [2022-07-12 10:47:17,837 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-07-12 10:47:17,837 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 7.0) internal successors, (42), 6 states have internal predecessors, (42), 3 states have call successors, (16), 2 states have call predecessors, (16), 3 states have return successors, (14), 3 states have call predecessors, (14), 3 states have call successors, (14) Word has length 87 [2022-07-12 10:47:17,838 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-12 10:47:17,840 INFO L225 Difference]: With dead ends: 436 [2022-07-12 10:47:17,840 INFO L226 Difference]: Without dead ends: 232 [2022-07-12 10:47:17,842 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 121 GetRequests, 108 SyntacticMatches, 0 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 22 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=42, Invalid=168, Unknown=0, NotChecked=0, Total=210 [2022-07-12 10:47:17,842 INFO L413 NwaCegarLoop]: 257 mSDtfsCounter, 306 mSDsluCounter, 713 mSDsCounter, 0 mSdLazyCounter, 191 mSolverCounterSat, 38 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 326 SdHoareTripleChecker+Valid, 970 SdHoareTripleChecker+Invalid, 229 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 38 IncrementalHoareTripleChecker+Valid, 191 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-07-12 10:47:17,843 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [326 Valid, 970 Invalid, 229 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [38 Valid, 191 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-07-12 10:47:17,844 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 232 states. [2022-07-12 10:47:17,857 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 232 to 232. [2022-07-12 10:47:17,858 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 232 states, 137 states have (on average 1.1824817518248176) internal successors, (162), 140 states have internal predecessors, (162), 73 states have call successors, (73), 21 states have call predecessors, (73), 21 states have return successors, (80), 70 states have call predecessors, (80), 70 states have call successors, (80) [2022-07-12 10:47:17,859 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 232 states to 232 states and 315 transitions. [2022-07-12 10:47:17,860 INFO L78 Accepts]: Start accepts. Automaton has 232 states and 315 transitions. Word has length 87 [2022-07-12 10:47:17,860 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-12 10:47:17,860 INFO L495 AbstractCegarLoop]: Abstraction has 232 states and 315 transitions. [2022-07-12 10:47:17,860 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 7.0) internal successors, (42), 6 states have internal predecessors, (42), 3 states have call successors, (16), 2 states have call predecessors, (16), 3 states have return successors, (14), 3 states have call predecessors, (14), 3 states have call successors, (14) [2022-07-12 10:47:17,860 INFO L276 IsEmpty]: Start isEmpty. Operand 232 states and 315 transitions. [2022-07-12 10:47:17,863 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 103 [2022-07-12 10:47:17,863 INFO L187 NwaCegarLoop]: Found error trace [2022-07-12 10:47:17,863 INFO L195 NwaCegarLoop]: trace histogram [5, 5, 5, 4, 4, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-12 10:47:17,887 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2022-07-12 10:47:18,086 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-12 10:47:18,087 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-12 10:47:18,087 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-12 10:47:18,088 INFO L85 PathProgramCache]: Analyzing trace with hash -149436210, now seen corresponding path program 1 times [2022-07-12 10:47:18,088 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-12 10:47:18,088 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [14731850] [2022-07-12 10:47:18,088 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-12 10:47:18,088 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-12 10:47:18,131 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-12 10:47:18,132 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1980202782] [2022-07-12 10:47:18,132 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-12 10:47:18,132 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-12 10:47:18,132 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-12 10:47:18,133 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-12 10:47:18,134 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2022-07-12 10:47:18,482 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-12 10:47:18,489 INFO L263 TraceCheckSpWp]: Trace formula consists of 2379 conjuncts, 3 conjunts are in the unsatisfiable core [2022-07-12 10:47:18,493 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-12 10:47:18,506 INFO L134 CoverageAnalysis]: Checked inductivity of 64 backedges. 30 proven. 0 refuted. 0 times theorem prover too weak. 34 trivial. 0 not checked. [2022-07-12 10:47:18,506 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-07-12 10:47:18,506 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-12 10:47:18,507 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [14731850] [2022-07-12 10:47:18,507 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-12 10:47:18,507 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1980202782] [2022-07-12 10:47:18,507 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1980202782] provided 1 perfect and 0 imperfect interpolant sequences [2022-07-12 10:47:18,507 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-07-12 10:47:18,507 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2022-07-12 10:47:18,507 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1736458] [2022-07-12 10:47:18,507 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-12 10:47:18,508 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2022-07-12 10:47:18,508 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-12 10:47:18,508 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2022-07-12 10:47:18,508 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2022-07-12 10:47:18,509 INFO L87 Difference]: Start difference. First operand 232 states and 315 transitions. Second operand has 4 states, 4 states have (on average 13.0) internal successors, (52), 4 states have internal predecessors, (52), 2 states have call successors, (18), 2 states have call predecessors, (18), 2 states have return successors, (16), 2 states have call predecessors, (16), 2 states have call successors, (16) [2022-07-12 10:47:18,532 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-12 10:47:18,533 INFO L93 Difference]: Finished difference Result 443 states and 614 transitions. [2022-07-12 10:47:18,533 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-07-12 10:47:18,533 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 13.0) internal successors, (52), 4 states have internal predecessors, (52), 2 states have call successors, (18), 2 states have call predecessors, (18), 2 states have return successors, (16), 2 states have call predecessors, (16), 2 states have call successors, (16) Word has length 102 [2022-07-12 10:47:18,534 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-12 10:47:18,535 INFO L225 Difference]: With dead ends: 443 [2022-07-12 10:47:18,535 INFO L226 Difference]: Without dead ends: 237 [2022-07-12 10:47:18,536 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 102 GetRequests, 99 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2022-07-12 10:47:18,537 INFO L413 NwaCegarLoop]: 303 mSDtfsCounter, 10 mSDsluCounter, 596 mSDsCounter, 0 mSdLazyCounter, 12 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 899 SdHoareTripleChecker+Invalid, 13 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 12 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-07-12 10:47:18,537 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 899 Invalid, 13 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 12 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-07-12 10:47:18,538 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 237 states. [2022-07-12 10:47:18,549 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 237 to 234. [2022-07-12 10:47:18,550 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 234 states, 139 states have (on average 1.1798561151079137) internal successors, (164), 142 states have internal predecessors, (164), 73 states have call successors, (73), 21 states have call predecessors, (73), 21 states have return successors, (80), 70 states have call predecessors, (80), 70 states have call successors, (80) [2022-07-12 10:47:18,551 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 234 states to 234 states and 317 transitions. [2022-07-12 10:47:18,551 INFO L78 Accepts]: Start accepts. Automaton has 234 states and 317 transitions. Word has length 102 [2022-07-12 10:47:18,552 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-12 10:47:18,552 INFO L495 AbstractCegarLoop]: Abstraction has 234 states and 317 transitions. [2022-07-12 10:47:18,552 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 13.0) internal successors, (52), 4 states have internal predecessors, (52), 2 states have call successors, (18), 2 states have call predecessors, (18), 2 states have return successors, (16), 2 states have call predecessors, (16), 2 states have call successors, (16) [2022-07-12 10:47:18,552 INFO L276 IsEmpty]: Start isEmpty. Operand 234 states and 317 transitions. [2022-07-12 10:47:18,553 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 103 [2022-07-12 10:47:18,553 INFO L187 NwaCegarLoop]: Found error trace [2022-07-12 10:47:18,553 INFO L195 NwaCegarLoop]: trace histogram [5, 5, 5, 4, 4, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-12 10:47:18,589 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2022-07-12 10:47:18,770 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable2 [2022-07-12 10:47:18,770 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-12 10:47:18,771 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-12 10:47:18,771 INFO L85 PathProgramCache]: Analyzing trace with hash -710135988, now seen corresponding path program 1 times [2022-07-12 10:47:18,771 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-12 10:47:18,771 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [42893379] [2022-07-12 10:47:18,771 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-12 10:47:18,771 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-12 10:47:18,822 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-12 10:47:18,822 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2062263785] [2022-07-12 10:47:18,822 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-12 10:47:18,822 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-12 10:47:18,823 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-12 10:47:18,827 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-12 10:47:18,828 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2022-07-12 10:47:19,154 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-12 10:47:19,161 INFO L263 TraceCheckSpWp]: Trace formula consists of 2384 conjuncts, 7 conjunts are in the unsatisfiable core [2022-07-12 10:47:19,165 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-12 10:47:19,214 INFO L134 CoverageAnalysis]: Checked inductivity of 64 backedges. 43 proven. 0 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2022-07-12 10:47:19,215 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-07-12 10:47:19,215 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-12 10:47:19,215 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [42893379] [2022-07-12 10:47:19,215 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-12 10:47:19,215 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2062263785] [2022-07-12 10:47:19,215 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2062263785] provided 1 perfect and 0 imperfect interpolant sequences [2022-07-12 10:47:19,215 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-07-12 10:47:19,216 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2022-07-12 10:47:19,216 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [213381943] [2022-07-12 10:47:19,216 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-12 10:47:19,216 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2022-07-12 10:47:19,216 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-12 10:47:19,217 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2022-07-12 10:47:19,217 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=43, Unknown=0, NotChecked=0, Total=56 [2022-07-12 10:47:19,217 INFO L87 Difference]: Start difference. First operand 234 states and 317 transitions. Second operand has 8 states, 7 states have (on average 8.0) internal successors, (56), 7 states have internal predecessors, (56), 4 states have call successors, (18), 3 states have call predecessors, (18), 3 states have return successors, (16), 3 states have call predecessors, (16), 4 states have call successors, (16) [2022-07-12 10:47:19,578 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-12 10:47:19,578 INFO L93 Difference]: Finished difference Result 432 states and 583 transitions. [2022-07-12 10:47:19,578 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-07-12 10:47:19,578 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 7 states have (on average 8.0) internal successors, (56), 7 states have internal predecessors, (56), 4 states have call successors, (18), 3 states have call predecessors, (18), 3 states have return successors, (16), 3 states have call predecessors, (16), 4 states have call successors, (16) Word has length 102 [2022-07-12 10:47:19,579 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-12 10:47:19,580 INFO L225 Difference]: With dead ends: 432 [2022-07-12 10:47:19,580 INFO L226 Difference]: Without dead ends: 234 [2022-07-12 10:47:19,581 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 108 GetRequests, 97 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=37, Invalid=119, Unknown=0, NotChecked=0, Total=156 [2022-07-12 10:47:19,581 INFO L413 NwaCegarLoop]: 230 mSDtfsCounter, 354 mSDsluCounter, 1008 mSDsCounter, 0 mSdLazyCounter, 396 mSolverCounterSat, 144 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 354 SdHoareTripleChecker+Valid, 1238 SdHoareTripleChecker+Invalid, 540 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 144 IncrementalHoareTripleChecker+Valid, 396 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-07-12 10:47:19,582 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [354 Valid, 1238 Invalid, 540 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [144 Valid, 396 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-07-12 10:47:19,582 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 234 states. [2022-07-12 10:47:19,592 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 234 to 234. [2022-07-12 10:47:19,592 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 234 states, 139 states have (on average 1.1798561151079137) internal successors, (164), 142 states have internal predecessors, (164), 73 states have call successors, (73), 21 states have call predecessors, (73), 21 states have return successors, (74), 70 states have call predecessors, (74), 70 states have call successors, (74) [2022-07-12 10:47:19,594 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 234 states to 234 states and 311 transitions. [2022-07-12 10:47:19,594 INFO L78 Accepts]: Start accepts. Automaton has 234 states and 311 transitions. Word has length 102 [2022-07-12 10:47:19,594 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-12 10:47:19,594 INFO L495 AbstractCegarLoop]: Abstraction has 234 states and 311 transitions. [2022-07-12 10:47:19,595 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 7 states have (on average 8.0) internal successors, (56), 7 states have internal predecessors, (56), 4 states have call successors, (18), 3 states have call predecessors, (18), 3 states have return successors, (16), 3 states have call predecessors, (16), 4 states have call successors, (16) [2022-07-12 10:47:19,595 INFO L276 IsEmpty]: Start isEmpty. Operand 234 states and 311 transitions. [2022-07-12 10:47:19,596 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 118 [2022-07-12 10:47:19,596 INFO L187 NwaCegarLoop]: Found error trace [2022-07-12 10:47:19,596 INFO L195 NwaCegarLoop]: trace histogram [5, 5, 5, 4, 4, 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] [2022-07-12 10:47:19,617 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2022-07-12 10:47:19,815 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-12 10:47:19,815 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-12 10:47:19,816 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-12 10:47:19,816 INFO L85 PathProgramCache]: Analyzing trace with hash 191134547, now seen corresponding path program 2 times [2022-07-12 10:47:19,816 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-12 10:47:19,816 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [254700926] [2022-07-12 10:47:19,816 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-12 10:47:19,816 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-12 10:47:19,856 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-12 10:47:19,856 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [160693622] [2022-07-12 10:47:19,856 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-07-12 10:47:19,856 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-12 10:47:19,857 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-12 10:47:19,858 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-12 10:47:19,871 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2022-07-12 10:47:20,153 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) [2022-07-12 10:47:20,153 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-12 10:47:20,159 INFO L263 TraceCheckSpWp]: Trace formula consists of 1918 conjuncts, 7 conjunts are in the unsatisfiable core [2022-07-12 10:47:20,162 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-12 10:47:20,178 INFO L134 CoverageAnalysis]: Checked inductivity of 79 backedges. 12 proven. 0 refuted. 0 times theorem prover too weak. 67 trivial. 0 not checked. [2022-07-12 10:47:20,179 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-07-12 10:47:20,179 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-12 10:47:20,179 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [254700926] [2022-07-12 10:47:20,179 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-12 10:47:20,179 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [160693622] [2022-07-12 10:47:20,179 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [160693622] provided 1 perfect and 0 imperfect interpolant sequences [2022-07-12 10:47:20,180 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-07-12 10:47:20,180 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-07-12 10:47:20,180 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1713998943] [2022-07-12 10:47:20,180 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-12 10:47:20,180 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-07-12 10:47:20,180 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-12 10:47:20,181 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-07-12 10:47:20,181 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-07-12 10:47:20,181 INFO L87 Difference]: Start difference. First operand 234 states and 311 transitions. Second operand has 5 states, 5 states have (on average 10.2) internal successors, (51), 5 states have internal predecessors, (51), 2 states have call successors, (18), 2 states have call predecessors, (18), 3 states have return successors, (16), 3 states have call predecessors, (16), 2 states have call successors, (16) [2022-07-12 10:47:20,204 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-12 10:47:20,205 INFO L93 Difference]: Finished difference Result 409 states and 535 transitions. [2022-07-12 10:47:20,205 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-07-12 10:47:20,205 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 10.2) internal successors, (51), 5 states have internal predecessors, (51), 2 states have call successors, (18), 2 states have call predecessors, (18), 3 states have return successors, (16), 3 states have call predecessors, (16), 2 states have call successors, (16) Word has length 117 [2022-07-12 10:47:20,205 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-12 10:47:20,206 INFO L225 Difference]: With dead ends: 409 [2022-07-12 10:47:20,206 INFO L226 Difference]: Without dead ends: 239 [2022-07-12 10:47:20,207 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 117 GetRequests, 113 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-07-12 10:47:20,208 INFO L413 NwaCegarLoop]: 301 mSDtfsCounter, 2 mSDsluCounter, 897 mSDsCounter, 0 mSdLazyCounter, 17 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 1198 SdHoareTripleChecker+Invalid, 17 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 17 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-07-12 10:47:20,208 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [2 Valid, 1198 Invalid, 17 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 17 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-07-12 10:47:20,209 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 239 states. [2022-07-12 10:47:20,217 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 239 to 239. [2022-07-12 10:47:20,217 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 239 states, 143 states have (on average 1.1748251748251748) internal successors, (168), 146 states have internal predecessors, (168), 73 states have call successors, (73), 21 states have call predecessors, (73), 22 states have return successors, (75), 71 states have call predecessors, (75), 70 states have call successors, (75) [2022-07-12 10:47:20,218 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 239 states to 239 states and 316 transitions. [2022-07-12 10:47:20,218 INFO L78 Accepts]: Start accepts. Automaton has 239 states and 316 transitions. Word has length 117 [2022-07-12 10:47:20,219 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-12 10:47:20,219 INFO L495 AbstractCegarLoop]: Abstraction has 239 states and 316 transitions. [2022-07-12 10:47:20,219 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 10.2) internal successors, (51), 5 states have internal predecessors, (51), 2 states have call successors, (18), 2 states have call predecessors, (18), 3 states have return successors, (16), 3 states have call predecessors, (16), 2 states have call successors, (16) [2022-07-12 10:47:20,219 INFO L276 IsEmpty]: Start isEmpty. Operand 239 states and 316 transitions. [2022-07-12 10:47:20,220 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 124 [2022-07-12 10:47:20,220 INFO L187 NwaCegarLoop]: Found error trace [2022-07-12 10:47:20,220 INFO L195 NwaCegarLoop]: trace histogram [5, 5, 5, 4, 4, 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] [2022-07-12 10:47:20,243 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2022-07-12 10:47:20,441 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-12 10:47:20,442 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-12 10:47:20,442 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-12 10:47:20,442 INFO L85 PathProgramCache]: Analyzing trace with hash 389087133, now seen corresponding path program 1 times [2022-07-12 10:47:20,442 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-12 10:47:20,442 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1708535010] [2022-07-12 10:47:20,442 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-12 10:47:20,442 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-12 10:47:20,479 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-12 10:47:20,479 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1730417219] [2022-07-12 10:47:20,479 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-12 10:47:20,480 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-12 10:47:20,480 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-12 10:47:20,481 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-12 10:47:20,482 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2022-07-12 10:47:20,839 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-12 10:47:20,847 INFO L263 TraceCheckSpWp]: Trace formula consists of 2529 conjuncts, 9 conjunts are in the unsatisfiable core [2022-07-12 10:47:20,851 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-12 10:47:20,918 INFO L134 CoverageAnalysis]: Checked inductivity of 79 backedges. 34 proven. 0 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2022-07-12 10:47:20,918 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-07-12 10:47:20,919 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-12 10:47:20,919 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1708535010] [2022-07-12 10:47:20,919 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-12 10:47:20,919 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1730417219] [2022-07-12 10:47:20,919 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1730417219] provided 1 perfect and 0 imperfect interpolant sequences [2022-07-12 10:47:20,919 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-07-12 10:47:20,920 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [] total 9 [2022-07-12 10:47:20,920 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1969005888] [2022-07-12 10:47:20,920 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-12 10:47:20,920 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-07-12 10:47:20,920 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-12 10:47:20,921 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-07-12 10:47:20,921 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=57, Unknown=0, NotChecked=0, Total=72 [2022-07-12 10:47:20,921 INFO L87 Difference]: Start difference. First operand 239 states and 316 transitions. Second operand has 9 states, 8 states have (on average 7.5) internal successors, (60), 8 states have internal predecessors, (60), 5 states have call successors, (19), 3 states have call predecessors, (19), 3 states have return successors, (17), 4 states have call predecessors, (17), 5 states have call successors, (17) [2022-07-12 10:47:21,274 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-12 10:47:21,274 INFO L93 Difference]: Finished difference Result 439 states and 576 transitions. [2022-07-12 10:47:21,274 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-07-12 10:47:21,275 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 8 states have (on average 7.5) internal successors, (60), 8 states have internal predecessors, (60), 5 states have call successors, (19), 3 states have call predecessors, (19), 3 states have return successors, (17), 4 states have call predecessors, (17), 5 states have call successors, (17) Word has length 123 [2022-07-12 10:47:21,275 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-12 10:47:21,276 INFO L225 Difference]: With dead ends: 439 [2022-07-12 10:47:21,276 INFO L226 Difference]: Without dead ends: 237 [2022-07-12 10:47:21,277 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 130 GetRequests, 117 SyntacticMatches, 0 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 11 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=47, Invalid=163, Unknown=0, NotChecked=0, Total=210 [2022-07-12 10:47:21,277 INFO L413 NwaCegarLoop]: 229 mSDtfsCounter, 392 mSDsluCounter, 1180 mSDsCounter, 0 mSdLazyCounter, 465 mSolverCounterSat, 153 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 392 SdHoareTripleChecker+Valid, 1409 SdHoareTripleChecker+Invalid, 618 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 153 IncrementalHoareTripleChecker+Valid, 465 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-07-12 10:47:21,278 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [392 Valid, 1409 Invalid, 618 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [153 Valid, 465 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-07-12 10:47:21,278 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 237 states. [2022-07-12 10:47:21,287 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 237 to 237. [2022-07-12 10:47:21,287 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 237 states, 142 states have (on average 1.1690140845070423) internal successors, (166), 144 states have internal predecessors, (166), 73 states have call successors, (73), 21 states have call predecessors, (73), 21 states have return successors, (71), 71 states have call predecessors, (71), 70 states have call successors, (71) [2022-07-12 10:47:21,288 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 237 states to 237 states and 310 transitions. [2022-07-12 10:47:21,289 INFO L78 Accepts]: Start accepts. Automaton has 237 states and 310 transitions. Word has length 123 [2022-07-12 10:47:21,289 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-12 10:47:21,289 INFO L495 AbstractCegarLoop]: Abstraction has 237 states and 310 transitions. [2022-07-12 10:47:21,289 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 8 states have (on average 7.5) internal successors, (60), 8 states have internal predecessors, (60), 5 states have call successors, (19), 3 states have call predecessors, (19), 3 states have return successors, (17), 4 states have call predecessors, (17), 5 states have call successors, (17) [2022-07-12 10:47:21,289 INFO L276 IsEmpty]: Start isEmpty. Operand 237 states and 310 transitions. [2022-07-12 10:47:21,290 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 154 [2022-07-12 10:47:21,290 INFO L187 NwaCegarLoop]: Found error trace [2022-07-12 10:47:21,291 INFO L195 NwaCegarLoop]: trace histogram [5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-12 10:47:21,313 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2022-07-12 10:47:21,511 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-12 10:47:21,511 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-12 10:47:21,511 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-12 10:47:21,511 INFO L85 PathProgramCache]: Analyzing trace with hash 1195830657, now seen corresponding path program 1 times [2022-07-12 10:47:21,511 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-12 10:47:21,511 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [228848050] [2022-07-12 10:47:21,512 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-12 10:47:21,512 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-12 10:47:21,585 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-12 10:47:21,586 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1859759950] [2022-07-12 10:47:21,586 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-12 10:47:21,586 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-12 10:47:21,586 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-12 10:47:21,600 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-12 10:47:21,603 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2022-07-12 10:47:22,167 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-12 10:47:22,182 INFO L263 TraceCheckSpWp]: Trace formula consists of 2811 conjuncts, 327 conjunts are in the unsatisfiable core [2022-07-12 10:47:22,191 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-12 10:47:22,214 INFO L390 Elim1Store]: Elim1 did not use preprocessing 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 [2022-07-12 10:47:22,489 INFO L390 Elim1Store]: Elim1 did not use preprocessing 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 9 treesize of output 3 [2022-07-12 10:47:22,492 INFO L390 Elim1Store]: Elim1 did not use preprocessing 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 9 treesize of output 3 [2022-07-12 10:47:22,706 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2022-07-12 10:47:22,959 INFO L356 Elim1Store]: treesize reduction 60, result has 24.1 percent of original size [2022-07-12 10:47:22,959 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 6 case distinctions, treesize of input 32 treesize of output 37 [2022-07-12 10:47:23,163 INFO L356 Elim1Store]: treesize reduction 60, result has 24.1 percent of original size [2022-07-12 10:47:23,163 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 6 case distinctions, treesize of input 29 treesize of output 37 [2022-07-12 10:47:34,037 INFO L356 Elim1Store]: treesize reduction 91, result has 30.0 percent of original size [2022-07-12 10:47:34,037 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 4 select indices, 4 select index equivalence classes, 1 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 9 case distinctions, treesize of input 46 treesize of output 69 [2022-07-12 10:47:34,051 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 4 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 24 treesize of output 23 [2022-07-12 10:47:34,598 INFO L356 Elim1Store]: treesize reduction 36, result has 34.5 percent of original size [2022-07-12 10:47:34,599 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 3 select indices, 3 select index equivalence classes, 1 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 4 case distinctions, treesize of input 22 treesize of output 33 [2022-07-12 10:47:37,634 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-12 10:47:37,635 INFO L173 IndexEqualityManager]: detected equality via solver [2022-07-12 10:47:37,636 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-12 10:47:37,638 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 2 stores, 3 select indices, 3 select index equivalence classes, 4 disjoint index pairs (out of 3 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 119 treesize of output 138 [2022-07-12 10:47:37,763 INFO L356 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2022-07-12 10:47:37,763 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 4 select indices, 4 select index equivalence classes, 1 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 5 case distinctions, treesize of input 148 treesize of output 180 [2022-07-12 10:47:38,063 INFO L356 Elim1Store]: treesize reduction 11, result has 8.3 percent of original size [2022-07-12 10:47:38,063 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 4 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 65 treesize of output 51 [2022-07-12 10:47:38,069 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 17 [2022-07-12 10:48:28,250 WARN L855 $PredicateComparison]: unable to prove that (let ((.cse3 (= |c_aws_array_list_is_valid_#res| 0))) (let ((.cse1 (exists ((|aws_array_list_is_valid_~#required_size~0.base| Int)) (and (= (store |c_old(#memory_int)| |aws_array_list_is_valid_~#required_size~0.base| (store (select |c_old(#memory_int)| |aws_array_list_is_valid_~#required_size~0.base|) 0 (let ((.cse5 (select |c_old(#memory_int)| |c_aws_array_list_is_valid_#in~list.base|))) (* (select .cse5 (+ |c_aws_array_list_is_valid_#in~list.offset| 24)) (select .cse5 (+ |c_aws_array_list_is_valid_#in~list.offset| 16)))))) |c_#memory_int|) (<= (mod (select (select |c_#memory_int| |aws_array_list_is_valid_~#required_size~0.base|) 0) 18446744073709551616) (mod (select (select |c_#memory_int| |c_aws_array_list_is_valid_#in~list.base|) (+ |c_aws_array_list_is_valid_#in~list.offset| 8)) 18446744073709551616))))) (.cse0 (and (exists ((|aws_array_list_is_valid_~#required_size~0.base| Int)) (and (= (store |c_old(#memory_int)| |aws_array_list_is_valid_~#required_size~0.base| (store (select |c_old(#memory_int)| |aws_array_list_is_valid_~#required_size~0.base|) 0 (let ((.cse4 (select |c_old(#memory_int)| |c_aws_array_list_is_valid_#in~list.base|))) (* (select .cse4 (+ |c_aws_array_list_is_valid_#in~list.offset| 24)) (select .cse4 (+ |c_aws_array_list_is_valid_#in~list.offset| 16)))))) |c_#memory_int|) (not (<= (mod (select (select |c_#memory_int| |aws_array_list_is_valid_~#required_size~0.base|) 0) 18446744073709551616) (mod (select (select |c_#memory_int| |c_aws_array_list_is_valid_#in~list.base|) (+ |c_aws_array_list_is_valid_#in~list.offset| 8)) 18446744073709551616))))) .cse3)) (.cse2 (= (mod (select (select |c_#memory_int| |c_aws_array_list_is_valid_#in~list.base|) (+ |c_aws_array_list_is_valid_#in~list.offset| 24)) 18446744073709551616) 0))) (or (and (or .cse0 (and .cse1 (= |c_aws_array_list_is_valid_#res| 1))) (not .cse2)) (and (or (and .cse1 .cse3) .cse0) .cse2)))) is different from true [2022-07-12 10:48:34,394 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-12 10:48:35,189 INFO L356 Elim1Store]: treesize reduction 72, result has 28.7 percent of original size [2022-07-12 10:48:35,190 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 4 stores, 4 select indices, 4 select index equivalence classes, 7 disjoint index pairs (out of 6 index pairs), introduced 8 new quantified variables, introduced 4 case distinctions, treesize of input 362 treesize of output 468 [2022-07-12 10:48:36,025 INFO L134 CoverageAnalysis]: Checked inductivity of 154 backedges. 28 proven. 108 refuted. 0 times theorem prover too weak. 12 trivial. 6 not checked. [2022-07-12 10:48:36,025 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-12 10:48:43,286 WARN L833 $PredicateComparison]: unable to prove that (and (forall ((|v_aws_array_list_is_valid_~#required_size~0.base_13| Int)) (let ((.cse1 (+ |c_aws_array_list_ensure_capacity_aws_array_list_calc_necessary_size_~list#1.offset| 24))) (let ((.cse2 (let ((.cse3 (select |c_#memory_int| |c_aws_array_list_ensure_capacity_aws_array_list_calc_necessary_size_~list#1.base|))) (* (select .cse3 .cse1) (select .cse3 (+ |c_aws_array_list_ensure_capacity_aws_array_list_calc_necessary_size_~list#1.offset| 16)))))) (let ((.cse0 (select (store |c_#memory_int| |v_aws_array_list_is_valid_~#required_size~0.base_13| (store (select |c_#memory_int| |v_aws_array_list_is_valid_~#required_size~0.base_13|) 0 .cse2)) |c_aws_array_list_ensure_capacity_aws_array_list_calc_necessary_size_~list#1.base|))) (or (not (= (mod (select .cse0 .cse1) 18446744073709551616) 0)) (not (<= (mod .cse2 18446744073709551616) (mod (select .cse0 (+ |c_aws_array_list_ensure_capacity_aws_array_list_calc_necessary_size_~list#1.offset| 8)) 18446744073709551616)))))))) (forall ((|v_aws_array_list_is_valid_~#required_size~0.base_13| Int)) (let ((.cse4 (let ((.cse5 (select |c_#memory_int| |c_aws_array_list_ensure_capacity_aws_array_list_calc_necessary_size_~list#1.base|))) (* (select .cse5 (+ |c_aws_array_list_ensure_capacity_aws_array_list_calc_necessary_size_~list#1.offset| 24)) (select .cse5 (+ |c_aws_array_list_ensure_capacity_aws_array_list_calc_necessary_size_~list#1.offset| 16)))))) (<= (mod .cse4 18446744073709551616) (mod (select (select (store |c_#memory_int| |v_aws_array_list_is_valid_~#required_size~0.base_13| (store (select |c_#memory_int| |v_aws_array_list_is_valid_~#required_size~0.base_13|) 0 .cse4)) |c_aws_array_list_ensure_capacity_aws_array_list_calc_necessary_size_~list#1.base|) (+ |c_aws_array_list_ensure_capacity_aws_array_list_calc_necessary_size_~list#1.offset| 8)) 18446744073709551616))))) is different from false [2022-07-12 10:48:43,312 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-12 10:48:43,312 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [228848050] [2022-07-12 10:48:43,312 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-12 10:48:43,312 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1859759950] [2022-07-12 10:48:43,312 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1859759950] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-12 10:48:43,312 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-07-12 10:48:43,312 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [66] total 66 [2022-07-12 10:48:43,312 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [412568157] [2022-07-12 10:48:43,312 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-07-12 10:48:43,313 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 66 states [2022-07-12 10:48:43,313 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-12 10:48:43,313 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 66 interpolants. [2022-07-12 10:48:43,314 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=227, Invalid=4297, Unknown=40, NotChecked=266, Total=4830 [2022-07-12 10:48:43,314 INFO L87 Difference]: Start difference. First operand 237 states and 310 transitions. Second operand has 66 states, 53 states have (on average 1.8679245283018868) internal successors, (99), 48 states have internal predecessors, (99), 20 states have call successors, (24), 11 states have call predecessors, (24), 17 states have return successors, (22), 18 states have call predecessors, (22), 18 states have call successors, (22) [2022-07-12 10:49:07,670 WARN L233 SmtUtils]: Spent 8.64s on a formula simplification. DAG size of input: 102 DAG size of output: 72 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-07-12 10:49:21,436 WARN L233 SmtUtils]: Spent 10.42s on a formula simplification. DAG size of input: 96 DAG size of output: 66 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-07-12 10:49:33,621 WARN L233 SmtUtils]: Spent 8.79s on a formula simplification. DAG size of input: 97 DAG size of output: 67 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-07-12 10:50:14,914 WARN L233 SmtUtils]: Spent 38.95s on a formula simplification. DAG size of input: 97 DAG size of output: 86 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-07-12 10:50:20,345 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-12 10:50:20,345 INFO L93 Difference]: Finished difference Result 335 states and 440 transitions. [2022-07-12 10:50:20,346 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 59 states. [2022-07-12 10:50:20,346 INFO L78 Accepts]: Start accepts. Automaton has has 66 states, 53 states have (on average 1.8679245283018868) internal successors, (99), 48 states have internal predecessors, (99), 20 states have call successors, (24), 11 states have call predecessors, (24), 17 states have return successors, (22), 18 states have call predecessors, (22), 18 states have call successors, (22) Word has length 153 [2022-07-12 10:50:20,346 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-12 10:50:20,348 INFO L225 Difference]: With dead ends: 335 [2022-07-12 10:50:20,348 INFO L226 Difference]: Without dead ends: 333 [2022-07-12 10:50:20,350 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 194 GetRequests, 91 SyntacticMatches, 5 SemanticMatches, 98 ConstructedPredicates, 2 IntricatePredicates, 0 DeprecatedPredicates, 2639 ImplicationChecksByTransitivity, 151.7s TimeCoverageRelationStatistics Valid=511, Invalid=8948, Unknown=55, NotChecked=386, Total=9900 [2022-07-12 10:50:20,350 INFO L413 NwaCegarLoop]: 264 mSDtfsCounter, 267 mSDsluCounter, 3212 mSDsCounter, 0 mSdLazyCounter, 3746 mSolverCounterSat, 309 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 269 SdHoareTripleChecker+Valid, 3476 SdHoareTripleChecker+Invalid, 8451 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 309 IncrementalHoareTripleChecker+Valid, 3746 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 4396 IncrementalHoareTripleChecker+Unchecked, 2.6s IncrementalHoareTripleChecker+Time [2022-07-12 10:50:20,350 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [269 Valid, 3476 Invalid, 8451 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [309 Valid, 3746 Invalid, 0 Unknown, 4396 Unchecked, 2.6s Time] [2022-07-12 10:50:20,351 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 333 states. [2022-07-12 10:50:20,365 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 333 to 308. [2022-07-12 10:50:20,366 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 308 states, 189 states have (on average 1.164021164021164) internal successors, (220), 194 states have internal predecessors, (220), 86 states have call successors, (86), 29 states have call predecessors, (86), 32 states have return successors, (105), 84 states have call predecessors, (105), 83 states have call successors, (105) [2022-07-12 10:50:20,367 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 308 states to 308 states and 411 transitions. [2022-07-12 10:50:20,367 INFO L78 Accepts]: Start accepts. Automaton has 308 states and 411 transitions. Word has length 153 [2022-07-12 10:50:20,369 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-12 10:50:20,369 INFO L495 AbstractCegarLoop]: Abstraction has 308 states and 411 transitions. [2022-07-12 10:50:20,369 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 66 states, 53 states have (on average 1.8679245283018868) internal successors, (99), 48 states have internal predecessors, (99), 20 states have call successors, (24), 11 states have call predecessors, (24), 17 states have return successors, (22), 18 states have call predecessors, (22), 18 states have call successors, (22) [2022-07-12 10:50:20,369 INFO L276 IsEmpty]: Start isEmpty. Operand 308 states and 411 transitions. [2022-07-12 10:50:20,371 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 178 [2022-07-12 10:50:20,371 INFO L187 NwaCegarLoop]: Found error trace [2022-07-12 10:50:20,372 INFO L195 NwaCegarLoop]: trace histogram [5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-12 10:50:20,413 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2022-07-12 10:50:20,593 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-12 10:50:20,594 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-12 10:50:20,594 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-12 10:50:20,594 INFO L85 PathProgramCache]: Analyzing trace with hash 1305403562, now seen corresponding path program 1 times [2022-07-12 10:50:20,595 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-12 10:50:20,595 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2004148766] [2022-07-12 10:50:20,595 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-12 10:50:20,595 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-12 10:50:20,658 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-12 10:50:20,658 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [474541471] [2022-07-12 10:50:20,659 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-12 10:50:20,659 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-12 10:50:20,659 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-12 10:50:20,676 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-12 10:50:20,720 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2022-07-12 10:50:21,152 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-12 10:50:21,161 INFO L263 TraceCheckSpWp]: Trace formula consists of 2862 conjuncts, 43 conjunts are in the unsatisfiable core [2022-07-12 10:50:21,165 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-12 10:50:21,188 INFO L390 Elim1Store]: Elim1 did not use preprocessing 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 21 treesize of output 9 [2022-07-12 10:50:21,473 INFO L134 CoverageAnalysis]: Checked inductivity of 184 backedges. 126 proven. 4 refuted. 0 times theorem prover too weak. 54 trivial. 0 not checked. [2022-07-12 10:50:21,473 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-12 10:50:22,312 INFO L134 CoverageAnalysis]: Checked inductivity of 184 backedges. 19 proven. 31 refuted. 0 times theorem prover too weak. 134 trivial. 0 not checked. [2022-07-12 10:50:22,313 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-12 10:50:22,313 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2004148766] [2022-07-12 10:50:22,313 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-12 10:50:22,313 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [474541471] [2022-07-12 10:50:22,313 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [474541471] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-12 10:50:22,313 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-07-12 10:50:22,314 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 15] total 26 [2022-07-12 10:50:22,314 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1964135088] [2022-07-12 10:50:22,314 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-07-12 10:50:22,314 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 26 states [2022-07-12 10:50:22,314 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-12 10:50:22,315 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2022-07-12 10:50:22,315 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=55, Invalid=595, Unknown=0, NotChecked=0, Total=650 [2022-07-12 10:50:22,315 INFO L87 Difference]: Start difference. First operand 308 states and 411 transitions. Second operand has 26 states, 21 states have (on average 5.571428571428571) internal successors, (117), 19 states have internal predecessors, (117), 7 states have call successors, (34), 3 states have call predecessors, (34), 8 states have return successors, (35), 9 states have call predecessors, (35), 6 states have call successors, (35) [2022-07-12 10:50:23,464 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-12 10:50:23,465 INFO L93 Difference]: Finished difference Result 541 states and 738 transitions. [2022-07-12 10:50:23,465 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2022-07-12 10:50:23,465 INFO L78 Accepts]: Start accepts. Automaton has has 26 states, 21 states have (on average 5.571428571428571) internal successors, (117), 19 states have internal predecessors, (117), 7 states have call successors, (34), 3 states have call predecessors, (34), 8 states have return successors, (35), 9 states have call predecessors, (35), 6 states have call successors, (35) Word has length 177 [2022-07-12 10:50:23,465 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-12 10:50:23,471 INFO L225 Difference]: With dead ends: 541 [2022-07-12 10:50:23,471 INFO L226 Difference]: Without dead ends: 330 [2022-07-12 10:50:23,472 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 358 GetRequests, 327 SyntacticMatches, 1 SemanticMatches, 30 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 26 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=83, Invalid=909, Unknown=0, NotChecked=0, Total=992 [2022-07-12 10:50:23,472 INFO L413 NwaCegarLoop]: 298 mSDtfsCounter, 24 mSDsluCounter, 6846 mSDsCounter, 0 mSdLazyCounter, 1176 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 29 SdHoareTripleChecker+Valid, 7144 SdHoareTripleChecker+Invalid, 1187 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 1176 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.0s IncrementalHoareTripleChecker+Time [2022-07-12 10:50:23,473 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [29 Valid, 7144 Invalid, 1187 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 1176 Invalid, 0 Unknown, 0 Unchecked, 1.0s Time] [2022-07-12 10:50:23,474 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 330 states. [2022-07-12 10:50:23,490 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 330 to 315. [2022-07-12 10:50:23,490 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 315 states, 195 states have (on average 1.1641025641025642) internal successors, (227), 201 states have internal predecessors, (227), 86 states have call successors, (86), 29 states have call predecessors, (86), 33 states have return successors, (119), 84 states have call predecessors, (119), 83 states have call successors, (119) [2022-07-12 10:50:23,492 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 315 states to 315 states and 432 transitions. [2022-07-12 10:50:23,492 INFO L78 Accepts]: Start accepts. Automaton has 315 states and 432 transitions. Word has length 177 [2022-07-12 10:50:23,492 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-12 10:50:23,492 INFO L495 AbstractCegarLoop]: Abstraction has 315 states and 432 transitions. [2022-07-12 10:50:23,492 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 26 states, 21 states have (on average 5.571428571428571) internal successors, (117), 19 states have internal predecessors, (117), 7 states have call successors, (34), 3 states have call predecessors, (34), 8 states have return successors, (35), 9 states have call predecessors, (35), 6 states have call successors, (35) [2022-07-12 10:50:23,493 INFO L276 IsEmpty]: Start isEmpty. Operand 315 states and 432 transitions. [2022-07-12 10:50:23,495 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 166 [2022-07-12 10:50:23,495 INFO L187 NwaCegarLoop]: Found error trace [2022-07-12 10:50:23,495 INFO L195 NwaCegarLoop]: trace histogram [5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-12 10:50:23,519 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2022-07-12 10:50:23,717 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-12 10:50:23,718 INFO L420 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-12 10:50:23,718 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-12 10:50:23,718 INFO L85 PathProgramCache]: Analyzing trace with hash -903903491, now seen corresponding path program 1 times [2022-07-12 10:50:23,718 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-12 10:50:23,718 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1382731034] [2022-07-12 10:50:23,718 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-12 10:50:23,718 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-12 10:50:23,771 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-12 10:50:23,771 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [314010229] [2022-07-12 10:50:23,771 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-12 10:50:23,771 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-12 10:50:23,772 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-12 10:50:23,773 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-12 10:50:23,773 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2022-07-12 10:50:24,177 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-12 10:50:24,186 INFO L263 TraceCheckSpWp]: Trace formula consists of 2819 conjuncts, 31 conjunts are in the unsatisfiable core [2022-07-12 10:50:24,190 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-12 10:50:24,316 INFO L134 CoverageAnalysis]: Checked inductivity of 168 backedges. 98 proven. 2 refuted. 0 times theorem prover too weak. 68 trivial. 0 not checked. [2022-07-12 10:50:24,316 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-12 10:50:24,889 INFO L134 CoverageAnalysis]: Checked inductivity of 168 backedges. 32 proven. 15 refuted. 0 times theorem prover too weak. 121 trivial. 0 not checked. [2022-07-12 10:50:24,889 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-12 10:50:24,889 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1382731034] [2022-07-12 10:50:24,889 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-12 10:50:24,889 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [314010229] [2022-07-12 10:50:24,889 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [314010229] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-12 10:50:24,889 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-07-12 10:50:24,889 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 15] total 21 [2022-07-12 10:50:24,889 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1339870140] [2022-07-12 10:50:24,890 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-07-12 10:50:24,890 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2022-07-12 10:50:24,890 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-12 10:50:24,890 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2022-07-12 10:50:24,890 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=45, Invalid=375, Unknown=0, NotChecked=0, Total=420 [2022-07-12 10:50:24,891 INFO L87 Difference]: Start difference. First operand 315 states and 432 transitions. Second operand has 21 states, 18 states have (on average 5.777777777777778) internal successors, (104), 14 states have internal predecessors, (104), 5 states have call successors, (29), 3 states have call predecessors, (29), 7 states have return successors, (30), 8 states have call predecessors, (30), 4 states have call successors, (30) [2022-07-12 10:50:25,270 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-12 10:50:25,270 INFO L93 Difference]: Finished difference Result 531 states and 726 transitions. [2022-07-12 10:50:25,270 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2022-07-12 10:50:25,270 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 18 states have (on average 5.777777777777778) internal successors, (104), 14 states have internal predecessors, (104), 5 states have call successors, (29), 3 states have call predecessors, (29), 7 states have return successors, (30), 8 states have call predecessors, (30), 4 states have call successors, (30) Word has length 165 [2022-07-12 10:50:25,271 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-12 10:50:25,272 INFO L225 Difference]: With dead ends: 531 [2022-07-12 10:50:25,272 INFO L226 Difference]: Without dead ends: 316 [2022-07-12 10:50:25,273 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 332 GetRequests, 308 SyntacticMatches, 1 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 16 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=65, Invalid=535, Unknown=0, NotChecked=0, Total=600 [2022-07-12 10:50:25,273 INFO L413 NwaCegarLoop]: 307 mSDtfsCounter, 19 mSDsluCounter, 4467 mSDsCounter, 0 mSdLazyCounter, 441 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 19 SdHoareTripleChecker+Valid, 4774 SdHoareTripleChecker+Invalid, 444 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 441 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-07-12 10:50:25,274 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [19 Valid, 4774 Invalid, 444 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 441 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-07-12 10:50:25,274 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 316 states. [2022-07-12 10:50:25,284 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 316 to 315. [2022-07-12 10:50:25,285 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 315 states, 195 states have (on average 1.1641025641025642) internal successors, (227), 201 states have internal predecessors, (227), 86 states have call successors, (86), 29 states have call predecessors, (86), 33 states have return successors, (117), 84 states have call predecessors, (117), 83 states have call successors, (117) [2022-07-12 10:50:25,286 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 315 states to 315 states and 430 transitions. [2022-07-12 10:50:25,286 INFO L78 Accepts]: Start accepts. Automaton has 315 states and 430 transitions. Word has length 165 [2022-07-12 10:50:25,287 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-12 10:50:25,287 INFO L495 AbstractCegarLoop]: Abstraction has 315 states and 430 transitions. [2022-07-12 10:50:25,287 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 18 states have (on average 5.777777777777778) internal successors, (104), 14 states have internal predecessors, (104), 5 states have call successors, (29), 3 states have call predecessors, (29), 7 states have return successors, (30), 8 states have call predecessors, (30), 4 states have call successors, (30) [2022-07-12 10:50:25,287 INFO L276 IsEmpty]: Start isEmpty. Operand 315 states and 430 transitions. [2022-07-12 10:50:25,288 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 160 [2022-07-12 10:50:25,288 INFO L187 NwaCegarLoop]: Found error trace [2022-07-12 10:50:25,289 INFO L195 NwaCegarLoop]: trace histogram [5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-12 10:50:25,313 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2022-07-12 10:50:25,504 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable8 [2022-07-12 10:50:25,504 INFO L420 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-12 10:50:25,504 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-12 10:50:25,504 INFO L85 PathProgramCache]: Analyzing trace with hash -1180527824, now seen corresponding path program 1 times [2022-07-12 10:50:25,504 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-12 10:50:25,504 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2117812696] [2022-07-12 10:50:25,505 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-12 10:50:25,505 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-12 10:50:25,570 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-12 10:50:25,570 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [473591575] [2022-07-12 10:50:25,570 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-12 10:50:25,571 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-12 10:50:25,571 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-12 10:50:25,583 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-12 10:50:25,584 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2022-07-12 10:50:26,004 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-12 10:50:26,014 INFO L263 TraceCheckSpWp]: Trace formula consists of 2850 conjuncts, 65 conjunts are in the unsatisfiable core [2022-07-12 10:50:26,018 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-12 10:50:26,022 INFO L390 Elim1Store]: Elim1 did not use preprocessing 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 [2022-07-12 10:50:26,138 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 13 treesize of output 9 [2022-07-12 10:50:26,168 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 24 treesize of output 15 [2022-07-12 10:50:30,242 INFO L356 Elim1Store]: treesize reduction 23, result has 28.1 percent of original size [2022-07-12 10:50:30,242 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 45 treesize of output 32 [2022-07-12 10:50:30,294 INFO L356 Elim1Store]: treesize reduction 30, result has 34.8 percent of original size [2022-07-12 10:50:30,295 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 29 treesize of output 33 [2022-07-12 10:50:30,474 WARN L855 $PredicateComparison]: unable to prove that (exists ((v_ArrVal_1070 (Array Int Int))) (= |c_#memory_$Pointer$.base| (store |c_old(#memory_$Pointer$.base)| |c_aws_mul_size_checked_#in~r#1.base| v_ArrVal_1070))) is different from true [2022-07-12 10:50:38,721 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-12 10:50:38,722 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 27 treesize of output 27 [2022-07-12 10:50:38,725 INFO L134 CoverageAnalysis]: Checked inductivity of 154 backedges. 81 proven. 4 refuted. 0 times theorem prover too weak. 69 trivial. 0 not checked. [2022-07-12 10:50:38,735 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-12 10:50:38,980 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-12 10:50:38,980 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2117812696] [2022-07-12 10:50:38,980 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-12 10:50:38,980 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [473591575] [2022-07-12 10:50:38,980 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [473591575] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-12 10:50:38,980 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-07-12 10:50:38,980 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [22] total 22 [2022-07-12 10:50:38,980 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1966987998] [2022-07-12 10:50:38,981 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-07-12 10:50:38,981 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2022-07-12 10:50:38,981 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-12 10:50:38,981 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2022-07-12 10:50:38,981 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=61, Invalid=386, Unknown=19, NotChecked=40, Total=506 [2022-07-12 10:50:38,981 INFO L87 Difference]: Start difference. First operand 315 states and 430 transitions. Second operand has 22 states, 20 states have (on average 3.75) internal successors, (75), 18 states have internal predecessors, (75), 8 states have call successors, (22), 7 states have call predecessors, (22), 8 states have return successors, (20), 8 states have call predecessors, (20), 8 states have call successors, (20) [2022-07-12 10:50:43,818 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-12 10:50:43,818 INFO L93 Difference]: Finished difference Result 569 states and 773 transitions. [2022-07-12 10:50:43,819 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 25 states. [2022-07-12 10:50:43,819 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 20 states have (on average 3.75) internal successors, (75), 18 states have internal predecessors, (75), 8 states have call successors, (22), 7 states have call predecessors, (22), 8 states have return successors, (20), 8 states have call predecessors, (20), 8 states have call successors, (20) Word has length 159 [2022-07-12 10:50:43,819 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-12 10:50:43,821 INFO L225 Difference]: With dead ends: 569 [2022-07-12 10:50:43,823 INFO L226 Difference]: Without dead ends: 341 [2022-07-12 10:50:43,824 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 270 GetRequests, 239 SyntacticMatches, 4 SemanticMatches, 27 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 137 ImplicationChecksByTransitivity, 16.6s TimeCoverageRelationStatistics Valid=91, Invalid=638, Unknown=31, NotChecked=52, Total=812 [2022-07-12 10:50:43,826 INFO L413 NwaCegarLoop]: 268 mSDtfsCounter, 253 mSDsluCounter, 1017 mSDsCounter, 0 mSdLazyCounter, 919 mSolverCounterSat, 288 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 268 SdHoareTripleChecker+Valid, 1285 SdHoareTripleChecker+Invalid, 3238 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 288 IncrementalHoareTripleChecker+Valid, 919 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 2031 IncrementalHoareTripleChecker+Unchecked, 0.7s IncrementalHoareTripleChecker+Time [2022-07-12 10:50:43,827 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [268 Valid, 1285 Invalid, 3238 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [288 Valid, 919 Invalid, 0 Unknown, 2031 Unchecked, 0.7s Time] [2022-07-12 10:50:43,828 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 341 states. [2022-07-12 10:50:43,838 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 341 to 322. [2022-07-12 10:50:43,840 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 322 states, 199 states have (on average 1.1608040201005025) internal successors, (231), 206 states have internal predecessors, (231), 87 states have call successors, (87), 30 states have call predecessors, (87), 35 states have return successors, (120), 85 states have call predecessors, (120), 84 states have call successors, (120) [2022-07-12 10:50:43,842 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 322 states to 322 states and 438 transitions. [2022-07-12 10:50:43,842 INFO L78 Accepts]: Start accepts. Automaton has 322 states and 438 transitions. Word has length 159 [2022-07-12 10:50:43,842 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-12 10:50:43,842 INFO L495 AbstractCegarLoop]: Abstraction has 322 states and 438 transitions. [2022-07-12 10:50:43,843 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 20 states have (on average 3.75) internal successors, (75), 18 states have internal predecessors, (75), 8 states have call successors, (22), 7 states have call predecessors, (22), 8 states have return successors, (20), 8 states have call predecessors, (20), 8 states have call successors, (20) [2022-07-12 10:50:43,843 INFO L276 IsEmpty]: Start isEmpty. Operand 322 states and 438 transitions. [2022-07-12 10:50:43,844 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 162 [2022-07-12 10:50:43,844 INFO L187 NwaCegarLoop]: Found error trace [2022-07-12 10:50:43,844 INFO L195 NwaCegarLoop]: trace histogram [5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 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] [2022-07-12 10:50:43,864 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2022-07-12 10:50:44,064 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2022-07-12 10:50:44,064 INFO L420 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-12 10:50:44,064 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-12 10:50:44,064 INFO L85 PathProgramCache]: Analyzing trace with hash -1416810633, now seen corresponding path program 1 times [2022-07-12 10:50:44,065 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-12 10:50:44,065 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1800932843] [2022-07-12 10:50:44,065 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-12 10:50:44,065 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-12 10:50:44,104 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-12 10:50:44,104 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1429614355] [2022-07-12 10:50:44,104 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-12 10:50:44,104 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-12 10:50:44,104 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-12 10:50:44,105 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-12 10:50:44,124 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2022-07-12 10:50:44,542 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-12 10:50:44,549 INFO L263 TraceCheckSpWp]: Trace formula consists of 2815 conjuncts, 8 conjunts are in the unsatisfiable core [2022-07-12 10:50:44,552 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-12 10:50:44,591 INFO L134 CoverageAnalysis]: Checked inductivity of 158 backedges. 100 proven. 0 refuted. 0 times theorem prover too weak. 58 trivial. 0 not checked. [2022-07-12 10:50:44,591 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-07-12 10:50:44,591 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-12 10:50:44,592 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1800932843] [2022-07-12 10:50:44,592 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-12 10:50:44,592 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1429614355] [2022-07-12 10:50:44,592 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1429614355] provided 1 perfect and 0 imperfect interpolant sequences [2022-07-12 10:50:44,592 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-07-12 10:50:44,592 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-07-12 10:50:44,592 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1318269209] [2022-07-12 10:50:44,592 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-12 10:50:44,593 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-07-12 10:50:44,593 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-12 10:50:44,593 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-07-12 10:50:44,593 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-07-12 10:50:44,593 INFO L87 Difference]: Start difference. First operand 322 states and 438 transitions. Second operand has 5 states, 5 states have (on average 15.2) internal successors, (76), 5 states have internal predecessors, (76), 2 states have call successors, (22), 2 states have call predecessors, (22), 2 states have return successors, (20), 2 states have call predecessors, (20), 2 states have call successors, (20) [2022-07-12 10:50:44,776 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-12 10:50:44,776 INFO L93 Difference]: Finished difference Result 560 states and 823 transitions. [2022-07-12 10:50:44,776 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-07-12 10:50:44,777 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 15.2) internal successors, (76), 5 states have internal predecessors, (76), 2 states have call successors, (22), 2 states have call predecessors, (22), 2 states have return successors, (20), 2 states have call predecessors, (20), 2 states have call successors, (20) Word has length 161 [2022-07-12 10:50:44,777 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-12 10:50:44,778 INFO L225 Difference]: With dead ends: 560 [2022-07-12 10:50:44,778 INFO L226 Difference]: Without dead ends: 332 [2022-07-12 10:50:44,779 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 163 GetRequests, 158 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=17, Invalid=25, Unknown=0, NotChecked=0, Total=42 [2022-07-12 10:50:44,780 INFO L413 NwaCegarLoop]: 311 mSDtfsCounter, 7 mSDsluCounter, 840 mSDsCounter, 0 mSdLazyCounter, 112 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 1151 SdHoareTripleChecker+Invalid, 115 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 112 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-07-12 10:50:44,780 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 1151 Invalid, 115 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 112 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-07-12 10:50:44,781 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 332 states. [2022-07-12 10:50:44,792 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 332 to 324. [2022-07-12 10:50:44,792 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 324 states, 201 states have (on average 1.1592039800995024) internal successors, (233), 208 states have internal predecessors, (233), 87 states have call successors, (87), 30 states have call predecessors, (87), 35 states have return successors, (120), 85 states have call predecessors, (120), 84 states have call successors, (120) [2022-07-12 10:50:44,794 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 324 states to 324 states and 440 transitions. [2022-07-12 10:50:44,794 INFO L78 Accepts]: Start accepts. Automaton has 324 states and 440 transitions. Word has length 161 [2022-07-12 10:50:44,794 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-12 10:50:44,794 INFO L495 AbstractCegarLoop]: Abstraction has 324 states and 440 transitions. [2022-07-12 10:50:44,794 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 15.2) internal successors, (76), 5 states have internal predecessors, (76), 2 states have call successors, (22), 2 states have call predecessors, (22), 2 states have return successors, (20), 2 states have call predecessors, (20), 2 states have call successors, (20) [2022-07-12 10:50:44,795 INFO L276 IsEmpty]: Start isEmpty. Operand 324 states and 440 transitions. [2022-07-12 10:50:44,796 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 171 [2022-07-12 10:50:44,796 INFO L187 NwaCegarLoop]: Found error trace [2022-07-12 10:50:44,796 INFO L195 NwaCegarLoop]: trace histogram [5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 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] [2022-07-12 10:50:44,833 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2022-07-12 10:50:45,031 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2022-07-12 10:50:45,031 INFO L420 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-12 10:50:45,032 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-12 10:50:45,032 INFO L85 PathProgramCache]: Analyzing trace with hash 1059586175, now seen corresponding path program 1 times [2022-07-12 10:50:45,032 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-12 10:50:45,032 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [498523724] [2022-07-12 10:50:45,032 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-12 10:50:45,032 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-12 10:50:45,095 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-12 10:50:45,095 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1252608817] [2022-07-12 10:50:45,095 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-12 10:50:45,096 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-12 10:50:45,096 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-12 10:50:45,120 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-12 10:50:45,138 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2022-07-12 10:50:45,569 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-12 10:50:45,578 INFO L263 TraceCheckSpWp]: Trace formula consists of 2867 conjuncts, 73 conjunts are in the unsatisfiable core [2022-07-12 10:50:45,582 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-12 10:50:45,588 INFO L390 Elim1Store]: Elim1 did not use preprocessing 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 [2022-07-12 10:50:45,700 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 13 treesize of output 9 [2022-07-12 10:50:45,731 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 24 treesize of output 15 [2022-07-12 10:50:49,794 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 24 treesize of output 15 [2022-07-12 10:50:53,862 INFO L356 Elim1Store]: treesize reduction 23, result has 28.1 percent of original size [2022-07-12 10:50:53,862 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 45 treesize of output 32 [2022-07-12 10:50:53,911 INFO L356 Elim1Store]: treesize reduction 30, result has 34.8 percent of original size [2022-07-12 10:50:53,911 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 29 treesize of output 33 [2022-07-12 10:50:54,079 WARN L855 $PredicateComparison]: unable to prove that (exists ((v_ArrVal_1363 (Array Int Int))) (= |c_#memory_$Pointer$.base| (store |c_old(#memory_$Pointer$.base)| |c_aws_mul_size_checked_#in~r#1.base| v_ArrVal_1363))) is different from true [2022-07-12 10:51:02,322 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-12 10:51:02,323 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 27 treesize of output 27 [2022-07-12 10:51:02,327 INFO L134 CoverageAnalysis]: Checked inductivity of 158 backedges. 81 proven. 4 refuted. 0 times theorem prover too weak. 73 trivial. 0 not checked. [2022-07-12 10:51:02,327 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-12 10:51:02,539 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-12 10:51:02,539 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [498523724] [2022-07-12 10:51:02,539 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-12 10:51:02,539 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1252608817] [2022-07-12 10:51:02,540 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1252608817] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-12 10:51:02,540 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-07-12 10:51:02,540 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [22] total 22 [2022-07-12 10:51:02,540 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1529353031] [2022-07-12 10:51:02,540 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-07-12 10:51:02,540 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2022-07-12 10:51:02,540 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-12 10:51:02,540 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2022-07-12 10:51:02,541 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=61, Invalid=386, Unknown=19, NotChecked=40, Total=506 [2022-07-12 10:51:02,541 INFO L87 Difference]: Start difference. First operand 324 states and 440 transitions. Second operand has 22 states, 20 states have (on average 4.0) internal successors, (80), 18 states have internal predecessors, (80), 8 states have call successors, (24), 7 states have call predecessors, (24), 8 states have return successors, (22), 8 states have call predecessors, (22), 8 states have call successors, (22) [2022-07-12 10:51:07,294 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-12 10:51:07,294 INFO L93 Difference]: Finished difference Result 575 states and 777 transitions. [2022-07-12 10:51:07,294 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2022-07-12 10:51:07,295 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 20 states have (on average 4.0) internal successors, (80), 18 states have internal predecessors, (80), 8 states have call successors, (24), 7 states have call predecessors, (24), 8 states have return successors, (22), 8 states have call predecessors, (22), 8 states have call successors, (22) Word has length 170 [2022-07-12 10:51:07,295 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-12 10:51:07,296 INFO L225 Difference]: With dead ends: 575 [2022-07-12 10:51:07,296 INFO L226 Difference]: Without dead ends: 345 [2022-07-12 10:51:07,297 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 286 GetRequests, 254 SyntacticMatches, 6 SemanticMatches, 26 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 132 ImplicationChecksByTransitivity, 20.6s TimeCoverageRelationStatistics Valid=86, Invalid=590, Unknown=30, NotChecked=50, Total=756 [2022-07-12 10:51:07,298 INFO L413 NwaCegarLoop]: 269 mSDtfsCounter, 200 mSDsluCounter, 1103 mSDsCounter, 0 mSdLazyCounter, 849 mSolverCounterSat, 190 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 215 SdHoareTripleChecker+Valid, 1372 SdHoareTripleChecker+Invalid, 3227 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 190 IncrementalHoareTripleChecker+Valid, 849 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 2188 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2022-07-12 10:51:07,298 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [215 Valid, 1372 Invalid, 3227 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [190 Valid, 849 Invalid, 0 Unknown, 2188 Unchecked, 0.6s Time] [2022-07-12 10:51:07,298 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 345 states. [2022-07-12 10:51:07,308 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 345 to 323. [2022-07-12 10:51:07,309 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 323 states, 201 states have (on average 1.1592039800995024) internal successors, (233), 207 states have internal predecessors, (233), 86 states have call successors, (86), 31 states have call predecessors, (86), 35 states have return successors, (116), 84 states have call predecessors, (116), 83 states have call successors, (116) [2022-07-12 10:51:07,310 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 323 states to 323 states and 435 transitions. [2022-07-12 10:51:07,310 INFO L78 Accepts]: Start accepts. Automaton has 323 states and 435 transitions. Word has length 170 [2022-07-12 10:51:07,311 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-12 10:51:07,311 INFO L495 AbstractCegarLoop]: Abstraction has 323 states and 435 transitions. [2022-07-12 10:51:07,311 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 20 states have (on average 4.0) internal successors, (80), 18 states have internal predecessors, (80), 8 states have call successors, (24), 7 states have call predecessors, (24), 8 states have return successors, (22), 8 states have call predecessors, (22), 8 states have call successors, (22) [2022-07-12 10:51:07,311 INFO L276 IsEmpty]: Start isEmpty. Operand 323 states and 435 transitions. [2022-07-12 10:51:07,312 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 162 [2022-07-12 10:51:07,312 INFO L187 NwaCegarLoop]: Found error trace [2022-07-12 10:51:07,313 INFO L195 NwaCegarLoop]: trace histogram [5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 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] [2022-07-12 10:51:07,339 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2022-07-12 10:51:07,533 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable11 [2022-07-12 10:51:07,533 INFO L420 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-12 10:51:07,533 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-12 10:51:07,533 INFO L85 PathProgramCache]: Analyzing trace with hash 459672185, now seen corresponding path program 1 times [2022-07-12 10:51:07,533 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-12 10:51:07,533 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1219225989] [2022-07-12 10:51:07,533 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-12 10:51:07,533 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-12 10:51:07,571 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-12 10:51:07,571 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1320047900] [2022-07-12 10:51:07,571 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-12 10:51:07,571 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-12 10:51:07,572 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-12 10:51:07,573 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-12 10:51:07,574 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2022-07-12 10:51:08,043 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-12 10:51:08,052 INFO L263 TraceCheckSpWp]: Trace formula consists of 2820 conjuncts, 108 conjunts are in the unsatisfiable core [2022-07-12 10:51:08,056 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-12 10:51:08,089 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2022-07-12 10:51:09,458 WARN L855 $PredicateComparison]: unable to prove that (exists ((v_ArrVal_1501 Int)) (= |c_#memory_int| (store |c_old(#memory_int)| |c_aws_mul_size_checked_#in~r#1.base| (store (select |c_old(#memory_int)| |c_aws_mul_size_checked_#in~r#1.base|) |c_aws_mul_size_checked_#in~r#1.offset| v_ArrVal_1501)))) is different from true [2022-07-12 10:51:10,414 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-12 10:51:10,416 INFO L356 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2022-07-12 10:51:10,416 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 30 treesize of output 25 [2022-07-12 10:51:10,421 INFO L134 CoverageAnalysis]: Checked inductivity of 158 backedges. 119 proven. 5 refuted. 0 times theorem prover too weak. 34 trivial. 0 not checked. [2022-07-12 10:51:10,421 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-12 10:51:10,710 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-12 10:51:10,711 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1219225989] [2022-07-12 10:51:10,711 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-12 10:51:10,711 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1320047900] [2022-07-12 10:51:10,711 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1320047900] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-12 10:51:10,711 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-07-12 10:51:10,711 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18] total 18 [2022-07-12 10:51:10,711 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [26255121] [2022-07-12 10:51:10,711 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-07-12 10:51:10,711 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2022-07-12 10:51:10,711 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-12 10:51:10,712 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2022-07-12 10:51:10,712 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=47, Invalid=259, Unknown=4, NotChecked=32, Total=342 [2022-07-12 10:51:10,712 INFO L87 Difference]: Start difference. First operand 323 states and 435 transitions. Second operand has 18 states, 16 states have (on average 5.4375) internal successors, (87), 15 states have internal predecessors, (87), 8 states have call successors, (24), 5 states have call predecessors, (24), 6 states have return successors, (22), 7 states have call predecessors, (22), 8 states have call successors, (22) [2022-07-12 10:51:17,712 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-12 10:51:17,713 INFO L93 Difference]: Finished difference Result 615 states and 867 transitions. [2022-07-12 10:51:17,713 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2022-07-12 10:51:17,713 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 16 states have (on average 5.4375) internal successors, (87), 15 states have internal predecessors, (87), 8 states have call successors, (24), 5 states have call predecessors, (24), 6 states have return successors, (22), 7 states have call predecessors, (22), 8 states have call successors, (22) Word has length 161 [2022-07-12 10:51:17,714 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-12 10:51:17,722 INFO L225 Difference]: With dead ends: 615 [2022-07-12 10:51:17,722 INFO L226 Difference]: Without dead ends: 393 [2022-07-12 10:51:17,723 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 224 GetRequests, 198 SyntacticMatches, 1 SemanticMatches, 25 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 115 ImplicationChecksByTransitivity, 7.3s TimeCoverageRelationStatistics Valid=104, Invalid=541, Unknown=9, NotChecked=48, Total=702 [2022-07-12 10:51:17,724 INFO L413 NwaCegarLoop]: 278 mSDtfsCounter, 145 mSDsluCounter, 1553 mSDsCounter, 0 mSdLazyCounter, 2220 mSolverCounterSat, 104 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 184 SdHoareTripleChecker+Valid, 1831 SdHoareTripleChecker+Invalid, 3850 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 104 IncrementalHoareTripleChecker+Valid, 2220 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 1526 IncrementalHoareTripleChecker+Unchecked, 1.8s IncrementalHoareTripleChecker+Time [2022-07-12 10:51:17,724 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [184 Valid, 1831 Invalid, 3850 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [104 Valid, 2220 Invalid, 0 Unknown, 1526 Unchecked, 1.8s Time] [2022-07-12 10:51:17,725 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 393 states. [2022-07-12 10:51:17,736 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 393 to 345. [2022-07-12 10:51:17,736 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 345 states, 216 states have (on average 1.1527777777777777) internal successors, (249), 224 states have internal predecessors, (249), 90 states have call successors, (90), 34 states have call predecessors, (90), 38 states have return successors, (148), 86 states have call predecessors, (148), 87 states have call successors, (148) [2022-07-12 10:51:17,738 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 345 states to 345 states and 487 transitions. [2022-07-12 10:51:17,738 INFO L78 Accepts]: Start accepts. Automaton has 345 states and 487 transitions. Word has length 161 [2022-07-12 10:51:17,738 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-12 10:51:17,738 INFO L495 AbstractCegarLoop]: Abstraction has 345 states and 487 transitions. [2022-07-12 10:51:17,739 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 18 states, 16 states have (on average 5.4375) internal successors, (87), 15 states have internal predecessors, (87), 8 states have call successors, (24), 5 states have call predecessors, (24), 6 states have return successors, (22), 7 states have call predecessors, (22), 8 states have call successors, (22) [2022-07-12 10:51:17,739 INFO L276 IsEmpty]: Start isEmpty. Operand 345 states and 487 transitions. [2022-07-12 10:51:17,740 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 162 [2022-07-12 10:51:17,740 INFO L187 NwaCegarLoop]: Found error trace [2022-07-12 10:51:17,741 INFO L195 NwaCegarLoop]: trace histogram [5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 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] [2022-07-12 10:51:17,761 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Ended with exit code 0 [2022-07-12 10:51:17,955 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2022-07-12 10:51:17,955 INFO L420 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-12 10:51:17,956 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-12 10:51:17,956 INFO L85 PathProgramCache]: Analyzing trace with hash -422116935, now seen corresponding path program 1 times [2022-07-12 10:51:17,956 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-12 10:51:17,956 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1541922992] [2022-07-12 10:51:17,956 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-12 10:51:17,956 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-12 10:51:17,993 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-12 10:51:17,994 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2044020706] [2022-07-12 10:51:17,994 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-12 10:51:17,994 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-12 10:51:17,994 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-12 10:51:17,995 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-12 10:51:17,996 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2022-07-12 10:51:18,427 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-12 10:51:18,438 INFO L263 TraceCheckSpWp]: Trace formula consists of 2820 conjuncts, 78 conjunts are in the unsatisfiable core [2022-07-12 10:51:18,442 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-12 10:51:20,747 WARN L855 $PredicateComparison]: unable to prove that (exists ((|aws_mul_size_checked_aws_mul_u64_checked_~r#1.base| Int) (v_ArrVal_1640 Int) (v_ArrVal_1641 Int)) (and (= (store |c_old(#memory_$Pointer$.offset)| |aws_mul_size_checked_aws_mul_u64_checked_~r#1.base| (store (select |c_old(#memory_$Pointer$.offset)| |aws_mul_size_checked_aws_mul_u64_checked_~r#1.base|) |c_aws_mul_size_checked_#in~r#1.offset| v_ArrVal_1640)) |c_#memory_$Pointer$.offset|) (= |c_#memory_$Pointer$.base| (store |c_old(#memory_$Pointer$.base)| |aws_mul_size_checked_aws_mul_u64_checked_~r#1.base| (store (select |c_old(#memory_$Pointer$.base)| |aws_mul_size_checked_aws_mul_u64_checked_~r#1.base|) |c_aws_mul_size_checked_#in~r#1.offset| v_ArrVal_1641))))) is different from true