./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/aws-c-common/aws_array_list_clean_up_harness.i --full-output --architecture 64bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version eb692b52 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_clean_up_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 5ba879a31f48d1f1f7d1dc7f928910bfb7ed0629fadb04ed483f94e60bfd5ef0 --- Real Ultimate output --- This is Ultimate 0.2.2-?-eb692b5 [2022-07-19 21:49:57,836 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-07-19 21:49:57,838 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-07-19 21:49:57,864 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-07-19 21:49:57,869 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-07-19 21:49:57,870 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-07-19 21:49:57,871 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-07-19 21:49:57,872 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-07-19 21:49:57,873 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-07-19 21:49:57,873 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-07-19 21:49:57,874 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-07-19 21:49:57,875 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-07-19 21:49:57,875 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-07-19 21:49:57,876 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-07-19 21:49:57,877 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-07-19 21:49:57,879 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-07-19 21:49:57,879 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-07-19 21:49:57,880 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-07-19 21:49:57,881 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-07-19 21:49:57,882 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-07-19 21:49:57,883 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-07-19 21:49:57,884 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-07-19 21:49:57,884 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-07-19 21:49:57,885 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-07-19 21:49:57,886 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-07-19 21:49:57,888 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-07-19 21:49:57,888 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-07-19 21:49:57,888 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-07-19 21:49:57,889 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-07-19 21:49:57,889 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-07-19 21:49:57,890 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-07-19 21:49:57,890 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-07-19 21:49:57,890 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-07-19 21:49:57,891 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-07-19 21:49:57,891 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-07-19 21:49:57,892 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-07-19 21:49:57,892 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-07-19 21:49:57,893 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-07-19 21:49:57,893 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-07-19 21:49:57,893 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-07-19 21:49:57,894 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-07-19 21:49:57,896 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-07-19 21:49:57,897 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-64bit-Automizer_Default.epf [2022-07-19 21:49:57,914 INFO L113 SettingsManager]: Loading preferences was successful [2022-07-19 21:49:57,914 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-07-19 21:49:57,914 INFO L136 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2022-07-19 21:49:57,914 INFO L138 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2022-07-19 21:49:57,915 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2022-07-19 21:49:57,915 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2022-07-19 21:49:57,916 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2022-07-19 21:49:57,916 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2022-07-19 21:49:57,916 INFO L138 SettingsManager]: * Use SBE=true [2022-07-19 21:49:57,917 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-07-19 21:49:57,917 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-07-19 21:49:57,917 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-07-19 21:49:57,917 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-07-19 21:49:57,917 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-07-19 21:49:57,917 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-07-19 21:49:57,918 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-07-19 21:49:57,918 INFO L138 SettingsManager]: * Use constant arrays=true [2022-07-19 21:49:57,918 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-07-19 21:49:57,918 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-07-19 21:49:57,918 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-07-19 21:49:57,918 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-07-19 21:49:57,919 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-07-19 21:49:57,919 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-07-19 21:49:57,919 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2022-07-19 21:49:57,919 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2022-07-19 21:49:57,919 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2022-07-19 21:49:57,919 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2022-07-19 21:49:57,920 INFO L138 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2022-07-19 21:49:57,920 INFO L138 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2022-07-19 21:49:57,920 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-07-19 21:49:57,920 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 -> 5ba879a31f48d1f1f7d1dc7f928910bfb7ed0629fadb04ed483f94e60bfd5ef0 [2022-07-19 21:49:58,112 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-07-19 21:49:58,129 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-07-19 21:49:58,132 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-07-19 21:49:58,132 INFO L271 PluginConnector]: Initializing CDTParser... [2022-07-19 21:49:58,133 INFO L275 PluginConnector]: CDTParser initialized [2022-07-19 21:49:58,134 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_clean_up_harness.i [2022-07-19 21:49:58,175 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/3de41929e/d9f4951e7365460c869dd17ccb32e0ef/FLAG3ae7039f0 [2022-07-19 21:49:58,754 INFO L306 CDTParser]: Found 1 translation units. [2022-07-19 21:49:58,755 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/aws-c-common/aws_array_list_clean_up_harness.i [2022-07-19 21:49:58,778 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/3de41929e/d9f4951e7365460c869dd17ccb32e0ef/FLAG3ae7039f0 [2022-07-19 21:49:59,206 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/3de41929e/d9f4951e7365460c869dd17ccb32e0ef [2022-07-19 21:49:59,208 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-07-19 21:49:59,209 INFO L131 ToolchainWalker]: Walking toolchain with 6 elements. [2022-07-19 21:49:59,210 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-07-19 21:49:59,210 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-07-19 21:49:59,214 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-07-19 21:49:59,215 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 19.07 09:49:59" (1/1) ... [2022-07-19 21:49:59,216 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@1d430c61 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.07 09:49:59, skipping insertion in model container [2022-07-19 21:49:59,216 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 19.07 09:49:59" (1/1) ... [2022-07-19 21:49:59,220 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-07-19 21:49:59,270 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-07-19 21:49:59,450 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_clean_up_harness.i[4497,4510] [2022-07-19 21:49:59,455 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_clean_up_harness.i[4557,4570] [2022-07-19 21:49:59,852 WARN L611 FunctionHandler]: implicit declaration of function __builtin_va_copy [2022-07-19 21:49:59,913 WARN L1550 CHandler]: Possible shadowing of function index [2022-07-19 21:49:59,914 WARN L1550 CHandler]: Possible shadowing of function index [2022-07-19 21:49:59,914 WARN L1550 CHandler]: Possible shadowing of function index [2022-07-19 21:49:59,915 WARN L1550 CHandler]: Possible shadowing of function index [2022-07-19 21:49:59,915 WARN L1550 CHandler]: Possible shadowing of function index [2022-07-19 21:49:59,921 WARN L1550 CHandler]: Possible shadowing of function index [2022-07-19 21:49:59,921 WARN L1550 CHandler]: Possible shadowing of function index [2022-07-19 21:49:59,922 WARN L1550 CHandler]: Possible shadowing of function index [2022-07-19 21:49:59,922 WARN L1550 CHandler]: Possible shadowing of function index [2022-07-19 21:49:59,923 WARN L1550 CHandler]: Possible shadowing of function index [2022-07-19 21:49:59,924 WARN L1550 CHandler]: Possible shadowing of function index [2022-07-19 21:49:59,924 WARN L1550 CHandler]: Possible shadowing of function index [2022-07-19 21:49:59,924 WARN L1550 CHandler]: Possible shadowing of function index [2022-07-19 21:50:00,094 WARN L611 FunctionHandler]: implicit declaration of function __atomic_load_n [2022-07-19 21:50:00,097 WARN L611 FunctionHandler]: implicit declaration of function __atomic_store_n [2022-07-19 21:50:00,098 WARN L611 FunctionHandler]: implicit declaration of function __atomic_exchange_n [2022-07-19 21:50:00,100 WARN L611 FunctionHandler]: implicit declaration of function __atomic_compare_exchange_n [2022-07-19 21:50:00,101 WARN L611 FunctionHandler]: implicit declaration of function __atomic_fetch_add [2022-07-19 21:50:00,101 WARN L611 FunctionHandler]: implicit declaration of function __atomic_fetch_sub [2022-07-19 21:50:00,101 WARN L611 FunctionHandler]: implicit declaration of function __atomic_fetch_or [2022-07-19 21:50:00,103 WARN L611 FunctionHandler]: implicit declaration of function __atomic_fetch_and [2022-07-19 21:50:00,105 WARN L611 FunctionHandler]: implicit declaration of function __atomic_fetch_xor [2022-07-19 21:50:00,105 WARN L611 FunctionHandler]: implicit declaration of function __atomic_thread_fence [2022-07-19 21:50:00,180 WARN L1550 CHandler]: Possible shadowing of function index [2022-07-19 21:50:00,184 WARN L1550 CHandler]: Possible shadowing of function index [2022-07-19 21:50:00,208 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-07-19 21:50:00,225 INFO L203 MainTranslator]: Completed pre-run [2022-07-19 21:50:00,242 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_clean_up_harness.i[4497,4510] [2022-07-19 21:50:00,243 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_clean_up_harness.i[4557,4570] [2022-07-19 21:50:00,275 WARN L611 FunctionHandler]: implicit declaration of function __builtin_va_copy [2022-07-19 21:50:00,292 WARN L1550 CHandler]: Possible shadowing of function index [2022-07-19 21:50:00,294 WARN L1550 CHandler]: Possible shadowing of function index [2022-07-19 21:50:00,294 WARN L1550 CHandler]: Possible shadowing of function index [2022-07-19 21:50:00,294 WARN L1550 CHandler]: Possible shadowing of function index [2022-07-19 21:50:00,295 WARN L1550 CHandler]: Possible shadowing of function index [2022-07-19 21:50:00,299 WARN L1550 CHandler]: Possible shadowing of function index [2022-07-19 21:50:00,301 WARN L1550 CHandler]: Possible shadowing of function index [2022-07-19 21:50:00,302 WARN L1550 CHandler]: Possible shadowing of function index [2022-07-19 21:50:00,302 WARN L1550 CHandler]: Possible shadowing of function index [2022-07-19 21:50:00,302 WARN L1550 CHandler]: Possible shadowing of function index [2022-07-19 21:50:00,303 WARN L1550 CHandler]: Possible shadowing of function index [2022-07-19 21:50:00,303 WARN L1550 CHandler]: Possible shadowing of function index [2022-07-19 21:50:00,303 WARN L1550 CHandler]: Possible shadowing of function index [2022-07-19 21:50:00,318 WARN L611 FunctionHandler]: implicit declaration of function __atomic_load_n [2022-07-19 21:50:00,319 WARN L611 FunctionHandler]: implicit declaration of function __atomic_store_n [2022-07-19 21:50:00,319 WARN L611 FunctionHandler]: implicit declaration of function __atomic_exchange_n [2022-07-19 21:50:00,320 WARN L611 FunctionHandler]: implicit declaration of function __atomic_compare_exchange_n [2022-07-19 21:50:00,320 WARN L611 FunctionHandler]: implicit declaration of function __atomic_fetch_add [2022-07-19 21:50:00,320 WARN L611 FunctionHandler]: implicit declaration of function __atomic_fetch_sub [2022-07-19 21:50:00,321 WARN L611 FunctionHandler]: implicit declaration of function __atomic_fetch_or [2022-07-19 21:50:00,321 WARN L611 FunctionHandler]: implicit declaration of function __atomic_fetch_and [2022-07-19 21:50:00,321 WARN L611 FunctionHandler]: implicit declaration of function __atomic_fetch_xor [2022-07-19 21:50:00,321 WARN L611 FunctionHandler]: implicit declaration of function __atomic_thread_fence [2022-07-19 21:50:00,332 WARN L1550 CHandler]: Possible shadowing of function index [2022-07-19 21:50:00,346 WARN L1550 CHandler]: Possible shadowing of function index [2022-07-19 21:50:00,366 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-07-19 21:50:00,512 INFO L208 MainTranslator]: Completed translation [2022-07-19 21:50:00,513 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.07 09:50:00 WrapperNode [2022-07-19 21:50:00,513 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-07-19 21:50:00,514 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2022-07-19 21:50:00,514 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2022-07-19 21:50:00,514 INFO L275 PluginConnector]: Boogie Procedure Inliner initialized [2022-07-19 21:50:00,519 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.07 09:50:00" (1/1) ... [2022-07-19 21:50:00,581 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.07 09:50:00" (1/1) ... [2022-07-19 21:50:00,623 INFO L137 Inliner]: procedures = 690, calls = 1553, calls flagged for inlining = 48, calls inlined = 7, statements flattened = 577 [2022-07-19 21:50:00,624 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2022-07-19 21:50:00,624 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-07-19 21:50:00,624 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-07-19 21:50:00,624 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-07-19 21:50:00,630 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.07 09:50:00" (1/1) ... [2022-07-19 21:50:00,630 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.07 09:50:00" (1/1) ... [2022-07-19 21:50:00,634 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.07 09:50:00" (1/1) ... [2022-07-19 21:50:00,634 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.07 09:50:00" (1/1) ... [2022-07-19 21:50:00,649 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.07 09:50:00" (1/1) ... [2022-07-19 21:50:00,652 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.07 09:50:00" (1/1) ... [2022-07-19 21:50:00,656 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.07 09:50:00" (1/1) ... [2022-07-19 21:50:00,661 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-07-19 21:50:00,661 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-07-19 21:50:00,661 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-07-19 21:50:00,662 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-07-19 21:50:00,662 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.07 09:50:00" (1/1) ... [2022-07-19 21:50:00,667 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-07-19 21:50:00,675 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-19 21:50:00,684 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-19 21:50:00,686 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-19 21:50:00,709 INFO L130 BoogieDeclarations]: Found specification of procedure aws_is_mem_zeroed [2022-07-19 21:50:00,709 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_is_mem_zeroed [2022-07-19 21:50:00,709 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-07-19 21:50:00,709 INFO L130 BoogieDeclarations]: Found specification of procedure aws_array_list_is_bounded [2022-07-19 21:50:00,709 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_array_list_is_bounded [2022-07-19 21:50:00,709 INFO L130 BoogieDeclarations]: Found specification of procedure aws_array_list_is_valid [2022-07-19 21:50:00,709 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_array_list_is_valid [2022-07-19 21:50:00,710 INFO L130 BoogieDeclarations]: Found specification of procedure nondet_bool [2022-07-19 21:50:00,710 INFO L138 BoogieDeclarations]: Found implementation of procedure nondet_bool [2022-07-19 21:50:00,710 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-07-19 21:50:00,710 INFO L130 BoogieDeclarations]: Found specification of procedure aws_raise_error [2022-07-19 21:50:00,710 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_raise_error [2022-07-19 21:50:00,710 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-07-19 21:50:00,710 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-07-19 21:50:00,710 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnHeap [2022-07-19 21:50:00,711 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-07-19 21:50:00,711 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$ [2022-07-19 21:50:00,711 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-07-19 21:50:00,711 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-07-19 21:50:00,711 INFO L130 BoogieDeclarations]: Found specification of procedure bounded_malloc [2022-07-19 21:50:00,711 INFO L138 BoogieDeclarations]: Found implementation of procedure bounded_malloc [2022-07-19 21:50:00,723 INFO L130 BoogieDeclarations]: Found specification of procedure aws_mul_size_checked [2022-07-19 21:50:00,724 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_mul_size_checked [2022-07-19 21:50:00,724 INFO L130 BoogieDeclarations]: Found specification of procedure aws_mem_release [2022-07-19 21:50:00,724 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_mem_release [2022-07-19 21:50:00,724 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.C_memset [2022-07-19 21:50:00,724 INFO L138 BoogieDeclarations]: Found implementation of procedure #Ultimate.C_memset [2022-07-19 21:50:00,724 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-07-19 21:50:00,725 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-07-19 21:50:00,725 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2022-07-19 21:50:00,725 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$ [2022-07-19 21:50:00,725 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$ [2022-07-19 21:50:00,725 INFO L130 BoogieDeclarations]: Found specification of procedure can_fail_allocator [2022-07-19 21:50:00,725 INFO L138 BoogieDeclarations]: Found implementation of procedure can_fail_allocator [2022-07-19 21:50:00,725 INFO L130 BoogieDeclarations]: Found specification of procedure __CPROVER_overflow_mult [2022-07-19 21:50:00,725 INFO L138 BoogieDeclarations]: Found implementation of procedure __CPROVER_overflow_mult [2022-07-19 21:50:00,726 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-07-19 21:50:00,726 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-07-19 21:50:00,874 INFO L234 CfgBuilder]: Building ICFG [2022-07-19 21:50:00,875 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-07-19 21:50:01,429 INFO L275 CfgBuilder]: Performing block encoding [2022-07-19 21:50:01,437 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-07-19 21:50:01,438 INFO L299 CfgBuilder]: Removed 3 assume(true) statements. [2022-07-19 21:50:01,440 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 19.07 09:50:01 BoogieIcfgContainer [2022-07-19 21:50:01,440 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-07-19 21:50:01,443 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-07-19 21:50:01,443 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-07-19 21:50:01,445 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-07-19 21:50:01,446 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 19.07 09:49:59" (1/3) ... [2022-07-19 21:50:01,446 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6cd03e03 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 19.07 09:50:01, skipping insertion in model container [2022-07-19 21:50:01,446 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.07 09:50:00" (2/3) ... [2022-07-19 21:50:01,447 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6cd03e03 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 19.07 09:50:01, skipping insertion in model container [2022-07-19 21:50:01,447 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 19.07 09:50:01" (3/3) ... [2022-07-19 21:50:01,448 INFO L111 eAbstractionObserver]: Analyzing ICFG aws_array_list_clean_up_harness.i [2022-07-19 21:50:01,462 INFO L201 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2022-07-19 21:50:01,462 INFO L160 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-07-19 21:50:01,519 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-07-19 21:50:01,526 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@411fd6ab, mLbeIndependenceSettings=de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings@5fc56836 [2022-07-19 21:50:01,526 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-07-19 21:50:01,530 INFO L276 IsEmpty]: Start isEmpty. Operand has 114 states, 78 states have (on average 1.2564102564102564) internal successors, (98), 78 states have internal predecessors, (98), 22 states have call successors, (22), 13 states have call predecessors, (22), 13 states have return successors, (22), 22 states have call predecessors, (22), 22 states have call successors, (22) [2022-07-19 21:50:01,539 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 66 [2022-07-19 21:50:01,540 INFO L187 NwaCegarLoop]: Found error trace [2022-07-19 21:50:01,540 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 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] [2022-07-19 21:50:01,541 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-19 21:50:01,546 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-19 21:50:01,548 INFO L85 PathProgramCache]: Analyzing trace with hash -1460968734, now seen corresponding path program 1 times [2022-07-19 21:50:01,554 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-19 21:50:01,554 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1298368530] [2022-07-19 21:50:01,554 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 21:50:01,556 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-19 21:50:01,835 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 21:50:01,951 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2022-07-19 21:50:01,955 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 21:50:01,968 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-07-19 21:50:01,977 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 21:50:01,986 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2022-07-19 21:50:01,989 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 21:50:01,996 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 20 [2022-07-19 21:50:01,997 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 21:50:02,018 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 26 [2022-07-19 21:50:02,023 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 21:50:02,032 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 31 [2022-07-19 21:50:02,033 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 21:50:02,038 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 37 [2022-07-19 21:50:02,041 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 21:50:02,056 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 45 [2022-07-19 21:50:02,058 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 21:50:02,063 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 55 [2022-07-19 21:50:02,065 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 21:50:02,072 INFO L134 CoverageAnalysis]: Checked inductivity of 29 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 29 trivial. 0 not checked. [2022-07-19 21:50:02,072 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-19 21:50:02,073 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1298368530] [2022-07-19 21:50:02,073 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1298368530] provided 1 perfect and 0 imperfect interpolant sequences [2022-07-19 21:50:02,074 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-07-19 21:50:02,074 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-07-19 21:50:02,075 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [936551224] [2022-07-19 21:50:02,076 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-19 21:50:02,081 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-07-19 21:50:02,082 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-19 21:50:02,102 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-07-19 21:50:02,103 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-07-19 21:50:02,104 INFO L87 Difference]: Start difference. First operand has 114 states, 78 states have (on average 1.2564102564102564) internal successors, (98), 78 states have internal predecessors, (98), 22 states have call successors, (22), 13 states have call predecessors, (22), 13 states have return successors, (22), 22 states have call predecessors, (22), 22 states have call successors, (22) Second operand has 3 states, 3 states have (on average 11.0) internal successors, (33), 2 states have internal predecessors, (33), 2 states have call successors, (10), 3 states have call predecessors, (10), 2 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) [2022-07-19 21:50:02,312 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-19 21:50:02,312 INFO L93 Difference]: Finished difference Result 228 states and 297 transitions. [2022-07-19 21:50:02,313 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-07-19 21:50:02,315 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 11.0) internal successors, (33), 2 states have internal predecessors, (33), 2 states have call successors, (10), 3 states have call predecessors, (10), 2 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) Word has length 65 [2022-07-19 21:50:02,315 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-19 21:50:02,325 INFO L225 Difference]: With dead ends: 228 [2022-07-19 21:50:02,326 INFO L226 Difference]: Without dead ends: 114 [2022-07-19 21:50:02,329 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 26 GetRequests, 25 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-07-19 21:50:02,333 INFO L413 NwaCegarLoop]: 128 mSDtfsCounter, 35 mSDsluCounter, 34 mSDsCounter, 0 mSdLazyCounter, 59 mSolverCounterSat, 22 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 38 SdHoareTripleChecker+Valid, 162 SdHoareTripleChecker+Invalid, 81 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 22 IncrementalHoareTripleChecker+Valid, 59 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-07-19 21:50:02,337 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [38 Valid, 162 Invalid, 81 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [22 Valid, 59 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-07-19 21:50:02,349 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 114 states. [2022-07-19 21:50:02,378 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 114 to 107. [2022-07-19 21:50:02,379 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 107 states, 72 states have (on average 1.2083333333333333) internal successors, (87), 72 states have internal predecessors, (87), 22 states have call successors, (22), 13 states have call predecessors, (22), 12 states have return successors, (21), 21 states have call predecessors, (21), 21 states have call successors, (21) [2022-07-19 21:50:02,385 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 107 states to 107 states and 130 transitions. [2022-07-19 21:50:02,386 INFO L78 Accepts]: Start accepts. Automaton has 107 states and 130 transitions. Word has length 65 [2022-07-19 21:50:02,387 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-19 21:50:02,387 INFO L495 AbstractCegarLoop]: Abstraction has 107 states and 130 transitions. [2022-07-19 21:50:02,387 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 11.0) internal successors, (33), 2 states have internal predecessors, (33), 2 states have call successors, (10), 3 states have call predecessors, (10), 2 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) [2022-07-19 21:50:02,387 INFO L276 IsEmpty]: Start isEmpty. Operand 107 states and 130 transitions. [2022-07-19 21:50:02,394 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 72 [2022-07-19 21:50:02,395 INFO L187 NwaCegarLoop]: Found error trace [2022-07-19 21:50:02,395 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 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] [2022-07-19 21:50:02,395 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-07-19 21:50:02,395 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-19 21:50:02,396 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-19 21:50:02,396 INFO L85 PathProgramCache]: Analyzing trace with hash -1894775411, now seen corresponding path program 1 times [2022-07-19 21:50:02,396 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-19 21:50:02,396 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1842388996] [2022-07-19 21:50:02,396 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 21:50:02,396 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-19 21:50:02,465 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 21:50:02,538 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2022-07-19 21:50:02,542 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 21:50:02,550 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-07-19 21:50:02,552 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 21:50:02,557 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2022-07-19 21:50:02,563 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 21:50:02,570 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 20 [2022-07-19 21:50:02,572 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 21:50:02,591 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 26 [2022-07-19 21:50:02,597 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 21:50:02,616 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 31 [2022-07-19 21:50:02,618 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 21:50:02,623 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 37 [2022-07-19 21:50:02,627 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 21:50:02,635 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 45 [2022-07-19 21:50:02,639 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 21:50:02,658 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 53 [2022-07-19 21:50:02,661 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 21:50:02,667 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 61 [2022-07-19 21:50:02,668 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 21:50:02,675 INFO L134 CoverageAnalysis]: Checked inductivity of 29 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 29 trivial. 0 not checked. [2022-07-19 21:50:02,676 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-19 21:50:02,676 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1842388996] [2022-07-19 21:50:02,676 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1842388996] provided 1 perfect and 0 imperfect interpolant sequences [2022-07-19 21:50:02,676 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-07-19 21:50:02,676 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2022-07-19 21:50:02,676 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1676541327] [2022-07-19 21:50:02,676 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-19 21:50:02,678 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2022-07-19 21:50:02,678 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-19 21:50:02,678 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2022-07-19 21:50:02,678 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=12, Invalid=30, Unknown=0, NotChecked=0, Total=42 [2022-07-19 21:50:02,678 INFO L87 Difference]: Start difference. First operand 107 states and 130 transitions. Second operand has 7 states, 7 states have (on average 5.285714285714286) internal successors, (37), 5 states have internal predecessors, (37), 2 states have call successors, (11), 4 states have call predecessors, (11), 2 states have return successors, (10), 2 states have call predecessors, (10), 2 states have call successors, (10) [2022-07-19 21:50:03,062 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-19 21:50:03,062 INFO L93 Difference]: Finished difference Result 199 states and 243 transitions. [2022-07-19 21:50:03,063 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-07-19 21:50:03,063 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 5.285714285714286) internal successors, (37), 5 states have internal predecessors, (37), 2 states have call successors, (11), 4 states have call predecessors, (11), 2 states have return successors, (10), 2 states have call predecessors, (10), 2 states have call successors, (10) Word has length 71 [2022-07-19 21:50:03,063 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-19 21:50:03,064 INFO L225 Difference]: With dead ends: 199 [2022-07-19 21:50:03,064 INFO L226 Difference]: Without dead ends: 126 [2022-07-19 21:50:03,065 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 27 GetRequests, 19 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=30, Invalid=60, Unknown=0, NotChecked=0, Total=90 [2022-07-19 21:50:03,066 INFO L413 NwaCegarLoop]: 115 mSDtfsCounter, 88 mSDsluCounter, 207 mSDsCounter, 0 mSdLazyCounter, 347 mSolverCounterSat, 30 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 106 SdHoareTripleChecker+Valid, 322 SdHoareTripleChecker+Invalid, 377 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 30 IncrementalHoareTripleChecker+Valid, 347 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-07-19 21:50:03,066 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [106 Valid, 322 Invalid, 377 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [30 Valid, 347 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-07-19 21:50:03,067 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 126 states. [2022-07-19 21:50:03,074 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 126 to 109. [2022-07-19 21:50:03,074 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 109 states, 73 states have (on average 1.2054794520547945) internal successors, (88), 74 states have internal predecessors, (88), 22 states have call successors, (22), 13 states have call predecessors, (22), 13 states have return successors, (22), 21 states have call predecessors, (22), 21 states have call successors, (22) [2022-07-19 21:50:03,075 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 109 states to 109 states and 132 transitions. [2022-07-19 21:50:03,075 INFO L78 Accepts]: Start accepts. Automaton has 109 states and 132 transitions. Word has length 71 [2022-07-19 21:50:03,075 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-19 21:50:03,075 INFO L495 AbstractCegarLoop]: Abstraction has 109 states and 132 transitions. [2022-07-19 21:50:03,076 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 5.285714285714286) internal successors, (37), 5 states have internal predecessors, (37), 2 states have call successors, (11), 4 states have call predecessors, (11), 2 states have return successors, (10), 2 states have call predecessors, (10), 2 states have call successors, (10) [2022-07-19 21:50:03,076 INFO L276 IsEmpty]: Start isEmpty. Operand 109 states and 132 transitions. [2022-07-19 21:50:03,076 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 87 [2022-07-19 21:50:03,077 INFO L187 NwaCegarLoop]: Found error trace [2022-07-19 21:50:03,077 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 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-19 21:50:03,077 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2022-07-19 21:50:03,077 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-19 21:50:03,078 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-19 21:50:03,078 INFO L85 PathProgramCache]: Analyzing trace with hash -1692678563, now seen corresponding path program 1 times [2022-07-19 21:50:03,078 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-19 21:50:03,078 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [666929746] [2022-07-19 21:50:03,078 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 21:50:03,078 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-19 21:50:03,159 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-19 21:50:03,160 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1040194328] [2022-07-19 21:50:03,160 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 21:50:03,160 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 21:50:03,160 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-19 21:50:03,162 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-19 21:50:03,163 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-19 21:50:03,476 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 21:50:03,485 INFO L263 TraceCheckSpWp]: Trace formula consists of 2123 conjuncts, 15 conjunts are in the unsatisfiable core [2022-07-19 21:50:03,491 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-19 21:50:03,563 INFO L134 CoverageAnalysis]: Checked inductivity of 29 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 29 trivial. 0 not checked. [2022-07-19 21:50:03,563 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-07-19 21:50:03,563 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-19 21:50:03,564 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [666929746] [2022-07-19 21:50:03,564 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-19 21:50:03,564 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1040194328] [2022-07-19 21:50:03,564 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1040194328] provided 1 perfect and 0 imperfect interpolant sequences [2022-07-19 21:50:03,564 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-07-19 21:50:03,564 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2022-07-19 21:50:03,564 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1567634324] [2022-07-19 21:50:03,565 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-19 21:50:03,565 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2022-07-19 21:50:03,565 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-19 21:50:03,566 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2022-07-19 21:50:03,566 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=43, Unknown=0, NotChecked=0, Total=56 [2022-07-19 21:50:03,566 INFO L87 Difference]: Start difference. First operand 109 states and 132 transitions. Second operand has 8 states, 7 states have (on average 6.857142857142857) internal successors, (48), 5 states have internal predecessors, (48), 2 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (12), 3 states have call predecessors, (12), 1 states have call successors, (12) [2022-07-19 21:50:03,614 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-19 21:50:03,614 INFO L93 Difference]: Finished difference Result 190 states and 229 transitions. [2022-07-19 21:50:03,615 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-07-19 21:50:03,615 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 7 states have (on average 6.857142857142857) internal successors, (48), 5 states have internal predecessors, (48), 2 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (12), 3 states have call predecessors, (12), 1 states have call successors, (12) Word has length 86 [2022-07-19 21:50:03,616 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-19 21:50:03,616 INFO L225 Difference]: With dead ends: 190 [2022-07-19 21:50:03,617 INFO L226 Difference]: Without dead ends: 117 [2022-07-19 21:50:03,617 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 88 GetRequests, 80 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=21, Invalid=69, Unknown=0, NotChecked=0, Total=90 [2022-07-19 21:50:03,618 INFO L413 NwaCegarLoop]: 129 mSDtfsCounter, 4 mSDsluCounter, 748 mSDsCounter, 0 mSdLazyCounter, 42 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 877 SdHoareTripleChecker+Invalid, 46 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 42 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-07-19 21:50:03,618 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [5 Valid, 877 Invalid, 46 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 42 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-07-19 21:50:03,619 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 117 states. [2022-07-19 21:50:03,624 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 117 to 113. [2022-07-19 21:50:03,624 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 113 states, 76 states have (on average 1.1973684210526316) internal successors, (91), 77 states have internal predecessors, (91), 22 states have call successors, (22), 13 states have call predecessors, (22), 14 states have return successors, (23), 22 states have call predecessors, (23), 21 states have call successors, (23) [2022-07-19 21:50:03,625 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 113 states to 113 states and 136 transitions. [2022-07-19 21:50:03,625 INFO L78 Accepts]: Start accepts. Automaton has 113 states and 136 transitions. Word has length 86 [2022-07-19 21:50:03,626 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-19 21:50:03,626 INFO L495 AbstractCegarLoop]: Abstraction has 113 states and 136 transitions. [2022-07-19 21:50:03,626 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 7 states have (on average 6.857142857142857) internal successors, (48), 5 states have internal predecessors, (48), 2 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (12), 3 states have call predecessors, (12), 1 states have call successors, (12) [2022-07-19 21:50:03,626 INFO L276 IsEmpty]: Start isEmpty. Operand 113 states and 136 transitions. [2022-07-19 21:50:03,627 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 87 [2022-07-19 21:50:03,627 INFO L187 NwaCegarLoop]: Found error trace [2022-07-19 21:50:03,627 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 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-19 21:50:03,651 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-19 21:50:03,846 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 21:50:03,847 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-19 21:50:03,847 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-19 21:50:03,847 INFO L85 PathProgramCache]: Analyzing trace with hash -124616364, now seen corresponding path program 1 times [2022-07-19 21:50:03,847 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-19 21:50:03,847 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1104730938] [2022-07-19 21:50:03,847 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 21:50:03,847 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-19 21:50:03,911 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-19 21:50:03,927 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2056749781] [2022-07-19 21:50:03,927 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 21:50:03,927 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 21:50:03,928 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-19 21:50:03,929 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-19 21:50:03,930 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-19 21:50:04,212 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 21:50:04,219 INFO L263 TraceCheckSpWp]: Trace formula consists of 2126 conjuncts, 14 conjunts are in the unsatisfiable core [2022-07-19 21:50:04,222 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-19 21:50:04,242 INFO L134 CoverageAnalysis]: Checked inductivity of 28 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-07-19 21:50:04,242 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-07-19 21:50:04,242 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-19 21:50:04,242 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1104730938] [2022-07-19 21:50:04,242 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-19 21:50:04,242 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2056749781] [2022-07-19 21:50:04,242 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2056749781] provided 1 perfect and 0 imperfect interpolant sequences [2022-07-19 21:50:04,242 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-07-19 21:50:04,242 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2022-07-19 21:50:04,242 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [682256906] [2022-07-19 21:50:04,242 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-19 21:50:04,243 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2022-07-19 21:50:04,243 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-19 21:50:04,243 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2022-07-19 21:50:04,243 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2022-07-19 21:50:04,243 INFO L87 Difference]: Start difference. First operand 113 states and 136 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, (13), 2 states have call predecessors, (13), 3 states have return successors, (12), 2 states have call predecessors, (12), 2 states have call successors, (12) [2022-07-19 21:50:04,258 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-19 21:50:04,258 INFO L93 Difference]: Finished difference Result 134 states and 158 transitions. [2022-07-19 21:50:04,258 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2022-07-19 21:50:04,259 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, (13), 2 states have call predecessors, (13), 3 states have return successors, (12), 2 states have call predecessors, (12), 2 states have call successors, (12) Word has length 86 [2022-07-19 21:50:04,259 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-19 21:50:04,260 INFO L225 Difference]: With dead ends: 134 [2022-07-19 21:50:04,260 INFO L226 Difference]: Without dead ends: 114 [2022-07-19 21:50:04,260 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 86 GetRequests, 83 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-19 21:50:04,261 INFO L413 NwaCegarLoop]: 128 mSDtfsCounter, 2 mSDsluCounter, 254 mSDsCounter, 0 mSdLazyCounter, 7 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 382 SdHoareTripleChecker+Invalid, 7 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 7 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-07-19 21:50:04,261 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [2 Valid, 382 Invalid, 7 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 7 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-07-19 21:50:04,261 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 114 states. [2022-07-19 21:50:04,265 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 114 to 114. [2022-07-19 21:50:04,266 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 114 states, 77 states have (on average 1.1948051948051948) internal successors, (92), 78 states have internal predecessors, (92), 22 states have call successors, (22), 13 states have call predecessors, (22), 14 states have return successors, (23), 22 states have call predecessors, (23), 21 states have call successors, (23) [2022-07-19 21:50:04,266 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 114 states to 114 states and 137 transitions. [2022-07-19 21:50:04,266 INFO L78 Accepts]: Start accepts. Automaton has 114 states and 137 transitions. Word has length 86 [2022-07-19 21:50:04,267 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-19 21:50:04,267 INFO L495 AbstractCegarLoop]: Abstraction has 114 states and 137 transitions. [2022-07-19 21:50:04,267 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, (13), 2 states have call predecessors, (13), 3 states have return successors, (12), 2 states have call predecessors, (12), 2 states have call successors, (12) [2022-07-19 21:50:04,267 INFO L276 IsEmpty]: Start isEmpty. Operand 114 states and 137 transitions. [2022-07-19 21:50:04,268 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 88 [2022-07-19 21:50:04,268 INFO L187 NwaCegarLoop]: Found error trace [2022-07-19 21:50:04,268 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 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-19 21:50:04,287 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-19 21:50:04,479 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,SelfDestructingSolverStorable3 [2022-07-19 21:50:04,479 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-19 21:50:04,480 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-19 21:50:04,480 INFO L85 PathProgramCache]: Analyzing trace with hash -117447722, now seen corresponding path program 1 times [2022-07-19 21:50:04,480 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-19 21:50:04,480 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1894005716] [2022-07-19 21:50:04,480 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 21:50:04,480 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-19 21:50:04,521 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-19 21:50:04,521 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1712087732] [2022-07-19 21:50:04,521 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 21:50:04,521 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 21:50:04,521 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-19 21:50:04,522 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-19 21:50:04,547 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-19 21:50:04,814 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 21:50:04,821 INFO L263 TraceCheckSpWp]: Trace formula consists of 2145 conjuncts, 12 conjunts are in the unsatisfiable core [2022-07-19 21:50:04,825 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-19 21:50:04,840 INFO L134 CoverageAnalysis]: Checked inductivity of 29 backedges. 16 proven. 0 refuted. 0 times theorem prover too weak. 13 trivial. 0 not checked. [2022-07-19 21:50:04,841 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-07-19 21:50:04,841 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-19 21:50:04,841 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1894005716] [2022-07-19 21:50:04,841 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-19 21:50:04,841 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1712087732] [2022-07-19 21:50:04,841 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1712087732] provided 1 perfect and 0 imperfect interpolant sequences [2022-07-19 21:50:04,841 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-07-19 21:50:04,841 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2022-07-19 21:50:04,842 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1094692156] [2022-07-19 21:50:04,842 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-19 21:50:04,842 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2022-07-19 21:50:04,842 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-19 21:50:04,842 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2022-07-19 21:50:04,843 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2022-07-19 21:50:04,843 INFO L87 Difference]: Start difference. First operand 114 states and 137 transitions. Second operand has 4 states, 4 states have (on average 14.0) internal successors, (56), 4 states have internal predecessors, (56), 2 states have call successors, (13), 2 states have call predecessors, (13), 3 states have return successors, (12), 2 states have call predecessors, (12), 2 states have call successors, (12) [2022-07-19 21:50:04,861 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-19 21:50:04,862 INFO L93 Difference]: Finished difference Result 166 states and 198 transitions. [2022-07-19 21:50:04,862 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2022-07-19 21:50:04,862 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 14.0) internal successors, (56), 4 states have internal predecessors, (56), 2 states have call successors, (13), 2 states have call predecessors, (13), 3 states have return successors, (12), 2 states have call predecessors, (12), 2 states have call successors, (12) Word has length 87 [2022-07-19 21:50:04,863 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-19 21:50:04,863 INFO L225 Difference]: With dead ends: 166 [2022-07-19 21:50:04,863 INFO L226 Difference]: Without dead ends: 119 [2022-07-19 21:50:04,864 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 87 GetRequests, 84 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-19 21:50:04,864 INFO L413 NwaCegarLoop]: 125 mSDtfsCounter, 7 mSDsluCounter, 245 mSDsCounter, 0 mSdLazyCounter, 19 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 370 SdHoareTripleChecker+Invalid, 19 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 19 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-07-19 21:50:04,864 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 370 Invalid, 19 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 19 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-07-19 21:50:04,865 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 119 states. [2022-07-19 21:50:04,885 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 119 to 115. [2022-07-19 21:50:04,885 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 115 states, 78 states have (on average 1.1923076923076923) internal successors, (93), 79 states have internal predecessors, (93), 22 states have call successors, (22), 13 states have call predecessors, (22), 14 states have return successors, (23), 22 states have call predecessors, (23), 21 states have call successors, (23) [2022-07-19 21:50:04,885 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 115 states to 115 states and 138 transitions. [2022-07-19 21:50:04,886 INFO L78 Accepts]: Start accepts. Automaton has 115 states and 138 transitions. Word has length 87 [2022-07-19 21:50:04,886 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-19 21:50:04,886 INFO L495 AbstractCegarLoop]: Abstraction has 115 states and 138 transitions. [2022-07-19 21:50:04,886 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 14.0) internal successors, (56), 4 states have internal predecessors, (56), 2 states have call successors, (13), 2 states have call predecessors, (13), 3 states have return successors, (12), 2 states have call predecessors, (12), 2 states have call successors, (12) [2022-07-19 21:50:04,886 INFO L276 IsEmpty]: Start isEmpty. Operand 115 states and 138 transitions. [2022-07-19 21:50:04,887 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 88 [2022-07-19 21:50:04,887 INFO L187 NwaCegarLoop]: Found error trace [2022-07-19 21:50:04,887 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-19 21:50:04,917 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-19 21:50:05,098 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 21:50:05,098 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-19 21:50:05,099 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-19 21:50:05,099 INFO L85 PathProgramCache]: Analyzing trace with hash 995990719, now seen corresponding path program 1 times [2022-07-19 21:50:05,099 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-19 21:50:05,099 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [284224111] [2022-07-19 21:50:05,099 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 21:50:05,099 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-19 21:50:05,134 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-19 21:50:05,135 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1599446637] [2022-07-19 21:50:05,135 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 21:50:05,135 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 21:50:05,135 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-19 21:50:05,136 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-19 21:50:05,137 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-19 21:50:05,475 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 21:50:05,483 INFO L263 TraceCheckSpWp]: Trace formula consists of 2148 conjuncts, 15 conjunts are in the unsatisfiable core [2022-07-19 21:50:05,486 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-19 21:50:05,527 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 17 proven. 0 refuted. 0 times theorem prover too weak. 13 trivial. 0 not checked. [2022-07-19 21:50:05,528 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-07-19 21:50:05,528 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-19 21:50:05,528 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [284224111] [2022-07-19 21:50:05,528 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-19 21:50:05,528 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1599446637] [2022-07-19 21:50:05,528 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1599446637] provided 1 perfect and 0 imperfect interpolant sequences [2022-07-19 21:50:05,528 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-07-19 21:50:05,528 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-07-19 21:50:05,529 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1600752480] [2022-07-19 21:50:05,529 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-19 21:50:05,529 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-07-19 21:50:05,529 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-19 21:50:05,529 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-07-19 21:50:05,530 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-07-19 21:50:05,530 INFO L87 Difference]: Start difference. First operand 115 states and 138 transitions. Second operand has 5 states, 5 states have (on average 11.2) internal successors, (56), 4 states have internal predecessors, (56), 2 states have call successors, (13), 2 states have call predecessors, (13), 3 states have return successors, (12), 3 states have call predecessors, (12), 2 states have call successors, (12) [2022-07-19 21:50:05,551 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-19 21:50:05,552 INFO L93 Difference]: Finished difference Result 160 states and 190 transitions. [2022-07-19 21:50:05,552 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-07-19 21:50:05,552 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 11.2) internal successors, (56), 4 states have internal predecessors, (56), 2 states have call successors, (13), 2 states have call predecessors, (13), 3 states have return successors, (12), 3 states have call predecessors, (12), 2 states have call successors, (12) Word has length 87 [2022-07-19 21:50:05,552 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-19 21:50:05,553 INFO L225 Difference]: With dead ends: 160 [2022-07-19 21:50:05,553 INFO L226 Difference]: Without dead ends: 117 [2022-07-19 21:50:05,554 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 87 GetRequests, 83 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-19 21:50:05,554 INFO L413 NwaCegarLoop]: 131 mSDtfsCounter, 4 mSDsluCounter, 375 mSDsCounter, 0 mSdLazyCounter, 19 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 506 SdHoareTripleChecker+Invalid, 21 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 19 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-07-19 21:50:05,554 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [5 Valid, 506 Invalid, 21 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 19 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-07-19 21:50:05,555 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 117 states. [2022-07-19 21:50:05,559 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 117 to 115. [2022-07-19 21:50:05,575 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 115 states, 78 states have (on average 1.1794871794871795) internal successors, (92), 79 states have internal predecessors, (92), 22 states have call successors, (22), 13 states have call predecessors, (22), 14 states have return successors, (23), 22 states have call predecessors, (23), 21 states have call successors, (23) [2022-07-19 21:50:05,576 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 115 states to 115 states and 137 transitions. [2022-07-19 21:50:05,576 INFO L78 Accepts]: Start accepts. Automaton has 115 states and 137 transitions. Word has length 87 [2022-07-19 21:50:05,576 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-19 21:50:05,576 INFO L495 AbstractCegarLoop]: Abstraction has 115 states and 137 transitions. [2022-07-19 21:50:05,576 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 11.2) internal successors, (56), 4 states have internal predecessors, (56), 2 states have call successors, (13), 2 states have call predecessors, (13), 3 states have return successors, (12), 3 states have call predecessors, (12), 2 states have call successors, (12) [2022-07-19 21:50:05,577 INFO L276 IsEmpty]: Start isEmpty. Operand 115 states and 137 transitions. [2022-07-19 21:50:05,577 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 91 [2022-07-19 21:50:05,577 INFO L187 NwaCegarLoop]: Found error trace [2022-07-19 21:50:05,577 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 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] [2022-07-19 21:50:05,600 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-19 21:50:05,798 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 21:50:05,798 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-19 21:50:05,798 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-19 21:50:05,799 INFO L85 PathProgramCache]: Analyzing trace with hash -462422751, now seen corresponding path program 1 times [2022-07-19 21:50:05,799 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-19 21:50:05,799 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1554602] [2022-07-19 21:50:05,799 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 21:50:05,799 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-19 21:50:05,833 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-19 21:50:05,834 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2027151577] [2022-07-19 21:50:05,834 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 21:50:05,834 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 21:50:05,834 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-19 21:50:05,835 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-19 21:50:05,836 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-19 21:50:06,270 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 21:50:06,278 INFO L263 TraceCheckSpWp]: Trace formula consists of 2152 conjuncts, 66 conjunts are in the unsatisfiable core [2022-07-19 21:50:06,282 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-19 21:50:07,282 WARN L855 $PredicateComparison]: unable to prove that (exists ((|v_#Ultimate.C_memset_#t~loopctr731_5| Int) (|#Ultimate.C_memset_#ptr.offset| Int)) (= (store |c_old(#memory_int)| |c_#Ultimate.C_memset_#ptr.base| (store (select |c_old(#memory_int)| |c_#Ultimate.C_memset_#ptr.base|) (+ |#Ultimate.C_memset_#ptr.offset| |v_#Ultimate.C_memset_#t~loopctr731_5|) |c_#Ultimate.C_memset_#value|)) |c_#memory_int|)) is different from true [2022-07-19 21:50:07,327 INFO L356 Elim1Store]: treesize reduction 15, result has 46.4 percent of original size [2022-07-19 21:50:07,327 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 23 treesize of output 28 [2022-07-19 21:50:07,605 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 15 proven. 4 refuted. 0 times theorem prover too weak. 12 trivial. 1 not checked. [2022-07-19 21:50:07,605 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-19 21:50:16,193 INFO L356 Elim1Store]: treesize reduction 4, result has 63.6 percent of original size [2022-07-19 21:50:16,193 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 19 treesize of output 18 [2022-07-19 21:50:16,335 INFO L356 Elim1Store]: treesize reduction 16, result has 67.3 percent of original size [2022-07-19 21:50:16,335 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 57 treesize of output 68 [2022-07-19 21:50:16,599 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 26 trivial. 0 not checked. [2022-07-19 21:50:16,600 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-19 21:50:16,600 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1554602] [2022-07-19 21:50:16,600 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-19 21:50:16,600 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2027151577] [2022-07-19 21:50:16,602 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2027151577] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-19 21:50:16,602 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-07-19 21:50:16,602 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 14] total 30 [2022-07-19 21:50:16,602 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1981663911] [2022-07-19 21:50:16,602 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-07-19 21:50:16,604 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 30 states [2022-07-19 21:50:16,604 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-19 21:50:16,604 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 30 interpolants. [2022-07-19 21:50:16,604 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=113, Invalid=702, Unknown=1, NotChecked=54, Total=870 [2022-07-19 21:50:16,605 INFO L87 Difference]: Start difference. First operand 115 states and 137 transitions. Second operand has 30 states, 28 states have (on average 3.142857142857143) internal successors, (88), 27 states have internal predecessors, (88), 8 states have call successors, (23), 6 states have call predecessors, (23), 8 states have return successors, (22), 8 states have call predecessors, (22), 7 states have call successors, (22) [2022-07-19 21:50:27,119 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-19 21:50:27,119 INFO L93 Difference]: Finished difference Result 174 states and 216 transitions. [2022-07-19 21:50:27,120 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 28 states. [2022-07-19 21:50:27,120 INFO L78 Accepts]: Start accepts. Automaton has has 30 states, 28 states have (on average 3.142857142857143) internal successors, (88), 27 states have internal predecessors, (88), 8 states have call successors, (23), 6 states have call predecessors, (23), 8 states have return successors, (22), 8 states have call predecessors, (22), 7 states have call successors, (22) Word has length 90 [2022-07-19 21:50:27,120 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-19 21:50:27,121 INFO L225 Difference]: With dead ends: 174 [2022-07-19 21:50:27,121 INFO L226 Difference]: Without dead ends: 167 [2022-07-19 21:50:27,122 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 193 GetRequests, 147 SyntacticMatches, 4 SemanticMatches, 42 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 491 ImplicationChecksByTransitivity, 19.0s TimeCoverageRelationStatistics Valid=238, Invalid=1557, Unknown=15, NotChecked=82, Total=1892 [2022-07-19 21:50:27,122 INFO L413 NwaCegarLoop]: 130 mSDtfsCounter, 143 mSDsluCounter, 861 mSDsCounter, 0 mSdLazyCounter, 862 mSolverCounterSat, 62 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 157 SdHoareTripleChecker+Valid, 991 SdHoareTripleChecker+Invalid, 1435 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 62 IncrementalHoareTripleChecker+Valid, 862 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 511 IncrementalHoareTripleChecker+Unchecked, 0.8s IncrementalHoareTripleChecker+Time [2022-07-19 21:50:27,123 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [157 Valid, 991 Invalid, 1435 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [62 Valid, 862 Invalid, 0 Unknown, 511 Unchecked, 0.8s Time] [2022-07-19 21:50:27,123 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 167 states. [2022-07-19 21:50:27,132 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 167 to 159. [2022-07-19 21:50:27,132 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 159 states, 111 states have (on average 1.1891891891891893) internal successors, (132), 114 states have internal predecessors, (132), 28 states have call successors, (28), 15 states have call predecessors, (28), 19 states have return successors, (38), 29 states have call predecessors, (38), 27 states have call successors, (38) [2022-07-19 21:50:27,133 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 159 states to 159 states and 198 transitions. [2022-07-19 21:50:27,133 INFO L78 Accepts]: Start accepts. Automaton has 159 states and 198 transitions. Word has length 90 [2022-07-19 21:50:27,134 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-19 21:50:27,134 INFO L495 AbstractCegarLoop]: Abstraction has 159 states and 198 transitions. [2022-07-19 21:50:27,134 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 30 states, 28 states have (on average 3.142857142857143) internal successors, (88), 27 states have internal predecessors, (88), 8 states have call successors, (23), 6 states have call predecessors, (23), 8 states have return successors, (22), 8 states have call predecessors, (22), 7 states have call successors, (22) [2022-07-19 21:50:27,134 INFO L276 IsEmpty]: Start isEmpty. Operand 159 states and 198 transitions. [2022-07-19 21:50:27,135 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 94 [2022-07-19 21:50:27,135 INFO L187 NwaCegarLoop]: Found error trace [2022-07-19 21:50:27,135 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-19 21:50:27,156 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-19 21:50:27,347 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 21:50:27,348 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-19 21:50:27,348 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-19 21:50:27,348 INFO L85 PathProgramCache]: Analyzing trace with hash 134736496, now seen corresponding path program 1 times [2022-07-19 21:50:27,348 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-19 21:50:27,348 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1443196687] [2022-07-19 21:50:27,348 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 21:50:27,348 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-19 21:50:27,389 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-19 21:50:27,389 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [675216817] [2022-07-19 21:50:27,390 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 21:50:27,390 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 21:50:27,390 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-19 21:50:27,392 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-19 21:50:27,393 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-19 21:50:27,696 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 21:50:27,704 INFO L263 TraceCheckSpWp]: Trace formula consists of 2182 conjuncts, 7 conjunts are in the unsatisfiable core [2022-07-19 21:50:27,707 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-19 21:50:27,757 INFO L134 CoverageAnalysis]: Checked inductivity of 34 backedges. 20 proven. 0 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2022-07-19 21:50:27,757 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-07-19 21:50:27,757 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-19 21:50:27,757 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1443196687] [2022-07-19 21:50:27,757 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-19 21:50:27,757 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [675216817] [2022-07-19 21:50:27,758 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [675216817] provided 1 perfect and 0 imperfect interpolant sequences [2022-07-19 21:50:27,758 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-07-19 21:50:27,758 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2022-07-19 21:50:27,758 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1157109802] [2022-07-19 21:50:27,758 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-19 21:50:27,760 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2022-07-19 21:50:27,760 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-19 21:50:27,760 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2022-07-19 21:50:27,761 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2022-07-19 21:50:27,761 INFO L87 Difference]: Start difference. First operand 159 states and 198 transitions. Second operand has 7 states, 7 states have (on average 8.571428571428571) internal successors, (60), 7 states have internal predecessors, (60), 4 states have call successors, (14), 2 states have call predecessors, (14), 3 states have return successors, (13), 4 states have call predecessors, (13), 4 states have call successors, (13) [2022-07-19 21:50:27,923 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-19 21:50:27,923 INFO L93 Difference]: Finished difference Result 232 states and 286 transitions. [2022-07-19 21:50:27,924 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-07-19 21:50:27,924 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 8.571428571428571) internal successors, (60), 7 states have internal predecessors, (60), 4 states have call successors, (14), 2 states have call predecessors, (14), 3 states have return successors, (13), 4 states have call predecessors, (13), 4 states have call successors, (13) Word has length 93 [2022-07-19 21:50:27,924 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-19 21:50:27,925 INFO L225 Difference]: With dead ends: 232 [2022-07-19 21:50:27,925 INFO L226 Difference]: Without dead ends: 157 [2022-07-19 21:50:27,925 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 98 GetRequests, 89 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=31, Invalid=79, Unknown=0, NotChecked=0, Total=110 [2022-07-19 21:50:27,925 INFO L413 NwaCegarLoop]: 99 mSDtfsCounter, 157 mSDsluCounter, 332 mSDsCounter, 0 mSdLazyCounter, 140 mSolverCounterSat, 34 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 157 SdHoareTripleChecker+Valid, 431 SdHoareTripleChecker+Invalid, 174 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 34 IncrementalHoareTripleChecker+Valid, 140 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-07-19 21:50:27,926 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [157 Valid, 431 Invalid, 174 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [34 Valid, 140 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-07-19 21:50:27,926 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 157 states. [2022-07-19 21:50:27,940 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 157 to 157. [2022-07-19 21:50:27,940 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 157 states, 110 states have (on average 1.1818181818181819) internal successors, (130), 112 states have internal predecessors, (130), 28 states have call successors, (28), 15 states have call predecessors, (28), 18 states have return successors, (36), 29 states have call predecessors, (36), 27 states have call successors, (36) [2022-07-19 21:50:27,943 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 157 states to 157 states and 194 transitions. [2022-07-19 21:50:27,943 INFO L78 Accepts]: Start accepts. Automaton has 157 states and 194 transitions. Word has length 93 [2022-07-19 21:50:27,943 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-19 21:50:27,943 INFO L495 AbstractCegarLoop]: Abstraction has 157 states and 194 transitions. [2022-07-19 21:50:27,944 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 8.571428571428571) internal successors, (60), 7 states have internal predecessors, (60), 4 states have call successors, (14), 2 states have call predecessors, (14), 3 states have return successors, (13), 4 states have call predecessors, (13), 4 states have call successors, (13) [2022-07-19 21:50:27,944 INFO L276 IsEmpty]: Start isEmpty. Operand 157 states and 194 transitions. [2022-07-19 21:50:27,944 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 94 [2022-07-19 21:50:27,945 INFO L187 NwaCegarLoop]: Found error trace [2022-07-19 21:50:27,945 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 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-19 21:50:27,967 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2022-07-19 21:50:28,161 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 21:50:28,161 INFO L420 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-19 21:50:28,162 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-19 21:50:28,162 INFO L85 PathProgramCache]: Analyzing trace with hash -910834864, now seen corresponding path program 2 times [2022-07-19 21:50:28,162 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-19 21:50:28,162 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [34672344] [2022-07-19 21:50:28,162 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 21:50:28,162 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-19 21:50:28,208 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-19 21:50:28,209 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [338692923] [2022-07-19 21:50:28,209 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-07-19 21:50:28,209 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 21:50:28,209 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-19 21:50:28,210 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-19 21:50:28,211 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-19 21:50:28,641 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-07-19 21:50:28,641 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-19 21:50:28,647 INFO L263 TraceCheckSpWp]: Trace formula consists of 2159 conjuncts, 20 conjunts are in the unsatisfiable core [2022-07-19 21:50:28,653 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-19 21:50:28,688 INFO L134 CoverageAnalysis]: Checked inductivity of 38 backedges. 22 proven. 1 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2022-07-19 21:50:28,688 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-19 21:50:28,792 INFO L134 CoverageAnalysis]: Checked inductivity of 38 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2022-07-19 21:50:28,792 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-19 21:50:28,792 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [34672344] [2022-07-19 21:50:28,792 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-19 21:50:28,792 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [338692923] [2022-07-19 21:50:28,792 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [338692923] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-19 21:50:28,792 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-07-19 21:50:28,792 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 8 [2022-07-19 21:50:28,792 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1114844252] [2022-07-19 21:50:28,792 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-07-19 21:50:28,792 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2022-07-19 21:50:28,792 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-19 21:50:28,793 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2022-07-19 21:50:28,793 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=22, Invalid=34, Unknown=0, NotChecked=0, Total=56 [2022-07-19 21:50:28,793 INFO L87 Difference]: Start difference. First operand 157 states and 194 transitions. Second operand has 8 states, 8 states have (on average 9.75) internal successors, (78), 8 states have internal predecessors, (78), 2 states have call successors, (16), 2 states have call predecessors, (16), 4 states have return successors, (16), 2 states have call predecessors, (16), 2 states have call successors, (16) [2022-07-19 21:50:28,866 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-19 21:50:28,867 INFO L93 Difference]: Finished difference Result 237 states and 292 transitions. [2022-07-19 21:50:28,867 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-07-19 21:50:28,867 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 9.75) internal successors, (78), 8 states have internal predecessors, (78), 2 states have call successors, (16), 2 states have call predecessors, (16), 4 states have return successors, (16), 2 states have call predecessors, (16), 2 states have call successors, (16) Word has length 93 [2022-07-19 21:50:28,867 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-19 21:50:28,868 INFO L225 Difference]: With dead ends: 237 [2022-07-19 21:50:28,868 INFO L226 Difference]: Without dead ends: 169 [2022-07-19 21:50:28,869 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 187 GetRequests, 179 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=38, Invalid=52, Unknown=0, NotChecked=0, Total=90 [2022-07-19 21:50:28,869 INFO L413 NwaCegarLoop]: 127 mSDtfsCounter, 37 mSDsluCounter, 380 mSDsCounter, 0 mSdLazyCounter, 51 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 37 SdHoareTripleChecker+Valid, 507 SdHoareTripleChecker+Invalid, 56 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 51 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-07-19 21:50:28,869 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [37 Valid, 507 Invalid, 56 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 51 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-07-19 21:50:28,870 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 169 states. [2022-07-19 21:50:28,877 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 169 to 165. [2022-07-19 21:50:28,877 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 165 states, 118 states have (on average 1.1864406779661016) internal successors, (140), 120 states have internal predecessors, (140), 28 states have call successors, (28), 15 states have call predecessors, (28), 18 states have return successors, (36), 29 states have call predecessors, (36), 27 states have call successors, (36) [2022-07-19 21:50:28,878 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 165 states to 165 states and 204 transitions. [2022-07-19 21:50:28,878 INFO L78 Accepts]: Start accepts. Automaton has 165 states and 204 transitions. Word has length 93 [2022-07-19 21:50:28,878 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-19 21:50:28,879 INFO L495 AbstractCegarLoop]: Abstraction has 165 states and 204 transitions. [2022-07-19 21:50:28,879 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 9.75) internal successors, (78), 8 states have internal predecessors, (78), 2 states have call successors, (16), 2 states have call predecessors, (16), 4 states have return successors, (16), 2 states have call predecessors, (16), 2 states have call successors, (16) [2022-07-19 21:50:28,879 INFO L276 IsEmpty]: Start isEmpty. Operand 165 states and 204 transitions. [2022-07-19 21:50:28,880 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 109 [2022-07-19 21:50:28,880 INFO L187 NwaCegarLoop]: Found error trace [2022-07-19 21:50:28,880 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 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-19 21:50:28,913 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-19 21:50:29,095 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 21:50:29,095 INFO L420 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-19 21:50:29,096 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-19 21:50:29,096 INFO L85 PathProgramCache]: Analyzing trace with hash 966825052, now seen corresponding path program 1 times [2022-07-19 21:50:29,096 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-19 21:50:29,096 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [798402505] [2022-07-19 21:50:29,096 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 21:50:29,096 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-19 21:50:29,130 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-19 21:50:29,131 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1008932872] [2022-07-19 21:50:29,131 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 21:50:29,131 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 21:50:29,131 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-19 21:50:29,132 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-19 21:50:29,133 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-19 21:50:29,473 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 21:50:29,480 INFO L263 TraceCheckSpWp]: Trace formula consists of 2323 conjuncts, 54 conjunts are in the unsatisfiable core [2022-07-19 21:50:29,484 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-19 21:50:29,603 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 11 treesize of output 7 [2022-07-19 21:50:29,727 INFO L134 CoverageAnalysis]: Checked inductivity of 49 backedges. 3 proven. 3 refuted. 0 times theorem prover too weak. 43 trivial. 0 not checked. [2022-07-19 21:50:29,727 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-19 21:50:29,959 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 27 treesize of output 23 [2022-07-19 21:50:30,018 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 14 treesize of output 12 [2022-07-19 21:50:30,020 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 26 treesize of output 24 [2022-07-19 21:50:30,176 INFO L134 CoverageAnalysis]: Checked inductivity of 49 backedges. 4 proven. 1 refuted. 0 times theorem prover too weak. 44 trivial. 0 not checked. [2022-07-19 21:50:30,176 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-19 21:50:30,176 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [798402505] [2022-07-19 21:50:30,176 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-19 21:50:30,176 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1008932872] [2022-07-19 21:50:30,176 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1008932872] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-19 21:50:30,176 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-07-19 21:50:30,177 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 11] total 23 [2022-07-19 21:50:30,177 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [626109716] [2022-07-19 21:50:30,177 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-07-19 21:50:30,177 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2022-07-19 21:50:30,177 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-19 21:50:30,177 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2022-07-19 21:50:30,178 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=74, Invalid=432, Unknown=0, NotChecked=0, Total=506 [2022-07-19 21:50:30,178 INFO L87 Difference]: Start difference. First operand 165 states and 204 transitions. Second operand has 23 states, 23 states have (on average 3.5217391304347827) internal successors, (81), 20 states have internal predecessors, (81), 7 states have call successors, (25), 3 states have call predecessors, (25), 6 states have return successors, (24), 9 states have call predecessors, (24), 6 states have call successors, (24) [2022-07-19 21:50:30,745 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-19 21:50:30,745 INFO L93 Difference]: Finished difference Result 177 states and 216 transitions. [2022-07-19 21:50:30,746 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2022-07-19 21:50:30,746 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 23 states have (on average 3.5217391304347827) internal successors, (81), 20 states have internal predecessors, (81), 7 states have call successors, (25), 3 states have call predecessors, (25), 6 states have return successors, (24), 9 states have call predecessors, (24), 6 states have call successors, (24) Word has length 108 [2022-07-19 21:50:30,746 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-19 21:50:30,747 INFO L225 Difference]: With dead ends: 177 [2022-07-19 21:50:30,747 INFO L226 Difference]: Without dead ends: 170 [2022-07-19 21:50:30,747 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 224 GetRequests, 196 SyntacticMatches, 0 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 185 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=128, Invalid=742, Unknown=0, NotChecked=0, Total=870 [2022-07-19 21:50:30,748 INFO L413 NwaCegarLoop]: 117 mSDtfsCounter, 39 mSDsluCounter, 1424 mSDsCounter, 0 mSdLazyCounter, 385 mSolverCounterSat, 15 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 48 SdHoareTripleChecker+Valid, 1541 SdHoareTripleChecker+Invalid, 504 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 15 IncrementalHoareTripleChecker+Valid, 385 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 104 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2022-07-19 21:50:30,748 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [48 Valid, 1541 Invalid, 504 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [15 Valid, 385 Invalid, 0 Unknown, 104 Unchecked, 0.4s Time] [2022-07-19 21:50:30,748 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 170 states. [2022-07-19 21:50:30,754 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 170 to 148. [2022-07-19 21:50:30,755 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 148 states, 106 states have (on average 1.179245283018868) internal successors, (125), 107 states have internal predecessors, (125), 24 states have call successors, (24), 15 states have call predecessors, (24), 17 states have return successors, (29), 25 states have call predecessors, (29), 23 states have call successors, (29) [2022-07-19 21:50:30,755 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 148 states to 148 states and 178 transitions. [2022-07-19 21:50:30,755 INFO L78 Accepts]: Start accepts. Automaton has 148 states and 178 transitions. Word has length 108 [2022-07-19 21:50:30,756 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-19 21:50:30,756 INFO L495 AbstractCegarLoop]: Abstraction has 148 states and 178 transitions. [2022-07-19 21:50:30,756 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 23 states have (on average 3.5217391304347827) internal successors, (81), 20 states have internal predecessors, (81), 7 states have call successors, (25), 3 states have call predecessors, (25), 6 states have return successors, (24), 9 states have call predecessors, (24), 6 states have call successors, (24) [2022-07-19 21:50:30,756 INFO L276 IsEmpty]: Start isEmpty. Operand 148 states and 178 transitions. [2022-07-19 21:50:30,757 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 118 [2022-07-19 21:50:30,757 INFO L187 NwaCegarLoop]: Found error trace [2022-07-19 21:50:30,757 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-19 21:50:30,778 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2022-07-19 21:50:30,970 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,SelfDestructingSolverStorable9 [2022-07-19 21:50:30,970 INFO L420 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-19 21:50:30,970 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-19 21:50:30,970 INFO L85 PathProgramCache]: Analyzing trace with hash -1784691315, now seen corresponding path program 1 times [2022-07-19 21:50:30,971 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-19 21:50:30,971 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [567851569] [2022-07-19 21:50:30,971 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 21:50:30,971 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-19 21:50:31,014 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-19 21:50:31,014 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [961467702] [2022-07-19 21:50:31,014 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 21:50:31,014 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 21:50:31,014 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-19 21:50:31,016 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-19 21:50:31,017 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-19 21:50:31,319 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 21:50:31,326 INFO L263 TraceCheckSpWp]: Trace formula consists of 2334 conjuncts, 16 conjunts are in the unsatisfiable core [2022-07-19 21:50:31,329 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-19 21:50:31,345 INFO L134 CoverageAnalysis]: Checked inductivity of 53 backedges. 7 proven. 1 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2022-07-19 21:50:31,345 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-19 21:50:31,459 INFO L134 CoverageAnalysis]: Checked inductivity of 53 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 52 trivial. 0 not checked. [2022-07-19 21:50:31,459 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-19 21:50:31,459 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [567851569] [2022-07-19 21:50:31,459 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-19 21:50:31,459 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [961467702] [2022-07-19 21:50:31,459 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [961467702] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-19 21:50:31,460 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-07-19 21:50:31,460 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 8 [2022-07-19 21:50:31,460 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1989379246] [2022-07-19 21:50:31,460 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-07-19 21:50:31,460 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2022-07-19 21:50:31,460 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-19 21:50:31,461 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2022-07-19 21:50:31,461 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=22, Invalid=34, Unknown=0, NotChecked=0, Total=56 [2022-07-19 21:50:31,461 INFO L87 Difference]: Start difference. First operand 148 states and 178 transitions. Second operand has 8 states, 8 states have (on average 8.375) internal successors, (67), 8 states have internal predecessors, (67), 2 states have call successors, (16), 2 states have call predecessors, (16), 4 states have return successors, (16), 2 states have call predecessors, (16), 2 states have call successors, (16) [2022-07-19 21:50:31,523 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-19 21:50:31,523 INFO L93 Difference]: Finished difference Result 183 states and 218 transitions. [2022-07-19 21:50:31,525 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-07-19 21:50:31,525 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 8.375) internal successors, (67), 8 states have internal predecessors, (67), 2 states have call successors, (16), 2 states have call predecessors, (16), 4 states have return successors, (16), 2 states have call predecessors, (16), 2 states have call successors, (16) Word has length 117 [2022-07-19 21:50:31,525 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-19 21:50:31,526 INFO L225 Difference]: With dead ends: 183 [2022-07-19 21:50:31,526 INFO L226 Difference]: Without dead ends: 151 [2022-07-19 21:50:31,526 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 234 GetRequests, 226 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=38, Invalid=52, Unknown=0, NotChecked=0, Total=90 [2022-07-19 21:50:31,526 INFO L413 NwaCegarLoop]: 127 mSDtfsCounter, 9 mSDsluCounter, 254 mSDsCounter, 0 mSdLazyCounter, 18 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 9 SdHoareTripleChecker+Valid, 381 SdHoareTripleChecker+Invalid, 22 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 18 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-07-19 21:50:31,527 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [9 Valid, 381 Invalid, 22 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 18 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-07-19 21:50:31,527 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 151 states. [2022-07-19 21:50:31,535 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 151 to 151. [2022-07-19 21:50:31,535 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 151 states, 109 states have (on average 1.1743119266055047) internal successors, (128), 110 states have internal predecessors, (128), 24 states have call successors, (24), 15 states have call predecessors, (24), 17 states have return successors, (29), 25 states have call predecessors, (29), 23 states have call successors, (29) [2022-07-19 21:50:31,536 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 151 states to 151 states and 181 transitions. [2022-07-19 21:50:31,536 INFO L78 Accepts]: Start accepts. Automaton has 151 states and 181 transitions. Word has length 117 [2022-07-19 21:50:31,536 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-19 21:50:31,537 INFO L495 AbstractCegarLoop]: Abstraction has 151 states and 181 transitions. [2022-07-19 21:50:31,537 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 8.375) internal successors, (67), 8 states have internal predecessors, (67), 2 states have call successors, (16), 2 states have call predecessors, (16), 4 states have return successors, (16), 2 states have call predecessors, (16), 2 states have call successors, (16) [2022-07-19 21:50:31,537 INFO L276 IsEmpty]: Start isEmpty. Operand 151 states and 181 transitions. [2022-07-19 21:50:31,538 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 115 [2022-07-19 21:50:31,538 INFO L187 NwaCegarLoop]: Found error trace [2022-07-19 21:50:31,538 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 4, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-19 21:50:31,557 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-19 21:50:31,743 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 21:50:31,743 INFO L420 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-19 21:50:31,744 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-19 21:50:31,744 INFO L85 PathProgramCache]: Analyzing trace with hash -564772413, now seen corresponding path program 1 times [2022-07-19 21:50:31,744 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-19 21:50:31,744 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [520661023] [2022-07-19 21:50:31,744 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 21:50:31,744 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-19 21:50:31,792 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-19 21:50:31,793 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1786733584] [2022-07-19 21:50:31,793 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 21:50:31,793 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 21:50:31,793 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-19 21:50:31,794 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-19 21:50:31,797 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-19 21:50:32,195 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 21:50:32,203 INFO L263 TraceCheckSpWp]: Trace formula consists of 2387 conjuncts, 69 conjunts are in the unsatisfiable core [2022-07-19 21:50:32,210 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-19 21:50:32,295 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 11 treesize of output 7 [2022-07-19 21:50:32,313 INFO L356 Elim1Store]: treesize reduction 21, result has 25.0 percent of original size [2022-07-19 21:50:32,313 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 21 treesize of output 20 [2022-07-19 21:50:32,349 INFO L356 Elim1Store]: treesize reduction 60, result has 22.1 percent of original size [2022-07-19 21:50:32,349 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 3 case distinctions, treesize of input 31 treesize of output 33 [2022-07-19 21:50:32,387 INFO L356 Elim1Store]: treesize reduction 104, result has 20.0 percent of original size [2022-07-19 21:50:32,387 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 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 39 treesize of output 44 [2022-07-19 21:50:32,678 INFO L134 CoverageAnalysis]: Checked inductivity of 62 backedges. 5 proven. 14 refuted. 0 times theorem prover too weak. 43 trivial. 0 not checked. [2022-07-19 21:50:32,678 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-19 21:50:33,060 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 111 treesize of output 105 [2022-07-19 21:50:33,439 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 34 treesize of output 32 [2022-07-19 21:50:33,442 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 382 treesize of output 378 [2022-07-19 21:50:33,462 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 34 treesize of output 32 [2022-07-19 21:50:33,464 INFO L173 IndexEqualityManager]: detected equality via solver [2022-07-19 21:50:33,468 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 184 treesize of output 180 [2022-07-19 21:50:33,485 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 34 treesize of output 32 [2022-07-19 21:50:33,487 INFO L173 IndexEqualityManager]: detected equality via solver [2022-07-19 21:50:33,487 INFO L173 IndexEqualityManager]: detected equality via solver [2022-07-19 21:50:33,490 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 84 treesize of output 80 [2022-07-19 21:50:33,500 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 32 treesize of output 30 [2022-07-19 21:50:33,502 INFO L173 IndexEqualityManager]: detected equality via solver [2022-07-19 21:50:33,502 INFO L173 IndexEqualityManager]: detected equality via solver [2022-07-19 21:50:33,503 INFO L173 IndexEqualityManager]: detected equality via solver [2022-07-19 21:50:33,504 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 26 treesize of output 24 [2022-07-19 21:50:33,822 INFO L134 CoverageAnalysis]: Checked inductivity of 62 backedges. 12 proven. 6 refuted. 0 times theorem prover too weak. 44 trivial. 0 not checked. [2022-07-19 21:50:33,823 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-19 21:50:33,823 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [520661023] [2022-07-19 21:50:33,823 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-19 21:50:33,823 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1786733584] [2022-07-19 21:50:33,823 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1786733584] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-19 21:50:33,823 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-07-19 21:50:33,823 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 15] total 31 [2022-07-19 21:50:33,823 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1819022905] [2022-07-19 21:50:33,824 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-07-19 21:50:33,824 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 31 states [2022-07-19 21:50:33,824 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-19 21:50:33,824 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 31 interpolants. [2022-07-19 21:50:33,825 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=109, Invalid=821, Unknown=0, NotChecked=0, Total=930 [2022-07-19 21:50:33,825 INFO L87 Difference]: Start difference. First operand 151 states and 181 transitions. Second operand has 31 states, 31 states have (on average 3.0) internal successors, (93), 28 states have internal predecessors, (93), 7 states have call successors, (25), 3 states have call predecessors, (25), 6 states have return successors, (24), 9 states have call predecessors, (24), 6 states have call successors, (24) [2022-07-19 21:50:34,749 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-19 21:50:34,749 INFO L93 Difference]: Finished difference Result 165 states and 196 transitions. [2022-07-19 21:50:34,749 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2022-07-19 21:50:34,750 INFO L78 Accepts]: Start accepts. Automaton has has 31 states, 31 states have (on average 3.0) internal successors, (93), 28 states have internal predecessors, (93), 7 states have call successors, (25), 3 states have call predecessors, (25), 6 states have return successors, (24), 9 states have call predecessors, (24), 6 states have call successors, (24) Word has length 114 [2022-07-19 21:50:34,750 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-19 21:50:34,750 INFO L225 Difference]: With dead ends: 165 [2022-07-19 21:50:34,751 INFO L226 Difference]: Without dead ends: 158 [2022-07-19 21:50:34,751 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 235 GetRequests, 199 SyntacticMatches, 0 SemanticMatches, 36 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 281 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=167, Invalid=1239, Unknown=0, NotChecked=0, Total=1406 [2022-07-19 21:50:34,752 INFO L413 NwaCegarLoop]: 122 mSDtfsCounter, 68 mSDsluCounter, 1769 mSDsCounter, 0 mSdLazyCounter, 628 mSolverCounterSat, 34 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 77 SdHoareTripleChecker+Valid, 1891 SdHoareTripleChecker+Invalid, 881 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 34 IncrementalHoareTripleChecker+Valid, 628 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 219 IncrementalHoareTripleChecker+Unchecked, 0.7s IncrementalHoareTripleChecker+Time [2022-07-19 21:50:34,752 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [77 Valid, 1891 Invalid, 881 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [34 Valid, 628 Invalid, 0 Unknown, 219 Unchecked, 0.7s Time] [2022-07-19 21:50:34,752 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 158 states. [2022-07-19 21:50:34,758 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 158 to 156. [2022-07-19 21:50:34,759 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 156 states, 113 states have (on average 1.168141592920354) internal successors, (132), 115 states have internal predecessors, (132), 24 states have call successors, (24), 15 states have call predecessors, (24), 18 states have return successors, (30), 25 states have call predecessors, (30), 23 states have call successors, (30) [2022-07-19 21:50:34,759 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 156 states to 156 states and 186 transitions. [2022-07-19 21:50:34,759 INFO L78 Accepts]: Start accepts. Automaton has 156 states and 186 transitions. Word has length 114 [2022-07-19 21:50:34,760 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-19 21:50:34,760 INFO L495 AbstractCegarLoop]: Abstraction has 156 states and 186 transitions. [2022-07-19 21:50:34,760 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 31 states, 31 states have (on average 3.0) internal successors, (93), 28 states have internal predecessors, (93), 7 states have call successors, (25), 3 states have call predecessors, (25), 6 states have return successors, (24), 9 states have call predecessors, (24), 6 states have call successors, (24) [2022-07-19 21:50:34,760 INFO L276 IsEmpty]: Start isEmpty. Operand 156 states and 186 transitions. [2022-07-19 21:50:34,761 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 124 [2022-07-19 21:50:34,761 INFO L187 NwaCegarLoop]: Found error trace [2022-07-19 21:50:34,761 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 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-19 21:50:34,782 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-19 21:50:34,980 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,SelfDestructingSolverStorable11 [2022-07-19 21:50:34,981 INFO L420 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-19 21:50:34,981 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-19 21:50:34,981 INFO L85 PathProgramCache]: Analyzing trace with hash -645338938, now seen corresponding path program 2 times [2022-07-19 21:50:34,981 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-19 21:50:34,981 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [913700779] [2022-07-19 21:50:34,981 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 21:50:34,981 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-19 21:50:35,030 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-19 21:50:35,030 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [60747421] [2022-07-19 21:50:35,031 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-07-19 21:50:35,031 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 21:50:35,031 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-19 21:50:35,032 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-19 21:50:35,033 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-19 21:50:35,690 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-07-19 21:50:35,690 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-19 21:50:35,699 INFO L263 TraceCheckSpWp]: Trace formula consists of 2398 conjuncts, 25 conjunts are in the unsatisfiable core [2022-07-19 21:50:35,702 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-19 21:50:35,827 INFO L134 CoverageAnalysis]: Checked inductivity of 69 backedges. 28 proven. 0 refuted. 0 times theorem prover too weak. 41 trivial. 0 not checked. [2022-07-19 21:50:35,827 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-07-19 21:50:35,827 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-19 21:50:35,827 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [913700779] [2022-07-19 21:50:35,827 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-19 21:50:35,827 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [60747421] [2022-07-19 21:50:35,828 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [60747421] provided 1 perfect and 0 imperfect interpolant sequences [2022-07-19 21:50:35,828 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-07-19 21:50:35,828 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [15] imperfect sequences [] total 15 [2022-07-19 21:50:35,828 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [217223884] [2022-07-19 21:50:35,828 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-19 21:50:35,828 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2022-07-19 21:50:35,828 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-19 21:50:35,828 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2022-07-19 21:50:35,828 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=183, Unknown=0, NotChecked=0, Total=210 [2022-07-19 21:50:35,829 INFO L87 Difference]: Start difference. First operand 156 states and 186 transitions. Second operand has 15 states, 15 states have (on average 4.8) internal successors, (72), 11 states have internal predecessors, (72), 3 states have call successors, (15), 2 states have call predecessors, (15), 7 states have return successors, (15), 6 states have call predecessors, (15), 3 states have call successors, (15) [2022-07-19 21:50:36,038 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-19 21:50:36,039 INFO L93 Difference]: Finished difference Result 214 states and 252 transitions. [2022-07-19 21:50:36,039 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2022-07-19 21:50:36,039 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 15 states have (on average 4.8) internal successors, (72), 11 states have internal predecessors, (72), 3 states have call successors, (15), 2 states have call predecessors, (15), 7 states have return successors, (15), 6 states have call predecessors, (15), 3 states have call successors, (15) Word has length 123 [2022-07-19 21:50:36,039 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-19 21:50:36,040 INFO L225 Difference]: With dead ends: 214 [2022-07-19 21:50:36,040 INFO L226 Difference]: Without dead ends: 156 [2022-07-19 21:50:36,041 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 128 GetRequests, 110 SyntacticMatches, 0 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=49, Invalid=331, Unknown=0, NotChecked=0, Total=380 [2022-07-19 21:50:36,041 INFO L413 NwaCegarLoop]: 131 mSDtfsCounter, 15 mSDsluCounter, 1626 mSDsCounter, 0 mSdLazyCounter, 267 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 16 SdHoareTripleChecker+Valid, 1757 SdHoareTripleChecker+Invalid, 273 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 267 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-07-19 21:50:36,041 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [16 Valid, 1757 Invalid, 273 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 267 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-07-19 21:50:36,042 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 156 states. [2022-07-19 21:50:36,048 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 156 to 150. [2022-07-19 21:50:36,048 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 150 states, 109 states have (on average 1.1743119266055047) internal successors, (128), 111 states have internal predecessors, (128), 23 states have call successors, (23), 15 states have call predecessors, (23), 17 states have return successors, (26), 23 states have call predecessors, (26), 22 states have call successors, (26) [2022-07-19 21:50:36,049 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 150 states to 150 states and 177 transitions. [2022-07-19 21:50:36,049 INFO L78 Accepts]: Start accepts. Automaton has 150 states and 177 transitions. Word has length 123 [2022-07-19 21:50:36,049 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-19 21:50:36,049 INFO L495 AbstractCegarLoop]: Abstraction has 150 states and 177 transitions. [2022-07-19 21:50:36,049 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 4.8) internal successors, (72), 11 states have internal predecessors, (72), 3 states have call successors, (15), 2 states have call predecessors, (15), 7 states have return successors, (15), 6 states have call predecessors, (15), 3 states have call successors, (15) [2022-07-19 21:50:36,050 INFO L276 IsEmpty]: Start isEmpty. Operand 150 states and 177 transitions. [2022-07-19 21:50:36,050 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 118 [2022-07-19 21:50:36,050 INFO L187 NwaCegarLoop]: Found error trace [2022-07-19 21:50:36,050 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 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-19 21:50:36,071 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-19 21:50:36,263 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,SelfDestructingSolverStorable12 [2022-07-19 21:50:36,263 INFO L420 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-19 21:50:36,264 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-19 21:50:36,264 INFO L85 PathProgramCache]: Analyzing trace with hash -582835346, now seen corresponding path program 2 times [2022-07-19 21:50:36,264 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-19 21:50:36,264 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [986855763] [2022-07-19 21:50:36,264 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 21:50:36,264 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-19 21:50:36,311 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-19 21:50:36,311 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [195451545] [2022-07-19 21:50:36,311 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-07-19 21:50:36,312 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 21:50:36,312 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-19 21:50:36,313 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-19 21:50:36,314 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-19 21:50:36,701 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-07-19 21:50:36,701 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-19 21:50:36,709 INFO L263 TraceCheckSpWp]: Trace formula consists of 2394 conjuncts, 86 conjunts are in the unsatisfiable core [2022-07-19 21:50:36,713 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-19 21:50:36,946 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 14 treesize of output 10 [2022-07-19 21:50:36,970 INFO L356 Elim1Store]: treesize reduction 32, result has 23.8 percent of original size [2022-07-19 21:50:36,970 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 25 treesize of output 24 [2022-07-19 21:50:37,006 INFO L356 Elim1Store]: treesize reduction 76, result has 21.6 percent of original size [2022-07-19 21:50:37,006 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 3 case distinctions, treesize of input 35 treesize of output 37 [2022-07-19 21:50:37,054 INFO L356 Elim1Store]: treesize reduction 104, result has 20.0 percent of original size [2022-07-19 21:50:37,054 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 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 39 treesize of output 44 [2022-07-19 21:50:37,478 INFO L134 CoverageAnalysis]: Checked inductivity of 69 backedges. 7 proven. 28 refuted. 0 times theorem prover too weak. 34 trivial. 0 not checked. [2022-07-19 21:50:37,478 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-19 21:50:38,039 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 111 treesize of output 105 [2022-07-19 21:50:38,503 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 34 treesize of output 32 [2022-07-19 21:50:38,505 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 380 treesize of output 376 [2022-07-19 21:50:38,559 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 34 treesize of output 32 [2022-07-19 21:50:38,561 INFO L173 IndexEqualityManager]: detected equality via solver [2022-07-19 21:50:38,564 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 184 treesize of output 180 [2022-07-19 21:50:38,576 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 34 treesize of output 32 [2022-07-19 21:50:38,577 INFO L173 IndexEqualityManager]: detected equality via solver [2022-07-19 21:50:38,578 INFO L173 IndexEqualityManager]: detected equality via solver [2022-07-19 21:50:38,580 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 84 treesize of output 80 [2022-07-19 21:50:38,591 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 32 treesize of output 30 [2022-07-19 21:50:38,594 INFO L173 IndexEqualityManager]: detected equality via solver [2022-07-19 21:50:38,594 INFO L173 IndexEqualityManager]: detected equality via solver [2022-07-19 21:50:38,594 INFO L173 IndexEqualityManager]: detected equality via solver [2022-07-19 21:50:38,596 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 26 treesize of output 24 [2022-07-19 21:50:38,975 INFO L134 CoverageAnalysis]: Checked inductivity of 69 backedges. 14 proven. 11 refuted. 0 times theorem prover too weak. 44 trivial. 0 not checked. [2022-07-19 21:50:38,975 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-19 21:50:38,975 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [986855763] [2022-07-19 21:50:38,975 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-19 21:50:38,975 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [195451545] [2022-07-19 21:50:38,975 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [195451545] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-19 21:50:38,975 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-07-19 21:50:38,976 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [23, 16] total 37 [2022-07-19 21:50:38,976 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1047389630] [2022-07-19 21:50:38,976 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-07-19 21:50:38,976 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 37 states [2022-07-19 21:50:38,976 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-19 21:50:38,976 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 37 interpolants. [2022-07-19 21:50:38,977 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=126, Invalid=1206, Unknown=0, NotChecked=0, Total=1332 [2022-07-19 21:50:38,977 INFO L87 Difference]: Start difference. First operand 150 states and 177 transitions. Second operand has 37 states, 36 states have (on average 2.888888888888889) internal successors, (104), 33 states have internal predecessors, (104), 8 states have call successors, (25), 3 states have call predecessors, (25), 8 states have return successors, (24), 10 states have call predecessors, (24), 7 states have call successors, (24) [2022-07-19 21:50:40,382 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-19 21:50:40,382 INFO L93 Difference]: Finished difference Result 165 states and 192 transitions. [2022-07-19 21:50:40,382 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 30 states. [2022-07-19 21:50:40,383 INFO L78 Accepts]: Start accepts. Automaton has has 37 states, 36 states have (on average 2.888888888888889) internal successors, (104), 33 states have internal predecessors, (104), 8 states have call successors, (25), 3 states have call predecessors, (25), 8 states have return successors, (24), 10 states have call predecessors, (24), 7 states have call successors, (24) Word has length 117 [2022-07-19 21:50:40,383 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-19 21:50:40,383 INFO L225 Difference]: With dead ends: 165 [2022-07-19 21:50:40,384 INFO L226 Difference]: Without dead ends: 158 [2022-07-19 21:50:40,384 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 243 GetRequests, 199 SyntacticMatches, 0 SemanticMatches, 44 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 391 ImplicationChecksByTransitivity, 1.5s TimeCoverageRelationStatistics Valid=195, Invalid=1875, Unknown=0, NotChecked=0, Total=2070 [2022-07-19 21:50:40,385 INFO L413 NwaCegarLoop]: 116 mSDtfsCounter, 48 mSDsluCounter, 2239 mSDsCounter, 0 mSdLazyCounter, 1059 mSolverCounterSat, 19 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 59 SdHoareTripleChecker+Valid, 2355 SdHoareTripleChecker+Invalid, 1385 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 19 IncrementalHoareTripleChecker+Valid, 1059 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 307 IncrementalHoareTripleChecker+Unchecked, 1.0s IncrementalHoareTripleChecker+Time [2022-07-19 21:50:40,385 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [59 Valid, 2355 Invalid, 1385 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [19 Valid, 1059 Invalid, 0 Unknown, 307 Unchecked, 1.0s Time] [2022-07-19 21:50:40,385 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 158 states. [2022-07-19 21:50:40,391 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 158 to 153. [2022-07-19 21:50:40,392 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 153 states, 112 states have (on average 1.1696428571428572) internal successors, (131), 114 states have internal predecessors, (131), 23 states have call successors, (23), 15 states have call predecessors, (23), 17 states have return successors, (26), 23 states have call predecessors, (26), 22 states have call successors, (26) [2022-07-19 21:50:40,392 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 153 states to 153 states and 180 transitions. [2022-07-19 21:50:40,392 INFO L78 Accepts]: Start accepts. Automaton has 153 states and 180 transitions. Word has length 117 [2022-07-19 21:50:40,393 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-19 21:50:40,393 INFO L495 AbstractCegarLoop]: Abstraction has 153 states and 180 transitions. [2022-07-19 21:50:40,393 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 37 states, 36 states have (on average 2.888888888888889) internal successors, (104), 33 states have internal predecessors, (104), 8 states have call successors, (25), 3 states have call predecessors, (25), 8 states have return successors, (24), 10 states have call predecessors, (24), 7 states have call successors, (24) [2022-07-19 21:50:40,393 INFO L276 IsEmpty]: Start isEmpty. Operand 153 states and 180 transitions. [2022-07-19 21:50:40,394 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 121 [2022-07-19 21:50:40,394 INFO L187 NwaCegarLoop]: Found error trace [2022-07-19 21:50:40,394 INFO L195 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-19 21:50:40,415 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-19 21:50:40,607 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,SelfDestructingSolverStorable13 [2022-07-19 21:50:40,607 INFO L420 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-19 21:50:40,607 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-19 21:50:40,607 INFO L85 PathProgramCache]: Analyzing trace with hash -1824760349, now seen corresponding path program 3 times [2022-07-19 21:50:40,607 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-19 21:50:40,607 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1114013136] [2022-07-19 21:50:40,608 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 21:50:40,608 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-19 21:50:40,644 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-19 21:50:40,644 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1715487657] [2022-07-19 21:50:40,644 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-07-19 21:50:40,644 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 21:50:40,644 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-19 21:50:40,645 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-19 21:50:40,646 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-19 21:50:41,418 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2022-07-19 21:50:41,418 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-19 21:50:41,427 INFO L263 TraceCheckSpWp]: Trace formula consists of 2365 conjuncts, 13 conjunts are in the unsatisfiable core [2022-07-19 21:50:41,431 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-19 21:50:41,463 INFO L134 CoverageAnalysis]: Checked inductivity of 79 backedges. 11 proven. 10 refuted. 0 times theorem prover too weak. 58 trivial. 0 not checked. [2022-07-19 21:50:41,463 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-19 21:50:41,637 INFO L134 CoverageAnalysis]: Checked inductivity of 79 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 69 trivial. 0 not checked. [2022-07-19 21:50:41,638 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-19 21:50:41,638 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1114013136] [2022-07-19 21:50:41,638 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-19 21:50:41,638 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1715487657] [2022-07-19 21:50:41,638 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1715487657] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-19 21:50:41,638 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-07-19 21:50:41,639 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 14 [2022-07-19 21:50:41,640 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [457208725] [2022-07-19 21:50:41,640 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-07-19 21:50:41,640 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2022-07-19 21:50:41,640 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-19 21:50:41,640 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2022-07-19 21:50:41,641 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=61, Invalid=121, Unknown=0, NotChecked=0, Total=182 [2022-07-19 21:50:41,641 INFO L87 Difference]: Start difference. First operand 153 states and 180 transitions. Second operand has 14 states, 14 states have (on average 4.857142857142857) internal successors, (68), 14 states have internal predecessors, (68), 2 states have call successors, (15), 2 states have call predecessors, (15), 4 states have return successors, (15), 2 states have call predecessors, (15), 2 states have call successors, (15) [2022-07-19 21:50:42,082 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-19 21:50:42,082 INFO L93 Difference]: Finished difference Result 191 states and 224 transitions. [2022-07-19 21:50:42,083 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2022-07-19 21:50:42,083 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 4.857142857142857) internal successors, (68), 14 states have internal predecessors, (68), 2 states have call successors, (15), 2 states have call predecessors, (15), 4 states have return successors, (15), 2 states have call predecessors, (15), 2 states have call successors, (15) Word has length 120 [2022-07-19 21:50:42,084 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-19 21:50:42,084 INFO L225 Difference]: With dead ends: 191 [2022-07-19 21:50:42,084 INFO L226 Difference]: Without dead ends: 159 [2022-07-19 21:50:42,084 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 243 GetRequests, 226 SyntacticMatches, 0 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 12 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=131, Invalid=211, Unknown=0, NotChecked=0, Total=342 [2022-07-19 21:50:42,085 INFO L413 NwaCegarLoop]: 127 mSDtfsCounter, 24 mSDsluCounter, 632 mSDsCounter, 0 mSdLazyCounter, 57 mSolverCounterSat, 19 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 24 SdHoareTripleChecker+Valid, 759 SdHoareTripleChecker+Invalid, 76 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 19 IncrementalHoareTripleChecker+Valid, 57 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-07-19 21:50:42,085 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [24 Valid, 759 Invalid, 76 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [19 Valid, 57 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-07-19 21:50:42,086 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 159 states. [2022-07-19 21:50:42,095 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 159 to 159. [2022-07-19 21:50:42,096 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 159 states, 118 states have (on average 1.1610169491525424) internal successors, (137), 120 states have internal predecessors, (137), 23 states have call successors, (23), 15 states have call predecessors, (23), 17 states have return successors, (26), 23 states have call predecessors, (26), 22 states have call successors, (26) [2022-07-19 21:50:42,096 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 159 states to 159 states and 186 transitions. [2022-07-19 21:50:42,096 INFO L78 Accepts]: Start accepts. Automaton has 159 states and 186 transitions. Word has length 120 [2022-07-19 21:50:42,097 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-19 21:50:42,097 INFO L495 AbstractCegarLoop]: Abstraction has 159 states and 186 transitions. [2022-07-19 21:50:42,097 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 4.857142857142857) internal successors, (68), 14 states have internal predecessors, (68), 2 states have call successors, (15), 2 states have call predecessors, (15), 4 states have return successors, (15), 2 states have call predecessors, (15), 2 states have call successors, (15) [2022-07-19 21:50:42,097 INFO L276 IsEmpty]: Start isEmpty. Operand 159 states and 186 transitions. [2022-07-19 21:50:42,098 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 127 [2022-07-19 21:50:42,098 INFO L187 NwaCegarLoop]: Found error trace [2022-07-19 21:50:42,098 INFO L195 NwaCegarLoop]: trace histogram [10, 5, 4, 4, 4, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-19 21:50:42,122 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Forceful destruction successful, exit code 0 [2022-07-19 21:50:42,305 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2022-07-19 21:50:42,306 INFO L420 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-19 21:50:42,306 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-19 21:50:42,306 INFO L85 PathProgramCache]: Analyzing trace with hash 1651611811, now seen corresponding path program 4 times [2022-07-19 21:50:42,306 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-19 21:50:42,306 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2029792799] [2022-07-19 21:50:42,306 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 21:50:42,306 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-19 21:50:42,346 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-19 21:50:42,346 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [135297737] [2022-07-19 21:50:42,346 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-07-19 21:50:42,346 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 21:50:42,346 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-19 21:50:42,347 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-19 21:50:42,348 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2022-07-19 21:50:42,827 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-07-19 21:50:42,827 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-19 21:50:42,836 INFO L263 TraceCheckSpWp]: Trace formula consists of 2515 conjuncts, 99 conjunts are in the unsatisfiable core [2022-07-19 21:50:42,840 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-19 21:50:42,925 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 14 treesize of output 10 [2022-07-19 21:50:42,953 INFO L356 Elim1Store]: treesize reduction 21, result has 25.0 percent of original size [2022-07-19 21:50:42,953 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 21 treesize of output 20 [2022-07-19 21:50:42,983 INFO L356 Elim1Store]: treesize reduction 56, result has 23.3 percent of original size [2022-07-19 21:50:42,983 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 3 case distinctions, treesize of input 30 treesize of output 32 [2022-07-19 21:50:43,026 INFO L356 Elim1Store]: treesize reduction 104, result has 20.0 percent of original size [2022-07-19 21:50:43,026 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 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 39 treesize of output 44 [2022-07-19 21:50:43,092 INFO L356 Elim1Store]: treesize reduction 164, result has 17.6 percent of original size [2022-07-19 21:50:43,092 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 4 select indices, 4 select index equivalence classes, 0 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 10 case distinctions, treesize of input 48 treesize of output 56 [2022-07-19 21:50:43,176 INFO L356 Elim1Store]: treesize reduction 236, result has 15.7 percent of original size [2022-07-19 21:50:43,177 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 5 select indices, 5 select index equivalence classes, 0 disjoint index pairs (out of 10 index pairs), introduced 5 new quantified variables, introduced 15 case distinctions, treesize of input 57 treesize of output 68 [2022-07-19 21:50:43,345 INFO L356 Elim1Store]: treesize reduction 320, result has 14.2 percent of original size [2022-07-19 21:50:43,345 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 6 select indices, 6 select index equivalence classes, 0 disjoint index pairs (out of 15 index pairs), introduced 6 new quantified variables, introduced 21 case distinctions, treesize of input 66 treesize of output 80 [2022-07-19 21:50:43,686 INFO L356 Elim1Store]: treesize reduction 416, result has 13.0 percent of original size [2022-07-19 21:50:43,686 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 7 select indices, 7 select index equivalence classes, 0 disjoint index pairs (out of 21 index pairs), introduced 7 new quantified variables, introduced 28 case distinctions, treesize of input 75 treesize of output 92 [2022-07-19 21:50:53,873 INFO L356 Elim1Store]: treesize reduction 416, result has 13.0 percent of original size [2022-07-19 21:50:53,873 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 7 select indices, 7 select index equivalence classes, 0 disjoint index pairs (out of 21 index pairs), introduced 7 new quantified variables, introduced 28 case distinctions, treesize of input 75 treesize of output 92 [2022-07-19 21:51:00,059 INFO L356 Elim1Store]: treesize reduction 416, result has 13.0 percent of original size [2022-07-19 21:51:00,059 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 7 select indices, 7 select index equivalence classes, 0 disjoint index pairs (out of 21 index pairs), introduced 7 new quantified variables, introduced 28 case distinctions, treesize of input 75 treesize of output 92 [2022-07-19 21:51:07,381 INFO L134 CoverageAnalysis]: Checked inductivity of 124 backedges. 15 proven. 63 refuted. 0 times theorem prover too weak. 46 trivial. 0 not checked. [2022-07-19 21:51:07,382 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-19 21:51:10,508 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 277910 treesize of output 277718 [2022-07-19 21:51:21,334 WARN L233 SmtUtils]: Spent 10.83s on a formula simplification. DAG size of input: 292 DAG size of output: 265 (called from [L 813] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2022-07-19 21:51:42,156 WARN L233 SmtUtils]: Spent 6.68s on a formula simplification. DAG size of input: 228 DAG size of output: 232 (called from [L 813] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify)