./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/aws-c-common/aws_priority_queue_init_dynamic_harness-1.i --full-output --architecture 64bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version c3fed411 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_priority_queue_init_dynamic_harness-1.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 f4db5fb03820aea666082345ea177387bf1c218ce33dad19402cb646ed5abf58 --- Real Ultimate output --- This is Ultimate 0.2.2-tmp.no-commuhash-c3fed41 [2021-12-18 01:06:53,912 INFO L177 SettingsManager]: Resetting all preferences to default values... [2021-12-18 01:06:53,918 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2021-12-18 01:06:53,953 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2021-12-18 01:06:53,953 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2021-12-18 01:06:53,954 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2021-12-18 01:06:53,955 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2021-12-18 01:06:53,956 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2021-12-18 01:06:53,957 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2021-12-18 01:06:53,958 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2021-12-18 01:06:53,958 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2021-12-18 01:06:53,959 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2021-12-18 01:06:53,959 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2021-12-18 01:06:53,960 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2021-12-18 01:06:53,961 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2021-12-18 01:06:53,962 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2021-12-18 01:06:53,962 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2021-12-18 01:06:53,965 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2021-12-18 01:06:53,966 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2021-12-18 01:06:53,968 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2021-12-18 01:06:53,969 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2021-12-18 01:06:53,975 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2021-12-18 01:06:53,976 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2021-12-18 01:06:53,977 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2021-12-18 01:06:53,979 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2021-12-18 01:06:53,980 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2021-12-18 01:06:53,980 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2021-12-18 01:06:53,980 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2021-12-18 01:06:53,981 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2021-12-18 01:06:53,981 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2021-12-18 01:06:53,981 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2021-12-18 01:06:53,982 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2021-12-18 01:06:53,982 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2021-12-18 01:06:53,983 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2021-12-18 01:06:53,984 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2021-12-18 01:06:53,984 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2021-12-18 01:06:53,984 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2021-12-18 01:06:53,984 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2021-12-18 01:06:53,985 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2021-12-18 01:06:53,985 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2021-12-18 01:06:53,986 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2021-12-18 01:06:53,986 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-64bit-Automizer_Default.epf [2021-12-18 01:06:54,002 INFO L113 SettingsManager]: Loading preferences was successful [2021-12-18 01:06:54,004 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2021-12-18 01:06:54,006 INFO L136 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2021-12-18 01:06:54,006 INFO L138 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2021-12-18 01:06:54,007 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2021-12-18 01:06:54,007 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2021-12-18 01:06:54,007 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2021-12-18 01:06:54,007 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2021-12-18 01:06:54,008 INFO L138 SettingsManager]: * Use SBE=true [2021-12-18 01:06:54,008 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2021-12-18 01:06:54,008 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2021-12-18 01:06:54,008 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2021-12-18 01:06:54,009 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2021-12-18 01:06:54,009 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2021-12-18 01:06:54,009 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2021-12-18 01:06:54,009 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2021-12-18 01:06:54,009 INFO L138 SettingsManager]: * Use constant arrays=true [2021-12-18 01:06:54,009 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2021-12-18 01:06:54,009 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2021-12-18 01:06:54,009 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2021-12-18 01:06:54,010 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2021-12-18 01:06:54,010 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2021-12-18 01:06:54,010 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2021-12-18 01:06:54,010 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2021-12-18 01:06:54,010 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2021-12-18 01:06:54,010 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2021-12-18 01:06:54,010 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2021-12-18 01:06:54,011 INFO L138 SettingsManager]: * Large block encoding in concurrent analysis=OFF [2021-12-18 01:06:54,011 INFO L138 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2021-12-18 01:06:54,011 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2021-12-18 01:06:54,011 INFO L138 SettingsManager]: * Trace refinement exception blacklist=NONE [2021-12-18 01:06:54,011 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 -> f4db5fb03820aea666082345ea177387bf1c218ce33dad19402cb646ed5abf58 [2021-12-18 01:06:54,197 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2021-12-18 01:06:54,222 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2021-12-18 01:06:54,225 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2021-12-18 01:06:54,226 INFO L271 PluginConnector]: Initializing CDTParser... [2021-12-18 01:06:54,227 INFO L275 PluginConnector]: CDTParser initialized [2021-12-18 01:06:54,228 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/aws-c-common/aws_priority_queue_init_dynamic_harness-1.i [2021-12-18 01:06:54,291 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/d3afa1ec7/b7a989525bec46bfadaaf223b366d061/FLAG0616e2907 [2021-12-18 01:06:54,873 INFO L306 CDTParser]: Found 1 translation units. [2021-12-18 01:06:54,873 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/aws-c-common/aws_priority_queue_init_dynamic_harness-1.i [2021-12-18 01:06:54,908 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/d3afa1ec7/b7a989525bec46bfadaaf223b366d061/FLAG0616e2907 [2021-12-18 01:06:55,248 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/d3afa1ec7/b7a989525bec46bfadaaf223b366d061 [2021-12-18 01:06:55,250 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2021-12-18 01:06:55,251 INFO L131 ToolchainWalker]: Walking toolchain with 6 elements. [2021-12-18 01:06:55,253 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2021-12-18 01:06:55,254 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2021-12-18 01:06:55,256 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2021-12-18 01:06:55,256 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 18.12 01:06:55" (1/1) ... [2021-12-18 01:06:55,257 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@4b6f9daa and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.12 01:06:55, skipping insertion in model container [2021-12-18 01:06:55,257 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 18.12 01:06:55" (1/1) ... [2021-12-18 01:06:55,262 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2021-12-18 01:06:55,344 INFO L178 MainTranslator]: Built tables and reachable declarations [2021-12-18 01:06:55,534 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/aws-c-common/aws_priority_queue_init_dynamic_harness-1.i[4505,4518] [2021-12-18 01:06:55,540 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_priority_queue_init_dynamic_harness-1.i[4565,4578] [2021-12-18 01:06:56,014 WARN L610 FunctionHandler]: implicit declaration of function __builtin_va_copy [2021-12-18 01:06:56,067 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-18 01:06:56,067 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-18 01:06:56,068 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-18 01:06:56,068 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-18 01:06:56,069 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-18 01:06:56,076 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-18 01:06:56,077 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-18 01:06:56,079 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-18 01:06:56,081 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-18 01:06:56,261 WARN L610 FunctionHandler]: implicit declaration of function __atomic_load_n [2021-12-18 01:06:56,262 WARN L610 FunctionHandler]: implicit declaration of function __atomic_store_n [2021-12-18 01:06:56,263 WARN L610 FunctionHandler]: implicit declaration of function __atomic_exchange_n [2021-12-18 01:06:56,263 WARN L610 FunctionHandler]: implicit declaration of function __atomic_compare_exchange_n [2021-12-18 01:06:56,264 WARN L610 FunctionHandler]: implicit declaration of function __atomic_fetch_add [2021-12-18 01:06:56,265 WARN L610 FunctionHandler]: implicit declaration of function __atomic_fetch_sub [2021-12-18 01:06:56,265 WARN L610 FunctionHandler]: implicit declaration of function __atomic_fetch_or [2021-12-18 01:06:56,266 WARN L610 FunctionHandler]: implicit declaration of function __atomic_fetch_and [2021-12-18 01:06:56,266 WARN L610 FunctionHandler]: implicit declaration of function __atomic_fetch_xor [2021-12-18 01:06:56,266 WARN L610 FunctionHandler]: implicit declaration of function __atomic_thread_fence [2021-12-18 01:06:56,342 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-18 01:06:56,342 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-18 01:06:56,387 INFO L209 PostProcessor]: Analyzing one entry point: main [2021-12-18 01:06:56,417 INFO L203 MainTranslator]: Completed pre-run [2021-12-18 01:06:56,445 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_priority_queue_init_dynamic_harness-1.i[4505,4518] [2021-12-18 01:06:56,447 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_priority_queue_init_dynamic_harness-1.i[4565,4578] [2021-12-18 01:06:56,464 WARN L610 FunctionHandler]: implicit declaration of function __builtin_va_copy [2021-12-18 01:06:56,473 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-18 01:06:56,474 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-18 01:06:56,474 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-18 01:06:56,474 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-18 01:06:56,475 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-18 01:06:56,479 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-18 01:06:56,479 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-18 01:06:56,480 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-18 01:06:56,480 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-18 01:06:56,501 WARN L610 FunctionHandler]: implicit declaration of function __atomic_load_n [2021-12-18 01:06:56,502 WARN L610 FunctionHandler]: implicit declaration of function __atomic_store_n [2021-12-18 01:06:56,503 WARN L610 FunctionHandler]: implicit declaration of function __atomic_exchange_n [2021-12-18 01:06:56,503 WARN L610 FunctionHandler]: implicit declaration of function __atomic_compare_exchange_n [2021-12-18 01:06:56,504 WARN L610 FunctionHandler]: implicit declaration of function __atomic_fetch_add [2021-12-18 01:06:56,505 WARN L610 FunctionHandler]: implicit declaration of function __atomic_fetch_sub [2021-12-18 01:06:56,505 WARN L610 FunctionHandler]: implicit declaration of function __atomic_fetch_or [2021-12-18 01:06:56,505 WARN L610 FunctionHandler]: implicit declaration of function __atomic_fetch_and [2021-12-18 01:06:56,506 WARN L610 FunctionHandler]: implicit declaration of function __atomic_fetch_xor [2021-12-18 01:06:56,506 WARN L610 FunctionHandler]: implicit declaration of function __atomic_thread_fence [2021-12-18 01:06:56,525 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-18 01:06:56,526 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-18 01:06:56,551 INFO L209 PostProcessor]: Analyzing one entry point: main [2021-12-18 01:06:56,684 INFO L208 MainTranslator]: Completed translation [2021-12-18 01:06:56,684 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.12 01:06:56 WrapperNode [2021-12-18 01:06:56,684 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2021-12-18 01:06:56,685 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2021-12-18 01:06:56,685 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2021-12-18 01:06:56,685 INFO L275 PluginConnector]: Boogie Procedure Inliner initialized [2021-12-18 01:06:56,689 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.12 01:06:56" (1/1) ... [2021-12-18 01:06:56,746 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.12 01:06:56" (1/1) ... [2021-12-18 01:06:56,816 INFO L137 Inliner]: procedures = 689, calls = 1517, calls flagged for inlining = 52, calls inlined = 9, statements flattened = 742 [2021-12-18 01:06:56,816 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2021-12-18 01:06:56,817 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2021-12-18 01:06:56,817 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2021-12-18 01:06:56,817 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2021-12-18 01:06:56,832 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.12 01:06:56" (1/1) ... [2021-12-18 01:06:56,833 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.12 01:06:56" (1/1) ... [2021-12-18 01:06:56,852 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.12 01:06:56" (1/1) ... [2021-12-18 01:06:56,852 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.12 01:06:56" (1/1) ... [2021-12-18 01:06:56,887 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.12 01:06:56" (1/1) ... [2021-12-18 01:06:56,908 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.12 01:06:56" (1/1) ... [2021-12-18 01:06:56,913 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.12 01:06:56" (1/1) ... [2021-12-18 01:06:56,918 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2021-12-18 01:06:56,919 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2021-12-18 01:06:56,919 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2021-12-18 01:06:56,919 INFO L275 PluginConnector]: RCFGBuilder initialized [2021-12-18 01:06:56,927 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.12 01:06:56" (1/1) ... [2021-12-18 01:06:56,932 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2021-12-18 01:06:56,939 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-18 01:06:56,962 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-18 01:06:56,991 INFO L130 BoogieDeclarations]: Found specification of procedure aws_is_mem_zeroed [2021-12-18 01:06:56,991 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_is_mem_zeroed [2021-12-18 01:06:56,991 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2021-12-18 01:06:56,991 INFO L130 BoogieDeclarations]: Found specification of procedure aws_array_list_is_valid [2021-12-18 01:06:56,991 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_array_list_is_valid [2021-12-18 01:06:56,991 INFO L130 BoogieDeclarations]: Found specification of procedure nondet_bool [2021-12-18 01:06:56,992 INFO L138 BoogieDeclarations]: Found implementation of procedure nondet_bool [2021-12-18 01:06:56,992 INFO L130 BoogieDeclarations]: Found specification of procedure aws_allocator_is_valid [2021-12-18 01:06:56,992 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_allocator_is_valid [2021-12-18 01:06:56,992 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2021-12-18 01:06:56,993 INFO L130 BoogieDeclarations]: Found specification of procedure aws_raise_error [2021-12-18 01:06:56,993 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_raise_error [2021-12-18 01:06:56,994 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2021-12-18 01:06:56,994 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2021-12-18 01:06:56,994 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnHeap [2021-12-18 01:06:56,995 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2021-12-18 01:06:56,995 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$ [2021-12-18 01:06:56,995 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2021-12-18 01:06:57,003 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2021-12-18 01:06:57,003 INFO L130 BoogieDeclarations]: Found specification of procedure bounded_malloc [2021-12-18 01:06:57,004 INFO L138 BoogieDeclarations]: Found implementation of procedure bounded_malloc [2021-12-18 01:06:56,983 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-18 01:06:57,006 INFO L130 BoogieDeclarations]: Found specification of procedure nondet_size_t [2021-12-18 01:06:57,006 INFO L138 BoogieDeclarations]: Found implementation of procedure nondet_size_t [2021-12-18 01:06:57,006 INFO L130 BoogieDeclarations]: Found specification of procedure aws_mul_size_checked [2021-12-18 01:06:57,006 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_mul_size_checked [2021-12-18 01:06:57,007 INFO L130 BoogieDeclarations]: Found specification of procedure can_fail_malloc [2021-12-18 01:06:57,007 INFO L138 BoogieDeclarations]: Found implementation of procedure can_fail_malloc [2021-12-18 01:06:57,007 INFO L130 BoogieDeclarations]: Found specification of procedure aws_priority_queue_is_valid [2021-12-18 01:06:57,007 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_priority_queue_is_valid [2021-12-18 01:06:57,007 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2021-12-18 01:06:57,008 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2021-12-18 01:06:57,008 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2021-12-18 01:06:57,008 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$ [2021-12-18 01:06:57,008 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$ [2021-12-18 01:06:57,008 INFO L130 BoogieDeclarations]: Found specification of procedure can_fail_allocator [2021-12-18 01:06:57,008 INFO L138 BoogieDeclarations]: Found implementation of procedure can_fail_allocator [2021-12-18 01:06:57,009 INFO L130 BoogieDeclarations]: Found specification of procedure __CPROVER_overflow_mult [2021-12-18 01:06:57,009 INFO L138 BoogieDeclarations]: Found implementation of procedure __CPROVER_overflow_mult [2021-12-18 01:06:57,009 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2021-12-18 01:06:57,009 INFO L130 BoogieDeclarations]: Found specification of procedure memset_impl [2021-12-18 01:06:57,009 INFO L138 BoogieDeclarations]: Found implementation of procedure memset_impl [2021-12-18 01:06:57,009 INFO L130 BoogieDeclarations]: Found specification of procedure my_memset [2021-12-18 01:06:57,010 INFO L138 BoogieDeclarations]: Found implementation of procedure my_memset [2021-12-18 01:06:57,010 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2021-12-18 01:06:57,272 INFO L236 CfgBuilder]: Building ICFG [2021-12-18 01:06:57,274 INFO L262 CfgBuilder]: Building CFG for each procedure with an implementation [2021-12-18 01:06:57,789 INFO L277 CfgBuilder]: Performing block encoding [2021-12-18 01:06:57,794 INFO L296 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2021-12-18 01:06:57,795 INFO L301 CfgBuilder]: Removed 6 assume(true) statements. [2021-12-18 01:06:57,797 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 18.12 01:06:57 BoogieIcfgContainer [2021-12-18 01:06:57,798 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2021-12-18 01:06:57,799 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2021-12-18 01:06:57,799 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2021-12-18 01:06:57,801 INFO L275 PluginConnector]: TraceAbstraction initialized [2021-12-18 01:06:57,801 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 18.12 01:06:55" (1/3) ... [2021-12-18 01:06:57,802 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@70784345 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 18.12 01:06:57, skipping insertion in model container [2021-12-18 01:06:57,802 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.12 01:06:56" (2/3) ... [2021-12-18 01:06:57,802 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@70784345 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 18.12 01:06:57, skipping insertion in model container [2021-12-18 01:06:57,802 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 18.12 01:06:57" (3/3) ... [2021-12-18 01:06:57,803 INFO L111 eAbstractionObserver]: Analyzing ICFG aws_priority_queue_init_dynamic_harness-1.i [2021-12-18 01:06:57,807 INFO L204 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2021-12-18 01:06:57,807 INFO L163 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2021-12-18 01:06:57,846 INFO L338 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2021-12-18 01:06:57,860 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-18 01:06:57,860 INFO L340 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2021-12-18 01:06:57,878 INFO L276 IsEmpty]: Start isEmpty. Operand has 205 states, 133 states have (on average 1.255639097744361) internal successors, (167), 133 states have internal predecessors, (167), 56 states have call successors, (56), 16 states have call predecessors, (56), 16 states have return successors, (56), 56 states have call predecessors, (56), 56 states have call successors, (56) [2021-12-18 01:06:57,888 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 113 [2021-12-18 01:06:57,888 INFO L506 BasicCegarLoop]: Found error trace [2021-12-18 01:06:57,889 INFO L514 BasicCegarLoop]: trace histogram [10, 10, 10, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-18 01:06:57,889 INFO L402 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-18 01:06:57,893 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-18 01:06:57,893 INFO L85 PathProgramCache]: Analyzing trace with hash -1293047729, now seen corresponding path program 1 times [2021-12-18 01:06:57,900 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-18 01:06:57,902 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [975455016] [2021-12-18 01:06:57,902 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-18 01:06:57,903 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-18 01:06:58,187 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-18 01:06:58,299 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2021-12-18 01:06:58,304 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-18 01:06:58,315 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2021-12-18 01:06:58,318 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-18 01:06:58,325 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2021-12-18 01:06:58,330 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-18 01:06:58,340 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2021-12-18 01:06:58,348 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-18 01:06:58,356 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 22 [2021-12-18 01:06:58,358 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-18 01:06:58,387 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 27 [2021-12-18 01:06:58,397 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-18 01:06:58,397 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [975455016] [2021-12-18 01:06:58,397 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unsupported non-linear arithmetic [2021-12-18 01:06:58,398 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1859492881] [2021-12-18 01:06:58,398 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-18 01:06:58,398 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-18 01:06:58,398 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-18 01:06:58,400 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-18 01:06:58,401 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-18 01:06:58,802 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-18 01:06:58,810 INFO L263 TraceCheckSpWp]: Trace formula consists of 2214 conjuncts, 1 conjunts are in the unsatisfiable core [2021-12-18 01:06:58,817 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-18 01:06:59,034 INFO L134 CoverageAnalysis]: Checked inductivity of 192 backedges. 18 proven. 0 refuted. 0 times theorem prover too weak. 174 trivial. 0 not checked. [2021-12-18 01:06:59,035 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-18 01:06:59,035 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1859492881] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-18 01:06:59,035 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-18 01:06:59,036 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2021-12-18 01:06:59,037 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [19203562] [2021-12-18 01:06:59,038 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-18 01:06:59,041 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2021-12-18 01:06:59,041 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-18 01:06:59,063 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2021-12-18 01:06:59,064 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2021-12-18 01:06:59,067 INFO L87 Difference]: Start difference. First operand has 205 states, 133 states have (on average 1.255639097744361) internal successors, (167), 133 states have internal predecessors, (167), 56 states have call successors, (56), 16 states have call predecessors, (56), 16 states have return successors, (56), 56 states have call predecessors, (56), 56 states have call successors, (56) Second operand has 2 states, 2 states have (on average 20.0) internal successors, (40), 2 states have internal predecessors, (40), 2 states have call successors, (19), 2 states have call predecessors, (19), 2 states have return successors, (18), 2 states have call predecessors, (18), 2 states have call successors, (18) [2021-12-18 01:06:59,114 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-18 01:06:59,115 INFO L93 Difference]: Finished difference Result 401 states and 585 transitions. [2021-12-18 01:06:59,116 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2021-12-18 01:06:59,117 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 20.0) internal successors, (40), 2 states have internal predecessors, (40), 2 states have call successors, (19), 2 states have call predecessors, (19), 2 states have return successors, (18), 2 states have call predecessors, (18), 2 states have call successors, (18) Word has length 112 [2021-12-18 01:06:59,117 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-18 01:06:59,127 INFO L225 Difference]: With dead ends: 401 [2021-12-18 01:06:59,127 INFO L226 Difference]: Without dead ends: 198 [2021-12-18 01:06:59,133 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 126 GetRequests, 125 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-18 01:06:59,139 INFO L933 BasicCegarLoop]: 271 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, 271 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-18 01:06:59,142 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [0 Valid, 271 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-12-18 01:06:59,157 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 198 states. [2021-12-18 01:06:59,185 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 198 to 198. [2021-12-18 01:06:59,186 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 198 states, 125 states have (on average 1.224) internal successors, (153), 127 states have internal predecessors, (153), 56 states have call successors, (56), 16 states have call predecessors, (56), 16 states have return successors, (54), 54 states have call predecessors, (54), 54 states have call successors, (54) [2021-12-18 01:06:59,187 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 198 states to 198 states and 263 transitions. [2021-12-18 01:06:59,188 INFO L78 Accepts]: Start accepts. Automaton has 198 states and 263 transitions. Word has length 112 [2021-12-18 01:06:59,189 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-18 01:06:59,189 INFO L470 AbstractCegarLoop]: Abstraction has 198 states and 263 transitions. [2021-12-18 01:06:59,189 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 20.0) internal successors, (40), 2 states have internal predecessors, (40), 2 states have call successors, (19), 2 states have call predecessors, (19), 2 states have return successors, (18), 2 states have call predecessors, (18), 2 states have call successors, (18) [2021-12-18 01:06:59,189 INFO L276 IsEmpty]: Start isEmpty. Operand 198 states and 263 transitions. [2021-12-18 01:06:59,191 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 147 [2021-12-18 01:06:59,191 INFO L506 BasicCegarLoop]: Found error trace [2021-12-18 01:06:59,191 INFO L514 BasicCegarLoop]: trace histogram [12, 12, 12, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-18 01:06:59,213 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-18 01:06:59,392 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-18 01:06:59,392 INFO L402 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-18 01:06:59,392 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-18 01:06:59,393 INFO L85 PathProgramCache]: Analyzing trace with hash -1403140028, now seen corresponding path program 1 times [2021-12-18 01:06:59,393 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-18 01:06:59,393 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [740621544] [2021-12-18 01:06:59,393 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-18 01:06:59,393 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-18 01:06:59,453 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-18 01:06:59,453 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1653403138] [2021-12-18 01:06:59,453 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-18 01:06:59,453 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-18 01:06:59,453 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-18 01:06:59,454 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-18 01:06:59,455 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-18 01:06:59,804 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-18 01:06:59,811 INFO L263 TraceCheckSpWp]: Trace formula consists of 2368 conjuncts, 7 conjunts are in the unsatisfiable core [2021-12-18 01:06:59,816 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-18 01:07:00,011 INFO L134 CoverageAnalysis]: Checked inductivity of 287 backedges. 3 proven. 0 refuted. 0 times theorem prover too weak. 284 trivial. 0 not checked. [2021-12-18 01:07:00,012 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-18 01:07:00,012 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-18 01:07:00,012 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [740621544] [2021-12-18 01:07:00,012 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-18 01:07:00,012 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1653403138] [2021-12-18 01:07:00,013 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1653403138] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-18 01:07:00,013 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-18 01:07:00,013 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2021-12-18 01:07:00,013 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1751524899] [2021-12-18 01:07:00,013 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-18 01:07:00,014 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2021-12-18 01:07:00,014 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-18 01:07:00,014 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2021-12-18 01:07:00,015 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2021-12-18 01:07:00,015 INFO L87 Difference]: Start difference. First operand 198 states and 263 transitions. Second operand has 5 states, 5 states have (on average 10.0) internal successors, (50), 5 states have internal predecessors, (50), 2 states have call successors, (23), 2 states have call predecessors, (23), 3 states have return successors, (22), 3 states have call predecessors, (22), 2 states have call successors, (22) [2021-12-18 01:07:00,070 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-18 01:07:00,071 INFO L93 Difference]: Finished difference Result 302 states and 404 transitions. [2021-12-18 01:07:00,071 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2021-12-18 01:07:00,071 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 10.0) internal successors, (50), 5 states have internal predecessors, (50), 2 states have call successors, (23), 2 states have call predecessors, (23), 3 states have return successors, (22), 3 states have call predecessors, (22), 2 states have call successors, (22) Word has length 146 [2021-12-18 01:07:00,072 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-18 01:07:00,074 INFO L225 Difference]: With dead ends: 302 [2021-12-18 01:07:00,074 INFO L226 Difference]: Without dead ends: 203 [2021-12-18 01:07:00,074 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 146 GetRequests, 142 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-18 01:07:00,075 INFO L933 BasicCegarLoop]: 260 mSDtfsCounter, 2 mSDsluCounter, 775 mSDsCounter, 0 mSdLazyCounter, 16 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 1035 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-18 01:07:00,075 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 1035 Invalid, 16 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 16 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-12-18 01:07:00,076 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 203 states. [2021-12-18 01:07:00,087 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 203 to 203. [2021-12-18 01:07:00,087 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 203 states, 129 states have (on average 1.2170542635658914) internal successors, (157), 131 states have internal predecessors, (157), 56 states have call successors, (56), 16 states have call predecessors, (56), 17 states have return successors, (57), 55 states have call predecessors, (57), 54 states have call successors, (57) [2021-12-18 01:07:00,088 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 203 states to 203 states and 270 transitions. [2021-12-18 01:07:00,088 INFO L78 Accepts]: Start accepts. Automaton has 203 states and 270 transitions. Word has length 146 [2021-12-18 01:07:00,089 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-18 01:07:00,089 INFO L470 AbstractCegarLoop]: Abstraction has 203 states and 270 transitions. [2021-12-18 01:07:00,089 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 10.0) internal successors, (50), 5 states have internal predecessors, (50), 2 states have call successors, (23), 2 states have call predecessors, (23), 3 states have return successors, (22), 3 states have call predecessors, (22), 2 states have call successors, (22) [2021-12-18 01:07:00,089 INFO L276 IsEmpty]: Start isEmpty. Operand 203 states and 270 transitions. [2021-12-18 01:07:00,091 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 148 [2021-12-18 01:07:00,091 INFO L506 BasicCegarLoop]: Found error trace [2021-12-18 01:07:00,091 INFO L514 BasicCegarLoop]: trace histogram [12, 12, 12, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-18 01:07:00,112 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-18 01:07:00,291 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-18 01:07:00,292 INFO L402 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-18 01:07:00,292 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-18 01:07:00,292 INFO L85 PathProgramCache]: Analyzing trace with hash 494695836, now seen corresponding path program 1 times [2021-12-18 01:07:00,292 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-18 01:07:00,292 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1192555838] [2021-12-18 01:07:00,293 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-18 01:07:00,293 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-18 01:07:00,333 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-18 01:07:00,336 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1931271541] [2021-12-18 01:07:00,337 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-18 01:07:00,337 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-18 01:07:00,337 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-18 01:07:00,344 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-18 01:07:00,345 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-18 01:07:00,697 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-18 01:07:00,706 INFO L263 TraceCheckSpWp]: Trace formula consists of 2388 conjuncts, 17 conjunts are in the unsatisfiable core [2021-12-18 01:07:00,710 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-18 01:07:00,982 INFO L134 CoverageAnalysis]: Checked inductivity of 293 backedges. 6 proven. 30 refuted. 0 times theorem prover too weak. 257 trivial. 0 not checked. [2021-12-18 01:07:00,982 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-18 01:07:01,247 INFO L134 CoverageAnalysis]: Checked inductivity of 293 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 293 trivial. 0 not checked. [2021-12-18 01:07:01,247 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-18 01:07:01,247 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1192555838] [2021-12-18 01:07:01,247 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-18 01:07:01,247 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1931271541] [2021-12-18 01:07:01,247 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1931271541] provided 1 perfect and 1 imperfect interpolant sequences [2021-12-18 01:07:01,247 INFO L186 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2021-12-18 01:07:01,247 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [10] total 12 [2021-12-18 01:07:01,248 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [13862137] [2021-12-18 01:07:01,248 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-18 01:07:01,248 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2021-12-18 01:07:01,248 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-18 01:07:01,248 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2021-12-18 01:07:01,249 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=23, Invalid=109, Unknown=0, NotChecked=0, Total=132 [2021-12-18 01:07:01,249 INFO L87 Difference]: Start difference. First operand 203 states and 270 transitions. Second operand has 5 states, 4 states have (on average 11.5) internal successors, (46), 4 states have internal predecessors, (46), 2 states have call successors, (23), 2 states have call predecessors, (23), 1 states have return successors, (22), 1 states have call predecessors, (22), 1 states have call successors, (22) [2021-12-18 01:07:01,301 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-18 01:07:01,301 INFO L93 Difference]: Finished difference Result 211 states and 278 transitions. [2021-12-18 01:07:01,302 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2021-12-18 01:07:01,302 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 11.5) internal successors, (46), 4 states have internal predecessors, (46), 2 states have call successors, (23), 2 states have call predecessors, (23), 1 states have return successors, (22), 1 states have call predecessors, (22), 1 states have call successors, (22) Word has length 147 [2021-12-18 01:07:01,303 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-18 01:07:01,304 INFO L225 Difference]: With dead ends: 211 [2021-12-18 01:07:01,304 INFO L226 Difference]: Without dead ends: 209 [2021-12-18 01:07:01,304 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 293 GetRequests, 282 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-18 01:07:01,305 INFO L933 BasicCegarLoop]: 264 mSDtfsCounter, 4 mSDsluCounter, 767 mSDsCounter, 0 mSdLazyCounter, 27 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 1031 SdHoareTripleChecker+Invalid, 28 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 27 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-12-18 01:07:01,305 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [5 Valid, 1031 Invalid, 28 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 27 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-12-18 01:07:01,306 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 209 states. [2021-12-18 01:07:01,320 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 209 to 208. [2021-12-18 01:07:01,320 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 208 states, 132 states have (on average 1.2121212121212122) internal successors, (160), 135 states have internal predecessors, (160), 57 states have call successors, (57), 17 states have call predecessors, (57), 18 states have return successors, (58), 55 states have call predecessors, (58), 55 states have call successors, (58) [2021-12-18 01:07:01,321 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 208 states to 208 states and 275 transitions. [2021-12-18 01:07:01,322 INFO L78 Accepts]: Start accepts. Automaton has 208 states and 275 transitions. Word has length 147 [2021-12-18 01:07:01,322 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-18 01:07:01,322 INFO L470 AbstractCegarLoop]: Abstraction has 208 states and 275 transitions. [2021-12-18 01:07:01,322 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 11.5) internal successors, (46), 4 states have internal predecessors, (46), 2 states have call successors, (23), 2 states have call predecessors, (23), 1 states have return successors, (22), 1 states have call predecessors, (22), 1 states have call successors, (22) [2021-12-18 01:07:01,322 INFO L276 IsEmpty]: Start isEmpty. Operand 208 states and 275 transitions. [2021-12-18 01:07:01,324 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 148 [2021-12-18 01:07:01,324 INFO L506 BasicCegarLoop]: Found error trace [2021-12-18 01:07:01,324 INFO L514 BasicCegarLoop]: trace histogram [12, 12, 12, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-18 01:07:01,363 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-18 01:07:01,539 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-18 01:07:01,540 INFO L402 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-18 01:07:01,540 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-18 01:07:01,540 INFO L85 PathProgramCache]: Analyzing trace with hash 496542878, now seen corresponding path program 1 times [2021-12-18 01:07:01,540 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-18 01:07:01,540 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1791900040] [2021-12-18 01:07:01,540 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-18 01:07:01,540 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-18 01:07:01,580 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-18 01:07:01,581 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [985759967] [2021-12-18 01:07:01,581 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-18 01:07:01,581 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-18 01:07:01,581 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-18 01:07:01,582 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-18 01:07:01,587 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-18 01:07:01,938 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-18 01:07:01,946 INFO L263 TraceCheckSpWp]: Trace formula consists of 2393 conjuncts, 9 conjunts are in the unsatisfiable core [2021-12-18 01:07:01,950 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-18 01:07:02,151 INFO L134 CoverageAnalysis]: Checked inductivity of 293 backedges. 154 proven. 0 refuted. 0 times theorem prover too weak. 139 trivial. 0 not checked. [2021-12-18 01:07:02,151 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-18 01:07:02,151 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-18 01:07:02,152 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1791900040] [2021-12-18 01:07:02,152 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-18 01:07:02,152 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [985759967] [2021-12-18 01:07:02,152 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [985759967] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-18 01:07:02,152 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-18 01:07:02,152 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2021-12-18 01:07:02,152 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1548823872] [2021-12-18 01:07:02,152 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-18 01:07:02,153 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2021-12-18 01:07:02,153 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-18 01:07:02,154 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2021-12-18 01:07:02,154 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2021-12-18 01:07:02,154 INFO L87 Difference]: Start difference. First operand 208 states and 275 transitions. Second operand has 6 states, 5 states have (on average 12.8) internal successors, (64), 6 states have internal predecessors, (64), 4 states have call successors, (26), 2 states have call predecessors, (26), 4 states have return successors, (25), 4 states have call predecessors, (25), 4 states have call successors, (25) [2021-12-18 01:07:02,204 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-18 01:07:02,204 INFO L93 Difference]: Finished difference Result 401 states and 523 transitions. [2021-12-18 01:07:02,205 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2021-12-18 01:07:02,205 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 12.8) internal successors, (64), 6 states have internal predecessors, (64), 4 states have call successors, (26), 2 states have call predecessors, (26), 4 states have return successors, (25), 4 states have call predecessors, (25), 4 states have call successors, (25) Word has length 147 [2021-12-18 01:07:02,205 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-18 01:07:02,207 INFO L225 Difference]: With dead ends: 401 [2021-12-18 01:07:02,207 INFO L226 Difference]: Without dead ends: 208 [2021-12-18 01:07:02,208 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 148 GetRequests, 142 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2021-12-18 01:07:02,208 INFO L933 BasicCegarLoop]: 256 mSDtfsCounter, 13 mSDsluCounter, 1007 mSDsCounter, 0 mSdLazyCounter, 38 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 15 SdHoareTripleChecker+Valid, 1263 SdHoareTripleChecker+Invalid, 39 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 38 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-12-18 01:07:02,209 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [15 Valid, 1263 Invalid, 39 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 38 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-12-18 01:07:02,209 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 208 states. [2021-12-18 01:07:02,217 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 208 to 208. [2021-12-18 01:07:02,218 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 208 states, 132 states have (on average 1.2045454545454546) internal successors, (159), 135 states have internal predecessors, (159), 57 states have call successors, (57), 17 states have call predecessors, (57), 18 states have return successors, (58), 55 states have call predecessors, (58), 55 states have call successors, (58) [2021-12-18 01:07:02,219 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 208 states to 208 states and 274 transitions. [2021-12-18 01:07:02,222 INFO L78 Accepts]: Start accepts. Automaton has 208 states and 274 transitions. Word has length 147 [2021-12-18 01:07:02,222 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-18 01:07:02,222 INFO L470 AbstractCegarLoop]: Abstraction has 208 states and 274 transitions. [2021-12-18 01:07:02,222 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 12.8) internal successors, (64), 6 states have internal predecessors, (64), 4 states have call successors, (26), 2 states have call predecessors, (26), 4 states have return successors, (25), 4 states have call predecessors, (25), 4 states have call successors, (25) [2021-12-18 01:07:02,222 INFO L276 IsEmpty]: Start isEmpty. Operand 208 states and 274 transitions. [2021-12-18 01:07:02,224 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 150 [2021-12-18 01:07:02,224 INFO L506 BasicCegarLoop]: Found error trace [2021-12-18 01:07:02,224 INFO L514 BasicCegarLoop]: trace histogram [12, 12, 12, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-18 01:07:02,246 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2021-12-18 01:07:02,427 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-18 01:07:02,427 INFO L402 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-18 01:07:02,428 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-18 01:07:02,428 INFO L85 PathProgramCache]: Analyzing trace with hash -50417486, now seen corresponding path program 1 times [2021-12-18 01:07:02,428 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-18 01:07:02,428 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1248437935] [2021-12-18 01:07:02,428 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-18 01:07:02,428 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-18 01:07:02,473 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-18 01:07:02,473 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1896456353] [2021-12-18 01:07:02,474 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-18 01:07:02,474 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-18 01:07:02,474 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-18 01:07:02,475 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-18 01:07:02,476 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-18 01:07:02,818 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-18 01:07:02,827 INFO L263 TraceCheckSpWp]: Trace formula consists of 2407 conjuncts, 22 conjunts are in the unsatisfiable core [2021-12-18 01:07:02,830 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-18 01:07:03,049 INFO L134 CoverageAnalysis]: Checked inductivity of 294 backedges. 15 proven. 7 refuted. 0 times theorem prover too weak. 272 trivial. 0 not checked. [2021-12-18 01:07:03,049 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-18 01:07:03,448 INFO L134 CoverageAnalysis]: Checked inductivity of 294 backedges. 10 proven. 0 refuted. 0 times theorem prover too weak. 284 trivial. 0 not checked. [2021-12-18 01:07:03,448 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-18 01:07:03,448 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1248437935] [2021-12-18 01:07:03,448 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-18 01:07:03,448 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1896456353] [2021-12-18 01:07:03,448 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1896456353] provided 1 perfect and 1 imperfect interpolant sequences [2021-12-18 01:07:03,448 INFO L186 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2021-12-18 01:07:03,448 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [9] total 13 [2021-12-18 01:07:03,448 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1846691153] [2021-12-18 01:07:03,448 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-18 01:07:03,449 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2021-12-18 01:07:03,449 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-18 01:07:03,449 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2021-12-18 01:07:03,449 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=34, Invalid=122, Unknown=0, NotChecked=0, Total=156 [2021-12-18 01:07:03,450 INFO L87 Difference]: Start difference. First operand 208 states and 274 transitions. Second operand has 7 states, 6 states have (on average 9.166666666666666) internal successors, (55), 7 states have internal predecessors, (55), 4 states have call successors, (25), 2 states have call predecessors, (25), 3 states have return successors, (24), 4 states have call predecessors, (24), 4 states have call successors, (24) [2021-12-18 01:07:03,489 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-18 01:07:03,489 INFO L93 Difference]: Finished difference Result 402 states and 523 transitions. [2021-12-18 01:07:03,489 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2021-12-18 01:07:03,490 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 6 states have (on average 9.166666666666666) internal successors, (55), 7 states have internal predecessors, (55), 4 states have call successors, (25), 2 states have call predecessors, (25), 3 states have return successors, (24), 4 states have call predecessors, (24), 4 states have call successors, (24) Word has length 149 [2021-12-18 01:07:03,490 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-18 01:07:03,491 INFO L225 Difference]: With dead ends: 402 [2021-12-18 01:07:03,491 INFO L226 Difference]: Without dead ends: 209 [2021-12-18 01:07:03,492 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 296 GetRequests, 285 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 11 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=34, Invalid=122, Unknown=0, NotChecked=0, Total=156 [2021-12-18 01:07:03,492 INFO L933 BasicCegarLoop]: 255 mSDtfsCounter, 17 mSDsluCounter, 1006 mSDsCounter, 0 mSdLazyCounter, 43 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 19 SdHoareTripleChecker+Valid, 1261 SdHoareTripleChecker+Invalid, 46 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 43 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-12-18 01:07:03,492 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [19 Valid, 1261 Invalid, 46 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 43 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-12-18 01:07:03,493 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 209 states. [2021-12-18 01:07:03,499 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 209 to 209. [2021-12-18 01:07:03,499 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 209 states, 133 states have (on average 1.2030075187969924) internal successors, (160), 136 states have internal predecessors, (160), 57 states have call successors, (57), 17 states have call predecessors, (57), 18 states have return successors, (58), 55 states have call predecessors, (58), 55 states have call successors, (58) [2021-12-18 01:07:03,500 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 209 states to 209 states and 275 transitions. [2021-12-18 01:07:03,501 INFO L78 Accepts]: Start accepts. Automaton has 209 states and 275 transitions. Word has length 149 [2021-12-18 01:07:03,501 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-18 01:07:03,501 INFO L470 AbstractCegarLoop]: Abstraction has 209 states and 275 transitions. [2021-12-18 01:07:03,501 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 6 states have (on average 9.166666666666666) internal successors, (55), 7 states have internal predecessors, (55), 4 states have call successors, (25), 2 states have call predecessors, (25), 3 states have return successors, (24), 4 states have call predecessors, (24), 4 states have call successors, (24) [2021-12-18 01:07:03,501 INFO L276 IsEmpty]: Start isEmpty. Operand 209 states and 275 transitions. [2021-12-18 01:07:03,502 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 154 [2021-12-18 01:07:03,502 INFO L506 BasicCegarLoop]: Found error trace [2021-12-18 01:07:03,503 INFO L514 BasicCegarLoop]: trace histogram [12, 12, 12, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-18 01:07:03,543 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-18 01:07:03,727 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-18 01:07:03,727 INFO L402 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-18 01:07:03,728 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-18 01:07:03,728 INFO L85 PathProgramCache]: Analyzing trace with hash 2024331122, now seen corresponding path program 1 times [2021-12-18 01:07:03,728 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-18 01:07:03,728 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2022177122] [2021-12-18 01:07:03,728 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-18 01:07:03,728 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-18 01:07:03,770 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-18 01:07:03,771 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [4588423] [2021-12-18 01:07:03,771 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-18 01:07:03,771 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-18 01:07:03,771 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-18 01:07:03,772 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-18 01:07:03,773 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-18 01:07:04,149 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-18 01:07:04,158 INFO L263 TraceCheckSpWp]: Trace formula consists of 2445 conjuncts, 26 conjunts are in the unsatisfiable core [2021-12-18 01:07:04,161 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-18 01:07:04,407 INFO L134 CoverageAnalysis]: Checked inductivity of 300 backedges. 159 proven. 1 refuted. 0 times theorem prover too weak. 140 trivial. 0 not checked. [2021-12-18 01:07:04,408 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-18 01:07:04,854 INFO L134 CoverageAnalysis]: Checked inductivity of 300 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 285 trivial. 0 not checked. [2021-12-18 01:07:04,855 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-18 01:07:04,855 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2022177122] [2021-12-18 01:07:04,855 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-18 01:07:04,855 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [4588423] [2021-12-18 01:07:04,855 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [4588423] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-18 01:07:04,855 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-12-18 01:07:04,855 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 13 [2021-12-18 01:07:04,855 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1248909238] [2021-12-18 01:07:04,856 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-12-18 01:07:04,856 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2021-12-18 01:07:04,856 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-18 01:07:04,857 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2021-12-18 01:07:04,857 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=38, Invalid=118, Unknown=0, NotChecked=0, Total=156 [2021-12-18 01:07:04,857 INFO L87 Difference]: Start difference. First operand 209 states and 275 transitions. Second operand has 13 states, 11 states have (on average 8.0) internal successors, (88), 13 states have internal predecessors, (88), 6 states have call successors, (36), 2 states have call predecessors, (36), 5 states have return successors, (36), 6 states have call predecessors, (36), 6 states have call successors, (36) [2021-12-18 01:07:04,980 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-18 01:07:04,980 INFO L93 Difference]: Finished difference Result 406 states and 527 transitions. [2021-12-18 01:07:04,983 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2021-12-18 01:07:04,983 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 11 states have (on average 8.0) internal successors, (88), 13 states have internal predecessors, (88), 6 states have call successors, (36), 2 states have call predecessors, (36), 5 states have return successors, (36), 6 states have call predecessors, (36), 6 states have call successors, (36) Word has length 153 [2021-12-18 01:07:04,984 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-18 01:07:04,985 INFO L225 Difference]: With dead ends: 406 [2021-12-18 01:07:04,985 INFO L226 Difference]: Without dead ends: 212 [2021-12-18 01:07:04,985 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 307 GetRequests, 292 SyntacticMatches, 1 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 32 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=60, Invalid=180, Unknown=0, NotChecked=0, Total=240 [2021-12-18 01:07:04,986 INFO L933 BasicCegarLoop]: 255 mSDtfsCounter, 25 mSDsluCounter, 1758 mSDsCounter, 0 mSdLazyCounter, 72 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 27 SdHoareTripleChecker+Valid, 2013 SdHoareTripleChecker+Invalid, 79 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 72 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2021-12-18 01:07:04,986 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [27 Valid, 2013 Invalid, 79 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 72 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2021-12-18 01:07:04,987 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 212 states. [2021-12-18 01:07:04,991 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 212 to 211. [2021-12-18 01:07:04,992 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 211 states, 135 states have (on average 1.2) internal successors, (162), 138 states have internal predecessors, (162), 57 states have call successors, (57), 17 states have call predecessors, (57), 18 states have return successors, (58), 55 states have call predecessors, (58), 55 states have call successors, (58) [2021-12-18 01:07:04,993 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 211 states to 211 states and 277 transitions. [2021-12-18 01:07:04,993 INFO L78 Accepts]: Start accepts. Automaton has 211 states and 277 transitions. Word has length 153 [2021-12-18 01:07:04,993 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-18 01:07:04,993 INFO L470 AbstractCegarLoop]: Abstraction has 211 states and 277 transitions. [2021-12-18 01:07:04,993 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 11 states have (on average 8.0) internal successors, (88), 13 states have internal predecessors, (88), 6 states have call successors, (36), 2 states have call predecessors, (36), 5 states have return successors, (36), 6 states have call predecessors, (36), 6 states have call successors, (36) [2021-12-18 01:07:04,993 INFO L276 IsEmpty]: Start isEmpty. Operand 211 states and 277 transitions. [2021-12-18 01:07:04,994 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 158 [2021-12-18 01:07:04,994 INFO L506 BasicCegarLoop]: Found error trace [2021-12-18 01:07:04,994 INFO L514 BasicCegarLoop]: trace histogram [12, 12, 12, 4, 4, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-18 01:07:05,024 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-18 01:07:05,211 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-18 01:07:05,211 INFO L402 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-18 01:07:05,212 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-18 01:07:05,212 INFO L85 PathProgramCache]: Analyzing trace with hash 1553173810, now seen corresponding path program 2 times [2021-12-18 01:07:05,212 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-18 01:07:05,212 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1892827783] [2021-12-18 01:07:05,212 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-18 01:07:05,212 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-18 01:07:05,263 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-18 01:07:05,263 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [174849565] [2021-12-18 01:07:05,263 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2021-12-18 01:07:05,263 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-18 01:07:05,263 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-18 01:07:05,264 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-18 01:07:05,265 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-18 01:07:05,879 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2021-12-18 01:07:05,879 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-12-18 01:07:05,890 INFO L263 TraceCheckSpWp]: Trace formula consists of 2483 conjuncts, 30 conjunts are in the unsatisfiable core [2021-12-18 01:07:05,894 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-18 01:07:06,165 INFO L134 CoverageAnalysis]: Checked inductivity of 314 backedges. 167 proven. 4 refuted. 0 times theorem prover too weak. 143 trivial. 0 not checked. [2021-12-18 01:07:06,165 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-18 01:07:06,674 INFO L134 CoverageAnalysis]: Checked inductivity of 314 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 288 trivial. 0 not checked. [2021-12-18 01:07:06,674 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-18 01:07:06,674 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1892827783] [2021-12-18 01:07:06,674 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-18 01:07:06,674 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [174849565] [2021-12-18 01:07:06,674 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [174849565] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-18 01:07:06,674 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-12-18 01:07:06,674 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 17 [2021-12-18 01:07:06,675 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1570123316] [2021-12-18 01:07:06,675 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-12-18 01:07:06,675 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2021-12-18 01:07:06,675 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-18 01:07:06,675 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2021-12-18 01:07:06,676 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=57, Invalid=215, Unknown=0, NotChecked=0, Total=272 [2021-12-18 01:07:06,676 INFO L87 Difference]: Start difference. First operand 211 states and 277 transitions. Second operand has 17 states, 15 states have (on average 6.133333333333334) internal successors, (92), 17 states have internal predecessors, (92), 6 states have call successors, (36), 2 states have call predecessors, (36), 5 states have return successors, (36), 6 states have call predecessors, (36), 6 states have call successors, (36) [2021-12-18 01:07:06,869 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-18 01:07:06,869 INFO L93 Difference]: Finished difference Result 410 states and 531 transitions. [2021-12-18 01:07:06,870 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2021-12-18 01:07:06,870 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 15 states have (on average 6.133333333333334) internal successors, (92), 17 states have internal predecessors, (92), 6 states have call successors, (36), 2 states have call predecessors, (36), 5 states have return successors, (36), 6 states have call predecessors, (36), 6 states have call successors, (36) Word has length 157 [2021-12-18 01:07:06,870 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-18 01:07:06,871 INFO L225 Difference]: With dead ends: 410 [2021-12-18 01:07:06,871 INFO L226 Difference]: Without dead ends: 214 [2021-12-18 01:07:06,872 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 317 GetRequests, 297 SyntacticMatches, 0 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 78 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=97, Invalid=365, Unknown=0, NotChecked=0, Total=462 [2021-12-18 01:07:06,872 INFO L933 BasicCegarLoop]: 255 mSDtfsCounter, 42 mSDsluCounter, 2264 mSDsCounter, 0 mSdLazyCounter, 124 mSolverCounterSat, 15 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 44 SdHoareTripleChecker+Valid, 2519 SdHoareTripleChecker+Invalid, 139 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 15 IncrementalHoareTripleChecker+Valid, 124 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2021-12-18 01:07:06,872 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [44 Valid, 2519 Invalid, 139 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [15 Valid, 124 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2021-12-18 01:07:06,873 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 214 states. [2021-12-18 01:07:06,877 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 214 to 213. [2021-12-18 01:07:06,877 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 213 states, 137 states have (on average 1.197080291970803) internal successors, (164), 140 states have internal predecessors, (164), 57 states have call successors, (57), 17 states have call predecessors, (57), 18 states have return successors, (58), 55 states have call predecessors, (58), 55 states have call successors, (58) [2021-12-18 01:07:06,878 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 213 states to 213 states and 279 transitions. [2021-12-18 01:07:06,878 INFO L78 Accepts]: Start accepts. Automaton has 213 states and 279 transitions. Word has length 157 [2021-12-18 01:07:06,879 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-18 01:07:06,879 INFO L470 AbstractCegarLoop]: Abstraction has 213 states and 279 transitions. [2021-12-18 01:07:06,879 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 15 states have (on average 6.133333333333334) internal successors, (92), 17 states have internal predecessors, (92), 6 states have call successors, (36), 2 states have call predecessors, (36), 5 states have return successors, (36), 6 states have call predecessors, (36), 6 states have call successors, (36) [2021-12-18 01:07:06,879 INFO L276 IsEmpty]: Start isEmpty. Operand 213 states and 279 transitions. [2021-12-18 01:07:06,880 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 162 [2021-12-18 01:07:06,880 INFO L506 BasicCegarLoop]: Found error trace [2021-12-18 01:07:06,880 INFO L514 BasicCegarLoop]: trace histogram [12, 12, 12, 6, 6, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-18 01:07:06,907 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2021-12-18 01:07:07,095 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-18 01:07:07,096 INFO L402 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-18 01:07:07,096 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-18 01:07:07,096 INFO L85 PathProgramCache]: Analyzing trace with hash 1663013362, now seen corresponding path program 3 times [2021-12-18 01:07:07,096 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-18 01:07:07,096 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [140721899] [2021-12-18 01:07:07,096 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-18 01:07:07,096 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-18 01:07:07,173 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-18 01:07:07,187 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2100783304] [2021-12-18 01:07:07,187 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2021-12-18 01:07:07,187 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-18 01:07:07,187 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-18 01:07:07,189 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-18 01:07:07,210 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-18 01:07:08,905 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2021-12-18 01:07:08,906 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-12-18 01:07:08,920 INFO L263 TraceCheckSpWp]: Trace formula consists of 2109 conjuncts, 86 conjunts are in the unsatisfiable core [2021-12-18 01:07:08,924 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-18 01:07:09,267 INFO L388 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 0 case distinctions, treesize of input 45 treesize of output 40 [2021-12-18 01:07:09,274 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 2 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 38 treesize of output 43 [2021-12-18 01:07:09,299 WARN L234 Elim1Store]: Array PQE input equivalent to false [2021-12-18 01:07:09,309 INFO L388 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 58 treesize of output 37 [2021-12-18 01:07:09,550 INFO L134 CoverageAnalysis]: Checked inductivity of 336 backedges. 49 proven. 9 refuted. 0 times theorem prover too weak. 278 trivial. 0 not checked. [2021-12-18 01:07:09,550 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-18 01:07:09,686 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-18 01:07:09,686 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [140721899] [2021-12-18 01:07:09,686 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-18 01:07:09,686 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2100783304] [2021-12-18 01:07:09,687 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2100783304] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-18 01:07:09,687 INFO L186 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2021-12-18 01:07:09,687 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11] total 11 [2021-12-18 01:07:09,687 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1026171515] [2021-12-18 01:07:09,687 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2021-12-18 01:07:09,687 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2021-12-18 01:07:09,687 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-18 01:07:09,687 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2021-12-18 01:07:09,688 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=183, Unknown=0, NotChecked=0, Total=210 [2021-12-18 01:07:09,688 INFO L87 Difference]: Start difference. First operand 213 states and 279 transitions. Second operand has 11 states, 10 states have (on average 7.1) internal successors, (71), 11 states have internal predecessors, (71), 4 states have call successors, (26), 2 states have call predecessors, (26), 4 states have return successors, (25), 4 states have call predecessors, (25), 4 states have call successors, (25) [2021-12-18 01:07:10,157 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-18 01:07:10,157 INFO L93 Difference]: Finished difference Result 414 states and 535 transitions. [2021-12-18 01:07:10,158 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2021-12-18 01:07:10,158 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 10 states have (on average 7.1) internal successors, (71), 11 states have internal predecessors, (71), 4 states have call successors, (26), 2 states have call predecessors, (26), 4 states have return successors, (25), 4 states have call predecessors, (25), 4 states have call successors, (25) Word has length 161 [2021-12-18 01:07:10,158 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-18 01:07:10,159 INFO L225 Difference]: With dead ends: 414 [2021-12-18 01:07:10,159 INFO L226 Difference]: Without dead ends: 216 [2021-12-18 01:07:10,160 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 174 GetRequests, 153 SyntacticMatches, 1 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 19 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=59, Invalid=403, Unknown=0, NotChecked=0, Total=462 [2021-12-18 01:07:10,160 INFO L933 BasicCegarLoop]: 254 mSDtfsCounter, 20 mSDsluCounter, 2172 mSDsCounter, 0 mSdLazyCounter, 227 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 22 SdHoareTripleChecker+Valid, 2426 SdHoareTripleChecker+Invalid, 234 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 227 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2021-12-18 01:07:10,161 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [22 Valid, 2426 Invalid, 234 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 227 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2021-12-18 01:07:10,161 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 216 states. [2021-12-18 01:07:10,165 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 216 to 215. [2021-12-18 01:07:10,166 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 215 states, 139 states have (on average 1.1942446043165467) internal successors, (166), 142 states have internal predecessors, (166), 57 states have call successors, (57), 17 states have call predecessors, (57), 18 states have return successors, (58), 55 states have call predecessors, (58), 55 states have call successors, (58) [2021-12-18 01:07:10,169 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 215 states to 215 states and 281 transitions. [2021-12-18 01:07:10,170 INFO L78 Accepts]: Start accepts. Automaton has 215 states and 281 transitions. Word has length 161 [2021-12-18 01:07:10,170 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-18 01:07:10,170 INFO L470 AbstractCegarLoop]: Abstraction has 215 states and 281 transitions. [2021-12-18 01:07:10,170 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 10 states have (on average 7.1) internal successors, (71), 11 states have internal predecessors, (71), 4 states have call successors, (26), 2 states have call predecessors, (26), 4 states have return successors, (25), 4 states have call predecessors, (25), 4 states have call successors, (25) [2021-12-18 01:07:10,171 INFO L276 IsEmpty]: Start isEmpty. Operand 215 states and 281 transitions. [2021-12-18 01:07:10,172 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 166 [2021-12-18 01:07:10,173 INFO L506 BasicCegarLoop]: Found error trace [2021-12-18 01:07:10,173 INFO L514 BasicCegarLoop]: trace histogram [12, 12, 12, 8, 8, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-18 01:07:10,199 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-18 01:07:10,384 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-18 01:07:10,385 INFO L402 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-18 01:07:10,385 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-18 01:07:10,385 INFO L85 PathProgramCache]: Analyzing trace with hash -650271310, now seen corresponding path program 4 times [2021-12-18 01:07:10,385 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-18 01:07:10,385 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1777605256] [2021-12-18 01:07:10,385 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-18 01:07:10,385 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-18 01:07:10,434 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-18 01:07:10,435 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [665034013] [2021-12-18 01:07:10,435 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2021-12-18 01:07:10,435 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-18 01:07:10,435 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-18 01:07:10,436 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-18 01:07:10,437 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-18 01:07:10,914 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2021-12-18 01:07:10,914 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-12-18 01:07:10,926 INFO L263 TraceCheckSpWp]: Trace formula consists of 2559 conjuncts, 28 conjunts are in the unsatisfiable core [2021-12-18 01:07:10,930 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-18 01:07:11,261 INFO L134 CoverageAnalysis]: Checked inductivity of 366 backedges. 64 proven. 16 refuted. 0 times theorem prover too weak. 286 trivial. 0 not checked. [2021-12-18 01:07:11,261 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-18 01:07:11,842 INFO L134 CoverageAnalysis]: Checked inductivity of 366 backedges. 50 proven. 16 refuted. 0 times theorem prover too weak. 300 trivial. 0 not checked. [2021-12-18 01:07:11,843 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-18 01:07:11,843 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1777605256] [2021-12-18 01:07:11,843 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-18 01:07:11,843 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [665034013] [2021-12-18 01:07:11,843 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [665034013] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-18 01:07:11,843 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-12-18 01:07:11,843 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11] total 19 [2021-12-18 01:07:11,844 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1244489073] [2021-12-18 01:07:11,844 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-12-18 01:07:11,844 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2021-12-18 01:07:11,844 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-18 01:07:11,845 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2021-12-18 01:07:11,845 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=71, Invalid=271, Unknown=0, NotChecked=0, Total=342 [2021-12-18 01:07:11,845 INFO L87 Difference]: Start difference. First operand 215 states and 281 transitions. Second operand has 19 states, 17 states have (on average 5.117647058823529) internal successors, (87), 19 states have internal predecessors, (87), 6 states have call successors, (30), 2 states have call predecessors, (30), 5 states have return successors, (31), 6 states have call predecessors, (31), 6 states have call successors, (31) [2021-12-18 01:07:12,037 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-18 01:07:12,037 INFO L93 Difference]: Finished difference Result 418 states and 539 transitions. [2021-12-18 01:07:12,038 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2021-12-18 01:07:12,038 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 17 states have (on average 5.117647058823529) internal successors, (87), 19 states have internal predecessors, (87), 6 states have call successors, (30), 2 states have call predecessors, (30), 5 states have return successors, (31), 6 states have call predecessors, (31), 6 states have call successors, (31) Word has length 165 [2021-12-18 01:07:12,039 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-18 01:07:12,040 INFO L225 Difference]: With dead ends: 418 [2021-12-18 01:07:12,040 INFO L226 Difference]: Without dead ends: 218 [2021-12-18 01:07:12,041 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 331 GetRequests, 311 SyntacticMatches, 0 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 86 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=99, Invalid=363, Unknown=0, NotChecked=0, Total=462 [2021-12-18 01:07:12,041 INFO L933 BasicCegarLoop]: 255 mSDtfsCounter, 46 mSDsluCounter, 2022 mSDsCounter, 0 mSdLazyCounter, 149 mSolverCounterSat, 24 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 48 SdHoareTripleChecker+Valid, 2277 SdHoareTripleChecker+Invalid, 173 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 24 IncrementalHoareTripleChecker+Valid, 149 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2021-12-18 01:07:12,041 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [48 Valid, 2277 Invalid, 173 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [24 Valid, 149 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2021-12-18 01:07:12,042 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 218 states. [2021-12-18 01:07:12,046 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 218 to 217. [2021-12-18 01:07:12,047 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 217 states, 141 states have (on average 1.1914893617021276) internal successors, (168), 144 states have internal predecessors, (168), 57 states have call successors, (57), 17 states have call predecessors, (57), 18 states have return successors, (58), 55 states have call predecessors, (58), 55 states have call successors, (58) [2021-12-18 01:07:12,048 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 217 states to 217 states and 283 transitions. [2021-12-18 01:07:12,048 INFO L78 Accepts]: Start accepts. Automaton has 217 states and 283 transitions. Word has length 165 [2021-12-18 01:07:12,048 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-18 01:07:12,048 INFO L470 AbstractCegarLoop]: Abstraction has 217 states and 283 transitions. [2021-12-18 01:07:12,048 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 17 states have (on average 5.117647058823529) internal successors, (87), 19 states have internal predecessors, (87), 6 states have call successors, (30), 2 states have call predecessors, (30), 5 states have return successors, (31), 6 states have call predecessors, (31), 6 states have call successors, (31) [2021-12-18 01:07:12,048 INFO L276 IsEmpty]: Start isEmpty. Operand 217 states and 283 transitions. [2021-12-18 01:07:12,050 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 170 [2021-12-18 01:07:12,050 INFO L506 BasicCegarLoop]: Found error trace [2021-12-18 01:07:12,050 INFO L514 BasicCegarLoop]: trace histogram [12, 12, 12, 10, 10, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-18 01:07:12,075 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-18 01:07:12,259 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-18 01:07:12,260 INFO L402 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-18 01:07:12,260 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-18 01:07:12,260 INFO L85 PathProgramCache]: Analyzing trace with hash 1517193330, now seen corresponding path program 5 times [2021-12-18 01:07:12,260 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-18 01:07:12,260 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1515386615] [2021-12-18 01:07:12,260 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-18 01:07:12,261 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-18 01:07:12,307 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-18 01:07:12,307 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [731748933] [2021-12-18 01:07:12,308 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2021-12-18 01:07:12,308 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-18 01:07:12,308 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-18 01:07:12,320 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-18 01:07:12,321 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-18 01:07:13,094 INFO L228 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 7 check-sat command(s) [2021-12-18 01:07:13,095 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-12-18 01:07:13,099 INFO L263 TraceCheckSpWp]: Trace formula consists of 462 conjuncts, 22 conjunts are in the unsatisfiable core [2021-12-18 01:07:13,107 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-18 01:07:13,430 INFO L134 CoverageAnalysis]: Checked inductivity of 404 backedges. 215 proven. 25 refuted. 0 times theorem prover too weak. 164 trivial. 0 not checked. [2021-12-18 01:07:13,431 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-18 01:07:13,992 INFO L134 CoverageAnalysis]: Checked inductivity of 404 backedges. 0 proven. 95 refuted. 0 times theorem prover too weak. 309 trivial. 0 not checked. [2021-12-18 01:07:13,992 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-18 01:07:13,992 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1515386615] [2021-12-18 01:07:13,992 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-18 01:07:13,992 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [731748933] [2021-12-18 01:07:13,992 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [731748933] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-18 01:07:13,992 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-12-18 01:07:13,993 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 21 [2021-12-18 01:07:13,993 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1156375396] [2021-12-18 01:07:13,993 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-12-18 01:07:13,993 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2021-12-18 01:07:13,993 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-18 01:07:13,994 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2021-12-18 01:07:13,994 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=84, Invalid=336, Unknown=0, NotChecked=0, Total=420 [2021-12-18 01:07:13,994 INFO L87 Difference]: Start difference. First operand 217 states and 283 transitions. Second operand has 21 states, 19 states have (on average 5.473684210526316) internal successors, (104), 21 states have internal predecessors, (104), 6 states have call successors, (36), 2 states have call predecessors, (36), 5 states have return successors, (36), 6 states have call predecessors, (36), 6 states have call successors, (36) [2021-12-18 01:07:14,252 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-18 01:07:14,253 INFO L93 Difference]: Finished difference Result 422 states and 543 transitions. [2021-12-18 01:07:14,259 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2021-12-18 01:07:14,259 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 19 states have (on average 5.473684210526316) internal successors, (104), 21 states have internal predecessors, (104), 6 states have call successors, (36), 2 states have call predecessors, (36), 5 states have return successors, (36), 6 states have call predecessors, (36), 6 states have call successors, (36) Word has length 169 [2021-12-18 01:07:14,260 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-18 01:07:14,261 INFO L225 Difference]: With dead ends: 422 [2021-12-18 01:07:14,261 INFO L226 Difference]: Without dead ends: 220 [2021-12-18 01:07:14,262 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 339 GetRequests, 317 SyntacticMatches, 0 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 111 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=114, Invalid=438, Unknown=0, NotChecked=0, Total=552 [2021-12-18 01:07:14,263 INFO L933 BasicCegarLoop]: 255 mSDtfsCounter, 37 mSDsluCounter, 4028 mSDsCounter, 0 mSdLazyCounter, 272 mSolverCounterSat, 19 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 39 SdHoareTripleChecker+Valid, 4283 SdHoareTripleChecker+Invalid, 291 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 19 IncrementalHoareTripleChecker+Valid, 272 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2021-12-18 01:07:14,263 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [39 Valid, 4283 Invalid, 291 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [19 Valid, 272 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2021-12-18 01:07:14,264 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 220 states. [2021-12-18 01:07:14,272 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 220 to 219. [2021-12-18 01:07:14,273 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 219 states, 143 states have (on average 1.1888111888111887) internal successors, (170), 146 states have internal predecessors, (170), 57 states have call successors, (57), 17 states have call predecessors, (57), 18 states have return successors, (58), 55 states have call predecessors, (58), 55 states have call successors, (58) [2021-12-18 01:07:14,274 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 219 states to 219 states and 285 transitions. [2021-12-18 01:07:14,274 INFO L78 Accepts]: Start accepts. Automaton has 219 states and 285 transitions. Word has length 169 [2021-12-18 01:07:14,275 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-18 01:07:14,275 INFO L470 AbstractCegarLoop]: Abstraction has 219 states and 285 transitions. [2021-12-18 01:07:14,287 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 19 states have (on average 5.473684210526316) internal successors, (104), 21 states have internal predecessors, (104), 6 states have call successors, (36), 2 states have call predecessors, (36), 5 states have return successors, (36), 6 states have call predecessors, (36), 6 states have call successors, (36) [2021-12-18 01:07:14,288 INFO L276 IsEmpty]: Start isEmpty. Operand 219 states and 285 transitions. [2021-12-18 01:07:14,289 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 174 [2021-12-18 01:07:14,289 INFO L506 BasicCegarLoop]: Found error trace [2021-12-18 01:07:14,290 INFO L514 BasicCegarLoop]: trace histogram [12, 12, 12, 12, 12, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-18 01:07:14,303 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-18 01:07:14,498 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,SelfDestructingSolverStorable9 [2021-12-18 01:07:14,498 INFO L402 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-18 01:07:14,498 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-18 01:07:14,498 INFO L85 PathProgramCache]: Analyzing trace with hash -1933379022, now seen corresponding path program 6 times [2021-12-18 01:07:14,499 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-18 01:07:14,499 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2061495294] [2021-12-18 01:07:14,499 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-18 01:07:14,499 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-18 01:07:14,545 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-18 01:07:14,546 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [548113934] [2021-12-18 01:07:14,546 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2021-12-18 01:07:14,546 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-18 01:07:14,546 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-18 01:07:14,547 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-18 01:07:14,548 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process Killed by 15