./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/aws-c-common/aws_array_list_init_dynamic_harness.i --full-output --architecture 64bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version e19ca921 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_init_dynamic_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 ffbf3b1479afd9aaa2ec45fcd2782998a39316f97238379433376f7ba5094eb5 --- Real Ultimate output --- This is Ultimate 0.2.2-dev-e19ca92 [2021-12-22 13:53:40,522 INFO L177 SettingsManager]: Resetting all preferences to default values... [2021-12-22 13:53:40,524 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2021-12-22 13:53:40,583 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2021-12-22 13:53:40,583 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2021-12-22 13:53:40,586 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2021-12-22 13:53:40,587 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2021-12-22 13:53:40,588 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2021-12-22 13:53:40,590 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2021-12-22 13:53:40,593 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2021-12-22 13:53:40,594 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2021-12-22 13:53:40,594 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2021-12-22 13:53:40,595 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2021-12-22 13:53:40,597 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2021-12-22 13:53:40,598 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2021-12-22 13:53:40,601 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2021-12-22 13:53:40,601 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2021-12-22 13:53:40,602 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2021-12-22 13:53:40,603 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2021-12-22 13:53:40,607 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2021-12-22 13:53:40,608 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2021-12-22 13:53:40,609 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2021-12-22 13:53:40,610 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2021-12-22 13:53:40,611 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2021-12-22 13:53:40,616 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2021-12-22 13:53:40,616 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2021-12-22 13:53:40,617 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2021-12-22 13:53:40,617 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2021-12-22 13:53:40,618 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2021-12-22 13:53:40,618 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2021-12-22 13:53:40,619 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2021-12-22 13:53:40,619 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2021-12-22 13:53:40,620 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2021-12-22 13:53:40,621 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2021-12-22 13:53:40,622 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2021-12-22 13:53:40,622 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2021-12-22 13:53:40,622 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2021-12-22 13:53:40,622 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2021-12-22 13:53:40,623 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2021-12-22 13:53:40,623 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2021-12-22 13:53:40,624 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2021-12-22 13:53:40,624 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-64bit-Automizer_Default.epf [2021-12-22 13:53:40,638 INFO L113 SettingsManager]: Loading preferences was successful [2021-12-22 13:53:40,639 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2021-12-22 13:53:40,639 INFO L136 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2021-12-22 13:53:40,639 INFO L138 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2021-12-22 13:53:40,640 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2021-12-22 13:53:40,640 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2021-12-22 13:53:40,640 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2021-12-22 13:53:40,640 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2021-12-22 13:53:40,640 INFO L138 SettingsManager]: * Use SBE=true [2021-12-22 13:53:40,641 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2021-12-22 13:53:40,641 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2021-12-22 13:53:40,641 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2021-12-22 13:53:40,642 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2021-12-22 13:53:40,642 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2021-12-22 13:53:40,642 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2021-12-22 13:53:40,642 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2021-12-22 13:53:40,642 INFO L138 SettingsManager]: * Use constant arrays=true [2021-12-22 13:53:40,642 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2021-12-22 13:53:40,642 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2021-12-22 13:53:40,642 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2021-12-22 13:53:40,643 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2021-12-22 13:53:40,643 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2021-12-22 13:53:40,643 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2021-12-22 13:53:40,643 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2021-12-22 13:53:40,643 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2021-12-22 13:53:40,643 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2021-12-22 13:53:40,644 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2021-12-22 13:53:40,645 INFO L138 SettingsManager]: * Large block encoding in concurrent analysis=OFF [2021-12-22 13:53:40,645 INFO L138 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2021-12-22 13:53:40,645 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2021-12-22 13:53:40,645 INFO L138 SettingsManager]: * Trace refinement exception blacklist=NONE [2021-12-22 13:53:40,645 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 -> ffbf3b1479afd9aaa2ec45fcd2782998a39316f97238379433376f7ba5094eb5 [2021-12-22 13:53:40,826 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2021-12-22 13:53:40,845 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2021-12-22 13:53:40,847 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2021-12-22 13:53:40,848 INFO L271 PluginConnector]: Initializing CDTParser... [2021-12-22 13:53:40,848 INFO L275 PluginConnector]: CDTParser initialized [2021-12-22 13:53:40,849 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_init_dynamic_harness.i [2021-12-22 13:53:40,884 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/54bc5e8e4/ccac1715c57e4e26ac9d3a8829d8636c/FLAGe9976a0b4 [2021-12-22 13:53:41,439 INFO L306 CDTParser]: Found 1 translation units. [2021-12-22 13:53:41,441 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/aws-c-common/aws_array_list_init_dynamic_harness.i [2021-12-22 13:53:41,469 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/54bc5e8e4/ccac1715c57e4e26ac9d3a8829d8636c/FLAGe9976a0b4 [2021-12-22 13:53:41,924 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/54bc5e8e4/ccac1715c57e4e26ac9d3a8829d8636c [2021-12-22 13:53:41,933 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2021-12-22 13:53:41,934 INFO L131 ToolchainWalker]: Walking toolchain with 6 elements. [2021-12-22 13:53:41,935 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2021-12-22 13:53:41,935 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2021-12-22 13:53:41,940 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2021-12-22 13:53:41,945 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 22.12 01:53:41" (1/1) ... [2021-12-22 13:53:41,946 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@1fe749e1 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.12 01:53:41, skipping insertion in model container [2021-12-22 13:53:41,946 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 22.12 01:53:41" (1/1) ... [2021-12-22 13:53:41,950 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2021-12-22 13:53:42,008 INFO L178 MainTranslator]: Built tables and reachable declarations [2021-12-22 13:53:42,199 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_init_dynamic_harness.i[4501,4514] [2021-12-22 13:53:42,204 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_init_dynamic_harness.i[4561,4574] [2021-12-22 13:53:42,627 WARN L610 FunctionHandler]: implicit declaration of function __builtin_va_copy [2021-12-22 13:53:42,665 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-22 13:53:42,666 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-22 13:53:42,666 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-22 13:53:42,667 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-22 13:53:42,667 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-22 13:53:42,674 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-22 13:53:42,675 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-22 13:53:42,676 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-22 13:53:42,676 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-22 13:53:42,677 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-22 13:53:42,678 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-22 13:53:42,678 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-22 13:53:42,679 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-22 13:53:42,860 WARN L610 FunctionHandler]: implicit declaration of function __atomic_load_n [2021-12-22 13:53:42,860 WARN L610 FunctionHandler]: implicit declaration of function __atomic_store_n [2021-12-22 13:53:42,861 WARN L610 FunctionHandler]: implicit declaration of function __atomic_exchange_n [2021-12-22 13:53:42,862 WARN L610 FunctionHandler]: implicit declaration of function __atomic_compare_exchange_n [2021-12-22 13:53:42,863 WARN L610 FunctionHandler]: implicit declaration of function __atomic_fetch_add [2021-12-22 13:53:42,863 WARN L610 FunctionHandler]: implicit declaration of function __atomic_fetch_sub [2021-12-22 13:53:42,864 WARN L610 FunctionHandler]: implicit declaration of function __atomic_fetch_or [2021-12-22 13:53:42,864 WARN L610 FunctionHandler]: implicit declaration of function __atomic_fetch_and [2021-12-22 13:53:42,865 WARN L610 FunctionHandler]: implicit declaration of function __atomic_fetch_xor [2021-12-22 13:53:42,865 WARN L610 FunctionHandler]: implicit declaration of function __atomic_thread_fence [2021-12-22 13:53:42,932 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-22 13:53:42,936 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-22 13:53:43,026 INFO L209 PostProcessor]: Analyzing one entry point: main [2021-12-22 13:53:43,043 INFO L203 MainTranslator]: Completed pre-run [2021-12-22 13:53:43,052 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_init_dynamic_harness.i[4501,4514] [2021-12-22 13:53:43,052 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_init_dynamic_harness.i[4561,4574] [2021-12-22 13:53:43,072 WARN L610 FunctionHandler]: implicit declaration of function __builtin_va_copy [2021-12-22 13:53:43,081 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-22 13:53:43,082 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-22 13:53:43,082 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-22 13:53:43,083 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-22 13:53:43,083 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-22 13:53:43,087 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-22 13:53:43,088 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-22 13:53:43,089 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-22 13:53:43,089 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-22 13:53:43,090 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-22 13:53:43,090 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-22 13:53:43,090 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-22 13:53:43,091 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-22 13:53:43,115 WARN L610 FunctionHandler]: implicit declaration of function __atomic_load_n [2021-12-22 13:53:43,117 WARN L610 FunctionHandler]: implicit declaration of function __atomic_store_n [2021-12-22 13:53:43,118 WARN L610 FunctionHandler]: implicit declaration of function __atomic_exchange_n [2021-12-22 13:53:43,118 WARN L610 FunctionHandler]: implicit declaration of function __atomic_compare_exchange_n [2021-12-22 13:53:43,122 WARN L610 FunctionHandler]: implicit declaration of function __atomic_fetch_add [2021-12-22 13:53:43,122 WARN L610 FunctionHandler]: implicit declaration of function __atomic_fetch_sub [2021-12-22 13:53:43,123 WARN L610 FunctionHandler]: implicit declaration of function __atomic_fetch_or [2021-12-22 13:53:43,123 WARN L610 FunctionHandler]: implicit declaration of function __atomic_fetch_and [2021-12-22 13:53:43,124 WARN L610 FunctionHandler]: implicit declaration of function __atomic_fetch_xor [2021-12-22 13:53:43,124 WARN L610 FunctionHandler]: implicit declaration of function __atomic_thread_fence [2021-12-22 13:53:43,137 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-22 13:53:43,146 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-22 13:53:43,171 INFO L209 PostProcessor]: Analyzing one entry point: main [2021-12-22 13:53:43,307 INFO L208 MainTranslator]: Completed translation [2021-12-22 13:53:43,308 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.12 01:53:43 WrapperNode [2021-12-22 13:53:43,308 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2021-12-22 13:53:43,309 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2021-12-22 13:53:43,309 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2021-12-22 13:53:43,309 INFO L275 PluginConnector]: Boogie Procedure Inliner initialized [2021-12-22 13:53:43,314 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.12 01:53:43" (1/1) ... [2021-12-22 13:53:43,374 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.12 01:53:43" (1/1) ... [2021-12-22 13:53:43,421 INFO L137 Inliner]: procedures = 690, calls = 1561, calls flagged for inlining = 47, calls inlined = 6, statements flattened = 595 [2021-12-22 13:53:43,427 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2021-12-22 13:53:43,427 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2021-12-22 13:53:43,427 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2021-12-22 13:53:43,428 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2021-12-22 13:53:43,433 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.12 01:53:43" (1/1) ... [2021-12-22 13:53:43,433 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.12 01:53:43" (1/1) ... [2021-12-22 13:53:43,439 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.12 01:53:43" (1/1) ... [2021-12-22 13:53:43,452 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.12 01:53:43" (1/1) ... [2021-12-22 13:53:43,474 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.12 01:53:43" (1/1) ... [2021-12-22 13:53:43,478 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.12 01:53:43" (1/1) ... [2021-12-22 13:53:43,481 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.12 01:53:43" (1/1) ... [2021-12-22 13:53:43,487 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2021-12-22 13:53:43,488 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2021-12-22 13:53:43,488 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2021-12-22 13:53:43,488 INFO L275 PluginConnector]: RCFGBuilder initialized [2021-12-22 13:53:43,489 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.12 01:53:43" (1/1) ... [2021-12-22 13:53:43,506 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2021-12-22 13:53:43,515 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-22 13:53:43,555 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) [2021-12-22 13:53:43,573 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 [2021-12-22 13:53:43,589 INFO L130 BoogieDeclarations]: Found specification of procedure aws_is_mem_zeroed [2021-12-22 13:53:43,589 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_is_mem_zeroed [2021-12-22 13:53:43,590 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2021-12-22 13:53:43,590 INFO L130 BoogieDeclarations]: Found specification of procedure aws_array_list_is_valid [2021-12-22 13:53:43,591 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_array_list_is_valid [2021-12-22 13:53:43,591 INFO L130 BoogieDeclarations]: Found specification of procedure nondet_bool [2021-12-22 13:53:43,591 INFO L138 BoogieDeclarations]: Found implementation of procedure nondet_bool [2021-12-22 13:53:43,592 INFO L130 BoogieDeclarations]: Found specification of procedure aws_allocator_is_valid [2021-12-22 13:53:43,592 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_allocator_is_valid [2021-12-22 13:53:43,592 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2021-12-22 13:53:43,592 INFO L130 BoogieDeclarations]: Found specification of procedure aws_raise_error [2021-12-22 13:53:43,592 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_raise_error [2021-12-22 13:53:43,592 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2021-12-22 13:53:43,592 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2021-12-22 13:53:43,593 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnHeap [2021-12-22 13:53:43,593 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2021-12-22 13:53:43,593 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$ [2021-12-22 13:53:43,593 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2021-12-22 13:53:43,593 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2021-12-22 13:53:43,593 INFO L130 BoogieDeclarations]: Found specification of procedure bounded_malloc [2021-12-22 13:53:43,593 INFO L138 BoogieDeclarations]: Found implementation of procedure bounded_malloc [2021-12-22 13:53:43,593 INFO L130 BoogieDeclarations]: Found specification of procedure aws_mul_size_checked [2021-12-22 13:53:43,594 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_mul_size_checked [2021-12-22 13:53:43,594 INFO L130 BoogieDeclarations]: Found specification of procedure can_fail_malloc [2021-12-22 13:53:43,595 INFO L138 BoogieDeclarations]: Found implementation of procedure can_fail_malloc [2021-12-22 13:53:43,595 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.C_memset [2021-12-22 13:53:43,595 INFO L138 BoogieDeclarations]: Found implementation of procedure #Ultimate.C_memset [2021-12-22 13:53:43,595 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2021-12-22 13:53:43,595 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2021-12-22 13:53:43,595 INFO L130 BoogieDeclarations]: Found specification of procedure aws_mem_acquire [2021-12-22 13:53:43,595 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_mem_acquire [2021-12-22 13:53:43,595 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2021-12-22 13:53:43,596 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$ [2021-12-22 13:53:43,596 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$ [2021-12-22 13:53:43,596 INFO L130 BoogieDeclarations]: Found specification of procedure can_fail_allocator [2021-12-22 13:53:43,596 INFO L138 BoogieDeclarations]: Found implementation of procedure can_fail_allocator [2021-12-22 13:53:43,596 INFO L130 BoogieDeclarations]: Found specification of procedure __CPROVER_overflow_mult [2021-12-22 13:53:43,596 INFO L138 BoogieDeclarations]: Found implementation of procedure __CPROVER_overflow_mult [2021-12-22 13:53:43,596 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2021-12-22 13:53:43,596 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2021-12-22 13:53:43,823 INFO L234 CfgBuilder]: Building ICFG [2021-12-22 13:53:43,824 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2021-12-22 13:53:44,354 INFO L275 CfgBuilder]: Performing block encoding [2021-12-22 13:53:44,362 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2021-12-22 13:53:44,362 INFO L299 CfgBuilder]: Removed 3 assume(true) statements. [2021-12-22 13:53:44,364 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.12 01:53:44 BoogieIcfgContainer [2021-12-22 13:53:44,364 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2021-12-22 13:53:44,365 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2021-12-22 13:53:44,365 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2021-12-22 13:53:44,368 INFO L275 PluginConnector]: TraceAbstraction initialized [2021-12-22 13:53:44,368 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 22.12 01:53:41" (1/3) ... [2021-12-22 13:53:44,368 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3c1cff5d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.12 01:53:44, skipping insertion in model container [2021-12-22 13:53:44,369 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.12 01:53:43" (2/3) ... [2021-12-22 13:53:44,369 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3c1cff5d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.12 01:53:44, skipping insertion in model container [2021-12-22 13:53:44,369 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.12 01:53:44" (3/3) ... [2021-12-22 13:53:44,370 INFO L111 eAbstractionObserver]: Analyzing ICFG aws_array_list_init_dynamic_harness.i [2021-12-22 13:53:44,375 INFO L204 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2021-12-22 13:53:44,375 INFO L163 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2021-12-22 13:53:44,411 INFO L338 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2021-12-22 13:53:44,424 INFO L339 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, mLoopAccelerationTechnique=FAST_UPR [2021-12-22 13:53:44,425 INFO L340 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2021-12-22 13:53:44,439 INFO L276 IsEmpty]: Start isEmpty. Operand has 137 states, 88 states have (on average 1.2272727272727273) internal successors, (108), 89 states have internal predecessors, (108), 34 states have call successors, (34), 14 states have call predecessors, (34), 14 states have return successors, (34), 34 states have call predecessors, (34), 34 states have call successors, (34) [2021-12-22 13:53:44,445 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 55 [2021-12-22 13:53:44,445 INFO L506 BasicCegarLoop]: Found error trace [2021-12-22 13:53:44,446 INFO L514 BasicCegarLoop]: trace histogram [5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-22 13:53:44,448 INFO L402 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-22 13:53:44,451 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-22 13:53:44,452 INFO L85 PathProgramCache]: Analyzing trace with hash 1457384713, now seen corresponding path program 1 times [2021-12-22 13:53:44,457 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-22 13:53:44,458 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [46401040] [2021-12-22 13:53:44,458 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-22 13:53:44,459 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-22 13:53:44,655 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-22 13:53:44,812 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2021-12-22 13:53:44,813 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-22 13:53:44,831 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2021-12-22 13:53:44,833 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-22 13:53:44,840 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2021-12-22 13:53:44,841 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-22 13:53:44,847 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2021-12-22 13:53:44,848 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-22 13:53:44,862 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 23 [2021-12-22 13:53:44,863 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-22 13:53:44,886 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 28 [2021-12-22 13:53:44,887 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-22 13:53:44,905 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 35 [2021-12-22 13:53:44,917 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-22 13:53:44,918 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [46401040] [2021-12-22 13:53:44,918 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unsupported non-linear arithmetic [2021-12-22 13:53:44,918 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1457303990] [2021-12-22 13:53:44,918 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-22 13:53:44,918 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-22 13:53:44,919 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-22 13:53:44,931 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) [2021-12-22 13:53:44,932 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2021-12-22 13:53:45,234 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-22 13:53:45,241 INFO L263 TraceCheckSpWp]: Trace formula consists of 1973 conjuncts, 1 conjunts are in the unsatisfiable core [2021-12-22 13:53:45,246 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-22 13:53:45,337 INFO L134 CoverageAnalysis]: Checked inductivity of 40 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2021-12-22 13:53:45,337 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-22 13:53:45,338 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1457303990] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-22 13:53:45,338 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-22 13:53:45,338 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2021-12-22 13:53:45,340 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1267154874] [2021-12-22 13:53:45,340 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-22 13:53:45,343 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2021-12-22 13:53:45,343 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-22 13:53:45,359 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2021-12-22 13:53:45,360 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2021-12-22 13:53:45,362 INFO L87 Difference]: Start difference. First operand has 137 states, 88 states have (on average 1.2272727272727273) internal successors, (108), 89 states have internal predecessors, (108), 34 states have call successors, (34), 14 states have call predecessors, (34), 14 states have return successors, (34), 34 states have call predecessors, (34), 34 states have call successors, (34) Second operand has 2 states, 2 states have (on average 12.5) internal successors, (25), 2 states have internal predecessors, (25), 2 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2021-12-22 13:53:45,385 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-22 13:53:45,386 INFO L93 Difference]: Finished difference Result 269 states and 367 transitions. [2021-12-22 13:53:45,396 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2021-12-22 13:53:45,397 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 12.5) internal successors, (25), 2 states have internal predecessors, (25), 2 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) Word has length 54 [2021-12-22 13:53:45,398 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-22 13:53:45,403 INFO L225 Difference]: With dead ends: 269 [2021-12-22 13:53:45,403 INFO L226 Difference]: Without dead ends: 130 [2021-12-22 13:53:45,406 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 68 GetRequests, 67 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2021-12-22 13:53:45,408 INFO L933 BasicCegarLoop]: 171 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 0 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 171 SdHoareTripleChecker+Invalid, 0 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 0 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-12-22 13:53:45,408 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [0 Valid, 171 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-12-22 13:53:45,419 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 130 states. [2021-12-22 13:53:45,434 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 130 to 130. [2021-12-22 13:53:45,435 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 130 states, 81 states have (on average 1.1975308641975309) internal successors, (97), 83 states have internal predecessors, (97), 34 states have call successors, (34), 14 states have call predecessors, (34), 14 states have return successors, (32), 32 states have call predecessors, (32), 32 states have call successors, (32) [2021-12-22 13:53:45,436 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 130 states to 130 states and 163 transitions. [2021-12-22 13:53:45,437 INFO L78 Accepts]: Start accepts. Automaton has 130 states and 163 transitions. Word has length 54 [2021-12-22 13:53:45,438 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-22 13:53:45,438 INFO L470 AbstractCegarLoop]: Abstraction has 130 states and 163 transitions. [2021-12-22 13:53:45,438 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 12.5) internal successors, (25), 2 states have internal predecessors, (25), 2 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2021-12-22 13:53:45,439 INFO L276 IsEmpty]: Start isEmpty. Operand 130 states and 163 transitions. [2021-12-22 13:53:45,440 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 61 [2021-12-22 13:53:45,440 INFO L506 BasicCegarLoop]: Found error trace [2021-12-22 13:53:45,440 INFO L514 BasicCegarLoop]: trace histogram [5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-22 13:53:45,462 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2021-12-22 13:53:45,659 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable0 [2021-12-22 13:53:45,660 INFO L402 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-22 13:53:45,660 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-22 13:53:45,660 INFO L85 PathProgramCache]: Analyzing trace with hash 1798443805, now seen corresponding path program 1 times [2021-12-22 13:53:45,660 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-22 13:53:45,660 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1956123508] [2021-12-22 13:53:45,660 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-22 13:53:45,661 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-22 13:53:45,702 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-22 13:53:45,702 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1656776683] [2021-12-22 13:53:45,702 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-22 13:53:45,703 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-22 13:53:45,703 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-22 13:53:45,704 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) [2021-12-22 13:53:45,731 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2021-12-22 13:53:46,000 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-22 13:53:46,006 INFO L263 TraceCheckSpWp]: Trace formula consists of 2001 conjuncts, 15 conjunts are in the unsatisfiable core [2021-12-22 13:53:46,009 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-22 13:53:46,158 INFO L134 CoverageAnalysis]: Checked inductivity of 40 backedges. 6 proven. 6 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2021-12-22 13:53:46,158 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-22 13:53:46,291 INFO L134 CoverageAnalysis]: Checked inductivity of 40 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2021-12-22 13:53:46,291 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-22 13:53:46,291 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1956123508] [2021-12-22 13:53:46,292 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-22 13:53:46,292 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1656776683] [2021-12-22 13:53:46,292 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1656776683] provided 1 perfect and 1 imperfect interpolant sequences [2021-12-22 13:53:46,292 INFO L186 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2021-12-22 13:53:46,292 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [10] total 12 [2021-12-22 13:53:46,292 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1535233246] [2021-12-22 13:53:46,292 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-22 13:53:46,293 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2021-12-22 13:53:46,293 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-22 13:53:46,294 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2021-12-22 13:53:46,294 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=23, Invalid=109, Unknown=0, NotChecked=0, Total=132 [2021-12-22 13:53:46,294 INFO L87 Difference]: Start difference. First operand 130 states and 163 transitions. Second operand has 5 states, 4 states have (on average 7.25) internal successors, (29), 4 states have internal predecessors, (29), 2 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (9), 1 states have call predecessors, (9), 1 states have call successors, (9) [2021-12-22 13:53:46,356 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-22 13:53:46,356 INFO L93 Difference]: Finished difference Result 138 states and 171 transitions. [2021-12-22 13:53:46,357 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2021-12-22 13:53:46,357 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 7.25) internal successors, (29), 4 states have internal predecessors, (29), 2 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (9), 1 states have call predecessors, (9), 1 states have call successors, (9) Word has length 60 [2021-12-22 13:53:46,357 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-22 13:53:46,359 INFO L225 Difference]: With dead ends: 138 [2021-12-22 13:53:46,359 INFO L226 Difference]: Without dead ends: 136 [2021-12-22 13:53:46,359 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 119 GetRequests, 108 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=27, Invalid=129, Unknown=0, NotChecked=0, Total=156 [2021-12-22 13:53:46,360 INFO L933 BasicCegarLoop]: 161 mSDtfsCounter, 6 mSDsluCounter, 468 mSDsCounter, 0 mSdLazyCounter, 23 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 629 SdHoareTripleChecker+Invalid, 24 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 23 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-12-22 13:53:46,360 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [7 Valid, 629 Invalid, 24 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 23 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-12-22 13:53:46,361 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 136 states. [2021-12-22 13:53:46,368 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 136 to 135. [2021-12-22 13:53:46,368 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 135 states, 84 states have (on average 1.1904761904761905) internal successors, (100), 87 states have internal predecessors, (100), 35 states have call successors, (35), 15 states have call predecessors, (35), 15 states have return successors, (33), 32 states have call predecessors, (33), 33 states have call successors, (33) [2021-12-22 13:53:46,369 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 135 states to 135 states and 168 transitions. [2021-12-22 13:53:46,370 INFO L78 Accepts]: Start accepts. Automaton has 135 states and 168 transitions. Word has length 60 [2021-12-22 13:53:46,370 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-22 13:53:46,370 INFO L470 AbstractCegarLoop]: Abstraction has 135 states and 168 transitions. [2021-12-22 13:53:46,370 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 7.25) internal successors, (29), 4 states have internal predecessors, (29), 2 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (9), 1 states have call predecessors, (9), 1 states have call successors, (9) [2021-12-22 13:53:46,370 INFO L276 IsEmpty]: Start isEmpty. Operand 135 states and 168 transitions. [2021-12-22 13:53:46,371 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 61 [2021-12-22 13:53:46,372 INFO L506 BasicCegarLoop]: Found error trace [2021-12-22 13:53:46,372 INFO L514 BasicCegarLoop]: trace histogram [5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-22 13:53:46,415 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2021-12-22 13:53:46,591 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable1 [2021-12-22 13:53:46,592 INFO L402 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-22 13:53:46,592 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-22 13:53:46,592 INFO L85 PathProgramCache]: Analyzing trace with hash 1800290847, now seen corresponding path program 1 times [2021-12-22 13:53:46,593 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-22 13:53:46,593 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1935034574] [2021-12-22 13:53:46,593 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-22 13:53:46,593 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-22 13:53:46,633 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-22 13:53:46,634 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1279328527] [2021-12-22 13:53:46,634 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-22 13:53:46,634 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-22 13:53:46,634 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-22 13:53:46,635 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) [2021-12-22 13:53:46,636 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2021-12-22 13:53:46,927 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-22 13:53:46,933 INFO L263 TraceCheckSpWp]: Trace formula consists of 2006 conjuncts, 5 conjunts are in the unsatisfiable core [2021-12-22 13:53:46,936 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-22 13:53:47,015 INFO L134 CoverageAnalysis]: Checked inductivity of 40 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2021-12-22 13:53:47,015 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-22 13:53:47,016 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-22 13:53:47,016 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1935034574] [2021-12-22 13:53:47,016 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-22 13:53:47,016 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1279328527] [2021-12-22 13:53:47,016 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1279328527] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-22 13:53:47,016 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-22 13:53:47,016 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2021-12-22 13:53:47,017 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [282188850] [2021-12-22 13:53:47,017 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-22 13:53:47,017 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2021-12-22 13:53:47,017 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-22 13:53:47,017 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2021-12-22 13:53:47,018 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2021-12-22 13:53:47,018 INFO L87 Difference]: Start difference. First operand 135 states and 168 transitions. Second operand has 4 states, 4 states have (on average 7.25) internal successors, (29), 4 states have internal predecessors, (29), 2 states have call successors, (10), 2 states have call predecessors, (10), 3 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) [2021-12-22 13:53:47,035 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-22 13:53:47,035 INFO L93 Difference]: Finished difference Result 258 states and 318 transitions. [2021-12-22 13:53:47,036 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2021-12-22 13:53:47,036 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 7.25) internal successors, (29), 4 states have internal predecessors, (29), 2 states have call successors, (10), 2 states have call predecessors, (10), 3 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) Word has length 60 [2021-12-22 13:53:47,036 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-22 13:53:47,038 INFO L225 Difference]: With dead ends: 258 [2021-12-22 13:53:47,038 INFO L226 Difference]: Without dead ends: 136 [2021-12-22 13:53:47,039 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 60 GetRequests, 57 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2021-12-22 13:53:47,039 INFO L933 BasicCegarLoop]: 161 mSDtfsCounter, 2 mSDsluCounter, 320 mSDsCounter, 0 mSdLazyCounter, 7 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 481 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 [2021-12-22 13:53:47,040 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 481 Invalid, 7 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 7 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-12-22 13:53:47,040 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 136 states. [2021-12-22 13:53:47,046 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 136 to 136. [2021-12-22 13:53:47,046 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 136 states, 85 states have (on average 1.188235294117647) internal successors, (101), 88 states have internal predecessors, (101), 35 states have call successors, (35), 15 states have call predecessors, (35), 15 states have return successors, (33), 32 states have call predecessors, (33), 33 states have call successors, (33) [2021-12-22 13:53:47,047 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 136 states to 136 states and 169 transitions. [2021-12-22 13:53:47,047 INFO L78 Accepts]: Start accepts. Automaton has 136 states and 169 transitions. Word has length 60 [2021-12-22 13:53:47,047 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-22 13:53:47,048 INFO L470 AbstractCegarLoop]: Abstraction has 136 states and 169 transitions. [2021-12-22 13:53:47,048 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 7.25) internal successors, (29), 4 states have internal predecessors, (29), 2 states have call successors, (10), 2 states have call predecessors, (10), 3 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) [2021-12-22 13:53:47,048 INFO L276 IsEmpty]: Start isEmpty. Operand 136 states and 169 transitions. [2021-12-22 13:53:47,049 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 62 [2021-12-22 13:53:47,049 INFO L506 BasicCegarLoop]: Found error trace [2021-12-22 13:53:47,049 INFO L514 BasicCegarLoop]: trace histogram [5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-22 13:53:47,070 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2021-12-22 13:53:47,267 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-22 13:53:47,268 INFO L402 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-22 13:53:47,268 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-22 13:53:47,268 INFO L85 PathProgramCache]: Analyzing trace with hash 169080727, now seen corresponding path program 1 times [2021-12-22 13:53:47,268 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-22 13:53:47,268 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1396520243] [2021-12-22 13:53:47,268 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-22 13:53:47,268 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-22 13:53:47,349 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-22 13:53:47,349 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1437372012] [2021-12-22 13:53:47,350 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-22 13:53:47,350 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-22 13:53:47,350 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-22 13:53:47,351 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) [2021-12-22 13:53:47,367 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2021-12-22 13:53:47,683 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-22 13:53:47,690 INFO L263 TraceCheckSpWp]: Trace formula consists of 2025 conjuncts, 7 conjunts are in the unsatisfiable core [2021-12-22 13:53:47,692 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-22 13:53:47,776 INFO L134 CoverageAnalysis]: Checked inductivity of 41 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2021-12-22 13:53:47,776 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-22 13:53:47,920 INFO L134 CoverageAnalysis]: Checked inductivity of 41 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2021-12-22 13:53:47,920 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-22 13:53:47,920 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1396520243] [2021-12-22 13:53:47,920 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-22 13:53:47,921 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1437372012] [2021-12-22 13:53:47,921 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1437372012] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-22 13:53:47,921 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-12-22 13:53:47,921 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 8 [2021-12-22 13:53:47,921 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1026384840] [2021-12-22 13:53:47,921 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-12-22 13:53:47,922 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2021-12-22 13:53:47,922 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-22 13:53:47,922 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2021-12-22 13:53:47,922 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=22, Invalid=34, Unknown=0, NotChecked=0, Total=56 [2021-12-22 13:53:47,922 INFO L87 Difference]: Start difference. First operand 136 states and 169 transitions. Second operand has 8 states, 8 states have (on average 5.0) internal successors, (40), 8 states have internal predecessors, (40), 2 states have call successors, (12), 2 states have call predecessors, (12), 4 states have return successors, (12), 2 states have call predecessors, (12), 2 states have call successors, (12) [2021-12-22 13:53:47,985 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-22 13:53:47,985 INFO L93 Difference]: Finished difference Result 263 states and 325 transitions. [2021-12-22 13:53:47,985 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2021-12-22 13:53:47,986 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 5.0) internal successors, (40), 8 states have internal predecessors, (40), 2 states have call successors, (12), 2 states have call predecessors, (12), 4 states have return successors, (12), 2 states have call predecessors, (12), 2 states have call successors, (12) Word has length 61 [2021-12-22 13:53:47,986 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-22 13:53:47,987 INFO L225 Difference]: With dead ends: 263 [2021-12-22 13:53:47,987 INFO L226 Difference]: Without dead ends: 139 [2021-12-22 13:53:47,987 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 122 GetRequests, 114 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=38, Invalid=52, Unknown=0, NotChecked=0, Total=90 [2021-12-22 13:53:47,988 INFO L933 BasicCegarLoop]: 161 mSDtfsCounter, 11 mSDsluCounter, 323 mSDsCounter, 0 mSdLazyCounter, 20 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 484 SdHoareTripleChecker+Invalid, 24 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 20 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-12-22 13:53:47,988 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [11 Valid, 484 Invalid, 24 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 20 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-12-22 13:53:47,990 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 139 states. [2021-12-22 13:53:47,996 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 139 to 139. [2021-12-22 13:53:47,996 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 139 states, 88 states have (on average 1.1818181818181819) internal successors, (104), 91 states have internal predecessors, (104), 35 states have call successors, (35), 15 states have call predecessors, (35), 15 states have return successors, (33), 32 states have call predecessors, (33), 33 states have call successors, (33) [2021-12-22 13:53:47,997 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 139 states to 139 states and 172 transitions. [2021-12-22 13:53:47,997 INFO L78 Accepts]: Start accepts. Automaton has 139 states and 172 transitions. Word has length 61 [2021-12-22 13:53:47,997 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-22 13:53:47,997 INFO L470 AbstractCegarLoop]: Abstraction has 139 states and 172 transitions. [2021-12-22 13:53:47,998 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 5.0) internal successors, (40), 8 states have internal predecessors, (40), 2 states have call successors, (12), 2 states have call predecessors, (12), 4 states have return successors, (12), 2 states have call predecessors, (12), 2 states have call successors, (12) [2021-12-22 13:53:47,998 INFO L276 IsEmpty]: Start isEmpty. Operand 139 states and 172 transitions. [2021-12-22 13:53:47,998 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 65 [2021-12-22 13:53:47,998 INFO L506 BasicCegarLoop]: Found error trace [2021-12-22 13:53:47,998 INFO L514 BasicCegarLoop]: trace histogram [5, 5, 5, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-22 13:53:48,019 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2021-12-22 13:53:48,199 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-22 13:53:48,199 INFO L402 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-22 13:53:48,199 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-22 13:53:48,199 INFO L85 PathProgramCache]: Analyzing trace with hash -909385697, now seen corresponding path program 2 times [2021-12-22 13:53:48,200 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-22 13:53:48,200 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1330791363] [2021-12-22 13:53:48,200 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-22 13:53:48,200 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-22 13:53:48,292 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-22 13:53:48,307 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1608939823] [2021-12-22 13:53:48,307 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2021-12-22 13:53:48,307 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-22 13:53:48,308 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-22 13:53:48,309 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) [2021-12-22 13:53:48,330 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2021-12-22 13:53:50,584 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2021-12-22 13:53:50,584 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-12-22 13:53:50,598 INFO L263 TraceCheckSpWp]: Trace formula consists of 2082 conjuncts, 14 conjunts are in the unsatisfiable core [2021-12-22 13:53:50,600 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-22 13:53:50,746 INFO L134 CoverageAnalysis]: Checked inductivity of 50 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2021-12-22 13:53:50,747 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-22 13:53:51,051 INFO L134 CoverageAnalysis]: Checked inductivity of 50 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2021-12-22 13:53:51,051 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-22 13:53:51,052 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1330791363] [2021-12-22 13:53:51,052 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-22 13:53:51,052 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1608939823] [2021-12-22 13:53:51,052 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1608939823] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-22 13:53:51,052 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-12-22 13:53:51,052 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 14 [2021-12-22 13:53:51,052 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [486451941] [2021-12-22 13:53:51,053 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-12-22 13:53:51,053 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2021-12-22 13:53:51,053 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-22 13:53:51,053 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2021-12-22 13:53:51,054 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=61, Invalid=121, Unknown=0, NotChecked=0, Total=182 [2021-12-22 13:53:51,054 INFO L87 Difference]: Start difference. First operand 139 states and 172 transitions. Second operand has 14 states, 14 states have (on average 3.2857142857142856) internal successors, (46), 14 states have internal predecessors, (46), 2 states have call successors, (12), 2 states have call predecessors, (12), 4 states have return successors, (12), 2 states have call predecessors, (12), 2 states have call successors, (12) [2021-12-22 13:53:51,897 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-22 13:53:51,898 INFO L93 Difference]: Finished difference Result 269 states and 334 transitions. [2021-12-22 13:53:51,898 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2021-12-22 13:53:51,898 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 3.2857142857142856) internal successors, (46), 14 states have internal predecessors, (46), 2 states have call successors, (12), 2 states have call predecessors, (12), 4 states have return successors, (12), 2 states have call predecessors, (12), 2 states have call successors, (12) Word has length 64 [2021-12-22 13:53:51,899 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-22 13:53:51,899 INFO L225 Difference]: With dead ends: 269 [2021-12-22 13:53:51,900 INFO L226 Difference]: Without dead ends: 145 [2021-12-22 13:53:51,900 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 132 GetRequests, 114 SyntacticMatches, 0 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 18 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=145, Invalid=235, Unknown=0, NotChecked=0, Total=380 [2021-12-22 13:53:51,901 INFO L933 BasicCegarLoop]: 160 mSDtfsCounter, 25 mSDsluCounter, 1425 mSDsCounter, 0 mSdLazyCounter, 71 mSolverCounterSat, 22 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 25 SdHoareTripleChecker+Valid, 1585 SdHoareTripleChecker+Invalid, 93 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 22 IncrementalHoareTripleChecker+Valid, 71 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2021-12-22 13:53:51,901 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [25 Valid, 1585 Invalid, 93 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [22 Valid, 71 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2021-12-22 13:53:51,902 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 145 states. [2021-12-22 13:53:51,908 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 145 to 145. [2021-12-22 13:53:51,909 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 145 states, 94 states have (on average 1.1702127659574468) internal successors, (110), 97 states have internal predecessors, (110), 35 states have call successors, (35), 15 states have call predecessors, (35), 15 states have return successors, (33), 32 states have call predecessors, (33), 33 states have call successors, (33) [2021-12-22 13:53:51,909 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 145 states to 145 states and 178 transitions. [2021-12-22 13:53:51,910 INFO L78 Accepts]: Start accepts. Automaton has 145 states and 178 transitions. Word has length 64 [2021-12-22 13:53:51,910 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-22 13:53:51,910 INFO L470 AbstractCegarLoop]: Abstraction has 145 states and 178 transitions. [2021-12-22 13:53:51,910 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 3.2857142857142856) internal successors, (46), 14 states have internal predecessors, (46), 2 states have call successors, (12), 2 states have call predecessors, (12), 4 states have return successors, (12), 2 states have call predecessors, (12), 2 states have call successors, (12) [2021-12-22 13:53:51,910 INFO L276 IsEmpty]: Start isEmpty. Operand 145 states and 178 transitions. [2021-12-22 13:53:51,911 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 71 [2021-12-22 13:53:51,911 INFO L506 BasicCegarLoop]: Found error trace [2021-12-22 13:53:51,911 INFO L514 BasicCegarLoop]: trace histogram [10, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-22 13:53:51,936 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2021-12-22 13:53:52,128 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-22 13:53:52,128 INFO L402 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-22 13:53:52,129 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-22 13:53:52,129 INFO L85 PathProgramCache]: Analyzing trace with hash -555602657, now seen corresponding path program 3 times [2021-12-22 13:53:52,129 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-22 13:53:52,129 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [676977702] [2021-12-22 13:53:52,129 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-22 13:53:52,129 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-22 13:53:52,170 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-22 13:53:52,170 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1865693684] [2021-12-22 13:53:52,170 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2021-12-22 13:53:52,170 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-22 13:53:52,171 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-22 13:53:52,186 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) [2021-12-22 13:53:52,187 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2021-12-22 13:54:00,123 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2021-12-22 13:54:00,123 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-12-22 13:54:00,148 INFO L263 TraceCheckSpWp]: Trace formula consists of 2196 conjuncts, 60 conjunts are in the unsatisfiable core [2021-12-22 13:54:00,152 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-22 13:54:00,193 INFO L387 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2021-12-22 13:54:00,525 INFO L387 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 13 treesize of output 9 [2021-12-22 13:54:00,561 INFO L353 Elim1Store]: treesize reduction 27, result has 25.0 percent of original size [2021-12-22 13:54:00,561 INFO L387 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 22 [2021-12-22 13:54:00,660 INFO L353 Elim1Store]: treesize reduction 4, result has 50.0 percent of original size [2021-12-22 13:54:00,661 INFO L387 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 11 treesize of output 11 [2021-12-22 13:54:00,711 WARN L860 $PredicateComparison]: unable to prove that (exists ((v_ArrVal_604 (Array Int Int))) (= (store |c_old(#memory_int)| |c_aws_mul_size_checked_#in~r#1.base| v_ArrVal_604) |c_#memory_int|)) is different from true [2021-12-22 13:54:00,742 INFO L387 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 18 [2021-12-22 13:54:00,778 INFO L387 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 55 treesize of output 49 [2021-12-22 13:54:00,781 INFO L387 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 157 treesize of output 145 [2021-12-22 13:54:00,799 INFO L134 CoverageAnalysis]: Checked inductivity of 95 backedges. 0 proven. 55 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2021-12-22 13:54:00,799 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-22 13:54:00,888 WARN L838 $PredicateComparison]: unable to prove that (forall ((v_ArrVal_606 Int) (v_ArrVal_605 Int) (v_ArrVal_610 (Array Int Int))) (= (mod (select (store (store (select (store |c_#memory_int| |c_ULTIMATE.start_aws_array_list_init_dynamic_~#allocation_size~0#1.base| v_ArrVal_610) |c_ULTIMATE.start_aws_array_list_init_dynamic_~list#1.base|) (+ |c_ULTIMATE.start_aws_array_list_init_dynamic_~list#1.offset| 24) v_ArrVal_606) |c_ULTIMATE.start_aws_array_list_init_dynamic_~list#1.offset| v_ArrVal_605) (+ |c_ULTIMATE.start_aws_array_list_init_dynamic_~list#1.offset| 8)) 18446744073709551616) 0)) is different from false [2021-12-22 13:54:00,889 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-22 13:54:00,889 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [676977702] [2021-12-22 13:54:00,889 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-22 13:54:00,889 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1865693684] [2021-12-22 13:54:00,890 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1865693684] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-22 13:54:00,890 INFO L186 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2021-12-22 13:54:00,890 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [23] total 23 [2021-12-22 13:54:00,890 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [712717075] [2021-12-22 13:54:00,890 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2021-12-22 13:54:00,890 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2021-12-22 13:54:00,890 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-22 13:54:00,891 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2021-12-22 13:54:00,891 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=69, Invalid=443, Unknown=2, NotChecked=86, Total=600 [2021-12-22 13:54:00,891 INFO L87 Difference]: Start difference. First operand 145 states and 178 transitions. Second operand has 23 states, 21 states have (on average 1.8571428571428572) internal successors, (39), 22 states have internal predecessors, (39), 5 states have call successors, (10), 4 states have call predecessors, (10), 4 states have return successors, (9), 5 states have call predecessors, (9), 4 states have call successors, (9) [2021-12-22 13:54:01,361 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-22 13:54:01,361 INFO L93 Difference]: Finished difference Result 277 states and 360 transitions. [2021-12-22 13:54:01,361 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 28 states. [2021-12-22 13:54:01,361 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 21 states have (on average 1.8571428571428572) internal successors, (39), 22 states have internal predecessors, (39), 5 states have call successors, (10), 4 states have call predecessors, (10), 4 states have return successors, (9), 5 states have call predecessors, (9), 4 states have call successors, (9) Word has length 70 [2021-12-22 13:54:01,362 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-22 13:54:01,363 INFO L225 Difference]: With dead ends: 277 [2021-12-22 13:54:01,363 INFO L226 Difference]: Without dead ends: 218 [2021-12-22 13:54:01,364 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 85 GetRequests, 44 SyntacticMatches, 12 SemanticMatches, 29 ConstructedPredicates, 2 IntricatePredicates, 0 DeprecatedPredicates, 163 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=104, Invalid=714, Unknown=2, NotChecked=110, Total=930 [2021-12-22 13:54:01,365 INFO L933 BasicCegarLoop]: 164 mSDtfsCounter, 97 mSDsluCounter, 1006 mSDsCounter, 0 mSdLazyCounter, 647 mSolverCounterSat, 68 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 121 SdHoareTripleChecker+Valid, 1170 SdHoareTripleChecker+Invalid, 1844 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 68 IncrementalHoareTripleChecker+Valid, 647 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 1129 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2021-12-22 13:54:01,365 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [121 Valid, 1170 Invalid, 1844 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [68 Valid, 647 Invalid, 0 Unknown, 1129 Unchecked, 0.4s Time] [2021-12-22 13:54:01,365 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 218 states. [2021-12-22 13:54:01,375 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 218 to 164. [2021-12-22 13:54:01,375 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 164 states, 109 states have (on average 1.1743119266055047) internal successors, (128), 112 states have internal predecessors, (128), 36 states have call successors, (36), 17 states have call predecessors, (36), 18 states have return successors, (35), 34 states have call predecessors, (35), 34 states have call successors, (35) [2021-12-22 13:54:01,376 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 164 states to 164 states and 199 transitions. [2021-12-22 13:54:01,376 INFO L78 Accepts]: Start accepts. Automaton has 164 states and 199 transitions. Word has length 70 [2021-12-22 13:54:01,376 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-22 13:54:01,376 INFO L470 AbstractCegarLoop]: Abstraction has 164 states and 199 transitions. [2021-12-22 13:54:01,377 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 21 states have (on average 1.8571428571428572) internal successors, (39), 22 states have internal predecessors, (39), 5 states have call successors, (10), 4 states have call predecessors, (10), 4 states have return successors, (9), 5 states have call predecessors, (9), 4 states have call successors, (9) [2021-12-22 13:54:01,377 INFO L276 IsEmpty]: Start isEmpty. Operand 164 states and 199 transitions. [2021-12-22 13:54:01,377 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 72 [2021-12-22 13:54:01,378 INFO L506 BasicCegarLoop]: Found error trace [2021-12-22 13:54:01,378 INFO L514 BasicCegarLoop]: trace histogram [11, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-22 13:54:01,411 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2021-12-22 13:54:01,614 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-22 13:54:01,614 INFO L402 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-22 13:54:01,615 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-22 13:54:01,615 INFO L85 PathProgramCache]: Analyzing trace with hash 150826135, now seen corresponding path program 4 times [2021-12-22 13:54:01,615 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-22 13:54:01,615 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2115221387] [2021-12-22 13:54:01,615 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-22 13:54:01,615 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-22 13:54:01,687 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-22 13:54:01,688 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1472390223] [2021-12-22 13:54:01,688 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2021-12-22 13:54:01,688 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-22 13:54:01,688 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-22 13:54:01,703 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) [2021-12-22 13:54:01,751 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2021-12-22 13:54:02,052 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2021-12-22 13:54:02,052 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-12-22 13:54:02,059 INFO L263 TraceCheckSpWp]: Trace formula consists of 2215 conjuncts, 68 conjunts are in the unsatisfiable core [2021-12-22 13:54:02,063 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-22 13:54:02,067 INFO L387 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2021-12-22 13:54:02,362 INFO L387 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 [2021-12-22 13:54:02,394 INFO L353 Elim1Store]: treesize reduction 27, result has 25.0 percent of original size [2021-12-22 13:54:02,394 INFO L387 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 22 [2021-12-22 13:54:02,426 INFO L353 Elim1Store]: treesize reduction 27, result has 25.0 percent of original size [2021-12-22 13:54:02,427 INFO L387 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 22 [2021-12-22 13:54:02,505 INFO L353 Elim1Store]: treesize reduction 4, result has 50.0 percent of original size [2021-12-22 13:54:02,505 INFO L387 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 11 treesize of output 11 [2021-12-22 13:54:02,560 WARN L860 $PredicateComparison]: unable to prove that (exists ((v_ArrVal_852 (Array Int Int))) (= (store |c_old(#memory_int)| |c_aws_mul_size_checked_#in~r#1.base| v_ArrVal_852) |c_#memory_int|)) is different from true [2021-12-22 13:54:02,571 INFO L387 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 18 [2021-12-22 13:54:02,605 INFO L387 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 45 treesize of output 39 [2021-12-22 13:54:02,607 INFO L387 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 27 treesize of output 21 [2021-12-22 13:54:02,623 INFO L134 CoverageAnalysis]: Checked inductivity of 106 backedges. 0 proven. 66 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2021-12-22 13:54:02,623 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-22 13:54:02,703 WARN L838 $PredicateComparison]: unable to prove that (forall ((v_ArrVal_858 (Array Int Int)) (v_ArrVal_854 Int) (v_ArrVal_853 Int)) (= (mod (select (store (store (select (store |c_#memory_int| |c_ULTIMATE.start_aws_array_list_init_dynamic_~#allocation_size~0#1.base| v_ArrVal_858) |c_ULTIMATE.start_aws_array_list_init_dynamic_~list#1.base|) (+ |c_ULTIMATE.start_aws_array_list_init_dynamic_~list#1.offset| 24) v_ArrVal_854) |c_ULTIMATE.start_aws_array_list_init_dynamic_~list#1.offset| v_ArrVal_853) (+ |c_ULTIMATE.start_aws_array_list_init_dynamic_~list#1.offset| 8)) 18446744073709551616) 0)) is different from false [2021-12-22 13:54:02,704 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-22 13:54:02,704 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2115221387] [2021-12-22 13:54:02,704 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-22 13:54:02,704 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1472390223] [2021-12-22 13:54:02,704 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1472390223] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-22 13:54:02,704 INFO L186 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2021-12-22 13:54:02,704 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [24] total 24 [2021-12-22 13:54:02,704 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [565339822] [2021-12-22 13:54:02,704 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2021-12-22 13:54:02,705 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 24 states [2021-12-22 13:54:02,705 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-22 13:54:02,705 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2021-12-22 13:54:02,705 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=73, Invalid=485, Unknown=2, NotChecked=90, Total=650 [2021-12-22 13:54:02,705 INFO L87 Difference]: Start difference. First operand 164 states and 199 transitions. Second operand has 24 states, 22 states have (on average 1.8181818181818181) internal successors, (40), 23 states have internal predecessors, (40), 5 states have call successors, (10), 4 states have call predecessors, (10), 4 states have return successors, (9), 5 states have call predecessors, (9), 4 states have call successors, (9) [2021-12-22 13:54:03,246 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-22 13:54:03,246 INFO L93 Difference]: Finished difference Result 294 states and 384 transitions. [2021-12-22 13:54:03,247 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 28 states. [2021-12-22 13:54:03,247 INFO L78 Accepts]: Start accepts. Automaton has has 24 states, 22 states have (on average 1.8181818181818181) internal successors, (40), 23 states have internal predecessors, (40), 5 states have call successors, (10), 4 states have call predecessors, (10), 4 states have return successors, (9), 5 states have call predecessors, (9), 4 states have call successors, (9) Word has length 71 [2021-12-22 13:54:03,247 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-22 13:54:03,248 INFO L225 Difference]: With dead ends: 294 [2021-12-22 13:54:03,248 INFO L226 Difference]: Without dead ends: 235 [2021-12-22 13:54:03,249 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 86 GetRequests, 44 SyntacticMatches, 12 SemanticMatches, 30 ConstructedPredicates, 2 IntricatePredicates, 0 DeprecatedPredicates, 172 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=108, Invalid=768, Unknown=2, NotChecked=114, Total=992 [2021-12-22 13:54:03,249 INFO L933 BasicCegarLoop]: 152 mSDtfsCounter, 101 mSDsluCounter, 1065 mSDsCounter, 0 mSdLazyCounter, 744 mSolverCounterSat, 72 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 125 SdHoareTripleChecker+Valid, 1217 SdHoareTripleChecker+Invalid, 2093 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 72 IncrementalHoareTripleChecker+Valid, 744 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 1277 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2021-12-22 13:54:03,249 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [125 Valid, 1217 Invalid, 2093 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [72 Valid, 744 Invalid, 0 Unknown, 1277 Unchecked, 0.4s Time] [2021-12-22 13:54:03,250 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 235 states. [2021-12-22 13:54:03,258 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 235 to 165. [2021-12-22 13:54:03,259 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 165 states, 110 states have (on average 1.1818181818181819) internal successors, (130), 113 states have internal predecessors, (130), 36 states have call successors, (36), 17 states have call predecessors, (36), 18 states have return successors, (35), 34 states have call predecessors, (35), 34 states have call successors, (35) [2021-12-22 13:54:03,268 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 165 states to 165 states and 201 transitions. [2021-12-22 13:54:03,268 INFO L78 Accepts]: Start accepts. Automaton has 165 states and 201 transitions. Word has length 71 [2021-12-22 13:54:03,269 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-22 13:54:03,269 INFO L470 AbstractCegarLoop]: Abstraction has 165 states and 201 transitions. [2021-12-22 13:54:03,269 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 24 states, 22 states have (on average 1.8181818181818181) internal successors, (40), 23 states have internal predecessors, (40), 5 states have call successors, (10), 4 states have call predecessors, (10), 4 states have return successors, (9), 5 states have call predecessors, (9), 4 states have call successors, (9) [2021-12-22 13:54:03,269 INFO L276 IsEmpty]: Start isEmpty. Operand 165 states and 201 transitions. [2021-12-22 13:54:03,269 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 73 [2021-12-22 13:54:03,270 INFO L506 BasicCegarLoop]: Found error trace [2021-12-22 13:54:03,270 INFO L514 BasicCegarLoop]: trace histogram [12, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-22 13:54:03,289 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2021-12-22 13:54:03,470 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-22 13:54:03,470 INFO L402 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-22 13:54:03,470 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-22 13:54:03,471 INFO L85 PathProgramCache]: Analyzing trace with hash 575282207, now seen corresponding path program 5 times [2021-12-22 13:54:03,471 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-22 13:54:03,471 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2061449701] [2021-12-22 13:54:03,471 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-22 13:54:03,471 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-22 13:54:03,530 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-22 13:54:03,530 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [57434851] [2021-12-22 13:54:03,530 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2021-12-22 13:54:03,530 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-22 13:54:03,531 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-22 13:54:03,531 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) [2021-12-22 13:54:03,533 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2021-12-22 13:54:11,720 INFO L228 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 7 check-sat command(s) [2021-12-22 13:54:11,720 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-12-22 13:54:11,738 INFO L263 TraceCheckSpWp]: Trace formula consists of 2234 conjuncts, 69 conjunts are in the unsatisfiable core [2021-12-22 13:54:11,742 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-22 13:54:11,747 INFO L387 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2021-12-22 13:54:12,099 INFO L387 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 13 treesize of output 9 [2021-12-22 13:54:12,135 INFO L353 Elim1Store]: treesize reduction 27, result has 25.0 percent of original size [2021-12-22 13:54:12,135 INFO L387 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 22 [2021-12-22 13:54:12,172 INFO L353 Elim1Store]: treesize reduction 27, result has 25.0 percent of original size [2021-12-22 13:54:12,172 INFO L387 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 22 [2021-12-22 13:54:12,214 INFO L353 Elim1Store]: treesize reduction 27, result has 25.0 percent of original size [2021-12-22 13:54:12,215 INFO L387 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 22 [2021-12-22 13:54:12,290 INFO L353 Elim1Store]: treesize reduction 4, result has 50.0 percent of original size [2021-12-22 13:54:12,290 INFO L387 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 11 treesize of output 11 [2021-12-22 13:54:12,344 WARN L860 $PredicateComparison]: unable to prove that (exists ((v_ArrVal_1118 (Array Int Int))) (= (store |c_old(#memory_int)| |c_aws_mul_size_checked_#in~r#1.base| v_ArrVal_1118) |c_#memory_int|)) is different from true [2021-12-22 13:54:12,355 INFO L387 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 18 [2021-12-22 13:54:12,390 INFO L387 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 45 treesize of output 39 [2021-12-22 13:54:12,400 INFO L387 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 27 treesize of output 21 [2021-12-22 13:54:12,415 INFO L134 CoverageAnalysis]: Checked inductivity of 118 backedges. 3 proven. 75 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2021-12-22 13:54:12,415 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-22 13:54:12,487 WARN L838 $PredicateComparison]: unable to prove that (forall ((v_ArrVal_1121 Int) (v_ArrVal_1120 Int) (v_ArrVal_1124 (Array Int Int))) (= (mod (select (store (store (select (store |c_#memory_int| |c_ULTIMATE.start_aws_array_list_init_dynamic_~#allocation_size~0#1.base| v_ArrVal_1124) |c_ULTIMATE.start_aws_array_list_init_dynamic_~list#1.base|) (+ |c_ULTIMATE.start_aws_array_list_init_dynamic_~list#1.offset| 24) v_ArrVal_1121) |c_ULTIMATE.start_aws_array_list_init_dynamic_~list#1.offset| v_ArrVal_1120) (+ |c_ULTIMATE.start_aws_array_list_init_dynamic_~list#1.offset| 8)) 18446744073709551616) 0)) is different from false [2021-12-22 13:54:12,488 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-22 13:54:12,488 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2061449701] [2021-12-22 13:54:12,488 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-22 13:54:12,488 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [57434851] [2021-12-22 13:54:12,488 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [57434851] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-22 13:54:12,488 INFO L186 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2021-12-22 13:54:12,488 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [25] total 25 [2021-12-22 13:54:12,488 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [512220714] [2021-12-22 13:54:12,488 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2021-12-22 13:54:12,488 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 25 states [2021-12-22 13:54:12,488 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-22 13:54:12,489 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2021-12-22 13:54:12,489 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=80, Invalid=526, Unknown=2, NotChecked=94, Total=702 [2021-12-22 13:54:12,489 INFO L87 Difference]: Start difference. First operand 165 states and 201 transitions. Second operand has 25 states, 23 states have (on average 1.7826086956521738) internal successors, (41), 24 states have internal predecessors, (41), 5 states have call successors, (10), 4 states have call predecessors, (10), 4 states have return successors, (9), 5 states have call predecessors, (9), 4 states have call successors, (9) [2021-12-22 13:54:12,939 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-22 13:54:12,939 INFO L93 Difference]: Finished difference Result 279 states and 361 transitions. [2021-12-22 13:54:12,940 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 28 states. [2021-12-22 13:54:12,940 INFO L78 Accepts]: Start accepts. Automaton has has 25 states, 23 states have (on average 1.7826086956521738) internal successors, (41), 24 states have internal predecessors, (41), 5 states have call successors, (10), 4 states have call predecessors, (10), 4 states have return successors, (9), 5 states have call predecessors, (9), 4 states have call successors, (9) Word has length 72 [2021-12-22 13:54:12,940 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-22 13:54:12,941 INFO L225 Difference]: With dead ends: 279 [2021-12-22 13:54:12,941 INFO L226 Difference]: Without dead ends: 220 [2021-12-22 13:54:12,942 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 86 GetRequests, 44 SyntacticMatches, 12 SemanticMatches, 30 ConstructedPredicates, 2 IntricatePredicates, 0 DeprecatedPredicates, 187 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=110, Invalid=766, Unknown=2, NotChecked=114, Total=992 [2021-12-22 13:54:12,943 INFO L933 BasicCegarLoop]: 148 mSDtfsCounter, 105 mSDsluCounter, 476 mSDsCounter, 0 mSdLazyCounter, 628 mSolverCounterSat, 67 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 129 SdHoareTripleChecker+Valid, 624 SdHoareTripleChecker+Invalid, 1359 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 67 IncrementalHoareTripleChecker+Valid, 628 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 664 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2021-12-22 13:54:12,943 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [129 Valid, 624 Invalid, 1359 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [67 Valid, 628 Invalid, 0 Unknown, 664 Unchecked, 0.4s Time] [2021-12-22 13:54:12,943 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 220 states. [2021-12-22 13:54:12,950 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 220 to 154. [2021-12-22 13:54:12,951 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 154 states, 101 states have (on average 1.1584158415841583) internal successors, (117), 104 states have internal predecessors, (117), 35 states have call successors, (35), 17 states have call predecessors, (35), 17 states have return successors, (33), 32 states have call predecessors, (33), 33 states have call successors, (33) [2021-12-22 13:54:12,951 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 154 states to 154 states and 185 transitions. [2021-12-22 13:54:12,951 INFO L78 Accepts]: Start accepts. Automaton has 154 states and 185 transitions. Word has length 72 [2021-12-22 13:54:12,952 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-22 13:54:12,952 INFO L470 AbstractCegarLoop]: Abstraction has 154 states and 185 transitions. [2021-12-22 13:54:12,952 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 25 states, 23 states have (on average 1.7826086956521738) internal successors, (41), 24 states have internal predecessors, (41), 5 states have call successors, (10), 4 states have call predecessors, (10), 4 states have return successors, (9), 5 states have call predecessors, (9), 4 states have call successors, (9) [2021-12-22 13:54:12,952 INFO L276 IsEmpty]: Start isEmpty. Operand 154 states and 185 transitions. [2021-12-22 13:54:12,952 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 74 [2021-12-22 13:54:12,952 INFO L506 BasicCegarLoop]: Found error trace [2021-12-22 13:54:12,952 INFO L514 BasicCegarLoop]: trace histogram [10, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-22 13:54:12,985 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2021-12-22 13:54:13,153 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable7 [2021-12-22 13:54:13,153 INFO L402 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-22 13:54:13,154 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-22 13:54:13,154 INFO L85 PathProgramCache]: Analyzing trace with hash 1655426551, now seen corresponding path program 1 times [2021-12-22 13:54:13,154 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-22 13:54:13,154 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2032525821] [2021-12-22 13:54:13,154 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-22 13:54:13,154 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-22 13:54:13,217 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-22 13:54:13,217 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1249170362] [2021-12-22 13:54:13,217 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-22 13:54:13,217 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-22 13:54:13,217 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-22 13:54:13,218 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) [2021-12-22 13:54:13,219 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2021-12-22 13:54:13,542 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-22 13:54:13,549 INFO L263 TraceCheckSpWp]: Trace formula consists of 2179 conjuncts, 7 conjunts are in the unsatisfiable core [2021-12-22 13:54:13,550 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-22 13:54:13,634 INFO L134 CoverageAnalysis]: Checked inductivity of 95 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 95 trivial. 0 not checked. [2021-12-22 13:54:13,634 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-22 13:54:13,635 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-22 13:54:13,635 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2032525821] [2021-12-22 13:54:13,635 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-22 13:54:13,635 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1249170362] [2021-12-22 13:54:13,635 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1249170362] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-22 13:54:13,635 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-22 13:54:13,635 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2021-12-22 13:54:13,635 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2000220537] [2021-12-22 13:54:13,636 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-22 13:54:13,636 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2021-12-22 13:54:13,636 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-22 13:54:13,636 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2021-12-22 13:54:13,636 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2021-12-22 13:54:13,637 INFO L87 Difference]: Start difference. First operand 154 states and 185 transitions. Second operand has 5 states, 5 states have (on average 6.2) internal successors, (31), 5 states have internal predecessors, (31), 2 states have call successors, (11), 2 states have call predecessors, (11), 3 states have return successors, (10), 3 states have call predecessors, (10), 2 states have call successors, (10) [2021-12-22 13:54:13,656 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-22 13:54:13,656 INFO L93 Difference]: Finished difference Result 216 states and 262 transitions. [2021-12-22 13:54:13,657 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2021-12-22 13:54:13,658 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 6.2) internal successors, (31), 5 states have internal predecessors, (31), 2 states have call successors, (11), 2 states have call predecessors, (11), 3 states have return successors, (10), 3 states have call predecessors, (10), 2 states have call successors, (10) Word has length 73 [2021-12-22 13:54:13,658 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-22 13:54:13,659 INFO L225 Difference]: With dead ends: 216 [2021-12-22 13:54:13,659 INFO L226 Difference]: Without dead ends: 159 [2021-12-22 13:54:13,659 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 73 GetRequests, 69 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2021-12-22 13:54:13,660 INFO L933 BasicCegarLoop]: 160 mSDtfsCounter, 2 mSDsluCounter, 475 mSDsCounter, 0 mSdLazyCounter, 16 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 635 SdHoareTripleChecker+Invalid, 16 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 16 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-12-22 13:54:13,660 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 635 Invalid, 16 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 16 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-12-22 13:54:13,660 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 159 states. [2021-12-22 13:54:13,665 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 159 to 159. [2021-12-22 13:54:13,665 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 159 states, 105 states have (on average 1.1523809523809523) internal successors, (121), 108 states have internal predecessors, (121), 35 states have call successors, (35), 17 states have call predecessors, (35), 18 states have return successors, (35), 33 states have call predecessors, (35), 33 states have call successors, (35) [2021-12-22 13:54:13,666 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 159 states to 159 states and 191 transitions. [2021-12-22 13:54:13,666 INFO L78 Accepts]: Start accepts. Automaton has 159 states and 191 transitions. Word has length 73 [2021-12-22 13:54:13,667 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-22 13:54:13,667 INFO L470 AbstractCegarLoop]: Abstraction has 159 states and 191 transitions. [2021-12-22 13:54:13,667 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 6.2) internal successors, (31), 5 states have internal predecessors, (31), 2 states have call successors, (11), 2 states have call predecessors, (11), 3 states have return successors, (10), 3 states have call predecessors, (10), 2 states have call successors, (10) [2021-12-22 13:54:13,667 INFO L276 IsEmpty]: Start isEmpty. Operand 159 states and 191 transitions. [2021-12-22 13:54:13,667 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 80 [2021-12-22 13:54:13,668 INFO L506 BasicCegarLoop]: Found error trace [2021-12-22 13:54:13,668 INFO L514 BasicCegarLoop]: trace histogram [10, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-22 13:54:13,705 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2021-12-22 13:54:13,884 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-22 13:54:13,884 INFO L402 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-22 13:54:13,885 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-22 13:54:13,885 INFO L85 PathProgramCache]: Analyzing trace with hash -209615541, now seen corresponding path program 1 times [2021-12-22 13:54:13,885 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-22 13:54:13,885 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1663484985] [2021-12-22 13:54:13,885 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-22 13:54:13,885 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-22 13:54:13,970 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-22 13:54:14,050 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2021-12-22 13:54:14,051 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-22 13:54:14,057 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2021-12-22 13:54:14,060 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-22 13:54:14,065 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2021-12-22 13:54:14,066 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-22 13:54:14,072 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2021-12-22 13:54:14,073 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-22 13:54:14,080 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 23 [2021-12-22 13:54:14,081 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-22 13:54:14,099 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 28 [2021-12-22 13:54:14,100 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-22 13:54:14,110 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 33 [2021-12-22 13:54:14,116 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-22 13:54:14,145 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 51 [2021-12-22 13:54:14,147 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-22 13:54:14,175 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2021-12-22 13:54:14,177 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-22 13:54:14,187 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2021-12-22 13:54:14,188 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-22 13:54:14,194 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 69 [2021-12-22 13:54:14,197 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-22 13:54:14,235 INFO L134 CoverageAnalysis]: Checked inductivity of 95 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 95 trivial. 0 not checked. [2021-12-22 13:54:14,235 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-22 13:54:14,236 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1663484985] [2021-12-22 13:54:14,236 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1663484985] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-22 13:54:14,236 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-22 13:54:14,236 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [10] imperfect sequences [] total 10 [2021-12-22 13:54:14,236 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [405751963] [2021-12-22 13:54:14,236 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-22 13:54:14,237 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2021-12-22 13:54:14,237 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-22 13:54:14,238 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2021-12-22 13:54:14,238 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=70, Unknown=0, NotChecked=0, Total=90 [2021-12-22 13:54:14,238 INFO L87 Difference]: Start difference. First operand 159 states and 191 transitions. Second operand has 10 states, 9 states have (on average 3.888888888888889) internal successors, (35), 4 states have internal predecessors, (35), 2 states have call successors, (12), 6 states have call predecessors, (12), 2 states have return successors, (11), 2 states have call predecessors, (11), 1 states have call successors, (11) [2021-12-22 13:54:14,668 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-22 13:54:14,668 INFO L93 Difference]: Finished difference Result 196 states and 236 transitions. [2021-12-22 13:54:14,669 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2021-12-22 13:54:14,669 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 9 states have (on average 3.888888888888889) internal successors, (35), 4 states have internal predecessors, (35), 2 states have call successors, (12), 6 states have call predecessors, (12), 2 states have return successors, (11), 2 states have call predecessors, (11), 1 states have call successors, (11) Word has length 79 [2021-12-22 13:54:14,669 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-22 13:54:14,670 INFO L225 Difference]: With dead ends: 196 [2021-12-22 13:54:14,670 INFO L226 Difference]: Without dead ends: 194 [2021-12-22 13:54:14,670 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 36 GetRequests, 22 SyntacticMatches, 0 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 11 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=67, Invalid=173, Unknown=0, NotChecked=0, Total=240 [2021-12-22 13:54:14,671 INFO L933 BasicCegarLoop]: 154 mSDtfsCounter, 243 mSDsluCounter, 531 mSDsCounter, 0 mSdLazyCounter, 459 mSolverCounterSat, 183 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 250 SdHoareTripleChecker+Valid, 685 SdHoareTripleChecker+Invalid, 642 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 183 IncrementalHoareTripleChecker+Valid, 459 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2021-12-22 13:54:14,671 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [250 Valid, 685 Invalid, 642 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [183 Valid, 459 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2021-12-22 13:54:14,671 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 194 states. [2021-12-22 13:54:14,677 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 194 to 166. [2021-12-22 13:54:14,677 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 166 states, 109 states have (on average 1.146788990825688) internal successors, (125), 113 states have internal predecessors, (125), 36 states have call successors, (36), 18 states have call predecessors, (36), 20 states have return successors, (38), 34 states have call predecessors, (38), 34 states have call successors, (38) [2021-12-22 13:54:14,678 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 166 states to 166 states and 199 transitions. [2021-12-22 13:54:14,678 INFO L78 Accepts]: Start accepts. Automaton has 166 states and 199 transitions. Word has length 79 [2021-12-22 13:54:14,678 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-22 13:54:14,678 INFO L470 AbstractCegarLoop]: Abstraction has 166 states and 199 transitions. [2021-12-22 13:54:14,679 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 9 states have (on average 3.888888888888889) internal successors, (35), 4 states have internal predecessors, (35), 2 states have call successors, (12), 6 states have call predecessors, (12), 2 states have return successors, (11), 2 states have call predecessors, (11), 1 states have call successors, (11) [2021-12-22 13:54:14,679 INFO L276 IsEmpty]: Start isEmpty. Operand 166 states and 199 transitions. [2021-12-22 13:54:14,681 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 80 [2021-12-22 13:54:14,682 INFO L506 BasicCegarLoop]: Found error trace [2021-12-22 13:54:14,682 INFO L514 BasicCegarLoop]: trace histogram [10, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-22 13:54:14,682 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9 [2021-12-22 13:54:14,682 INFO L402 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-22 13:54:14,682 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-22 13:54:14,683 INFO L85 PathProgramCache]: Analyzing trace with hash 1358446658, now seen corresponding path program 1 times [2021-12-22 13:54:14,683 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-22 13:54:14,683 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [677589732] [2021-12-22 13:54:14,683 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-22 13:54:14,683 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-22 13:54:14,772 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-22 13:54:14,847 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2021-12-22 13:54:14,848 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-22 13:54:14,853 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2021-12-22 13:54:14,854 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-22 13:54:14,859 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2021-12-22 13:54:14,860 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-22 13:54:14,864 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2021-12-22 13:54:14,865 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-22 13:54:14,870 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 23 [2021-12-22 13:54:14,871 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-22 13:54:14,876 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 28 [2021-12-22 13:54:14,876 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-22 13:54:14,886 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 33 [2021-12-22 13:54:14,912 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-22 13:54:15,161 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 51 [2021-12-22 13:54:15,164 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-22 13:54:15,184 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2021-12-22 13:54:15,185 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-22 13:54:15,202 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2021-12-22 13:54:15,203 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-22 13:54:15,208 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 69 [2021-12-22 13:54:15,209 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-22 13:54:15,215 INFO L134 CoverageAnalysis]: Checked inductivity of 95 backedges. 0 proven. 55 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2021-12-22 13:54:15,215 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-22 13:54:15,215 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [677589732] [2021-12-22 13:54:15,215 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [677589732] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-22 13:54:15,215 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1306763259] [2021-12-22 13:54:15,216 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-22 13:54:15,216 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-22 13:54:15,216 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-22 13:54:15,217 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) [2021-12-22 13:54:15,251 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2021-12-22 13:54:15,726 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-22 13:54:15,734 INFO L263 TraceCheckSpWp]: Trace formula consists of 2186 conjuncts, 92 conjunts are in the unsatisfiable core [2021-12-22 13:54:15,738 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-22 13:54:15,880 INFO L387 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 [2021-12-22 13:54:15,918 INFO L353 Elim1Store]: treesize reduction 32, result has 23.8 percent of original size [2021-12-22 13:54:15,918 INFO L387 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 [2021-12-22 13:54:15,966 INFO L353 Elim1Store]: treesize reduction 76, result has 21.6 percent of original size [2021-12-22 13:54:15,966 INFO L387 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 [2021-12-22 13:54:16,027 INFO L353 Elim1Store]: treesize reduction 135, result has 18.7 percent of original size [2021-12-22 13:54:16,027 INFO L387 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 45 treesize of output 50 [2021-12-22 13:54:16,110 INFO L353 Elim1Store]: treesize reduction 208, result has 16.5 percent of original size [2021-12-22 13:54:16,110 INFO L387 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 55 treesize of output 63 [2021-12-22 13:54:16,188 INFO L353 Elim1Store]: treesize reduction 208, result has 16.5 percent of original size [2021-12-22 13:54:16,188 INFO L387 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 55 treesize of output 63 [2021-12-22 13:54:16,268 INFO L353 Elim1Store]: treesize reduction 208, result has 16.5 percent of original size [2021-12-22 13:54:16,268 INFO L387 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 55 treesize of output 63 [2021-12-22 13:54:16,392 INFO L353 Elim1Store]: treesize reduction 295, result has 14.7 percent of original size [2021-12-22 13:54:16,392 INFO L387 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 65 treesize of output 76 [2021-12-22 13:54:16,508 INFO L353 Elim1Store]: treesize reduction 396, result has 13.3 percent of original size [2021-12-22 13:54:16,508 INFO L387 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 75 treesize of output 89 [2021-12-22 13:54:16,623 INFO L353 Elim1Store]: treesize reduction 384, result has 13.7 percent of original size [2021-12-22 13:54:16,623 INFO L387 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 74 treesize of output 88 [2021-12-22 13:54:22,108 INFO L134 CoverageAnalysis]: Checked inductivity of 95 backedges. 3 proven. 64 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2021-12-22 13:54:22,108 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-22 13:54:22,597 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1306763259] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-22 13:54:22,598 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-12-22 13:54:22,598 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 24] total 39 [2021-12-22 13:54:22,598 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1638696888] [2021-12-22 13:54:22,598 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-12-22 13:54:22,598 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 39 states [2021-12-22 13:54:22,598 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-22 13:54:22,598 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 39 interpolants. [2021-12-22 13:54:22,599 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=113, Invalid=1777, Unknown=2, NotChecked=0, Total=1892 [2021-12-22 13:54:22,599 INFO L87 Difference]: Start difference. First operand 166 states and 199 transitions. Second operand has 39 states, 38 states have (on average 2.1052631578947367) internal successors, (80), 34 states have internal predecessors, (80), 6 states have call successors, (23), 8 states have call predecessors, (23), 6 states have return successors, (22), 6 states have call predecessors, (22), 6 states have call successors, (22) [2021-12-22 13:54:25,527 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-22 13:54:25,527 INFO L93 Difference]: Finished difference Result 333 states and 403 transitions. [2021-12-22 13:54:25,527 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 26 states. [2021-12-22 13:54:25,528 INFO L78 Accepts]: Start accepts. Automaton has has 39 states, 38 states have (on average 2.1052631578947367) internal successors, (80), 34 states have internal predecessors, (80), 6 states have call successors, (23), 8 states have call predecessors, (23), 6 states have return successors, (22), 6 states have call predecessors, (22), 6 states have call successors, (22) Word has length 79 [2021-12-22 13:54:25,528 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-22 13:54:25,530 INFO L225 Difference]: With dead ends: 333 [2021-12-22 13:54:25,530 INFO L226 Difference]: Without dead ends: 197 [2021-12-22 13:54:25,531 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 160 GetRequests, 94 SyntacticMatches, 1 SemanticMatches, 65 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 475 ImplicationChecksByTransitivity, 6.3s TimeCoverageRelationStatistics Valid=339, Invalid=4081, Unknown=2, NotChecked=0, Total=4422 [2021-12-22 13:54:25,532 INFO L933 BasicCegarLoop]: 119 mSDtfsCounter, 354 mSDsluCounter, 1943 mSDsCounter, 0 mSdLazyCounter, 2936 mSolverCounterSat, 315 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 354 SdHoareTripleChecker+Valid, 2062 SdHoareTripleChecker+Invalid, 3976 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 315 IncrementalHoareTripleChecker+Valid, 2936 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 725 IncrementalHoareTripleChecker+Unchecked, 1.9s IncrementalHoareTripleChecker+Time [2021-12-22 13:54:25,532 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [354 Valid, 2062 Invalid, 3976 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [315 Valid, 2936 Invalid, 0 Unknown, 725 Unchecked, 1.9s Time] [2021-12-22 13:54:25,532 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 197 states. [2021-12-22 13:54:25,541 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 197 to 167. [2021-12-22 13:54:25,541 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 167 states, 110 states have (on average 1.1454545454545455) internal successors, (126), 114 states have internal predecessors, (126), 36 states have call successors, (36), 18 states have call predecessors, (36), 20 states have return successors, (38), 34 states have call predecessors, (38), 34 states have call successors, (38) [2021-12-22 13:54:25,542 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 167 states to 167 states and 200 transitions. [2021-12-22 13:54:25,542 INFO L78 Accepts]: Start accepts. Automaton has 167 states and 200 transitions. Word has length 79 [2021-12-22 13:54:25,542 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-22 13:54:25,542 INFO L470 AbstractCegarLoop]: Abstraction has 167 states and 200 transitions. [2021-12-22 13:54:25,543 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 39 states, 38 states have (on average 2.1052631578947367) internal successors, (80), 34 states have internal predecessors, (80), 6 states have call successors, (23), 8 states have call predecessors, (23), 6 states have return successors, (22), 6 states have call predecessors, (22), 6 states have call successors, (22) [2021-12-22 13:54:25,543 INFO L276 IsEmpty]: Start isEmpty. Operand 167 states and 200 transitions. [2021-12-22 13:54:25,543 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 81 [2021-12-22 13:54:25,543 INFO L506 BasicCegarLoop]: Found error trace [2021-12-22 13:54:25,543 INFO L514 BasicCegarLoop]: trace histogram [11, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-22 13:54:25,579 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2021-12-22 13:54:25,764 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2021-12-22 13:54:25,765 INFO L402 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-22 13:54:25,765 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-22 13:54:25,765 INFO L85 PathProgramCache]: Analyzing trace with hash -360650806, now seen corresponding path program 2 times [2021-12-22 13:54:25,765 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-22 13:54:25,765 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [775631439] [2021-12-22 13:54:25,766 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-22 13:54:25,766 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-22 13:54:25,857 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-22 13:54:25,918 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2021-12-22 13:54:25,919 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-22 13:54:25,923 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2021-12-22 13:54:25,925 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-22 13:54:25,930 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2021-12-22 13:54:25,931 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-22 13:54:25,935 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2021-12-22 13:54:25,936 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-22 13:54:25,944 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 23 [2021-12-22 13:54:25,945 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-22 13:54:25,949 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 28 [2021-12-22 13:54:25,950 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-22 13:54:25,959 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 33 [2021-12-22 13:54:25,978 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-22 13:54:26,269 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 52 [2021-12-22 13:54:26,272 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-22 13:54:26,298 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2021-12-22 13:54:26,299 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-22 13:54:26,317 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2021-12-22 13:54:26,318 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-22 13:54:26,322 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 70 [2021-12-22 13:54:26,323 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-22 13:54:26,327 INFO L134 CoverageAnalysis]: Checked inductivity of 106 backedges. 0 proven. 66 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2021-12-22 13:54:26,327 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-22 13:54:26,327 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [775631439] [2021-12-22 13:54:26,327 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [775631439] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-22 13:54:26,327 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1269940012] [2021-12-22 13:54:26,327 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2021-12-22 13:54:26,327 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-22 13:54:26,327 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-22 13:54:26,344 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) [2021-12-22 13:54:26,371 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2021-12-22 13:54:27,002 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2021-12-22 13:54:27,003 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-12-22 13:54:27,011 INFO L263 TraceCheckSpWp]: Trace formula consists of 2205 conjuncts, 100 conjunts are in the unsatisfiable core [2021-12-22 13:54:27,015 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-22 13:54:27,063 INFO L387 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 [2021-12-22 13:54:27,097 INFO L353 Elim1Store]: treesize reduction 32, result has 23.8 percent of original size [2021-12-22 13:54:27,098 INFO L387 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 [2021-12-22 13:54:27,148 INFO L353 Elim1Store]: treesize reduction 76, result has 21.6 percent of original size [2021-12-22 13:54:27,148 INFO L387 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 [2021-12-22 13:54:27,212 INFO L353 Elim1Store]: treesize reduction 135, result has 18.7 percent of original size [2021-12-22 13:54:27,213 INFO L387 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 45 treesize of output 50 [2021-12-22 13:54:27,307 INFO L353 Elim1Store]: treesize reduction 208, result has 16.5 percent of original size [2021-12-22 13:54:27,307 INFO L387 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 55 treesize of output 63 [2021-12-22 13:54:27,412 INFO L353 Elim1Store]: treesize reduction 295, result has 14.7 percent of original size [2021-12-22 13:54:27,412 INFO L387 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 65 treesize of output 76 [2021-12-22 13:54:27,544 INFO L353 Elim1Store]: treesize reduction 396, result has 13.3 percent of original size [2021-12-22 13:54:27,544 INFO L387 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 75 treesize of output 89 [2021-12-22 13:54:27,708 INFO L353 Elim1Store]: treesize reduction 511, result has 12.2 percent of original size [2021-12-22 13:54:27,708 INFO L387 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 85 treesize of output 102 [2021-12-22 13:54:27,919 INFO L353 Elim1Store]: treesize reduction 640, result has 11.2 percent of original size [2021-12-22 13:54:27,920 INFO L387 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 8 select indices, 8 select index equivalence classes, 0 disjoint index pairs (out of 28 index pairs), introduced 8 new quantified variables, introduced 36 case distinctions, treesize of input 95 treesize of output 115 [2021-12-22 13:54:28,211 INFO L353 Elim1Store]: treesize reduction 783, result has 10.4 percent of original size [2021-12-22 13:54:28,211 INFO L387 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 9 select indices, 9 select index equivalence classes, 0 disjoint index pairs (out of 36 index pairs), introduced 9 new quantified variables, introduced 45 case distinctions, treesize of input 105 treesize of output 128 [2021-12-22 13:54:28,471 INFO L353 Elim1Store]: treesize reduction 920, result has 9.9 percent of original size [2021-12-22 13:54:28,472 INFO L387 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 10 select indices, 10 select index equivalence classes, 0 disjoint index pairs (out of 45 index pairs), introduced 10 new quantified variables, introduced 55 case distinctions, treesize of input 114 treesize of output 140 [2021-12-22 13:54:31,588 INFO L134 CoverageAnalysis]: Checked inductivity of 106 backedges. 0 proven. 66 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2021-12-22 13:54:31,588 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-22 13:54:32,174 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1269940012] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-22 13:54:32,174 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-12-22 13:54:32,174 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 20] total 36 [2021-12-22 13:54:32,174 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [810737856] [2021-12-22 13:54:32,174 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-12-22 13:54:32,174 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 36 states [2021-12-22 13:54:32,174 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-22 13:54:32,175 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 36 interpolants. [2021-12-22 13:54:32,175 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=109, Invalid=1531, Unknown=0, NotChecked=0, Total=1640 [2021-12-22 13:54:32,175 INFO L87 Difference]: Start difference. First operand 167 states and 200 transitions. Second operand has 36 states, 36 states have (on average 2.0833333333333335) internal successors, (75), 31 states have internal predecessors, (75), 4 states have call successors, (17), 8 states have call predecessors, (17), 5 states have return successors, (16), 4 states have call predecessors, (16), 4 states have call successors, (16) [2021-12-22 13:54:35,739 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-22 13:54:35,739 INFO L93 Difference]: Finished difference Result 332 states and 402 transitions. [2021-12-22 13:54:35,739 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2021-12-22 13:54:35,739 INFO L78 Accepts]: Start accepts. Automaton has has 36 states, 36 states have (on average 2.0833333333333335) internal successors, (75), 31 states have internal predecessors, (75), 4 states have call successors, (17), 8 states have call predecessors, (17), 5 states have return successors, (16), 4 states have call predecessors, (16), 4 states have call successors, (16) Word has length 80 [2021-12-22 13:54:35,740 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-22 13:54:35,740 INFO L225 Difference]: With dead ends: 332 [2021-12-22 13:54:35,740 INFO L226 Difference]: Without dead ends: 196 [2021-12-22 13:54:35,741 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 151 GetRequests, 95 SyntacticMatches, 1 SemanticMatches, 55 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 315 ImplicationChecksByTransitivity, 4.1s TimeCoverageRelationStatistics Valid=231, Invalid=2961, Unknown=0, NotChecked=0, Total=3192 [2021-12-22 13:54:35,741 INFO L933 BasicCegarLoop]: 151 mSDtfsCounter, 146 mSDsluCounter, 1635 mSDsCounter, 0 mSdLazyCounter, 1904 mSolverCounterSat, 130 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 152 SdHoareTripleChecker+Valid, 1786 SdHoareTripleChecker+Invalid, 2579 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 130 IncrementalHoareTripleChecker+Valid, 1904 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 545 IncrementalHoareTripleChecker+Unchecked, 2.4s IncrementalHoareTripleChecker+Time [2021-12-22 13:54:35,742 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [152 Valid, 1786 Invalid, 2579 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [130 Valid, 1904 Invalid, 0 Unknown, 545 Unchecked, 2.4s Time] [2021-12-22 13:54:35,742 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 196 states. [2021-12-22 13:54:35,750 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 196 to 168. [2021-12-22 13:54:35,751 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 168 states, 111 states have (on average 1.1441441441441442) internal successors, (127), 115 states have internal predecessors, (127), 36 states have call successors, (36), 18 states have call predecessors, (36), 20 states have return successors, (38), 34 states have call predecessors, (38), 34 states have call successors, (38) [2021-12-22 13:54:35,753 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 168 states to 168 states and 201 transitions. [2021-12-22 13:54:35,754 INFO L78 Accepts]: Start accepts. Automaton has 168 states and 201 transitions. Word has length 80 [2021-12-22 13:54:35,754 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-22 13:54:35,754 INFO L470 AbstractCegarLoop]: Abstraction has 168 states and 201 transitions. [2021-12-22 13:54:35,754 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 36 states, 36 states have (on average 2.0833333333333335) internal successors, (75), 31 states have internal predecessors, (75), 4 states have call successors, (17), 8 states have call predecessors, (17), 5 states have return successors, (16), 4 states have call predecessors, (16), 4 states have call successors, (16) [2021-12-22 13:54:35,754 INFO L276 IsEmpty]: Start isEmpty. Operand 168 states and 201 transitions. [2021-12-22 13:54:35,754 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 82 [2021-12-22 13:54:35,754 INFO L506 BasicCegarLoop]: Found error trace [2021-12-22 13:54:35,755 INFO L514 BasicCegarLoop]: trace histogram [12, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-22 13:54:35,779 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Ended with exit code 0 [2021-12-22 13:54:35,969 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable11 [2021-12-22 13:54:35,969 INFO L402 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-22 13:54:35,969 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-22 13:54:35,969 INFO L85 PathProgramCache]: Analyzing trace with hash -2113064638, now seen corresponding path program 3 times [2021-12-22 13:54:35,969 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-22 13:54:35,969 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1227356551] [2021-12-22 13:54:35,970 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-22 13:54:35,970 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-22 13:54:36,028 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-22 13:54:36,079 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2021-12-22 13:54:36,080 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-22 13:54:36,084 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2021-12-22 13:54:36,084 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-22 13:54:36,088 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2021-12-22 13:54:36,088 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-22 13:54:36,092 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2021-12-22 13:54:36,092 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-22 13:54:36,096 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 23 [2021-12-22 13:54:36,096 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-22 13:54:36,100 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 28 [2021-12-22 13:54:36,101 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-22 13:54:36,109 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 33 [2021-12-22 13:54:36,126 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-22 13:54:36,436 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 53 [2021-12-22 13:54:36,439 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-22 13:54:36,472 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2021-12-22 13:54:36,473 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-22 13:54:36,494 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2021-12-22 13:54:36,495 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-22 13:54:36,498 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 71 [2021-12-22 13:54:36,499 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-22 13:54:36,503 INFO L134 CoverageAnalysis]: Checked inductivity of 118 backedges. 0 proven. 78 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2021-12-22 13:54:36,503 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-22 13:54:36,504 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1227356551] [2021-12-22 13:54:36,504 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1227356551] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-22 13:54:36,504 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [369786766] [2021-12-22 13:54:36,504 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2021-12-22 13:54:36,504 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-22 13:54:36,504 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-22 13:54:36,505 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) [2021-12-22 13:54:36,546 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2021-12-22 13:54:42,551 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 7 check-sat command(s) [2021-12-22 13:54:42,551 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-12-22 13:54:42,569 INFO L263 TraceCheckSpWp]: Trace formula consists of 2224 conjuncts, 85 conjunts are in the unsatisfiable core [2021-12-22 13:54:42,574 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-22 13:54:42,673 INFO L387 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 13 treesize of output 9 [2021-12-22 13:54:42,736 INFO L353 Elim1Store]: treesize reduction 27, result has 25.0 percent of original size [2021-12-22 13:54:42,736 INFO L387 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 22 [2021-12-22 13:54:42,800 INFO L353 Elim1Store]: treesize reduction 27, result has 25.0 percent of original size [2021-12-22 13:54:42,801 INFO L387 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 22 [2021-12-22 13:54:42,874 INFO L353 Elim1Store]: treesize reduction 27, result has 25.0 percent of original size [2021-12-22 13:54:42,875 INFO L387 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 22 [2021-12-22 13:54:42,945 INFO L353 Elim1Store]: treesize reduction 27, result has 25.0 percent of original size [2021-12-22 13:54:42,945 INFO L387 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 22 [2021-12-22 13:54:43,025 INFO L353 Elim1Store]: treesize reduction 27, result has 25.0 percent of original size [2021-12-22 13:54:43,025 INFO L387 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 22 [2021-12-22 13:54:43,097 INFO L353 Elim1Store]: treesize reduction 27, result has 25.0 percent of original size [2021-12-22 13:54:43,097 INFO L387 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 22 [2021-12-22 13:54:43,178 INFO L353 Elim1Store]: treesize reduction 29, result has 23.7 percent of original size [2021-12-22 13:54:43,178 INFO L387 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 24 treesize of output 23 [2021-12-22 13:54:43,252 INFO L353 Elim1Store]: treesize reduction 27, result has 25.0 percent of original size [2021-12-22 13:54:43,254 INFO L387 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 22 [2021-12-22 13:54:43,377 INFO L353 Elim1Store]: treesize reduction 64, result has 22.9 percent of original size [2021-12-22 13:54:43,377 INFO L387 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 32 treesize of output 34 [2021-12-22 13:54:43,550 INFO L353 Elim1Store]: treesize reduction 64, result has 22.9 percent of original size [2021-12-22 13:54:43,551 INFO L387 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 32 treesize of output 34 [2021-12-22 13:54:43,748 INFO L353 Elim1Store]: treesize reduction 64, result has 22.9 percent of original size [2021-12-22 13:54:43,749 INFO L387 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 32 treesize of output 34 [2021-12-22 13:54:44,807 INFO L134 CoverageAnalysis]: Checked inductivity of 118 backedges. 28 proven. 44 refuted. 0 times theorem prover too weak. 46 trivial. 0 not checked. [2021-12-22 13:54:44,807 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-22 13:54:45,289 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [369786766] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-22 13:54:45,289 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-12-22 13:54:45,289 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 20] total 37 [2021-12-22 13:54:45,289 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [674482149] [2021-12-22 13:54:45,289 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-12-22 13:54:45,289 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 37 states [2021-12-22 13:54:45,290 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-22 13:54:45,290 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 37 interpolants. [2021-12-22 13:54:45,290 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=141, Invalid=1581, Unknown=0, NotChecked=0, Total=1722 [2021-12-22 13:54:45,290 INFO L87 Difference]: Start difference. First operand 168 states and 201 transitions. Second operand has 37 states, 36 states have (on average 2.1666666666666665) internal successors, (78), 32 states have internal predecessors, (78), 6 states have call successors, (23), 8 states have call predecessors, (23), 5 states have return successors, (22), 6 states have call predecessors, (22), 6 states have call successors, (22) [2021-12-22 13:54:46,438 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-22 13:54:46,438 INFO L93 Difference]: Finished difference Result 356 states and 432 transitions. [2021-12-22 13:54:46,439 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 31 states. [2021-12-22 13:54:46,439 INFO L78 Accepts]: Start accepts. Automaton has has 37 states, 36 states have (on average 2.1666666666666665) internal successors, (78), 32 states have internal predecessors, (78), 6 states have call successors, (23), 8 states have call predecessors, (23), 5 states have return successors, (22), 6 states have call predecessors, (22), 6 states have call successors, (22) Word has length 81 [2021-12-22 13:54:46,439 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-22 13:54:46,440 INFO L225 Difference]: With dead ends: 356 [2021-12-22 13:54:46,440 INFO L226 Difference]: Without dead ends: 218 [2021-12-22 13:54:46,441 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 155 GetRequests, 93 SyntacticMatches, 4 SemanticMatches, 58 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 555 ImplicationChecksByTransitivity, 2.6s TimeCoverageRelationStatistics Valid=313, Invalid=3227, Unknown=0, NotChecked=0, Total=3540 [2021-12-22 13:54:46,441 INFO L933 BasicCegarLoop]: 164 mSDtfsCounter, 262 mSDsluCounter, 1376 mSDsCounter, 0 mSdLazyCounter, 607 mSolverCounterSat, 193 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 268 SdHoareTripleChecker+Valid, 1540 SdHoareTripleChecker+Invalid, 1386 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 193 IncrementalHoareTripleChecker+Valid, 607 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 586 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2021-12-22 13:54:46,441 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [268 Valid, 1540 Invalid, 1386 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [193 Valid, 607 Invalid, 0 Unknown, 586 Unchecked, 0.4s Time] [2021-12-22 13:54:46,442 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 218 states. [2021-12-22 13:54:46,451 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 218 to 186. [2021-12-22 13:54:46,451 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 186 states, 124 states have (on average 1.1612903225806452) internal successors, (144), 128 states have internal predecessors, (144), 39 states have call successors, (39), 21 states have call predecessors, (39), 22 states have return successors, (42), 36 states have call predecessors, (42), 37 states have call successors, (42) [2021-12-22 13:54:46,452 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 186 states to 186 states and 225 transitions. [2021-12-22 13:54:46,452 INFO L78 Accepts]: Start accepts. Automaton has 186 states and 225 transitions. Word has length 81 [2021-12-22 13:54:46,452 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-22 13:54:46,452 INFO L470 AbstractCegarLoop]: Abstraction has 186 states and 225 transitions. [2021-12-22 13:54:46,452 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 37 states, 36 states have (on average 2.1666666666666665) internal successors, (78), 32 states have internal predecessors, (78), 6 states have call successors, (23), 8 states have call predecessors, (23), 5 states have return successors, (22), 6 states have call predecessors, (22), 6 states have call successors, (22) [2021-12-22 13:54:46,452 INFO L276 IsEmpty]: Start isEmpty. Operand 186 states and 225 transitions. [2021-12-22 13:54:46,453 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 85 [2021-12-22 13:54:46,453 INFO L506 BasicCegarLoop]: Found error trace [2021-12-22 13:54:46,453 INFO L514 BasicCegarLoop]: trace histogram [13, 5, 5, 5, 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] [2021-12-22 13:54:46,481 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Forceful destruction successful, exit code 0 [2021-12-22 13:54:46,664 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2021-12-22 13:54:46,664 INFO L402 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-22 13:54:46,664 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-22 13:54:46,665 INFO L85 PathProgramCache]: Analyzing trace with hash -780390283, now seen corresponding path program 1 times [2021-12-22 13:54:46,665 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-22 13:54:46,665 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1653305815] [2021-12-22 13:54:46,665 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-22 13:54:46,665 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-22 13:54:46,706 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-22 13:54:46,707 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [726018278] [2021-12-22 13:54:46,707 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-22 13:54:46,707 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-22 13:54:46,707 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-22 13:54:46,708 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) [2021-12-22 13:54:46,709 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2021-12-22 13:54:47,131 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-22 13:54:47,137 INFO L263 TraceCheckSpWp]: Trace formula consists of 2291 conjuncts, 7 conjunts are in the unsatisfiable core [2021-12-22 13:54:47,139 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-22 13:54:47,229 INFO L134 CoverageAnalysis]: Checked inductivity of 133 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 131 trivial. 0 not checked. [2021-12-22 13:54:47,229 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-22 13:54:47,229 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-22 13:54:47,229 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1653305815] [2021-12-22 13:54:47,229 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-22 13:54:47,229 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [726018278] [2021-12-22 13:54:47,230 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [726018278] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-22 13:54:47,230 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-22 13:54:47,230 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2021-12-22 13:54:47,230 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [469876563] [2021-12-22 13:54:47,230 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-22 13:54:47,230 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2021-12-22 13:54:47,230 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-22 13:54:47,231 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2021-12-22 13:54:47,231 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2021-12-22 13:54:47,231 INFO L87 Difference]: Start difference. First operand 186 states and 225 transitions. Second operand has 7 states, 7 states have (on average 5.285714285714286) internal successors, (37), 7 states have internal predecessors, (37), 4 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (11), 4 states have call predecessors, (11), 3 states have call successors, (11) [2021-12-22 13:54:47,386 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-22 13:54:47,386 INFO L93 Difference]: Finished difference Result 246 states and 298 transitions. [2021-12-22 13:54:47,386 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2021-12-22 13:54:47,386 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 5.285714285714286) internal successors, (37), 7 states have internal predecessors, (37), 4 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (11), 4 states have call predecessors, (11), 3 states have call successors, (11) Word has length 84 [2021-12-22 13:54:47,386 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-22 13:54:47,387 INFO L225 Difference]: With dead ends: 246 [2021-12-22 13:54:47,387 INFO L226 Difference]: Without dead ends: 186 [2021-12-22 13:54:47,388 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 87 GetRequests, 78 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=31, Invalid=79, Unknown=0, NotChecked=0, Total=110 [2021-12-22 13:54:47,388 INFO L933 BasicCegarLoop]: 122 mSDtfsCounter, 192 mSDsluCounter, 445 mSDsCounter, 0 mSdLazyCounter, 143 mSolverCounterSat, 55 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 192 SdHoareTripleChecker+Valid, 567 SdHoareTripleChecker+Invalid, 198 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 55 IncrementalHoareTripleChecker+Valid, 143 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2021-12-22 13:54:47,389 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [192 Valid, 567 Invalid, 198 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [55 Valid, 143 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2021-12-22 13:54:47,390 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 186 states. [2021-12-22 13:54:47,408 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 186 to 186. [2021-12-22 13:54:47,408 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 186 states, 124 states have (on average 1.153225806451613) internal successors, (143), 128 states have internal predecessors, (143), 39 states have call successors, (39), 21 states have call predecessors, (39), 22 states have return successors, (42), 36 states have call predecessors, (42), 37 states have call successors, (42) [2021-12-22 13:54:47,410 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 186 states to 186 states and 224 transitions. [2021-12-22 13:54:47,410 INFO L78 Accepts]: Start accepts. Automaton has 186 states and 224 transitions. Word has length 84 [2021-12-22 13:54:47,411 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-22 13:54:47,411 INFO L470 AbstractCegarLoop]: Abstraction has 186 states and 224 transitions. [2021-12-22 13:54:47,411 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 5.285714285714286) internal successors, (37), 7 states have internal predecessors, (37), 4 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (11), 4 states have call predecessors, (11), 3 states have call successors, (11) [2021-12-22 13:54:47,411 INFO L276 IsEmpty]: Start isEmpty. Operand 186 states and 224 transitions. [2021-12-22 13:54:47,412 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 86 [2021-12-22 13:54:47,412 INFO L506 BasicCegarLoop]: Found error trace [2021-12-22 13:54:47,412 INFO L514 BasicCegarLoop]: trace histogram [13, 5, 5, 5, 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] [2021-12-22 13:54:47,432 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Ended with exit code 0 [2021-12-22 13:54:47,627 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2021-12-22 13:54:47,628 INFO L402 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-22 13:54:47,628 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-22 13:54:47,628 INFO L85 PathProgramCache]: Analyzing trace with hash -699058586, now seen corresponding path program 1 times [2021-12-22 13:54:47,628 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-22 13:54:47,628 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2056788321] [2021-12-22 13:54:47,629 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-22 13:54:47,629 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-22 13:54:47,716 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-22 13:54:47,755 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2021-12-22 13:54:47,756 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-22 13:54:47,759 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2021-12-22 13:54:47,760 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-22 13:54:47,763 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2021-12-22 13:54:47,764 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-22 13:54:47,769 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2021-12-22 13:54:47,770 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-22 13:54:47,775 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 23 [2021-12-22 13:54:47,775 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-22 13:54:47,779 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 28 [2021-12-22 13:54:47,779 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-22 13:54:47,786 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 33 [2021-12-22 13:54:47,802 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-22 13:54:48,212 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 54 [2021-12-22 13:54:48,215 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-22 13:54:48,272 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2021-12-22 13:54:48,274 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-22 13:54:48,304 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2021-12-22 13:54:48,305 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-22 13:54:48,309 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 72 [2021-12-22 13:54:48,310 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-22 13:54:48,314 INFO L134 CoverageAnalysis]: Checked inductivity of 133 backedges. 0 proven. 91 refuted. 0 times theorem prover too weak. 42 trivial. 0 not checked. [2021-12-22 13:54:48,314 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-22 13:54:48,315 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2056788321] [2021-12-22 13:54:48,315 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2056788321] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-22 13:54:48,315 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [807239493] [2021-12-22 13:54:48,315 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-22 13:54:48,315 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-22 13:54:48,315 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-22 13:54:48,332 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) [2021-12-22 13:54:48,333 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process