./Ultimate.py --spec ../../sv-benchmarks/c/properties/unreach-call.prp --file ../../sv-benchmarks/c/nla-digbench-scaling/ps6-ll_valuebound50.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 839c364b Calling Ultimate with: /usr/bin/java -Dosgi.configuration.area=/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/config/TaipanReach.xml -i ../../sv-benchmarks/c/nla-digbench-scaling/ps6-ll_valuebound50.c -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/config/svcomp-Reach-32bit-Taipan_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7 --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 Taipan --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash aa3033c827040052fc2b3f2ac84da9b892249c5596676af10298d2e88bf55166 --- Real Ultimate output --- This is Ultimate 0.2.2-hotfix-svcomp22-839c364 [2021-11-25 18:51:09,528 INFO L177 SettingsManager]: Resetting all preferences to default values... [2021-11-25 18:51:09,531 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2021-11-25 18:51:09,577 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2021-11-25 18:51:09,578 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2021-11-25 18:51:09,579 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2021-11-25 18:51:09,581 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2021-11-25 18:51:09,583 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2021-11-25 18:51:09,585 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2021-11-25 18:51:09,586 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2021-11-25 18:51:09,588 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2021-11-25 18:51:09,589 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2021-11-25 18:51:09,590 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2021-11-25 18:51:09,591 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2021-11-25 18:51:09,592 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2021-11-25 18:51:09,594 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2021-11-25 18:51:09,595 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2021-11-25 18:51:09,596 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2021-11-25 18:51:09,598 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2021-11-25 18:51:09,601 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2021-11-25 18:51:09,603 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2021-11-25 18:51:09,607 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2021-11-25 18:51:09,609 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2021-11-25 18:51:09,610 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2021-11-25 18:51:09,614 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2021-11-25 18:51:09,619 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2021-11-25 18:51:09,620 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2021-11-25 18:51:09,621 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2021-11-25 18:51:09,622 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2021-11-25 18:51:09,623 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2021-11-25 18:51:09,623 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2021-11-25 18:51:09,624 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2021-11-25 18:51:09,625 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2021-11-25 18:51:09,626 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2021-11-25 18:51:09,627 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2021-11-25 18:51:09,628 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2021-11-25 18:51:09,628 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2021-11-25 18:51:09,629 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2021-11-25 18:51:09,629 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2021-11-25 18:51:09,630 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2021-11-25 18:51:09,631 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2021-11-25 18:51:09,633 INFO L101 SettingsManager]: Beginning loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/config/svcomp-Reach-32bit-Taipan_Default.epf [2021-11-25 18:51:09,676 INFO L113 SettingsManager]: Loading preferences was successful [2021-11-25 18:51:09,676 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2021-11-25 18:51:09,677 INFO L136 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2021-11-25 18:51:09,677 INFO L138 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2021-11-25 18:51:09,684 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2021-11-25 18:51:09,685 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2021-11-25 18:51:09,685 INFO L138 SettingsManager]: * User list type=DISABLED [2021-11-25 18:51:09,685 INFO L136 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2021-11-25 18:51:09,685 INFO L138 SettingsManager]: * Explicit value domain=true [2021-11-25 18:51:09,686 INFO L138 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2021-11-25 18:51:09,687 INFO L138 SettingsManager]: * Octagon Domain=false [2021-11-25 18:51:09,687 INFO L138 SettingsManager]: * Abstract domain=CompoundDomain [2021-11-25 18:51:09,687 INFO L138 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2021-11-25 18:51:09,688 INFO L138 SettingsManager]: * Use the RCFG-of-the-future interface=true [2021-11-25 18:51:09,688 INFO L138 SettingsManager]: * Interval Domain=false [2021-11-25 18:51:09,688 INFO L136 SettingsManager]: Preferences of Sifa differ from their defaults: [2021-11-25 18:51:09,688 INFO L138 SettingsManager]: * Call Summarizer=TopInputCallSummarizer [2021-11-25 18:51:09,689 INFO L138 SettingsManager]: * Simplification Technique=POLY_PAC [2021-11-25 18:51:09,689 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2021-11-25 18:51:09,690 INFO L138 SettingsManager]: * sizeof long=4 [2021-11-25 18:51:09,690 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2021-11-25 18:51:09,690 INFO L138 SettingsManager]: * sizeof POINTER=4 [2021-11-25 18:51:09,690 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2021-11-25 18:51:09,690 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2021-11-25 18:51:09,691 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2021-11-25 18:51:09,691 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2021-11-25 18:51:09,692 INFO L138 SettingsManager]: * sizeof long double=12 [2021-11-25 18:51:09,693 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2021-11-25 18:51:09,693 INFO L138 SettingsManager]: * Use constant arrays=true [2021-11-25 18:51:09,693 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2021-11-25 18:51:09,694 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2021-11-25 18:51:09,694 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2021-11-25 18:51:09,694 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2021-11-25 18:51:09,694 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2021-11-25 18:51:09,695 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2021-11-25 18:51:09,695 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2021-11-25 18:51:09,695 INFO L138 SettingsManager]: * Trace refinement strategy=SIFA_TAIPAN [2021-11-25 18:51:09,695 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2021-11-25 18:51:09,696 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2021-11-25 18:51:09,696 INFO L138 SettingsManager]: * Trace refinement exception blacklist=NONE [2021-11-25 18:51:09,696 INFO L138 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2021-11-25 18:51:09,696 INFO L138 SettingsManager]: * Abstract interpretation Mode=USE_PREDICATES WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Entry function -> main Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness directory -> /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7 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 -> Taipan Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data architecture -> 32bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> aa3033c827040052fc2b3f2ac84da9b892249c5596676af10298d2e88bf55166 [2021-11-25 18:51:09,979 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2021-11-25 18:51:10,001 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2021-11-25 18:51:10,004 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2021-11-25 18:51:10,005 INFO L271 PluginConnector]: Initializing CDTParser... [2021-11-25 18:51:10,006 INFO L275 PluginConnector]: CDTParser initialized [2021-11-25 18:51:10,007 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/../../sv-benchmarks/c/nla-digbench-scaling/ps6-ll_valuebound50.c [2021-11-25 18:51:10,084 INFO L220 CDTParser]: Created temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/data/cbb30bc0a/d4330877c73c44d39bc30be35ff53722/FLAG276f24422 [2021-11-25 18:51:10,567 INFO L306 CDTParser]: Found 1 translation units. [2021-11-25 18:51:10,567 INFO L160 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/sv-benchmarks/c/nla-digbench-scaling/ps6-ll_valuebound50.c [2021-11-25 18:51:10,582 INFO L349 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/data/cbb30bc0a/d4330877c73c44d39bc30be35ff53722/FLAG276f24422 [2021-11-25 18:51:10,932 INFO L357 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/data/cbb30bc0a/d4330877c73c44d39bc30be35ff53722 [2021-11-25 18:51:10,935 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2021-11-25 18:51:10,936 INFO L131 ToolchainWalker]: Walking toolchain with 6 elements. [2021-11-25 18:51:10,938 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2021-11-25 18:51:10,938 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2021-11-25 18:51:10,942 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2021-11-25 18:51:10,942 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 25.11 06:51:10" (1/1) ... [2021-11-25 18:51:10,944 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@388a9b16 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.11 06:51:10, skipping insertion in model container [2021-11-25 18:51:10,944 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 25.11 06:51:10" (1/1) ... [2021-11-25 18:51:10,955 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2021-11-25 18:51:10,969 INFO L178 MainTranslator]: Built tables and reachable declarations [2021-11-25 18:51:11,131 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/sv-benchmarks/c/nla-digbench-scaling/ps6-ll_valuebound50.c[458,471] [2021-11-25 18:51:11,173 INFO L209 PostProcessor]: Analyzing one entry point: main [2021-11-25 18:51:11,182 INFO L203 MainTranslator]: Completed pre-run [2021-11-25 18:51:11,205 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/sv-benchmarks/c/nla-digbench-scaling/ps6-ll_valuebound50.c[458,471] [2021-11-25 18:51:11,221 INFO L209 PostProcessor]: Analyzing one entry point: main [2021-11-25 18:51:11,239 INFO L208 MainTranslator]: Completed translation [2021-11-25 18:51:11,240 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.11 06:51:11 WrapperNode [2021-11-25 18:51:11,240 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2021-11-25 18:51:11,241 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2021-11-25 18:51:11,241 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2021-11-25 18:51:11,241 INFO L275 PluginConnector]: Boogie Procedure Inliner initialized [2021-11-25 18:51:11,249 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.11 06:51:11" (1/1) ... [2021-11-25 18:51:11,257 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.11 06:51:11" (1/1) ... [2021-11-25 18:51:11,281 INFO L137 Inliner]: procedures = 14, calls = 12, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 36 [2021-11-25 18:51:11,282 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2021-11-25 18:51:11,283 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2021-11-25 18:51:11,284 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2021-11-25 18:51:11,284 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2021-11-25 18:51:11,294 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.11 06:51:11" (1/1) ... [2021-11-25 18:51:11,294 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.11 06:51:11" (1/1) ... [2021-11-25 18:51:11,305 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.11 06:51:11" (1/1) ... [2021-11-25 18:51:11,307 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.11 06:51:11" (1/1) ... [2021-11-25 18:51:11,314 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.11 06:51:11" (1/1) ... [2021-11-25 18:51:11,324 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.11 06:51:11" (1/1) ... [2021-11-25 18:51:11,326 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.11 06:51:11" (1/1) ... [2021-11-25 18:51:11,329 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2021-11-25 18:51:11,334 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2021-11-25 18:51:11,335 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2021-11-25 18:51:11,335 INFO L275 PluginConnector]: RCFGBuilder initialized [2021-11-25 18:51:11,336 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.11 06:51:11" (1/1) ... [2021-11-25 18:51:11,345 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2021-11-25 18:51:11,358 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 [2021-11-25 18:51:11,371 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2021-11-25 18:51:11,402 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2021-11-25 18:51:11,442 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2021-11-25 18:51:11,442 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2021-11-25 18:51:11,443 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2021-11-25 18:51:11,443 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2021-11-25 18:51:11,443 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2021-11-25 18:51:11,443 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2021-11-25 18:51:11,444 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2021-11-25 18:51:11,444 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2021-11-25 18:51:11,512 INFO L236 CfgBuilder]: Building ICFG [2021-11-25 18:51:11,514 INFO L262 CfgBuilder]: Building CFG for each procedure with an implementation [2021-11-25 18:51:11,633 INFO L277 CfgBuilder]: Performing block encoding [2021-11-25 18:51:11,662 INFO L296 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2021-11-25 18:51:11,663 INFO L301 CfgBuilder]: Removed 1 assume(true) statements. [2021-11-25 18:51:11,665 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 25.11 06:51:11 BoogieIcfgContainer [2021-11-25 18:51:11,665 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2021-11-25 18:51:11,671 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2021-11-25 18:51:11,671 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2021-11-25 18:51:11,680 INFO L275 PluginConnector]: TraceAbstraction initialized [2021-11-25 18:51:11,680 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 25.11 06:51:10" (1/3) ... [2021-11-25 18:51:11,681 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@657ce061 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 25.11 06:51:11, skipping insertion in model container [2021-11-25 18:51:11,682 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.11 06:51:11" (2/3) ... [2021-11-25 18:51:11,682 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@657ce061 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 25.11 06:51:11, skipping insertion in model container [2021-11-25 18:51:11,682 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 25.11 06:51:11" (3/3) ... [2021-11-25 18:51:11,686 INFO L111 eAbstractionObserver]: Analyzing ICFG ps6-ll_valuebound50.c [2021-11-25 18:51:11,692 INFO L204 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2021-11-25 18:51:11,692 INFO L163 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2021-11-25 18:51:11,745 INFO L338 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2021-11-25 18:51:11,753 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=FINITE_AUTOMATA, 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-11-25 18:51:11,753 INFO L340 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2021-11-25 18:51:11,771 INFO L276 IsEmpty]: Start isEmpty. Operand has 19 states, 10 states have (on average 1.4) internal successors, (14), 11 states have internal predecessors, (14), 5 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2021-11-25 18:51:11,776 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 14 [2021-11-25 18:51:11,776 INFO L506 BasicCegarLoop]: Found error trace [2021-11-25 18:51:11,777 INFO L514 BasicCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-25 18:51:11,777 INFO L402 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-25 18:51:11,783 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-25 18:51:11,783 INFO L85 PathProgramCache]: Analyzing trace with hash 2113922188, now seen corresponding path program 1 times [2021-11-25 18:51:11,793 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-25 18:51:11,793 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [220034809] [2021-11-25 18:51:11,794 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 18:51:11,795 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-25 18:51:11,931 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-25 18:51:12,014 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2021-11-25 18:51:12,015 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-25 18:51:12,017 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [220034809] [2021-11-25 18:51:12,018 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [220034809] provided 1 perfect and 0 imperfect interpolant sequences [2021-11-25 18:51:12,018 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-11-25 18:51:12,019 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2021-11-25 18:51:12,021 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [27722137] [2021-11-25 18:51:12,022 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-11-25 18:51:12,028 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2021-11-25 18:51:12,029 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-25 18:51:12,065 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2021-11-25 18:51:12,069 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2021-11-25 18:51:12,072 INFO L87 Difference]: Start difference. First operand has 19 states, 10 states have (on average 1.4) internal successors, (14), 11 states have internal predecessors, (14), 5 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) Second operand has 2 states, 2 states have (on average 3.5) internal successors, (7), 2 states have internal predecessors, (7), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2021-11-25 18:51:12,116 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-25 18:51:12,116 INFO L93 Difference]: Finished difference Result 32 states and 44 transitions. [2021-11-25 18:51:12,118 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2021-11-25 18:51:12,120 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 3.5) internal successors, (7), 2 states have internal predecessors, (7), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 13 [2021-11-25 18:51:12,120 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-25 18:51:12,129 INFO L225 Difference]: With dead ends: 32 [2021-11-25 18:51:12,129 INFO L226 Difference]: Without dead ends: 17 [2021-11-25 18:51:12,134 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2021-11-25 18:51:12,142 INFO L933 BasicCegarLoop]: 19 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 3 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 19 SdHoareTripleChecker+Invalid, 3 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 3 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-11-25 18:51:12,143 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [0 Valid, 19 Invalid, 3 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 3 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-11-25 18:51:12,165 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 17 states. [2021-11-25 18:51:12,196 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 17 to 17. [2021-11-25 18:51:12,199 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 17 states, 9 states have (on average 1.2222222222222223) internal successors, (11), 10 states have internal predecessors, (11), 5 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2021-11-25 18:51:12,208 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 17 states to 17 states and 20 transitions. [2021-11-25 18:51:12,211 INFO L78 Accepts]: Start accepts. Automaton has 17 states and 20 transitions. Word has length 13 [2021-11-25 18:51:12,212 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-25 18:51:12,213 INFO L470 AbstractCegarLoop]: Abstraction has 17 states and 20 transitions. [2021-11-25 18:51:12,213 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 3.5) internal successors, (7), 2 states have internal predecessors, (7), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2021-11-25 18:51:12,213 INFO L276 IsEmpty]: Start isEmpty. Operand 17 states and 20 transitions. [2021-11-25 18:51:12,216 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 14 [2021-11-25 18:51:12,217 INFO L506 BasicCegarLoop]: Found error trace [2021-11-25 18:51:12,217 INFO L514 BasicCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-25 18:51:12,218 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2021-11-25 18:51:12,219 INFO L402 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-25 18:51:12,225 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-25 18:51:12,225 INFO L85 PathProgramCache]: Analyzing trace with hash 2066763035, now seen corresponding path program 1 times [2021-11-25 18:51:12,225 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-25 18:51:12,226 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1277938566] [2021-11-25 18:51:12,226 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 18:51:12,227 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-25 18:51:12,258 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-11-25 18:51:12,259 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [255240148] [2021-11-25 18:51:12,260 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 18:51:12,260 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 18:51:12,260 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 [2021-11-25 18:51:12,266 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-25 18:51:12,270 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2021-11-25 18:51:12,341 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-25 18:51:12,343 INFO L263 TraceCheckSpWp]: Trace formula consists of 59 conjuncts, 7 conjunts are in the unsatisfiable core [2021-11-25 18:51:12,348 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-25 18:51:12,490 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2021-11-25 18:51:12,490 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-11-25 18:51:12,491 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-25 18:51:12,491 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1277938566] [2021-11-25 18:51:12,491 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-11-25 18:51:12,492 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [255240148] [2021-11-25 18:51:12,498 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [255240148] provided 1 perfect and 0 imperfect interpolant sequences [2021-11-25 18:51:12,498 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-11-25 18:51:12,498 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2021-11-25 18:51:12,499 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [633712334] [2021-11-25 18:51:12,499 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-11-25 18:51:12,500 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2021-11-25 18:51:12,500 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-25 18:51:12,501 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2021-11-25 18:51:12,501 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2021-11-25 18:51:12,502 INFO L87 Difference]: Start difference. First operand 17 states and 20 transitions. Second operand has 5 states, 5 states have (on average 1.4) internal successors, (7), 4 states have internal predecessors, (7), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2021-11-25 18:51:12,673 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-25 18:51:12,673 INFO L93 Difference]: Finished difference Result 28 states and 33 transitions. [2021-11-25 18:51:12,674 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2021-11-25 18:51:12,674 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.4) internal successors, (7), 4 states have internal predecessors, (7), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 13 [2021-11-25 18:51:12,674 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-25 18:51:12,675 INFO L225 Difference]: With dead ends: 28 [2021-11-25 18:51:12,675 INFO L226 Difference]: Without dead ends: 24 [2021-11-25 18:51:12,676 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 13 GetRequests, 9 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-11-25 18:51:12,678 INFO L933 BasicCegarLoop]: 15 mSDtfsCounter, 6 mSDsluCounter, 46 mSDsCounter, 0 mSdLazyCounter, 29 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 56 SdHoareTripleChecker+Invalid, 31 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 29 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2021-11-25 18:51:12,679 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [8 Valid, 56 Invalid, 31 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 29 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2021-11-25 18:51:12,680 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 24 states. [2021-11-25 18:51:12,685 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 24 to 24. [2021-11-25 18:51:12,686 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 24 states, 14 states have (on average 1.1428571428571428) internal successors, (16), 15 states have internal predecessors, (16), 6 states have call successors, (6), 3 states have call predecessors, (6), 3 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2021-11-25 18:51:12,687 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 27 transitions. [2021-11-25 18:51:12,687 INFO L78 Accepts]: Start accepts. Automaton has 24 states and 27 transitions. Word has length 13 [2021-11-25 18:51:12,688 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-25 18:51:12,688 INFO L470 AbstractCegarLoop]: Abstraction has 24 states and 27 transitions. [2021-11-25 18:51:12,688 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.4) internal successors, (7), 4 states have internal predecessors, (7), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2021-11-25 18:51:12,689 INFO L276 IsEmpty]: Start isEmpty. Operand 24 states and 27 transitions. [2021-11-25 18:51:12,689 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2021-11-25 18:51:12,690 INFO L506 BasicCegarLoop]: Found error trace [2021-11-25 18:51:12,690 INFO L514 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-25 18:51:12,717 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2021-11-25 18:51:12,894 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable1 [2021-11-25 18:51:12,894 INFO L402 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-25 18:51:12,895 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-25 18:51:12,895 INFO L85 PathProgramCache]: Analyzing trace with hash 1985624712, now seen corresponding path program 1 times [2021-11-25 18:51:12,897 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-25 18:51:12,897 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [863848268] [2021-11-25 18:51:12,897 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 18:51:12,898 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-25 18:51:12,924 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-11-25 18:51:12,925 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1121824264] [2021-11-25 18:51:12,925 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 18:51:12,927 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 18:51:12,927 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 [2021-11-25 18:51:12,928 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-25 18:51:12,953 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2021-11-25 18:51:13,010 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-25 18:51:13,014 INFO L263 TraceCheckSpWp]: Trace formula consists of 76 conjuncts, 11 conjunts are in the unsatisfiable core [2021-11-25 18:51:13,016 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-25 18:51:13,204 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2021-11-25 18:51:13,204 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-11-25 18:51:13,911 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2021-11-25 18:51:13,911 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-25 18:51:13,911 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [863848268] [2021-11-25 18:51:13,911 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-11-25 18:51:13,912 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1121824264] [2021-11-25 18:51:13,912 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1121824264] provided 1 perfect and 1 imperfect interpolant sequences [2021-11-25 18:51:13,912 INFO L186 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2021-11-25 18:51:13,912 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 7 [2021-11-25 18:51:13,913 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2018004742] [2021-11-25 18:51:13,913 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-11-25 18:51:13,913 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2021-11-25 18:51:13,913 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-25 18:51:13,914 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2021-11-25 18:51:13,914 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2021-11-25 18:51:13,915 INFO L87 Difference]: Start difference. First operand 24 states and 27 transitions. Second operand has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2021-11-25 18:51:13,969 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-25 18:51:13,969 INFO L93 Difference]: Finished difference Result 30 states and 32 transitions. [2021-11-25 18:51:13,970 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2021-11-25 18:51:13,970 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 20 [2021-11-25 18:51:13,970 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-25 18:51:13,971 INFO L225 Difference]: With dead ends: 30 [2021-11-25 18:51:13,971 INFO L226 Difference]: Without dead ends: 26 [2021-11-25 18:51:13,972 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 39 GetRequests, 32 SyntacticMatches, 1 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2021-11-25 18:51:13,973 INFO L933 BasicCegarLoop]: 13 mSDtfsCounter, 6 mSDsluCounter, 38 mSDsCounter, 0 mSdLazyCounter, 26 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 46 SdHoareTripleChecker+Invalid, 27 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 26 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-11-25 18:51:13,974 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [7 Valid, 46 Invalid, 27 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 26 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-11-25 18:51:13,975 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 26 states. [2021-11-25 18:51:13,981 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 26 to 26. [2021-11-25 18:51:13,981 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 26 states, 16 states have (on average 1.0625) internal successors, (17), 16 states have internal predecessors, (17), 6 states have call successors, (6), 4 states have call predecessors, (6), 3 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2021-11-25 18:51:13,983 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 28 transitions. [2021-11-25 18:51:13,983 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 28 transitions. Word has length 20 [2021-11-25 18:51:13,983 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-25 18:51:13,983 INFO L470 AbstractCegarLoop]: Abstraction has 26 states and 28 transitions. [2021-11-25 18:51:13,984 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2021-11-25 18:51:13,984 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 28 transitions. [2021-11-25 18:51:13,985 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2021-11-25 18:51:13,985 INFO L506 BasicCegarLoop]: Found error trace [2021-11-25 18:51:13,985 INFO L514 BasicCegarLoop]: trace histogram [4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-25 18:51:14,023 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2021-11-25 18:51:14,206 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 18:51:14,207 INFO L402 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-25 18:51:14,208 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-25 18:51:14,208 INFO L85 PathProgramCache]: Analyzing trace with hash -1002189902, now seen corresponding path program 1 times [2021-11-25 18:51:14,208 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-25 18:51:14,209 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [673856400] [2021-11-25 18:51:14,209 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 18:51:14,209 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-25 18:51:14,224 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-11-25 18:51:14,229 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2121059174] [2021-11-25 18:51:14,230 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 18:51:14,237 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 18:51:14,238 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 [2021-11-25 18:51:14,239 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-25 18:51:14,242 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2021-11-25 18:51:14,289 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-25 18:51:14,290 INFO L263 TraceCheckSpWp]: Trace formula consists of 95 conjuncts, 12 conjunts are in the unsatisfiable core [2021-11-25 18:51:14,292 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-25 18:51:14,510 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 6 proven. 3 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2021-11-25 18:51:14,510 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-11-25 18:51:14,715 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-25 18:51:14,715 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [673856400] [2021-11-25 18:51:14,716 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-11-25 18:51:14,716 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2121059174] [2021-11-25 18:51:14,717 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2121059174] provided 0 perfect and 1 imperfect interpolant sequences [2021-11-25 18:51:14,717 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1904346480] [2021-11-25 18:51:14,744 INFO L159 IcfgInterpreter]: Started Sifa with 17 locations of interest [2021-11-25 18:51:14,745 INFO L166 IcfgInterpreter]: Building call graph [2021-11-25 18:51:14,749 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2021-11-25 18:51:14,755 INFO L176 IcfgInterpreter]: Starting interpretation [2021-11-25 18:51:14,756 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2021-11-25 18:51:16,368 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 10 for LOIs [2021-11-25 18:51:16,382 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 75 for LOIs [2021-11-25 18:51:16,424 INFO L180 IcfgInterpreter]: Interpretation finished [2021-11-25 18:51:17,388 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '572#(and (<= 0 |#NULL.base|) (<= |#NULL.offset| 0) (= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond) (= __VERIFIER_assert_~cond 0) (<= |#NULL.base| 0) (<= 0 |#NULL.offset|) (<= 0 |#StackHeapBarrier|))' at error location [2021-11-25 18:51:17,388 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2021-11-25 18:51:17,388 INFO L186 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2021-11-25 18:51:17,389 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7] total 7 [2021-11-25 18:51:17,389 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [786131851] [2021-11-25 18:51:17,389 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2021-11-25 18:51:17,390 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2021-11-25 18:51:17,390 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-25 18:51:17,390 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2021-11-25 18:51:17,391 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=63, Invalid=357, Unknown=0, NotChecked=0, Total=420 [2021-11-25 18:51:17,392 INFO L87 Difference]: Start difference. First operand 26 states and 28 transitions. Second operand has 7 states, 6 states have (on average 2.1666666666666665) internal successors, (13), 6 states have internal predecessors, (13), 4 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 4 states have call predecessors, (5), 4 states have call successors, (5) [2021-11-25 18:51:17,491 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-25 18:51:17,491 INFO L93 Difference]: Finished difference Result 35 states and 39 transitions. [2021-11-25 18:51:17,491 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2021-11-25 18:51:17,492 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 6 states have (on average 2.1666666666666665) internal successors, (13), 6 states have internal predecessors, (13), 4 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 4 states have call predecessors, (5), 4 states have call successors, (5) Word has length 31 [2021-11-25 18:51:17,492 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-25 18:51:17,493 INFO L225 Difference]: With dead ends: 35 [2021-11-25 18:51:17,493 INFO L226 Difference]: Without dead ends: 29 [2021-11-25 18:51:17,494 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 81 GetRequests, 57 SyntacticMatches, 3 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 87 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=73, Invalid=433, Unknown=0, NotChecked=0, Total=506 [2021-11-25 18:51:17,495 INFO L933 BasicCegarLoop]: 21 mSDtfsCounter, 2 mSDsluCounter, 90 mSDsCounter, 0 mSdLazyCounter, 48 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 104 SdHoareTripleChecker+Invalid, 49 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 48 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2021-11-25 18:51:17,495 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 104 Invalid, 49 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 48 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2021-11-25 18:51:17,496 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 29 states. [2021-11-25 18:51:17,502 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 29 to 29. [2021-11-25 18:51:17,503 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 29 states, 18 states have (on average 1.0555555555555556) internal successors, (19), 18 states have internal predecessors, (19), 7 states have call successors, (7), 4 states have call predecessors, (7), 3 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2021-11-25 18:51:17,504 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 29 states to 29 states and 32 transitions. [2021-11-25 18:51:17,504 INFO L78 Accepts]: Start accepts. Automaton has 29 states and 32 transitions. Word has length 31 [2021-11-25 18:51:17,504 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-25 18:51:17,505 INFO L470 AbstractCegarLoop]: Abstraction has 29 states and 32 transitions. [2021-11-25 18:51:17,505 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 6 states have (on average 2.1666666666666665) internal successors, (13), 6 states have internal predecessors, (13), 4 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 4 states have call predecessors, (5), 4 states have call successors, (5) [2021-11-25 18:51:17,505 INFO L276 IsEmpty]: Start isEmpty. Operand 29 states and 32 transitions. [2021-11-25 18:51:17,506 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2021-11-25 18:51:17,506 INFO L506 BasicCegarLoop]: Found error trace [2021-11-25 18:51:17,507 INFO L514 BasicCegarLoop]: trace histogram [5, 4, 4, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-25 18:51:17,551 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2021-11-25 18:51:17,720 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 18:51:17,720 INFO L402 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-25 18:51:17,721 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-25 18:51:17,721 INFO L85 PathProgramCache]: Analyzing trace with hash -180873249, now seen corresponding path program 2 times [2021-11-25 18:51:17,721 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-25 18:51:17,721 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [958575619] [2021-11-25 18:51:17,722 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 18:51:17,722 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-25 18:51:17,734 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-11-25 18:51:17,734 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1088873588] [2021-11-25 18:51:17,734 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2021-11-25 18:51:17,734 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 18:51:17,735 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 [2021-11-25 18:51:17,735 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-25 18:51:17,742 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2021-11-25 18:51:17,853 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2021-11-25 18:51:17,854 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-11-25 18:51:17,855 INFO L263 TraceCheckSpWp]: Trace formula consists of 112 conjuncts, 16 conjunts are in the unsatisfiable core [2021-11-25 18:51:17,858 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-25 18:51:18,080 INFO L134 CoverageAnalysis]: Checked inductivity of 43 backedges. 8 proven. 9 refuted. 0 times theorem prover too weak. 26 trivial. 0 not checked. [2021-11-25 18:51:18,080 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-11-25 18:51:18,344 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-25 18:51:18,344 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [958575619] [2021-11-25 18:51:18,344 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-11-25 18:51:18,344 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1088873588] [2021-11-25 18:51:18,345 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1088873588] provided 0 perfect and 1 imperfect interpolant sequences [2021-11-25 18:51:18,345 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1884631493] [2021-11-25 18:51:18,348 INFO L159 IcfgInterpreter]: Started Sifa with 17 locations of interest [2021-11-25 18:51:18,348 INFO L166 IcfgInterpreter]: Building call graph [2021-11-25 18:51:18,349 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2021-11-25 18:51:18,349 INFO L176 IcfgInterpreter]: Starting interpretation [2021-11-25 18:51:18,349 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2021-11-25 18:51:19,779 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 10 for LOIs [2021-11-25 18:51:19,791 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 75 for LOIs [2021-11-25 18:51:19,827 INFO L180 IcfgInterpreter]: Interpretation finished [2021-11-25 18:51:20,798 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '858#(and (<= 0 |#NULL.base|) (<= |#NULL.offset| 0) (= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond) (= __VERIFIER_assert_~cond 0) (<= |#NULL.base| 0) (<= 0 |#NULL.offset|) (<= 0 |#StackHeapBarrier|))' at error location [2021-11-25 18:51:20,798 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2021-11-25 18:51:20,799 INFO L186 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2021-11-25 18:51:20,799 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8] total 8 [2021-11-25 18:51:20,799 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2063113252] [2021-11-25 18:51:20,799 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2021-11-25 18:51:20,800 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2021-11-25 18:51:20,800 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-25 18:51:20,801 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2021-11-25 18:51:20,801 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=66, Invalid=396, Unknown=0, NotChecked=0, Total=462 [2021-11-25 18:51:20,802 INFO L87 Difference]: Start difference. First operand 29 states and 32 transitions. Second operand has 8 states, 7 states have (on average 2.142857142857143) internal successors, (15), 7 states have internal predecessors, (15), 5 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 5 states have call predecessors, (6), 5 states have call successors, (6) [2021-11-25 18:51:20,928 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-25 18:51:20,928 INFO L93 Difference]: Finished difference Result 38 states and 43 transitions. [2021-11-25 18:51:20,930 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2021-11-25 18:51:20,930 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 7 states have (on average 2.142857142857143) internal successors, (15), 7 states have internal predecessors, (15), 5 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 5 states have call predecessors, (6), 5 states have call successors, (6) Word has length 38 [2021-11-25 18:51:20,931 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-25 18:51:20,932 INFO L225 Difference]: With dead ends: 38 [2021-11-25 18:51:20,932 INFO L226 Difference]: Without dead ends: 32 [2021-11-25 18:51:20,933 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 95 GetRequests, 70 SyntacticMatches, 3 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 87 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=76, Invalid=476, Unknown=0, NotChecked=0, Total=552 [2021-11-25 18:51:20,934 INFO L933 BasicCegarLoop]: 24 mSDtfsCounter, 2 mSDsluCounter, 120 mSDsCounter, 0 mSdLazyCounter, 68 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 136 SdHoareTripleChecker+Invalid, 69 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 68 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2021-11-25 18:51:20,934 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 136 Invalid, 69 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 68 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2021-11-25 18:51:20,935 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 32 states. [2021-11-25 18:51:20,947 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 32 to 32. [2021-11-25 18:51:20,947 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 32 states, 20 states have (on average 1.05) internal successors, (21), 20 states have internal predecessors, (21), 8 states have call successors, (8), 4 states have call predecessors, (8), 3 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2021-11-25 18:51:20,951 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 36 transitions. [2021-11-25 18:51:20,951 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 36 transitions. Word has length 38 [2021-11-25 18:51:20,952 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-25 18:51:20,953 INFO L470 AbstractCegarLoop]: Abstraction has 32 states and 36 transitions. [2021-11-25 18:51:20,953 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 7 states have (on average 2.142857142857143) internal successors, (15), 7 states have internal predecessors, (15), 5 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 5 states have call predecessors, (6), 5 states have call successors, (6) [2021-11-25 18:51:20,953 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 36 transitions. [2021-11-25 18:51:20,959 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 46 [2021-11-25 18:51:20,959 INFO L506 BasicCegarLoop]: Found error trace [2021-11-25 18:51:20,959 INFO L514 BasicCegarLoop]: trace histogram [6, 5, 5, 4, 4, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-25 18:51:21,006 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2021-11-25 18:51:21,185 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 18:51:21,186 INFO L402 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-25 18:51:21,186 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-25 18:51:21,187 INFO L85 PathProgramCache]: Analyzing trace with hash -1515507950, now seen corresponding path program 3 times [2021-11-25 18:51:21,187 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-25 18:51:21,187 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1622624045] [2021-11-25 18:51:21,187 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 18:51:21,187 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-25 18:51:21,201 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-11-25 18:51:21,201 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [398539174] [2021-11-25 18:51:21,201 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2021-11-25 18:51:21,202 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 18:51:21,202 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 [2021-11-25 18:51:21,203 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-25 18:51:21,231 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2021-11-25 18:51:21,271 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2021-11-25 18:51:21,271 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-11-25 18:51:21,273 INFO L263 TraceCheckSpWp]: Trace formula consists of 76 conjuncts, 20 conjunts are in the unsatisfiable core [2021-11-25 18:51:21,275 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-25 18:51:21,483 INFO L134 CoverageAnalysis]: Checked inductivity of 70 backedges. 10 proven. 18 refuted. 0 times theorem prover too weak. 42 trivial. 0 not checked. [2021-11-25 18:51:21,483 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-11-25 18:51:21,672 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-25 18:51:21,672 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1622624045] [2021-11-25 18:51:21,672 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-11-25 18:51:21,673 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [398539174] [2021-11-25 18:51:21,673 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [398539174] provided 0 perfect and 1 imperfect interpolant sequences [2021-11-25 18:51:21,673 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [892599189] [2021-11-25 18:51:21,675 INFO L159 IcfgInterpreter]: Started Sifa with 17 locations of interest [2021-11-25 18:51:21,676 INFO L166 IcfgInterpreter]: Building call graph [2021-11-25 18:51:21,676 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2021-11-25 18:51:21,676 INFO L176 IcfgInterpreter]: Starting interpretation [2021-11-25 18:51:21,676 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2021-11-25 18:51:22,759 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 10 for LOIs [2021-11-25 18:51:22,768 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 75 for LOIs [2021-11-25 18:51:22,803 INFO L180 IcfgInterpreter]: Interpretation finished [2021-11-25 18:51:23,747 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1176#(and (<= 0 |#NULL.base|) (<= |#NULL.offset| 0) (= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond) (= __VERIFIER_assert_~cond 0) (<= |#NULL.base| 0) (<= 0 |#NULL.offset|) (<= 0 |#StackHeapBarrier|))' at error location [2021-11-25 18:51:23,748 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2021-11-25 18:51:23,748 INFO L186 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2021-11-25 18:51:23,748 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2021-11-25 18:51:23,748 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [869291215] [2021-11-25 18:51:23,748 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2021-11-25 18:51:23,749 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2021-11-25 18:51:23,749 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-25 18:51:23,749 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2021-11-25 18:51:23,749 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=69, Invalid=437, Unknown=0, NotChecked=0, Total=506 [2021-11-25 18:51:23,750 INFO L87 Difference]: Start difference. First operand 32 states and 36 transitions. Second operand has 9 states, 8 states have (on average 2.125) internal successors, (17), 8 states have internal predecessors, (17), 6 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 6 states have call predecessors, (7), 6 states have call successors, (7) [2021-11-25 18:51:23,898 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-25 18:51:23,899 INFO L93 Difference]: Finished difference Result 41 states and 47 transitions. [2021-11-25 18:51:23,899 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2021-11-25 18:51:23,900 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 8 states have (on average 2.125) internal successors, (17), 8 states have internal predecessors, (17), 6 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 6 states have call predecessors, (7), 6 states have call successors, (7) Word has length 45 [2021-11-25 18:51:23,900 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-25 18:51:23,901 INFO L225 Difference]: With dead ends: 41 [2021-11-25 18:51:23,901 INFO L226 Difference]: Without dead ends: 35 [2021-11-25 18:51:23,902 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 109 GetRequests, 83 SyntacticMatches, 3 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 87 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=79, Invalid=521, Unknown=0, NotChecked=0, Total=600 [2021-11-25 18:51:23,903 INFO L933 BasicCegarLoop]: 27 mSDtfsCounter, 2 mSDsluCounter, 154 mSDsCounter, 0 mSdLazyCounter, 92 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 172 SdHoareTripleChecker+Invalid, 93 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 92 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2021-11-25 18:51:23,903 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 172 Invalid, 93 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 92 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2021-11-25 18:51:23,904 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 35 states. [2021-11-25 18:51:23,916 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 35 to 35. [2021-11-25 18:51:23,921 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 35 states, 22 states have (on average 1.0454545454545454) internal successors, (23), 22 states have internal predecessors, (23), 9 states have call successors, (9), 4 states have call predecessors, (9), 3 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2021-11-25 18:51:23,924 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 35 states to 35 states and 40 transitions. [2021-11-25 18:51:23,924 INFO L78 Accepts]: Start accepts. Automaton has 35 states and 40 transitions. Word has length 45 [2021-11-25 18:51:23,925 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-25 18:51:23,925 INFO L470 AbstractCegarLoop]: Abstraction has 35 states and 40 transitions. [2021-11-25 18:51:23,926 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 8 states have (on average 2.125) internal successors, (17), 8 states have internal predecessors, (17), 6 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 6 states have call predecessors, (7), 6 states have call successors, (7) [2021-11-25 18:51:23,926 INFO L276 IsEmpty]: Start isEmpty. Operand 35 states and 40 transitions. [2021-11-25 18:51:23,927 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 53 [2021-11-25 18:51:23,927 INFO L506 BasicCegarLoop]: Found error trace [2021-11-25 18:51:23,928 INFO L514 BasicCegarLoop]: trace histogram [7, 6, 6, 5, 5, 5, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-25 18:51:23,978 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2021-11-25 18:51:24,147 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 18:51:24,148 INFO L402 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-25 18:51:24,148 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-25 18:51:24,148 INFO L85 PathProgramCache]: Analyzing trace with hash 180103295, now seen corresponding path program 4 times [2021-11-25 18:51:24,148 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-25 18:51:24,148 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1471528283] [2021-11-25 18:51:24,148 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 18:51:24,149 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-25 18:51:24,160 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-11-25 18:51:24,161 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2000314865] [2021-11-25 18:51:24,161 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2021-11-25 18:51:24,161 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 18:51:24,162 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 [2021-11-25 18:51:24,162 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-25 18:51:24,181 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2021-11-25 18:51:24,551 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-25 18:51:24,552 INFO L263 TraceCheckSpWp]: Trace formula consists of 146 conjuncts, 24 conjunts are in the unsatisfiable core [2021-11-25 18:51:24,554 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-25 18:51:24,778 INFO L134 CoverageAnalysis]: Checked inductivity of 104 backedges. 12 proven. 30 refuted. 0 times theorem prover too weak. 62 trivial. 0 not checked. [2021-11-25 18:51:24,778 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-11-25 18:51:25,022 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-25 18:51:25,022 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1471528283] [2021-11-25 18:51:25,022 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-11-25 18:51:25,022 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2000314865] [2021-11-25 18:51:25,023 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2000314865] provided 0 perfect and 1 imperfect interpolant sequences [2021-11-25 18:51:25,023 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [279760943] [2021-11-25 18:51:25,026 INFO L159 IcfgInterpreter]: Started Sifa with 17 locations of interest [2021-11-25 18:51:25,026 INFO L166 IcfgInterpreter]: Building call graph [2021-11-25 18:51:25,027 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2021-11-25 18:51:25,027 INFO L176 IcfgInterpreter]: Starting interpretation [2021-11-25 18:51:25,027 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2021-11-25 18:51:26,033 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 10 for LOIs [2021-11-25 18:51:26,042 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 75 for LOIs [2021-11-25 18:51:26,071 INFO L180 IcfgInterpreter]: Interpretation finished [2021-11-25 18:51:26,863 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1526#(and (<= 0 |#NULL.base|) (<= |#NULL.offset| 0) (= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond) (= __VERIFIER_assert_~cond 0) (<= |#NULL.base| 0) (<= 0 |#NULL.offset|) (<= 0 |#StackHeapBarrier|))' at error location [2021-11-25 18:51:26,863 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2021-11-25 18:51:26,863 INFO L186 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2021-11-25 18:51:26,863 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10] total 10 [2021-11-25 18:51:26,864 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1489691470] [2021-11-25 18:51:26,864 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2021-11-25 18:51:26,864 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2021-11-25 18:51:26,865 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-25 18:51:26,865 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2021-11-25 18:51:26,865 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=72, Invalid=480, Unknown=0, NotChecked=0, Total=552 [2021-11-25 18:51:26,866 INFO L87 Difference]: Start difference. First operand 35 states and 40 transitions. Second operand has 10 states, 9 states have (on average 2.111111111111111) internal successors, (19), 9 states have internal predecessors, (19), 7 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 7 states have call predecessors, (8), 7 states have call successors, (8) [2021-11-25 18:51:27,022 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-25 18:51:27,023 INFO L93 Difference]: Finished difference Result 44 states and 51 transitions. [2021-11-25 18:51:27,023 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2021-11-25 18:51:27,023 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 9 states have (on average 2.111111111111111) internal successors, (19), 9 states have internal predecessors, (19), 7 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 7 states have call predecessors, (8), 7 states have call successors, (8) Word has length 52 [2021-11-25 18:51:27,024 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-25 18:51:27,025 INFO L225 Difference]: With dead ends: 44 [2021-11-25 18:51:27,025 INFO L226 Difference]: Without dead ends: 38 [2021-11-25 18:51:27,026 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 123 GetRequests, 96 SyntacticMatches, 3 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 87 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=82, Invalid=568, Unknown=0, NotChecked=0, Total=650 [2021-11-25 18:51:27,027 INFO L933 BasicCegarLoop]: 30 mSDtfsCounter, 2 mSDsluCounter, 192 mSDsCounter, 0 mSdLazyCounter, 120 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 212 SdHoareTripleChecker+Invalid, 121 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 120 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2021-11-25 18:51:27,027 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 212 Invalid, 121 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 120 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2021-11-25 18:51:27,028 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 38 states. [2021-11-25 18:51:27,034 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 38 to 38. [2021-11-25 18:51:27,035 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 38 states, 24 states have (on average 1.0416666666666667) internal successors, (25), 24 states have internal predecessors, (25), 10 states have call successors, (10), 4 states have call predecessors, (10), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2021-11-25 18:51:27,036 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 38 states to 38 states and 44 transitions. [2021-11-25 18:51:27,036 INFO L78 Accepts]: Start accepts. Automaton has 38 states and 44 transitions. Word has length 52 [2021-11-25 18:51:27,036 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-25 18:51:27,037 INFO L470 AbstractCegarLoop]: Abstraction has 38 states and 44 transitions. [2021-11-25 18:51:27,037 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 9 states have (on average 2.111111111111111) internal successors, (19), 9 states have internal predecessors, (19), 7 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 7 states have call predecessors, (8), 7 states have call successors, (8) [2021-11-25 18:51:27,037 INFO L276 IsEmpty]: Start isEmpty. Operand 38 states and 44 transitions. [2021-11-25 18:51:27,038 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 60 [2021-11-25 18:51:27,038 INFO L506 BasicCegarLoop]: Found error trace [2021-11-25 18:51:27,038 INFO L514 BasicCegarLoop]: trace histogram [8, 7, 7, 6, 6, 6, 5, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-25 18:51:27,043 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2021-11-25 18:51:27,243 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 7 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable6 [2021-11-25 18:51:27,243 INFO L402 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-25 18:51:27,244 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-25 18:51:27,244 INFO L85 PathProgramCache]: Analyzing trace with hash 321989234, now seen corresponding path program 5 times [2021-11-25 18:51:27,244 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-25 18:51:27,244 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1881977506] [2021-11-25 18:51:27,245 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 18:51:27,245 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-25 18:51:27,256 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-11-25 18:51:27,257 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [526054880] [2021-11-25 18:51:27,257 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2021-11-25 18:51:27,257 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 18:51:27,258 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 [2021-11-25 18:51:27,258 INFO L229 MonitoredProcess]: Starting monitored process 8 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-25 18:51:27,264 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2021-11-25 18:51:28,487 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2021-11-25 18:51:28,487 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-11-25 18:51:28,491 INFO L263 TraceCheckSpWp]: Trace formula consists of 163 conjuncts, 28 conjunts are in the unsatisfiable core [2021-11-25 18:51:28,494 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-25 18:51:28,727 INFO L134 CoverageAnalysis]: Checked inductivity of 145 backedges. 14 proven. 45 refuted. 0 times theorem prover too weak. 86 trivial. 0 not checked. [2021-11-25 18:51:28,727 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-11-25 18:51:28,887 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-25 18:51:28,887 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1881977506] [2021-11-25 18:51:28,888 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-11-25 18:51:28,888 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [526054880] [2021-11-25 18:51:28,888 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [526054880] provided 0 perfect and 1 imperfect interpolant sequences [2021-11-25 18:51:28,888 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1124545385] [2021-11-25 18:51:28,890 INFO L159 IcfgInterpreter]: Started Sifa with 17 locations of interest [2021-11-25 18:51:28,890 INFO L166 IcfgInterpreter]: Building call graph [2021-11-25 18:51:28,891 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2021-11-25 18:51:28,891 INFO L176 IcfgInterpreter]: Starting interpretation [2021-11-25 18:51:28,891 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2021-11-25 18:51:29,827 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 10 for LOIs [2021-11-25 18:51:29,837 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 75 for LOIs [2021-11-25 18:51:29,866 INFO L180 IcfgInterpreter]: Interpretation finished [2021-11-25 18:51:30,655 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1908#(and (<= 0 |#NULL.base|) (<= |#NULL.offset| 0) (= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond) (= __VERIFIER_assert_~cond 0) (<= |#NULL.base| 0) (<= 0 |#NULL.offset|) (<= 0 |#StackHeapBarrier|))' at error location [2021-11-25 18:51:30,655 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2021-11-25 18:51:30,655 INFO L186 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2021-11-25 18:51:30,655 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11] total 11 [2021-11-25 18:51:30,655 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1163519759] [2021-11-25 18:51:30,655 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2021-11-25 18:51:30,656 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2021-11-25 18:51:30,656 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-25 18:51:30,657 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2021-11-25 18:51:30,657 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=75, Invalid=525, Unknown=0, NotChecked=0, Total=600 [2021-11-25 18:51:30,657 INFO L87 Difference]: Start difference. First operand 38 states and 44 transitions. Second operand has 11 states, 10 states have (on average 2.1) internal successors, (21), 10 states have internal predecessors, (21), 8 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (9), 8 states have call predecessors, (9), 8 states have call successors, (9) [2021-11-25 18:51:30,826 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-25 18:51:30,826 INFO L93 Difference]: Finished difference Result 47 states and 55 transitions. [2021-11-25 18:51:30,827 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2021-11-25 18:51:30,827 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 10 states have (on average 2.1) internal successors, (21), 10 states have internal predecessors, (21), 8 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (9), 8 states have call predecessors, (9), 8 states have call successors, (9) Word has length 59 [2021-11-25 18:51:30,827 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-25 18:51:30,828 INFO L225 Difference]: With dead ends: 47 [2021-11-25 18:51:30,828 INFO L226 Difference]: Without dead ends: 41 [2021-11-25 18:51:30,829 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 137 GetRequests, 109 SyntacticMatches, 3 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 87 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=85, Invalid=617, Unknown=0, NotChecked=0, Total=702 [2021-11-25 18:51:30,830 INFO L933 BasicCegarLoop]: 33 mSDtfsCounter, 2 mSDsluCounter, 234 mSDsCounter, 0 mSdLazyCounter, 152 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 256 SdHoareTripleChecker+Invalid, 153 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 152 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2021-11-25 18:51:30,830 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 256 Invalid, 153 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 152 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2021-11-25 18:51:30,831 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 41 states. [2021-11-25 18:51:30,838 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 41 to 41. [2021-11-25 18:51:30,839 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 41 states, 26 states have (on average 1.0384615384615385) internal successors, (27), 26 states have internal predecessors, (27), 11 states have call successors, (11), 4 states have call predecessors, (11), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2021-11-25 18:51:30,840 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 41 states to 41 states and 48 transitions. [2021-11-25 18:51:30,840 INFO L78 Accepts]: Start accepts. Automaton has 41 states and 48 transitions. Word has length 59 [2021-11-25 18:51:30,840 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-25 18:51:30,841 INFO L470 AbstractCegarLoop]: Abstraction has 41 states and 48 transitions. [2021-11-25 18:51:30,841 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 10 states have (on average 2.1) internal successors, (21), 10 states have internal predecessors, (21), 8 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (9), 8 states have call predecessors, (9), 8 states have call successors, (9) [2021-11-25 18:51:30,841 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 48 transitions. [2021-11-25 18:51:30,842 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 67 [2021-11-25 18:51:30,842 INFO L506 BasicCegarLoop]: Found error trace [2021-11-25 18:51:30,843 INFO L514 BasicCegarLoop]: trace histogram [9, 8, 8, 7, 7, 7, 6, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-25 18:51:30,862 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2021-11-25 18:51:31,051 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 8 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable7 [2021-11-25 18:51:31,052 INFO L402 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-25 18:51:31,052 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-25 18:51:31,052 INFO L85 PathProgramCache]: Analyzing trace with hash 151429407, now seen corresponding path program 6 times [2021-11-25 18:51:31,052 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-25 18:51:31,052 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [744950229] [2021-11-25 18:51:31,052 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 18:51:31,053 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-25 18:51:31,081 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-11-25 18:51:31,081 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1363489907] [2021-11-25 18:51:31,082 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2021-11-25 18:51:31,083 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 18:51:31,083 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 [2021-11-25 18:51:31,084 INFO L229 MonitoredProcess]: Starting monitored process 9 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-25 18:51:31,095 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2021-11-25 18:51:31,133 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2021-11-25 18:51:31,133 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-11-25 18:51:31,134 INFO L263 TraceCheckSpWp]: Trace formula consists of 115 conjuncts, 32 conjunts are in the unsatisfiable core [2021-11-25 18:51:31,137 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-25 18:51:31,395 INFO L134 CoverageAnalysis]: Checked inductivity of 193 backedges. 16 proven. 63 refuted. 0 times theorem prover too weak. 114 trivial. 0 not checked. [2021-11-25 18:51:31,395 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-11-25 18:51:31,562 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-25 18:51:31,563 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [744950229] [2021-11-25 18:51:31,563 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-11-25 18:51:31,563 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1363489907] [2021-11-25 18:51:31,563 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1363489907] provided 0 perfect and 1 imperfect interpolant sequences [2021-11-25 18:51:31,563 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1286463948] [2021-11-25 18:51:31,565 INFO L159 IcfgInterpreter]: Started Sifa with 17 locations of interest [2021-11-25 18:51:31,565 INFO L166 IcfgInterpreter]: Building call graph [2021-11-25 18:51:31,566 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2021-11-25 18:51:31,566 INFO L176 IcfgInterpreter]: Starting interpretation [2021-11-25 18:51:31,566 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2021-11-25 18:51:32,602 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 10 for LOIs [2021-11-25 18:51:32,608 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 75 for LOIs [2021-11-25 18:51:32,630 INFO L180 IcfgInterpreter]: Interpretation finished [2021-11-25 18:51:33,341 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '2322#(and (<= 0 |#NULL.base|) (<= |#NULL.offset| 0) (= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond) (= __VERIFIER_assert_~cond 0) (<= |#NULL.base| 0) (<= 0 |#NULL.offset|) (<= 0 |#StackHeapBarrier|))' at error location [2021-11-25 18:51:33,342 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2021-11-25 18:51:33,342 INFO L186 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2021-11-25 18:51:33,342 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12] total 12 [2021-11-25 18:51:33,342 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [663061630] [2021-11-25 18:51:33,343 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2021-11-25 18:51:33,343 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2021-11-25 18:51:33,343 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-25 18:51:33,344 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2021-11-25 18:51:33,344 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=78, Invalid=572, Unknown=0, NotChecked=0, Total=650 [2021-11-25 18:51:33,344 INFO L87 Difference]: Start difference. First operand 41 states and 48 transitions. Second operand has 12 states, 11 states have (on average 2.090909090909091) internal successors, (23), 11 states have internal predecessors, (23), 9 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (10), 9 states have call predecessors, (10), 9 states have call successors, (10) [2021-11-25 18:51:33,562 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-25 18:51:33,562 INFO L93 Difference]: Finished difference Result 50 states and 59 transitions. [2021-11-25 18:51:33,563 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2021-11-25 18:51:33,564 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 11 states have (on average 2.090909090909091) internal successors, (23), 11 states have internal predecessors, (23), 9 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (10), 9 states have call predecessors, (10), 9 states have call successors, (10) Word has length 66 [2021-11-25 18:51:33,564 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-25 18:51:33,565 INFO L225 Difference]: With dead ends: 50 [2021-11-25 18:51:33,565 INFO L226 Difference]: Without dead ends: 44 [2021-11-25 18:51:33,566 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 151 GetRequests, 122 SyntacticMatches, 3 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 87 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=88, Invalid=668, Unknown=0, NotChecked=0, Total=756 [2021-11-25 18:51:33,567 INFO L933 BasicCegarLoop]: 36 mSDtfsCounter, 2 mSDsluCounter, 280 mSDsCounter, 0 mSdLazyCounter, 188 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 304 SdHoareTripleChecker+Invalid, 189 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 188 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2021-11-25 18:51:33,567 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 304 Invalid, 189 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 188 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2021-11-25 18:51:33,568 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 44 states. [2021-11-25 18:51:33,575 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 44 to 44. [2021-11-25 18:51:33,576 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 44 states, 28 states have (on average 1.0357142857142858) internal successors, (29), 28 states have internal predecessors, (29), 12 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2021-11-25 18:51:33,577 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 44 states to 44 states and 52 transitions. [2021-11-25 18:51:33,577 INFO L78 Accepts]: Start accepts. Automaton has 44 states and 52 transitions. Word has length 66 [2021-11-25 18:51:33,577 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-25 18:51:33,577 INFO L470 AbstractCegarLoop]: Abstraction has 44 states and 52 transitions. [2021-11-25 18:51:33,578 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 11 states have (on average 2.090909090909091) internal successors, (23), 11 states have internal predecessors, (23), 9 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (10), 9 states have call predecessors, (10), 9 states have call successors, (10) [2021-11-25 18:51:33,578 INFO L276 IsEmpty]: Start isEmpty. Operand 44 states and 52 transitions. [2021-11-25 18:51:33,579 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 74 [2021-11-25 18:51:33,579 INFO L506 BasicCegarLoop]: Found error trace [2021-11-25 18:51:33,580 INFO L514 BasicCegarLoop]: trace histogram [10, 9, 9, 8, 8, 8, 7, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-25 18:51:33,618 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2021-11-25 18:51:33,805 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,9 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 18:51:33,806 INFO L402 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-25 18:51:33,806 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-25 18:51:33,807 INFO L85 PathProgramCache]: Analyzing trace with hash -949240366, now seen corresponding path program 7 times [2021-11-25 18:51:33,807 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-25 18:51:33,807 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1577692862] [2021-11-25 18:51:33,807 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 18:51:33,807 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-25 18:51:33,819 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-11-25 18:51:33,819 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1151684805] [2021-11-25 18:51:33,819 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2021-11-25 18:51:33,820 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 18:51:33,820 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 [2021-11-25 18:51:33,823 INFO L229 MonitoredProcess]: Starting monitored process 10 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-25 18:51:33,858 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2021-11-25 18:51:34,565 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-25 18:51:34,567 INFO L263 TraceCheckSpWp]: Trace formula consists of 197 conjuncts, 36 conjunts are in the unsatisfiable core [2021-11-25 18:51:34,570 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-25 18:51:34,892 INFO L134 CoverageAnalysis]: Checked inductivity of 248 backedges. 18 proven. 84 refuted. 0 times theorem prover too weak. 146 trivial. 0 not checked. [2021-11-25 18:51:34,893 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-11-25 18:51:35,040 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-25 18:51:35,040 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1577692862] [2021-11-25 18:51:35,040 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-11-25 18:51:35,040 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1151684805] [2021-11-25 18:51:35,040 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1151684805] provided 0 perfect and 1 imperfect interpolant sequences [2021-11-25 18:51:35,040 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1909446099] [2021-11-25 18:51:35,043 INFO L159 IcfgInterpreter]: Started Sifa with 17 locations of interest [2021-11-25 18:51:35,043 INFO L166 IcfgInterpreter]: Building call graph [2021-11-25 18:51:35,043 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2021-11-25 18:51:35,043 INFO L176 IcfgInterpreter]: Starting interpretation [2021-11-25 18:51:35,044 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2021-11-25 18:51:36,091 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 10 for LOIs [2021-11-25 18:51:36,099 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 75 for LOIs [2021-11-25 18:51:36,124 INFO L180 IcfgInterpreter]: Interpretation finished [2021-11-25 18:51:36,888 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '2768#(and (<= 0 |#NULL.base|) (<= |#NULL.offset| 0) (= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond) (= __VERIFIER_assert_~cond 0) (<= |#NULL.base| 0) (<= 0 |#NULL.offset|) (<= 0 |#StackHeapBarrier|))' at error location [2021-11-25 18:51:36,888 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2021-11-25 18:51:36,888 INFO L186 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2021-11-25 18:51:36,888 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13] total 13 [2021-11-25 18:51:36,888 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1194114733] [2021-11-25 18:51:36,888 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2021-11-25 18:51:36,889 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2021-11-25 18:51:36,889 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-25 18:51:36,890 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2021-11-25 18:51:36,890 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=81, Invalid=621, Unknown=0, NotChecked=0, Total=702 [2021-11-25 18:51:36,890 INFO L87 Difference]: Start difference. First operand 44 states and 52 transitions. Second operand has 13 states, 12 states have (on average 2.0833333333333335) internal successors, (25), 12 states have internal predecessors, (25), 10 states have call successors, (12), 2 states have call predecessors, (12), 1 states have return successors, (11), 10 states have call predecessors, (11), 10 states have call successors, (11) [2021-11-25 18:51:37,156 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-25 18:51:37,156 INFO L93 Difference]: Finished difference Result 53 states and 63 transitions. [2021-11-25 18:51:37,156 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2021-11-25 18:51:37,156 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 12 states have (on average 2.0833333333333335) internal successors, (25), 12 states have internal predecessors, (25), 10 states have call successors, (12), 2 states have call predecessors, (12), 1 states have return successors, (11), 10 states have call predecessors, (11), 10 states have call successors, (11) Word has length 73 [2021-11-25 18:51:37,157 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-25 18:51:37,158 INFO L225 Difference]: With dead ends: 53 [2021-11-25 18:51:37,158 INFO L226 Difference]: Without dead ends: 47 [2021-11-25 18:51:37,159 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 165 GetRequests, 135 SyntacticMatches, 3 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 87 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=91, Invalid=721, Unknown=0, NotChecked=0, Total=812 [2021-11-25 18:51:37,159 INFO L933 BasicCegarLoop]: 39 mSDtfsCounter, 2 mSDsluCounter, 330 mSDsCounter, 0 mSdLazyCounter, 228 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 356 SdHoareTripleChecker+Invalid, 229 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 228 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2021-11-25 18:51:37,160 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 356 Invalid, 229 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 228 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2021-11-25 18:51:37,160 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2021-11-25 18:51:37,168 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 47. [2021-11-25 18:51:37,175 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 47 states, 30 states have (on average 1.0333333333333334) internal successors, (31), 30 states have internal predecessors, (31), 13 states have call successors, (13), 4 states have call predecessors, (13), 3 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2021-11-25 18:51:37,176 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 47 states to 47 states and 56 transitions. [2021-11-25 18:51:37,176 INFO L78 Accepts]: Start accepts. Automaton has 47 states and 56 transitions. Word has length 73 [2021-11-25 18:51:37,177 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-25 18:51:37,177 INFO L470 AbstractCegarLoop]: Abstraction has 47 states and 56 transitions. [2021-11-25 18:51:37,177 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 12 states have (on average 2.0833333333333335) internal successors, (25), 12 states have internal predecessors, (25), 10 states have call successors, (12), 2 states have call predecessors, (12), 1 states have return successors, (11), 10 states have call predecessors, (11), 10 states have call successors, (11) [2021-11-25 18:51:37,178 INFO L276 IsEmpty]: Start isEmpty. Operand 47 states and 56 transitions. [2021-11-25 18:51:37,179 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 81 [2021-11-25 18:51:37,179 INFO L506 BasicCegarLoop]: Found error trace [2021-11-25 18:51:37,179 INFO L514 BasicCegarLoop]: trace histogram [11, 10, 10, 9, 9, 9, 8, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-25 18:51:37,185 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2021-11-25 18:51:37,380 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,10 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 18:51:37,380 INFO L402 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-25 18:51:37,381 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-25 18:51:37,381 INFO L85 PathProgramCache]: Analyzing trace with hash 1086423487, now seen corresponding path program 8 times [2021-11-25 18:51:37,381 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-25 18:51:37,381 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1003994931] [2021-11-25 18:51:37,381 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 18:51:37,381 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-25 18:51:37,391 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-11-25 18:51:37,392 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [182643840] [2021-11-25 18:51:37,392 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2021-11-25 18:51:37,392 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 18:51:37,393 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 [2021-11-25 18:51:37,393 INFO L229 MonitoredProcess]: Starting monitored process 11 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-25 18:51:37,397 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2021-11-25 18:51:49,410 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 9 check-sat command(s) [2021-11-25 18:51:49,410 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-11-25 18:51:49,426 INFO L263 TraceCheckSpWp]: Trace formula consists of 214 conjuncts, 41 conjunts are in the unsatisfiable core [2021-11-25 18:51:49,428 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-25 18:51:49,823 INFO L134 CoverageAnalysis]: Checked inductivity of 310 backedges. 20 proven. 108 refuted. 0 times theorem prover too weak. 182 trivial. 0 not checked. [2021-11-25 18:51:49,823 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-11-25 18:51:50,595 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-25 18:51:50,595 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1003994931] [2021-11-25 18:51:50,595 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-11-25 18:51:50,595 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [182643840] [2021-11-25 18:51:50,595 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [182643840] provided 0 perfect and 1 imperfect interpolant sequences [2021-11-25 18:51:50,596 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1723238157] [2021-11-25 18:51:50,598 INFO L159 IcfgInterpreter]: Started Sifa with 17 locations of interest [2021-11-25 18:51:50,598 INFO L166 IcfgInterpreter]: Building call graph [2021-11-25 18:51:50,599 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2021-11-25 18:51:50,599 INFO L176 IcfgInterpreter]: Starting interpretation [2021-11-25 18:51:50,599 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2021-11-25 18:51:51,637 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 10 for LOIs [2021-11-25 18:51:51,645 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 75 for LOIs [2021-11-25 18:51:51,671 INFO L180 IcfgInterpreter]: Interpretation finished [2021-11-25 18:51:52,660 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '3400#(and (<= 0 |#NULL.base|) (<= |#NULL.offset| 0) (= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond) (= __VERIFIER_assert_~cond 0) (<= |#NULL.base| 0) (<= 0 |#NULL.offset|) (<= 0 |#StackHeapBarrier|))' at error location [2021-11-25 18:51:52,660 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2021-11-25 18:51:52,660 INFO L186 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2021-11-25 18:51:52,660 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14] total 14 [2021-11-25 18:51:52,660 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2048053545] [2021-11-25 18:51:52,661 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2021-11-25 18:51:52,661 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2021-11-25 18:51:52,661 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-25 18:51:52,662 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2021-11-25 18:51:52,662 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=162, Invalid=1028, Unknown=0, NotChecked=0, Total=1190 [2021-11-25 18:51:52,663 INFO L87 Difference]: Start difference. First operand 47 states and 56 transitions. Second operand has 14 states, 13 states have (on average 2.076923076923077) internal successors, (27), 13 states have internal predecessors, (27), 11 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (12), 11 states have call predecessors, (12), 11 states have call successors, (12) [2021-11-25 18:51:52,898 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-25 18:51:52,898 INFO L93 Difference]: Finished difference Result 56 states and 67 transitions. [2021-11-25 18:51:52,898 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2021-11-25 18:51:52,899 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 13 states have (on average 2.076923076923077) internal successors, (27), 13 states have internal predecessors, (27), 11 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (12), 11 states have call predecessors, (12), 11 states have call successors, (12) Word has length 80 [2021-11-25 18:51:52,899 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-25 18:51:52,900 INFO L225 Difference]: With dead ends: 56 [2021-11-25 18:51:52,900 INFO L226 Difference]: Without dead ends: 50 [2021-11-25 18:51:52,901 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 228 GetRequests, 190 SyntacticMatches, 3 SemanticMatches, 35 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 192 ImplicationChecksByTransitivity, 1.5s TimeCoverageRelationStatistics Valid=172, Invalid=1160, Unknown=0, NotChecked=0, Total=1332 [2021-11-25 18:51:52,902 INFO L933 BasicCegarLoop]: 42 mSDtfsCounter, 2 mSDsluCounter, 384 mSDsCounter, 0 mSdLazyCounter, 272 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 412 SdHoareTripleChecker+Invalid, 273 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 272 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2021-11-25 18:51:52,902 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 412 Invalid, 273 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 272 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2021-11-25 18:51:52,903 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 50 states. [2021-11-25 18:51:52,910 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 50 to 50. [2021-11-25 18:51:52,910 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 50 states, 32 states have (on average 1.03125) internal successors, (33), 32 states have internal predecessors, (33), 14 states have call successors, (14), 4 states have call predecessors, (14), 3 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2021-11-25 18:51:52,911 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 50 states to 50 states and 60 transitions. [2021-11-25 18:51:52,912 INFO L78 Accepts]: Start accepts. Automaton has 50 states and 60 transitions. Word has length 80 [2021-11-25 18:51:52,912 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-25 18:51:52,912 INFO L470 AbstractCegarLoop]: Abstraction has 50 states and 60 transitions. [2021-11-25 18:51:52,913 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 13 states have (on average 2.076923076923077) internal successors, (27), 13 states have internal predecessors, (27), 11 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (12), 11 states have call predecessors, (12), 11 states have call successors, (12) [2021-11-25 18:51:52,913 INFO L276 IsEmpty]: Start isEmpty. Operand 50 states and 60 transitions. [2021-11-25 18:51:52,914 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 88 [2021-11-25 18:51:52,915 INFO L506 BasicCegarLoop]: Found error trace [2021-11-25 18:51:52,915 INFO L514 BasicCegarLoop]: trace histogram [12, 11, 11, 10, 10, 10, 9, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-25 18:51:52,929 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2021-11-25 18:51:53,126 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2021-11-25 18:51:53,126 INFO L402 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-25 18:51:53,126 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-25 18:51:53,126 INFO L85 PathProgramCache]: Analyzing trace with hash 1047587122, now seen corresponding path program 9 times [2021-11-25 18:51:53,127 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-25 18:51:53,127 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [4242704] [2021-11-25 18:51:53,127 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 18:51:53,127 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-25 18:51:53,136 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-11-25 18:51:53,136 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [491213055] [2021-11-25 18:51:53,137 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2021-11-25 18:51:53,137 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 18:51:53,137 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 [2021-11-25 18:51:53,138 INFO L229 MonitoredProcess]: Starting monitored process 12 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-25 18:51:53,148 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2021-11-25 18:51:53,193 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2021-11-25 18:51:53,193 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-11-25 18:51:53,195 INFO L263 TraceCheckSpWp]: Trace formula consists of 154 conjuncts, 44 conjunts are in the unsatisfiable core [2021-11-25 18:51:53,198 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-25 18:51:53,558 INFO L134 CoverageAnalysis]: Checked inductivity of 379 backedges. 22 proven. 135 refuted. 0 times theorem prover too weak. 222 trivial. 0 not checked. [2021-11-25 18:51:53,559 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-11-25 18:51:53,758 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-25 18:51:53,758 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [4242704] [2021-11-25 18:51:53,759 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-11-25 18:51:53,759 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [491213055] [2021-11-25 18:51:53,759 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [491213055] provided 0 perfect and 1 imperfect interpolant sequences [2021-11-25 18:51:53,759 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [589386951] [2021-11-25 18:51:53,761 INFO L159 IcfgInterpreter]: Started Sifa with 17 locations of interest [2021-11-25 18:51:53,762 INFO L166 IcfgInterpreter]: Building call graph [2021-11-25 18:51:53,762 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2021-11-25 18:51:53,762 INFO L176 IcfgInterpreter]: Starting interpretation [2021-11-25 18:51:53,762 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2021-11-25 18:51:54,362 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 8 for LOIs [2021-11-25 18:51:54,368 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 75 for LOIs [2021-11-25 18:51:54,401 INFO L180 IcfgInterpreter]: Interpretation finished [2021-11-25 18:51:55,035 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '3910#(and (= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond) (= __VERIFIER_assert_~cond 0) (= |#NULL.offset| 0) (<= 0 |#StackHeapBarrier|) (= |#NULL.base| 0))' at error location [2021-11-25 18:51:55,035 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2021-11-25 18:51:55,035 INFO L186 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2021-11-25 18:51:55,035 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15] total 15 [2021-11-25 18:51:55,035 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [473512399] [2021-11-25 18:51:55,035 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2021-11-25 18:51:55,036 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2021-11-25 18:51:55,036 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-25 18:51:55,036 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2021-11-25 18:51:55,036 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=87, Invalid=725, Unknown=0, NotChecked=0, Total=812 [2021-11-25 18:51:55,037 INFO L87 Difference]: Start difference. First operand 50 states and 60 transitions. Second operand has 15 states, 14 states have (on average 2.0714285714285716) internal successors, (29), 14 states have internal predecessors, (29), 12 states have call successors, (14), 2 states have call predecessors, (14), 1 states have return successors, (13), 12 states have call predecessors, (13), 12 states have call successors, (13) [2021-11-25 18:51:55,271 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-25 18:51:55,271 INFO L93 Difference]: Finished difference Result 59 states and 71 transitions. [2021-11-25 18:51:55,271 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2021-11-25 18:51:55,272 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 14 states have (on average 2.0714285714285716) internal successors, (29), 14 states have internal predecessors, (29), 12 states have call successors, (14), 2 states have call predecessors, (14), 1 states have return successors, (13), 12 states have call predecessors, (13), 12 states have call successors, (13) Word has length 87 [2021-11-25 18:51:55,272 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-25 18:51:55,273 INFO L225 Difference]: With dead ends: 59 [2021-11-25 18:51:55,273 INFO L226 Difference]: Without dead ends: 53 [2021-11-25 18:51:55,274 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 193 GetRequests, 161 SyntacticMatches, 3 SemanticMatches, 29 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 87 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=97, Invalid=833, Unknown=0, NotChecked=0, Total=930 [2021-11-25 18:51:55,275 INFO L933 BasicCegarLoop]: 45 mSDtfsCounter, 2 mSDsluCounter, 442 mSDsCounter, 0 mSdLazyCounter, 320 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 472 SdHoareTripleChecker+Invalid, 321 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 320 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2021-11-25 18:51:55,275 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 472 Invalid, 321 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 320 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2021-11-25 18:51:55,276 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 53 states. [2021-11-25 18:51:55,283 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 53 to 53. [2021-11-25 18:51:55,283 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 53 states, 34 states have (on average 1.0294117647058822) internal successors, (35), 34 states have internal predecessors, (35), 15 states have call successors, (15), 4 states have call predecessors, (15), 3 states have return successors, (14), 14 states have call predecessors, (14), 14 states have call successors, (14) [2021-11-25 18:51:55,284 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 53 states to 53 states and 64 transitions. [2021-11-25 18:51:55,284 INFO L78 Accepts]: Start accepts. Automaton has 53 states and 64 transitions. Word has length 87 [2021-11-25 18:51:55,284 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-25 18:51:55,285 INFO L470 AbstractCegarLoop]: Abstraction has 53 states and 64 transitions. [2021-11-25 18:51:55,285 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 14 states have (on average 2.0714285714285716) internal successors, (29), 14 states have internal predecessors, (29), 12 states have call successors, (14), 2 states have call predecessors, (14), 1 states have return successors, (13), 12 states have call predecessors, (13), 12 states have call successors, (13) [2021-11-25 18:51:55,285 INFO L276 IsEmpty]: Start isEmpty. Operand 53 states and 64 transitions. [2021-11-25 18:51:55,286 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 95 [2021-11-25 18:51:55,287 INFO L506 BasicCegarLoop]: Found error trace [2021-11-25 18:51:55,287 INFO L514 BasicCegarLoop]: trace histogram [13, 12, 12, 11, 11, 11, 10, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-25 18:51:55,308 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2021-11-25 18:51:55,494 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable11 [2021-11-25 18:51:55,494 INFO L402 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-25 18:51:55,494 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-25 18:51:55,494 INFO L85 PathProgramCache]: Analyzing trace with hash -1860777377, now seen corresponding path program 10 times [2021-11-25 18:51:55,494 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-25 18:51:55,495 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [326318555] [2021-11-25 18:51:55,495 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 18:51:55,495 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-25 18:51:55,504 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-11-25 18:51:55,504 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [119351462] [2021-11-25 18:51:55,504 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2021-11-25 18:51:55,504 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 18:51:55,504 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 [2021-11-25 18:51:55,511 INFO L229 MonitoredProcess]: Starting monitored process 13 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-25 18:51:55,512 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2021-11-25 18:51:56,878 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-25 18:51:56,881 INFO L263 TraceCheckSpWp]: Trace formula consists of 248 conjuncts, 48 conjunts are in the unsatisfiable core [2021-11-25 18:51:56,882 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-25 18:51:57,306 INFO L134 CoverageAnalysis]: Checked inductivity of 455 backedges. 24 proven. 165 refuted. 0 times theorem prover too weak. 266 trivial. 0 not checked. [2021-11-25 18:51:57,306 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-11-25 18:51:57,446 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-25 18:51:57,447 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [326318555] [2021-11-25 18:51:57,447 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-11-25 18:51:57,447 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [119351462] [2021-11-25 18:51:57,447 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [119351462] provided 0 perfect and 1 imperfect interpolant sequences [2021-11-25 18:51:57,447 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1050250145] [2021-11-25 18:51:57,449 INFO L159 IcfgInterpreter]: Started Sifa with 17 locations of interest [2021-11-25 18:51:57,449 INFO L166 IcfgInterpreter]: Building call graph [2021-11-25 18:51:57,449 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2021-11-25 18:51:57,450 INFO L176 IcfgInterpreter]: Starting interpretation [2021-11-25 18:51:57,450 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2021-11-25 18:51:58,430 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 10 for LOIs [2021-11-25 18:51:58,437 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 75 for LOIs [2021-11-25 18:51:58,461 INFO L180 IcfgInterpreter]: Interpretation finished [2021-11-25 18:51:59,396 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '4452#(and (<= 0 |#NULL.base|) (<= |#NULL.offset| 0) (= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond) (= __VERIFIER_assert_~cond 0) (<= |#NULL.base| 0) (<= 0 |#NULL.offset|) (<= 0 |#StackHeapBarrier|))' at error location [2021-11-25 18:51:59,396 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2021-11-25 18:51:59,396 INFO L186 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2021-11-25 18:51:59,396 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16] total 16 [2021-11-25 18:51:59,396 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [800043323] [2021-11-25 18:51:59,397 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2021-11-25 18:51:59,397 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2021-11-25 18:51:59,397 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-25 18:51:59,397 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2021-11-25 18:51:59,398 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=90, Invalid=780, Unknown=0, NotChecked=0, Total=870 [2021-11-25 18:51:59,398 INFO L87 Difference]: Start difference. First operand 53 states and 64 transitions. Second operand has 16 states, 15 states have (on average 2.066666666666667) internal successors, (31), 15 states have internal predecessors, (31), 13 states have call successors, (15), 2 states have call predecessors, (15), 1 states have return successors, (14), 13 states have call predecessors, (14), 13 states have call successors, (14) [2021-11-25 18:51:59,687 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-25 18:51:59,688 INFO L93 Difference]: Finished difference Result 62 states and 75 transitions. [2021-11-25 18:51:59,689 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2021-11-25 18:51:59,690 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 15 states have (on average 2.066666666666667) internal successors, (31), 15 states have internal predecessors, (31), 13 states have call successors, (15), 2 states have call predecessors, (15), 1 states have return successors, (14), 13 states have call predecessors, (14), 13 states have call successors, (14) Word has length 94 [2021-11-25 18:51:59,690 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-25 18:51:59,691 INFO L225 Difference]: With dead ends: 62 [2021-11-25 18:51:59,691 INFO L226 Difference]: Without dead ends: 56 [2021-11-25 18:51:59,692 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 207 GetRequests, 174 SyntacticMatches, 3 SemanticMatches, 30 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 87 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=100, Invalid=892, Unknown=0, NotChecked=0, Total=992 [2021-11-25 18:51:59,693 INFO L933 BasicCegarLoop]: 48 mSDtfsCounter, 2 mSDsluCounter, 504 mSDsCounter, 0 mSdLazyCounter, 372 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 536 SdHoareTripleChecker+Invalid, 373 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 372 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2021-11-25 18:51:59,693 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 536 Invalid, 373 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 372 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2021-11-25 18:51:59,694 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 56 states. [2021-11-25 18:51:59,704 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 56 to 56. [2021-11-25 18:51:59,704 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 56 states, 36 states have (on average 1.0277777777777777) internal successors, (37), 36 states have internal predecessors, (37), 16 states have call successors, (16), 4 states have call predecessors, (16), 3 states have return successors, (15), 15 states have call predecessors, (15), 15 states have call successors, (15) [2021-11-25 18:51:59,706 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 56 states to 56 states and 68 transitions. [2021-11-25 18:51:59,706 INFO L78 Accepts]: Start accepts. Automaton has 56 states and 68 transitions. Word has length 94 [2021-11-25 18:51:59,707 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-25 18:51:59,707 INFO L470 AbstractCegarLoop]: Abstraction has 56 states and 68 transitions. [2021-11-25 18:51:59,707 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 15 states have (on average 2.066666666666667) internal successors, (31), 15 states have internal predecessors, (31), 13 states have call successors, (15), 2 states have call predecessors, (15), 1 states have return successors, (14), 13 states have call predecessors, (14), 13 states have call successors, (14) [2021-11-25 18:51:59,707 INFO L276 IsEmpty]: Start isEmpty. Operand 56 states and 68 transitions. [2021-11-25 18:51:59,709 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 102 [2021-11-25 18:51:59,709 INFO L506 BasicCegarLoop]: Found error trace [2021-11-25 18:51:59,710 INFO L514 BasicCegarLoop]: trace histogram [14, 13, 13, 12, 12, 12, 11, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-25 18:51:59,718 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Forceful destruction successful, exit code 0 [2021-11-25 18:51:59,915 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable12,13 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 18:51:59,916 INFO L402 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-25 18:51:59,916 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-25 18:51:59,916 INFO L85 PathProgramCache]: Analyzing trace with hash 366390418, now seen corresponding path program 11 times [2021-11-25 18:51:59,917 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-25 18:51:59,917 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1924424981] [2021-11-25 18:51:59,917 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 18:51:59,917 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-25 18:51:59,930 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-11-25 18:51:59,930 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1123472151] [2021-11-25 18:51:59,931 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2021-11-25 18:51:59,931 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 18:51:59,931 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 [2021-11-25 18:51:59,932 INFO L229 MonitoredProcess]: Starting monitored process 14 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-25 18:51:59,933 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2021-11-25 18:52:06,634 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 12 check-sat command(s) [2021-11-25 18:52:06,634 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-11-25 18:52:06,642 INFO L263 TraceCheckSpWp]: Trace formula consists of 265 conjuncts, 52 conjunts are in the unsatisfiable core [2021-11-25 18:52:06,644 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-25 18:52:07,014 INFO L134 CoverageAnalysis]: Checked inductivity of 538 backedges. 26 proven. 198 refuted. 0 times theorem prover too weak. 314 trivial. 0 not checked. [2021-11-25 18:52:07,014 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-11-25 18:52:07,205 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-25 18:52:07,205 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1924424981] [2021-11-25 18:52:07,205 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-11-25 18:52:07,205 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1123472151] [2021-11-25 18:52:07,205 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1123472151] provided 0 perfect and 1 imperfect interpolant sequences [2021-11-25 18:52:07,205 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [25706320] [2021-11-25 18:52:07,207 INFO L159 IcfgInterpreter]: Started Sifa with 17 locations of interest [2021-11-25 18:52:07,207 INFO L166 IcfgInterpreter]: Building call graph [2021-11-25 18:52:07,208 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2021-11-25 18:52:07,208 INFO L176 IcfgInterpreter]: Starting interpretation [2021-11-25 18:52:07,208 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2021-11-25 18:52:07,623 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 8 for LOIs [2021-11-25 18:52:07,639 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 75 for LOIs [2021-11-25 18:52:07,660 INFO L180 IcfgInterpreter]: Interpretation finished [2021-11-25 18:52:08,421 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '5026#(and (= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond) (= __VERIFIER_assert_~cond 0) (= |#NULL.offset| 0) (<= 0 |#StackHeapBarrier|) (= |#NULL.base| 0))' at error location [2021-11-25 18:52:08,422 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2021-11-25 18:52:08,422 INFO L186 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2021-11-25 18:52:08,422 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17] total 17 [2021-11-25 18:52:08,422 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [837573477] [2021-11-25 18:52:08,422 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2021-11-25 18:52:08,423 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2021-11-25 18:52:08,423 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-25 18:52:08,423 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2021-11-25 18:52:08,424 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=93, Invalid=837, Unknown=0, NotChecked=0, Total=930 [2021-11-25 18:52:08,424 INFO L87 Difference]: Start difference. First operand 56 states and 68 transitions. Second operand has 17 states, 16 states have (on average 2.0625) internal successors, (33), 16 states have internal predecessors, (33), 14 states have call successors, (16), 2 states have call predecessors, (16), 1 states have return successors, (15), 14 states have call predecessors, (15), 14 states have call successors, (15) [2021-11-25 18:52:08,804 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-25 18:52:08,805 INFO L93 Difference]: Finished difference Result 65 states and 79 transitions. [2021-11-25 18:52:08,805 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2021-11-25 18:52:08,805 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 16 states have (on average 2.0625) internal successors, (33), 16 states have internal predecessors, (33), 14 states have call successors, (16), 2 states have call predecessors, (16), 1 states have return successors, (15), 14 states have call predecessors, (15), 14 states have call successors, (15) Word has length 101 [2021-11-25 18:52:08,805 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-25 18:52:08,806 INFO L225 Difference]: With dead ends: 65 [2021-11-25 18:52:08,806 INFO L226 Difference]: Without dead ends: 59 [2021-11-25 18:52:08,807 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 221 GetRequests, 187 SyntacticMatches, 3 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 87 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=103, Invalid=953, Unknown=0, NotChecked=0, Total=1056 [2021-11-25 18:52:08,807 INFO L933 BasicCegarLoop]: 51 mSDtfsCounter, 2 mSDsluCounter, 570 mSDsCounter, 0 mSdLazyCounter, 428 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 604 SdHoareTripleChecker+Invalid, 429 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 428 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2021-11-25 18:52:08,807 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 604 Invalid, 429 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 428 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2021-11-25 18:52:08,808 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 59 states. [2021-11-25 18:52:08,816 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 59 to 59. [2021-11-25 18:52:08,817 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 59 states, 38 states have (on average 1.0263157894736843) internal successors, (39), 38 states have internal predecessors, (39), 17 states have call successors, (17), 4 states have call predecessors, (17), 3 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2021-11-25 18:52:08,818 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 59 states to 59 states and 72 transitions. [2021-11-25 18:52:08,818 INFO L78 Accepts]: Start accepts. Automaton has 59 states and 72 transitions. Word has length 101 [2021-11-25 18:52:08,818 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-25 18:52:08,819 INFO L470 AbstractCegarLoop]: Abstraction has 59 states and 72 transitions. [2021-11-25 18:52:08,819 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 16 states have (on average 2.0625) internal successors, (33), 16 states have internal predecessors, (33), 14 states have call successors, (16), 2 states have call predecessors, (16), 1 states have return successors, (15), 14 states have call predecessors, (15), 14 states have call successors, (15) [2021-11-25 18:52:08,819 INFO L276 IsEmpty]: Start isEmpty. Operand 59 states and 72 transitions. [2021-11-25 18:52:08,821 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 109 [2021-11-25 18:52:08,821 INFO L506 BasicCegarLoop]: Found error trace [2021-11-25 18:52:08,821 INFO L514 BasicCegarLoop]: trace histogram [15, 14, 14, 13, 13, 13, 12, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-25 18:52:08,830 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Forceful destruction successful, exit code 0 [2021-11-25 18:52:09,030 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2021-11-25 18:52:09,030 INFO L402 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-25 18:52:09,030 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-25 18:52:09,030 INFO L85 PathProgramCache]: Analyzing trace with hash 129006335, now seen corresponding path program 12 times [2021-11-25 18:52:09,031 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-25 18:52:09,031 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1123093995] [2021-11-25 18:52:09,031 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 18:52:09,031 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-25 18:52:09,043 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-11-25 18:52:09,044 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1086000671] [2021-11-25 18:52:09,044 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2021-11-25 18:52:09,044 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 18:52:09,045 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 [2021-11-25 18:52:09,058 INFO L229 MonitoredProcess]: Starting monitored process 15 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-25 18:52:09,060 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2021-11-25 18:52:09,109 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2021-11-25 18:52:09,109 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-11-25 18:52:09,111 INFO L263 TraceCheckSpWp]: Trace formula consists of 193 conjuncts, 56 conjunts are in the unsatisfiable core [2021-11-25 18:52:09,114 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-25 18:52:09,529 INFO L134 CoverageAnalysis]: Checked inductivity of 628 backedges. 28 proven. 234 refuted. 0 times theorem prover too weak. 366 trivial. 0 not checked. [2021-11-25 18:52:09,529 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-11-25 18:52:09,776 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-25 18:52:09,776 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1123093995] [2021-11-25 18:52:09,776 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-11-25 18:52:09,776 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1086000671] [2021-11-25 18:52:09,776 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1086000671] provided 0 perfect and 1 imperfect interpolant sequences [2021-11-25 18:52:09,776 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1811556140] [2021-11-25 18:52:09,778 INFO L159 IcfgInterpreter]: Started Sifa with 17 locations of interest [2021-11-25 18:52:09,779 INFO L166 IcfgInterpreter]: Building call graph [2021-11-25 18:52:09,779 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2021-11-25 18:52:09,779 INFO L176 IcfgInterpreter]: Starting interpretation [2021-11-25 18:52:09,779 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2021-11-25 18:52:10,666 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 10 for LOIs [2021-11-25 18:52:10,673 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 75 for LOIs [2021-11-25 18:52:10,693 INFO L180 IcfgInterpreter]: Interpretation finished [2021-11-25 18:52:11,570 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '5632#(and (<= 0 |#NULL.base|) (<= |#NULL.offset| 0) (= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond) (= __VERIFIER_assert_~cond 0) (<= |#NULL.base| 0) (<= 0 |#NULL.offset|) (<= 0 |#StackHeapBarrier|))' at error location [2021-11-25 18:52:11,570 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2021-11-25 18:52:11,570 INFO L186 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2021-11-25 18:52:11,571 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18] total 18 [2021-11-25 18:52:11,571 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [719396501] [2021-11-25 18:52:11,571 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2021-11-25 18:52:11,571 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2021-11-25 18:52:11,571 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-25 18:52:11,572 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2021-11-25 18:52:11,572 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=96, Invalid=896, Unknown=0, NotChecked=0, Total=992 [2021-11-25 18:52:11,573 INFO L87 Difference]: Start difference. First operand 59 states and 72 transitions. Second operand has 18 states, 17 states have (on average 2.0588235294117645) internal successors, (35), 17 states have internal predecessors, (35), 15 states have call successors, (17), 2 states have call predecessors, (17), 1 states have return successors, (16), 15 states have call predecessors, (16), 15 states have call successors, (16) [2021-11-25 18:52:11,968 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-25 18:52:11,968 INFO L93 Difference]: Finished difference Result 68 states and 83 transitions. [2021-11-25 18:52:11,969 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2021-11-25 18:52:11,969 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 17 states have (on average 2.0588235294117645) internal successors, (35), 17 states have internal predecessors, (35), 15 states have call successors, (17), 2 states have call predecessors, (17), 1 states have return successors, (16), 15 states have call predecessors, (16), 15 states have call successors, (16) Word has length 108 [2021-11-25 18:52:11,969 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-25 18:52:11,970 INFO L225 Difference]: With dead ends: 68 [2021-11-25 18:52:11,970 INFO L226 Difference]: Without dead ends: 62 [2021-11-25 18:52:11,971 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 235 GetRequests, 200 SyntacticMatches, 3 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 87 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=106, Invalid=1016, Unknown=0, NotChecked=0, Total=1122 [2021-11-25 18:52:11,972 INFO L933 BasicCegarLoop]: 54 mSDtfsCounter, 2 mSDsluCounter, 640 mSDsCounter, 0 mSdLazyCounter, 488 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 676 SdHoareTripleChecker+Invalid, 489 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 488 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2021-11-25 18:52:11,972 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 676 Invalid, 489 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 488 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2021-11-25 18:52:11,973 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 62 states. [2021-11-25 18:52:11,982 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 62 to 62. [2021-11-25 18:52:11,982 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 62 states, 40 states have (on average 1.025) internal successors, (41), 40 states have internal predecessors, (41), 18 states have call successors, (18), 4 states have call predecessors, (18), 3 states have return successors, (17), 17 states have call predecessors, (17), 17 states have call successors, (17) [2021-11-25 18:52:11,983 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 62 states to 62 states and 76 transitions. [2021-11-25 18:52:11,983 INFO L78 Accepts]: Start accepts. Automaton has 62 states and 76 transitions. Word has length 108 [2021-11-25 18:52:11,984 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-25 18:52:11,984 INFO L470 AbstractCegarLoop]: Abstraction has 62 states and 76 transitions. [2021-11-25 18:52:11,984 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 18 states, 17 states have (on average 2.0588235294117645) internal successors, (35), 17 states have internal predecessors, (35), 15 states have call successors, (17), 2 states have call predecessors, (17), 1 states have return successors, (16), 15 states have call predecessors, (16), 15 states have call successors, (16) [2021-11-25 18:52:11,984 INFO L276 IsEmpty]: Start isEmpty. Operand 62 states and 76 transitions. [2021-11-25 18:52:11,986 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 116 [2021-11-25 18:52:11,986 INFO L506 BasicCegarLoop]: Found error trace [2021-11-25 18:52:11,986 INFO L514 BasicCegarLoop]: trace histogram [16, 15, 15, 14, 14, 14, 13, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-25 18:52:12,025 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Forceful destruction successful, exit code 0 [2021-11-25 18:52:12,209 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 15 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2021-11-25 18:52:12,210 INFO L402 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-25 18:52:12,210 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-25 18:52:12,210 INFO L85 PathProgramCache]: Analyzing trace with hash 1823672306, now seen corresponding path program 13 times [2021-11-25 18:52:12,210 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-25 18:52:12,210 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1412777848] [2021-11-25 18:52:12,211 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 18:52:12,211 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-25 18:52:12,218 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-11-25 18:52:12,218 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1749524002] [2021-11-25 18:52:12,219 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2021-11-25 18:52:12,219 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 18:52:12,219 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 [2021-11-25 18:52:12,220 INFO L229 MonitoredProcess]: Starting monitored process 16 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-25 18:52:12,231 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2021-11-25 18:52:13,864 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-25 18:52:13,868 INFO L263 TraceCheckSpWp]: Trace formula consists of 299 conjuncts, 60 conjunts are in the unsatisfiable core [2021-11-25 18:52:13,870 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-25 18:52:14,327 INFO L134 CoverageAnalysis]: Checked inductivity of 725 backedges. 30 proven. 273 refuted. 0 times theorem prover too weak. 422 trivial. 0 not checked. [2021-11-25 18:52:14,327 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-11-25 18:52:14,554 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-25 18:52:14,554 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1412777848] [2021-11-25 18:52:14,554 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-11-25 18:52:14,554 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1749524002] [2021-11-25 18:52:14,554 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1749524002] provided 0 perfect and 1 imperfect interpolant sequences [2021-11-25 18:52:14,554 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [681700382] [2021-11-25 18:52:14,556 INFO L159 IcfgInterpreter]: Started Sifa with 17 locations of interest [2021-11-25 18:52:14,556 INFO L166 IcfgInterpreter]: Building call graph [2021-11-25 18:52:14,557 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2021-11-25 18:52:14,557 INFO L176 IcfgInterpreter]: Starting interpretation [2021-11-25 18:52:14,557 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2021-11-25 18:52:15,060 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 8 for LOIs [2021-11-25 18:52:15,069 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 75 for LOIs [2021-11-25 18:52:15,094 INFO L180 IcfgInterpreter]: Interpretation finished [2021-11-25 18:52:15,995 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '6270#(and (= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond) (= __VERIFIER_assert_~cond 0) (= |#NULL.offset| 0) (<= 0 |#StackHeapBarrier|) (= |#NULL.base| 0))' at error location [2021-11-25 18:52:15,995 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2021-11-25 18:52:15,996 INFO L186 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2021-11-25 18:52:15,996 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19] total 19 [2021-11-25 18:52:15,996 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [334154060] [2021-11-25 18:52:15,996 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2021-11-25 18:52:15,997 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2021-11-25 18:52:15,997 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-25 18:52:15,997 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2021-11-25 18:52:15,998 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=99, Invalid=957, Unknown=0, NotChecked=0, Total=1056 [2021-11-25 18:52:15,998 INFO L87 Difference]: Start difference. First operand 62 states and 76 transitions. Second operand has 19 states, 18 states have (on average 2.0555555555555554) internal successors, (37), 18 states have internal predecessors, (37), 16 states have call successors, (18), 2 states have call predecessors, (18), 1 states have return successors, (17), 16 states have call predecessors, (17), 16 states have call successors, (17) [2021-11-25 18:52:16,510 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-25 18:52:16,510 INFO L93 Difference]: Finished difference Result 71 states and 87 transitions. [2021-11-25 18:52:16,511 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2021-11-25 18:52:16,511 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 18 states have (on average 2.0555555555555554) internal successors, (37), 18 states have internal predecessors, (37), 16 states have call successors, (18), 2 states have call predecessors, (18), 1 states have return successors, (17), 16 states have call predecessors, (17), 16 states have call successors, (17) Word has length 115 [2021-11-25 18:52:16,512 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-25 18:52:16,512 INFO L225 Difference]: With dead ends: 71 [2021-11-25 18:52:16,513 INFO L226 Difference]: Without dead ends: 65 [2021-11-25 18:52:16,513 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 249 GetRequests, 213 SyntacticMatches, 3 SemanticMatches, 33 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 87 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=109, Invalid=1081, Unknown=0, NotChecked=0, Total=1190 [2021-11-25 18:52:16,514 INFO L933 BasicCegarLoop]: 57 mSDtfsCounter, 2 mSDsluCounter, 714 mSDsCounter, 0 mSdLazyCounter, 552 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 752 SdHoareTripleChecker+Invalid, 553 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 552 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2021-11-25 18:52:16,515 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 752 Invalid, 553 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 552 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2021-11-25 18:52:16,515 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 65 states. [2021-11-25 18:52:16,525 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 65 to 65. [2021-11-25 18:52:16,525 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 65 states, 42 states have (on average 1.0238095238095237) internal successors, (43), 42 states have internal predecessors, (43), 19 states have call successors, (19), 4 states have call predecessors, (19), 3 states have return successors, (18), 18 states have call predecessors, (18), 18 states have call successors, (18) [2021-11-25 18:52:16,526 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 65 states to 65 states and 80 transitions. [2021-11-25 18:52:16,527 INFO L78 Accepts]: Start accepts. Automaton has 65 states and 80 transitions. Word has length 115 [2021-11-25 18:52:16,527 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-25 18:52:16,527 INFO L470 AbstractCegarLoop]: Abstraction has 65 states and 80 transitions. [2021-11-25 18:52:16,528 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 18 states have (on average 2.0555555555555554) internal successors, (37), 18 states have internal predecessors, (37), 16 states have call successors, (18), 2 states have call predecessors, (18), 1 states have return successors, (17), 16 states have call predecessors, (17), 16 states have call successors, (17) [2021-11-25 18:52:16,528 INFO L276 IsEmpty]: Start isEmpty. Operand 65 states and 80 transitions. [2021-11-25 18:52:16,529 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 123 [2021-11-25 18:52:16,529 INFO L506 BasicCegarLoop]: Found error trace [2021-11-25 18:52:16,530 INFO L514 BasicCegarLoop]: trace histogram [17, 16, 16, 15, 15, 15, 14, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-25 18:52:16,546 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Forceful destruction successful, exit code 0 [2021-11-25 18:52:16,746 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable15,16 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 18:52:16,747 INFO L402 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-25 18:52:16,747 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-25 18:52:16,747 INFO L85 PathProgramCache]: Analyzing trace with hash -2135387233, now seen corresponding path program 14 times [2021-11-25 18:52:16,747 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-25 18:52:16,747 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [690807820] [2021-11-25 18:52:16,748 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 18:52:16,748 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-25 18:52:16,760 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-11-25 18:52:16,760 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2067733039] [2021-11-25 18:52:16,760 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2021-11-25 18:52:16,761 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 18:52:16,761 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 [2021-11-25 18:52:16,761 INFO L229 MonitoredProcess]: Starting monitored process 17 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-25 18:52:16,763 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_aeee3a73-cfc8-4588-b6ac-f59e95bee580/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process