./Ultimate.py --spec ../../sv-benchmarks/c/properties/unreach-call.prp --file ../../sv-benchmarks/c/nla-digbench-scaling/egcd2-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_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/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_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/config/TaipanReach.xml -i ../../sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_valuebound50.c -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/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_f2dd3727-c906-496d-be50-91b3db092945/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 fc71ae13b1bed24e074eb2de07c8f2064aa903343708c3aabf1b928078c9e7f6 --- Real Ultimate output --- This is Ultimate 0.2.2-hotfix-svcomp22-839c364 [2021-11-25 18:17:38,004 INFO L177 SettingsManager]: Resetting all preferences to default values... [2021-11-25 18:17:38,007 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2021-11-25 18:17:38,037 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2021-11-25 18:17:38,038 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2021-11-25 18:17:38,039 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2021-11-25 18:17:38,041 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2021-11-25 18:17:38,044 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2021-11-25 18:17:38,047 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2021-11-25 18:17:38,048 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2021-11-25 18:17:38,049 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2021-11-25 18:17:38,051 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2021-11-25 18:17:38,052 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2021-11-25 18:17:38,053 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2021-11-25 18:17:38,055 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2021-11-25 18:17:38,061 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2021-11-25 18:17:38,062 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2021-11-25 18:17:38,063 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2021-11-25 18:17:38,065 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2021-11-25 18:17:38,068 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2021-11-25 18:17:38,070 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2021-11-25 18:17:38,072 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2021-11-25 18:17:38,073 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2021-11-25 18:17:38,074 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2021-11-25 18:17:38,078 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2021-11-25 18:17:38,079 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2021-11-25 18:17:38,079 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2021-11-25 18:17:38,080 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2021-11-25 18:17:38,081 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2021-11-25 18:17:38,082 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2021-11-25 18:17:38,082 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2021-11-25 18:17:38,083 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2021-11-25 18:17:38,084 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2021-11-25 18:17:38,085 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2021-11-25 18:17:38,087 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2021-11-25 18:17:38,087 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2021-11-25 18:17:38,088 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2021-11-25 18:17:38,088 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2021-11-25 18:17:38,089 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2021-11-25 18:17:38,090 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2021-11-25 18:17:38,091 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2021-11-25 18:17:38,092 INFO L101 SettingsManager]: Beginning loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/config/svcomp-Reach-32bit-Taipan_Default.epf [2021-11-25 18:17:38,122 INFO L113 SettingsManager]: Loading preferences was successful [2021-11-25 18:17:38,122 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2021-11-25 18:17:38,123 INFO L136 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2021-11-25 18:17:38,123 INFO L138 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2021-11-25 18:17:38,124 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2021-11-25 18:17:38,125 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2021-11-25 18:17:38,125 INFO L138 SettingsManager]: * User list type=DISABLED [2021-11-25 18:17:38,126 INFO L136 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2021-11-25 18:17:38,126 INFO L138 SettingsManager]: * Explicit value domain=true [2021-11-25 18:17:38,126 INFO L138 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2021-11-25 18:17:38,127 INFO L138 SettingsManager]: * Octagon Domain=false [2021-11-25 18:17:38,127 INFO L138 SettingsManager]: * Abstract domain=CompoundDomain [2021-11-25 18:17:38,128 INFO L138 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2021-11-25 18:17:38,128 INFO L138 SettingsManager]: * Use the RCFG-of-the-future interface=true [2021-11-25 18:17:38,128 INFO L138 SettingsManager]: * Interval Domain=false [2021-11-25 18:17:38,130 INFO L136 SettingsManager]: Preferences of Sifa differ from their defaults: [2021-11-25 18:17:38,131 INFO L138 SettingsManager]: * Call Summarizer=TopInputCallSummarizer [2021-11-25 18:17:38,131 INFO L138 SettingsManager]: * Simplification Technique=POLY_PAC [2021-11-25 18:17:38,132 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2021-11-25 18:17:38,132 INFO L138 SettingsManager]: * sizeof long=4 [2021-11-25 18:17:38,132 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2021-11-25 18:17:38,133 INFO L138 SettingsManager]: * sizeof POINTER=4 [2021-11-25 18:17:38,133 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2021-11-25 18:17:38,133 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2021-11-25 18:17:38,134 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2021-11-25 18:17:38,134 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2021-11-25 18:17:38,134 INFO L138 SettingsManager]: * sizeof long double=12 [2021-11-25 18:17:38,134 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2021-11-25 18:17:38,135 INFO L138 SettingsManager]: * Use constant arrays=true [2021-11-25 18:17:38,135 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2021-11-25 18:17:38,135 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2021-11-25 18:17:38,136 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2021-11-25 18:17:38,136 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2021-11-25 18:17:38,136 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2021-11-25 18:17:38,136 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2021-11-25 18:17:38,137 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2021-11-25 18:17:38,137 INFO L138 SettingsManager]: * Trace refinement strategy=SIFA_TAIPAN [2021-11-25 18:17:38,137 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2021-11-25 18:17:38,138 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2021-11-25 18:17:38,138 INFO L138 SettingsManager]: * Trace refinement exception blacklist=NONE [2021-11-25 18:17:38,138 INFO L138 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2021-11-25 18:17:38,139 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_f2dd3727-c906-496d-be50-91b3db092945/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_f2dd3727-c906-496d-be50-91b3db092945/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 -> fc71ae13b1bed24e074eb2de07c8f2064aa903343708c3aabf1b928078c9e7f6 [2021-11-25 18:17:38,547 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2021-11-25 18:17:38,575 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2021-11-25 18:17:38,578 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2021-11-25 18:17:38,580 INFO L271 PluginConnector]: Initializing CDTParser... [2021-11-25 18:17:38,581 INFO L275 PluginConnector]: CDTParser initialized [2021-11-25 18:17:38,582 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/../../sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_valuebound50.c [2021-11-25 18:17:38,665 INFO L220 CDTParser]: Created temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/data/382c84870/aa6539ece3f94139b3e67d4abc6ec1dd/FLAG500b5ff96 [2021-11-25 18:17:39,281 INFO L306 CDTParser]: Found 1 translation units. [2021-11-25 18:17:39,281 INFO L160 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_valuebound50.c [2021-11-25 18:17:39,298 INFO L349 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/data/382c84870/aa6539ece3f94139b3e67d4abc6ec1dd/FLAG500b5ff96 [2021-11-25 18:17:39,613 INFO L357 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/data/382c84870/aa6539ece3f94139b3e67d4abc6ec1dd [2021-11-25 18:17:39,618 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2021-11-25 18:17:39,621 INFO L131 ToolchainWalker]: Walking toolchain with 6 elements. [2021-11-25 18:17:39,627 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2021-11-25 18:17:39,627 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2021-11-25 18:17:39,632 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2021-11-25 18:17:39,633 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 25.11 06:17:39" (1/1) ... [2021-11-25 18:17:39,637 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@3c1a94b7 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.11 06:17:39, skipping insertion in model container [2021-11-25 18:17:39,637 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 25.11 06:17:39" (1/1) ... [2021-11-25 18:17:39,648 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2021-11-25 18:17:39,668 INFO L178 MainTranslator]: Built tables and reachable declarations [2021-11-25 18:17:39,882 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_f2dd3727-c906-496d-be50-91b3db092945/sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_valuebound50.c[490,503] [2021-11-25 18:17:39,934 INFO L209 PostProcessor]: Analyzing one entry point: main [2021-11-25 18:17:39,945 INFO L203 MainTranslator]: Completed pre-run [2021-11-25 18:17:39,964 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_f2dd3727-c906-496d-be50-91b3db092945/sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_valuebound50.c[490,503] [2021-11-25 18:17:39,988 INFO L209 PostProcessor]: Analyzing one entry point: main [2021-11-25 18:17:40,010 INFO L208 MainTranslator]: Completed translation [2021-11-25 18:17:40,011 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.11 06:17:40 WrapperNode [2021-11-25 18:17:40,011 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2021-11-25 18:17:40,013 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2021-11-25 18:17:40,013 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2021-11-25 18:17:40,013 INFO L275 PluginConnector]: Boogie Procedure Inliner initialized [2021-11-25 18:17:40,022 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:17:40" (1/1) ... [2021-11-25 18:17:40,043 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:17:40" (1/1) ... [2021-11-25 18:17:40,079 INFO L137 Inliner]: procedures = 14, calls = 19, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 77 [2021-11-25 18:17:40,080 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2021-11-25 18:17:40,081 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2021-11-25 18:17:40,081 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2021-11-25 18:17:40,081 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2021-11-25 18:17:40,091 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.11 06:17:40" (1/1) ... [2021-11-25 18:17:40,091 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.11 06:17:40" (1/1) ... [2021-11-25 18:17:40,097 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.11 06:17:40" (1/1) ... [2021-11-25 18:17:40,098 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.11 06:17:40" (1/1) ... [2021-11-25 18:17:40,113 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.11 06:17:40" (1/1) ... [2021-11-25 18:17:40,117 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.11 06:17:40" (1/1) ... [2021-11-25 18:17:40,118 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.11 06:17:40" (1/1) ... [2021-11-25 18:17:40,126 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2021-11-25 18:17:40,128 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2021-11-25 18:17:40,128 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2021-11-25 18:17:40,128 INFO L275 PluginConnector]: RCFGBuilder initialized [2021-11-25 18:17:40,129 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.11 06:17:40" (1/1) ... [2021-11-25 18:17:40,138 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2021-11-25 18:17:40,150 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 [2021-11-25 18:17:40,167 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2021-11-25 18:17:40,187 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2021-11-25 18:17:40,226 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2021-11-25 18:17:40,227 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2021-11-25 18:17:40,227 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2021-11-25 18:17:40,227 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2021-11-25 18:17:40,227 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2021-11-25 18:17:40,228 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2021-11-25 18:17:40,228 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2021-11-25 18:17:40,228 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2021-11-25 18:17:40,315 INFO L236 CfgBuilder]: Building ICFG [2021-11-25 18:17:40,317 INFO L262 CfgBuilder]: Building CFG for each procedure with an implementation [2021-11-25 18:17:40,473 INFO L277 CfgBuilder]: Performing block encoding [2021-11-25 18:17:40,497 INFO L296 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2021-11-25 18:17:40,497 INFO L301 CfgBuilder]: Removed 2 assume(true) statements. [2021-11-25 18:17:40,500 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 25.11 06:17:40 BoogieIcfgContainer [2021-11-25 18:17:40,500 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2021-11-25 18:17:40,502 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2021-11-25 18:17:40,502 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2021-11-25 18:17:40,506 INFO L275 PluginConnector]: TraceAbstraction initialized [2021-11-25 18:17:40,506 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 25.11 06:17:39" (1/3) ... [2021-11-25 18:17:40,507 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5589f977 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 25.11 06:17:40, skipping insertion in model container [2021-11-25 18:17:40,507 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.11 06:17:40" (2/3) ... [2021-11-25 18:17:40,508 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5589f977 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 25.11 06:17:40, skipping insertion in model container [2021-11-25 18:17:40,508 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 25.11 06:17:40" (3/3) ... [2021-11-25 18:17:40,509 INFO L111 eAbstractionObserver]: Analyzing ICFG egcd2-ll_valuebound50.c [2021-11-25 18:17:40,516 INFO L204 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2021-11-25 18:17:40,516 INFO L163 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2021-11-25 18:17:40,574 INFO L338 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2021-11-25 18:17:40,583 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:17:40,584 INFO L340 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2021-11-25 18:17:40,605 INFO L276 IsEmpty]: Start isEmpty. Operand has 30 states, 14 states have (on average 1.4285714285714286) internal successors, (20), 16 states have internal predecessors, (20), 12 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2021-11-25 18:17:40,612 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2021-11-25 18:17:40,612 INFO L506 BasicCegarLoop]: Found error trace [2021-11-25 18:17:40,613 INFO L514 BasicCegarLoop]: trace histogram [6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-25 18:17:40,614 INFO L402 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-25 18:17:40,620 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-25 18:17:40,621 INFO L85 PathProgramCache]: Analyzing trace with hash 966807424, now seen corresponding path program 1 times [2021-11-25 18:17:40,633 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-25 18:17:40,634 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [996069466] [2021-11-25 18:17:40,634 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 18:17:40,635 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-25 18:17:40,758 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-11-25 18:17:40,758 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [248390618] [2021-11-25 18:17:40,759 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 18:17:40,759 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 18:17:40,760 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 [2021-11-25 18:17:40,761 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-25 18:17:40,790 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2021-11-25 18:17:40,902 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-25 18:17:40,905 INFO L263 TraceCheckSpWp]: Trace formula consists of 109 conjuncts, 1 conjunts are in the unsatisfiable core [2021-11-25 18:17:40,912 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-25 18:17:41,094 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2021-11-25 18:17:41,095 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-11-25 18:17:41,097 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-25 18:17:41,098 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [996069466] [2021-11-25 18:17:41,098 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-11-25 18:17:41,100 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [248390618] [2021-11-25 18:17:41,100 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [248390618] provided 1 perfect and 0 imperfect interpolant sequences [2021-11-25 18:17:41,101 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-11-25 18:17:41,102 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2021-11-25 18:17:41,105 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1959574797] [2021-11-25 18:17:41,106 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-11-25 18:17:41,111 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2021-11-25 18:17:41,112 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-25 18:17:41,154 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2021-11-25 18:17:41,155 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2021-11-25 18:17:41,158 INFO L87 Difference]: Start difference. First operand has 30 states, 14 states have (on average 1.4285714285714286) internal successors, (20), 16 states have internal predecessors, (20), 12 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) Second operand has 2 states, 2 states have (on average 4.0) internal successors, (8), 2 states have internal predecessors, (8), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 1 states have call predecessors, (6), 1 states have call successors, (6) [2021-11-25 18:17:41,207 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-25 18:17:41,207 INFO L93 Difference]: Finished difference Result 49 states and 78 transitions. [2021-11-25 18:17:41,210 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2021-11-25 18:17:41,211 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 4.0) internal successors, (8), 2 states have internal predecessors, (8), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 1 states have call predecessors, (6), 1 states have call successors, (6) Word has length 26 [2021-11-25 18:17:41,217 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-25 18:17:41,226 INFO L225 Difference]: With dead ends: 49 [2021-11-25 18:17:41,227 INFO L226 Difference]: Without dead ends: 28 [2021-11-25 18:17:41,231 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 25 GetRequests, 25 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:17:41,243 INFO L933 BasicCegarLoop]: 38 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 3 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 38 SdHoareTripleChecker+Invalid, 4 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 3 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-11-25 18:17:41,247 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [0 Valid, 38 Invalid, 4 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 3 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-11-25 18:17:41,268 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 28 states. [2021-11-25 18:17:41,298 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 28 to 28. [2021-11-25 18:17:41,299 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 28 states, 13 states have (on average 1.2307692307692308) internal successors, (16), 15 states have internal predecessors, (16), 12 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2021-11-25 18:17:41,303 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 28 states to 28 states and 39 transitions. [2021-11-25 18:17:41,305 INFO L78 Accepts]: Start accepts. Automaton has 28 states and 39 transitions. Word has length 26 [2021-11-25 18:17:41,308 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-25 18:17:41,309 INFO L470 AbstractCegarLoop]: Abstraction has 28 states and 39 transitions. [2021-11-25 18:17:41,310 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 4.0) internal successors, (8), 2 states have internal predecessors, (8), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 1 states have call predecessors, (6), 1 states have call successors, (6) [2021-11-25 18:17:41,310 INFO L276 IsEmpty]: Start isEmpty. Operand 28 states and 39 transitions. [2021-11-25 18:17:41,315 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2021-11-25 18:17:41,316 INFO L506 BasicCegarLoop]: Found error trace [2021-11-25 18:17:41,317 INFO L514 BasicCegarLoop]: trace histogram [6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-25 18:17:41,357 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2021-11-25 18:17:41,541 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable0 [2021-11-25 18:17:41,542 INFO L402 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-25 18:17:41,542 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-25 18:17:41,543 INFO L85 PathProgramCache]: Analyzing trace with hash 1643993843, now seen corresponding path program 1 times [2021-11-25 18:17:41,543 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-25 18:17:41,543 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2052591766] [2021-11-25 18:17:41,543 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 18:17:41,544 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-25 18:17:41,567 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-11-25 18:17:41,568 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1199695117] [2021-11-25 18:17:41,568 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 18:17:41,568 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 18:17:41,569 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 [2021-11-25 18:17:41,570 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-25 18:17:41,584 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2021-11-25 18:17:41,664 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-25 18:17:41,669 INFO L263 TraceCheckSpWp]: Trace formula consists of 111 conjuncts, 7 conjunts are in the unsatisfiable core [2021-11-25 18:17:41,672 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-25 18:17:41,815 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 3 proven. 2 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2021-11-25 18:17:41,816 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-11-25 18:17:41,925 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 3 proven. 2 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2021-11-25 18:17:41,926 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-25 18:17:41,926 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2052591766] [2021-11-25 18:17:41,926 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-11-25 18:17:41,927 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1199695117] [2021-11-25 18:17:41,927 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1199695117] provided 0 perfect and 2 imperfect interpolant sequences [2021-11-25 18:17:41,927 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [121644515] [2021-11-25 18:17:41,949 INFO L159 IcfgInterpreter]: Started Sifa with 18 locations of interest [2021-11-25 18:17:41,950 INFO L166 IcfgInterpreter]: Building call graph [2021-11-25 18:17:41,955 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2021-11-25 18:17:41,961 INFO L176 IcfgInterpreter]: Starting interpretation [2021-11-25 18:17:41,961 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2021-11-25 18:17:43,365 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 59 for LOIs [2021-11-25 18:17:43,397 INFO L180 IcfgInterpreter]: Interpretation finished [2021-11-25 18:17:44,323 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSifa [121644515] provided 1 perfect and 0 imperfect interpolant sequences [2021-11-25 18:17:44,324 INFO L186 FreeRefinementEngine]: Found 1 perfect and 2 imperfect interpolant sequences. [2021-11-25 18:17:44,324 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [10] imperfect sequences [5, 5] total 14 [2021-11-25 18:17:44,324 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [587714387] [2021-11-25 18:17:44,325 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-11-25 18:17:44,325 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2021-11-25 18:17:44,325 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-25 18:17:44,326 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2021-11-25 18:17:44,326 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=58, Invalid=124, Unknown=0, NotChecked=0, Total=182 [2021-11-25 18:17:44,326 INFO L87 Difference]: Start difference. First operand 28 states and 39 transitions. Second operand has 11 states, 6 states have (on average 1.5) internal successors, (9), 5 states have internal predecessors, (9), 6 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:17:44,529 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-25 18:17:44,529 INFO L93 Difference]: Finished difference Result 38 states and 50 transitions. [2021-11-25 18:17:44,537 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2021-11-25 18:17:44,538 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 6 states have (on average 1.5) internal successors, (9), 5 states have internal predecessors, (9), 6 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 27 [2021-11-25 18:17:44,538 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-25 18:17:44,539 INFO L225 Difference]: With dead ends: 38 [2021-11-25 18:17:44,539 INFO L226 Difference]: Without dead ends: 30 [2021-11-25 18:17:44,540 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 79 GetRequests, 63 SyntacticMatches, 4 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 28 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=58, Invalid=124, Unknown=0, NotChecked=0, Total=182 [2021-11-25 18:17:44,541 INFO L933 BasicCegarLoop]: 24 mSDtfsCounter, 44 mSDsluCounter, 26 mSDsCounter, 0 mSdLazyCounter, 84 mSolverCounterSat, 37 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 53 SdHoareTripleChecker+Valid, 48 SdHoareTripleChecker+Invalid, 121 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 37 IncrementalHoareTripleChecker+Valid, 84 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2021-11-25 18:17:44,542 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [53 Valid, 48 Invalid, 121 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [37 Valid, 84 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2021-11-25 18:17:44,543 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 30 states. [2021-11-25 18:17:44,552 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 30 to 30. [2021-11-25 18:17:44,552 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 30 states, 15 states have (on average 1.2) internal successors, (18), 16 states have internal predecessors, (18), 12 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2021-11-25 18:17:44,554 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 30 states to 30 states and 41 transitions. [2021-11-25 18:17:44,554 INFO L78 Accepts]: Start accepts. Automaton has 30 states and 41 transitions. Word has length 27 [2021-11-25 18:17:44,554 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-25 18:17:44,554 INFO L470 AbstractCegarLoop]: Abstraction has 30 states and 41 transitions. [2021-11-25 18:17:44,555 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 6 states have (on average 1.5) internal successors, (9), 5 states have internal predecessors, (9), 6 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:17:44,555 INFO L276 IsEmpty]: Start isEmpty. Operand 30 states and 41 transitions. [2021-11-25 18:17:44,556 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2021-11-25 18:17:44,556 INFO L506 BasicCegarLoop]: Found error trace [2021-11-25 18:17:44,556 INFO L514 BasicCegarLoop]: trace histogram [6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-25 18:17:44,592 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2021-11-25 18:17:44,769 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 18:17:44,769 INFO L402 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-25 18:17:44,770 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-25 18:17:44,770 INFO L85 PathProgramCache]: Analyzing trace with hash -575116102, now seen corresponding path program 1 times [2021-11-25 18:17:44,770 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-25 18:17:44,771 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [202653063] [2021-11-25 18:17:44,771 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 18:17:44,771 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-25 18:17:44,800 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-11-25 18:17:44,809 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1047547334] [2021-11-25 18:17:44,809 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 18:17:44,809 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 18:17:44,809 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 [2021-11-25 18:17:44,810 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-25 18:17:44,841 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2021-11-25 18:17:44,872 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-25 18:17:44,874 INFO L263 TraceCheckSpWp]: Trace formula consists of 115 conjuncts, 14 conjunts are in the unsatisfiable core [2021-11-25 18:17:44,876 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-25 18:17:45,002 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 3 proven. 2 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2021-11-25 18:17:45,003 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-11-25 18:17:45,096 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2021-11-25 18:17:45,097 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-25 18:17:45,097 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [202653063] [2021-11-25 18:17:45,097 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-11-25 18:17:45,097 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1047547334] [2021-11-25 18:17:45,098 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1047547334] provided 1 perfect and 1 imperfect interpolant sequences [2021-11-25 18:17:45,098 INFO L186 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2021-11-25 18:17:45,099 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [8] total 9 [2021-11-25 18:17:45,100 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1898105944] [2021-11-25 18:17:45,100 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-11-25 18:17:45,101 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2021-11-25 18:17:45,101 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-25 18:17:45,102 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2021-11-25 18:17:45,102 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2021-11-25 18:17:45,103 INFO L87 Difference]: Start difference. First operand 30 states and 41 transitions. Second operand has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 1 states have call predecessors, (6), 1 states have call successors, (6) [2021-11-25 18:17:45,159 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-25 18:17:45,159 INFO L93 Difference]: Finished difference Result 36 states and 46 transitions. [2021-11-25 18:17:45,159 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2021-11-25 18:17:45,159 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 1 states have call predecessors, (6), 1 states have call successors, (6) Word has length 28 [2021-11-25 18:17:45,161 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-25 18:17:45,163 INFO L225 Difference]: With dead ends: 36 [2021-11-25 18:17:45,163 INFO L226 Difference]: Without dead ends: 34 [2021-11-25 18:17:45,164 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 55 GetRequests, 46 SyntacticMatches, 1 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=21, Invalid=69, Unknown=0, NotChecked=0, Total=90 [2021-11-25 18:17:45,170 INFO L933 BasicCegarLoop]: 31 mSDtfsCounter, 6 mSDsluCounter, 85 mSDsCounter, 0 mSdLazyCounter, 36 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 111 SdHoareTripleChecker+Invalid, 37 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 36 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-11-25 18:17:45,177 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [10 Valid, 111 Invalid, 37 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 36 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-11-25 18:17:45,178 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 34 states. [2021-11-25 18:17:45,194 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 34 to 34. [2021-11-25 18:17:45,195 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 34 states, 18 states have (on average 1.1666666666666667) internal successors, (21), 19 states have internal predecessors, (21), 12 states have call successors, (12), 3 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:17:45,198 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 34 states to 34 states and 44 transitions. [2021-11-25 18:17:45,198 INFO L78 Accepts]: Start accepts. Automaton has 34 states and 44 transitions. Word has length 28 [2021-11-25 18:17:45,199 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-25 18:17:45,199 INFO L470 AbstractCegarLoop]: Abstraction has 34 states and 44 transitions. [2021-11-25 18:17:45,200 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 1 states have call predecessors, (6), 1 states have call successors, (6) [2021-11-25 18:17:45,200 INFO L276 IsEmpty]: Start isEmpty. Operand 34 states and 44 transitions. [2021-11-25 18:17:45,202 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2021-11-25 18:17:45,202 INFO L506 BasicCegarLoop]: Found error trace [2021-11-25 18:17:45,202 INFO L514 BasicCegarLoop]: trace histogram [6, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-25 18:17:45,242 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2021-11-25 18:17:45,417 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 18:17:45,417 INFO L402 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-25 18:17:45,418 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-25 18:17:45,418 INFO L85 PathProgramCache]: Analyzing trace with hash -1810277145, now seen corresponding path program 1 times [2021-11-25 18:17:45,418 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-25 18:17:45,418 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1890069692] [2021-11-25 18:17:45,418 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 18:17:45,419 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-25 18:17:45,433 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-11-25 18:17:45,434 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [291094052] [2021-11-25 18:17:45,434 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 18:17:45,434 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 18:17:45,434 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 [2021-11-25 18:17:45,435 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-25 18:17:45,437 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2021-11-25 18:17:45,483 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-25 18:17:45,485 INFO L263 TraceCheckSpWp]: Trace formula consists of 124 conjuncts, 19 conjunts are in the unsatisfiable core [2021-11-25 18:17:45,487 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-25 18:17:45,692 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 5 proven. 5 refuted. 0 times theorem prover too weak. 22 trivial. 0 not checked. [2021-11-25 18:17:45,692 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-11-25 18:17:45,814 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2021-11-25 18:17:45,814 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-25 18:17:45,815 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1890069692] [2021-11-25 18:17:45,815 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-11-25 18:17:45,815 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [291094052] [2021-11-25 18:17:45,815 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [291094052] provided 1 perfect and 1 imperfect interpolant sequences [2021-11-25 18:17:45,816 INFO L186 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2021-11-25 18:17:45,816 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [8] total 9 [2021-11-25 18:17:45,816 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1777007310] [2021-11-25 18:17:45,816 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-11-25 18:17:45,817 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2021-11-25 18:17:45,817 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-25 18:17:45,817 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2021-11-25 18:17:45,818 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=19, Invalid=53, Unknown=0, NotChecked=0, Total=72 [2021-11-25 18:17:45,818 INFO L87 Difference]: Start difference. First operand 34 states and 44 transitions. Second operand has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2021-11-25 18:17:45,874 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-25 18:17:45,875 INFO L93 Difference]: Finished difference Result 47 states and 61 transitions. [2021-11-25 18:17:45,875 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2021-11-25 18:17:45,875 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 33 [2021-11-25 18:17:45,876 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-25 18:17:45,878 INFO L225 Difference]: With dead ends: 47 [2021-11-25 18:17:45,878 INFO L226 Difference]: Without dead ends: 45 [2021-11-25 18:17:45,879 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 65 GetRequests, 56 SyntacticMatches, 1 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=23, Invalid=67, Unknown=0, NotChecked=0, Total=90 [2021-11-25 18:17:45,884 INFO L933 BasicCegarLoop]: 39 mSDtfsCounter, 7 mSDsluCounter, 103 mSDsCounter, 0 mSdLazyCounter, 34 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 137 SdHoareTripleChecker+Invalid, 34 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 34 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-11-25 18:17:45,885 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [10 Valid, 137 Invalid, 34 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 34 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-11-25 18:17:45,887 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 45 states. [2021-11-25 18:17:45,904 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 45 to 44. [2021-11-25 18:17:45,905 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 44 states, 23 states have (on average 1.173913043478261) internal successors, (27), 24 states have internal predecessors, (27), 16 states have call successors, (16), 4 states have call predecessors, (16), 4 states have return successors, (15), 15 states have call predecessors, (15), 15 states have call successors, (15) [2021-11-25 18:17:45,907 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 44 states to 44 states and 58 transitions. [2021-11-25 18:17:45,908 INFO L78 Accepts]: Start accepts. Automaton has 44 states and 58 transitions. Word has length 33 [2021-11-25 18:17:45,908 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-25 18:17:45,908 INFO L470 AbstractCegarLoop]: Abstraction has 44 states and 58 transitions. [2021-11-25 18:17:45,908 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2021-11-25 18:17:45,909 INFO L276 IsEmpty]: Start isEmpty. Operand 44 states and 58 transitions. [2021-11-25 18:17:45,912 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2021-11-25 18:17:45,912 INFO L506 BasicCegarLoop]: Found error trace [2021-11-25 18:17:45,913 INFO L514 BasicCegarLoop]: trace histogram [6, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-25 18:17:45,946 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2021-11-25 18:17:46,129 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 18:17:46,129 INFO L402 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-25 18:17:46,130 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-25 18:17:46,130 INFO L85 PathProgramCache]: Analyzing trace with hash -1313498982, now seen corresponding path program 1 times [2021-11-25 18:17:46,130 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-25 18:17:46,130 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2019667012] [2021-11-25 18:17:46,131 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 18:17:46,131 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-25 18:17:46,147 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-11-25 18:17:46,147 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [160634422] [2021-11-25 18:17:46,147 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 18:17:46,147 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 18:17:46,148 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 [2021-11-25 18:17:46,148 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-25 18:17:46,182 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2021-11-25 18:17:46,242 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-25 18:17:46,244 INFO L263 TraceCheckSpWp]: Trace formula consists of 133 conjuncts, 14 conjunts are in the unsatisfiable core [2021-11-25 18:17:46,246 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-25 18:17:46,404 INFO L134 CoverageAnalysis]: Checked inductivity of 38 backedges. 7 proven. 2 refuted. 0 times theorem prover too weak. 29 trivial. 0 not checked. [2021-11-25 18:17:46,404 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-11-25 18:17:46,459 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-25 18:17:46,459 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2019667012] [2021-11-25 18:17:46,459 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-11-25 18:17:46,460 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [160634422] [2021-11-25 18:17:46,460 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [160634422] provided 0 perfect and 1 imperfect interpolant sequences [2021-11-25 18:17:46,460 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1547072898] [2021-11-25 18:17:46,464 INFO L159 IcfgInterpreter]: Started Sifa with 23 locations of interest [2021-11-25 18:17:46,465 INFO L166 IcfgInterpreter]: Building call graph [2021-11-25 18:17:46,465 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2021-11-25 18:17:46,467 INFO L176 IcfgInterpreter]: Starting interpretation [2021-11-25 18:17:46,467 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2021-11-25 18:17:47,546 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 38 for LOIs [2021-11-25 18:17:47,562 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 59 for LOIs [2021-11-25 18:17:47,580 INFO L180 IcfgInterpreter]: Interpretation finished [2021-11-25 18:17:49,028 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSifa [1547072898] provided 1 perfect and 0 imperfect interpolant sequences [2021-11-25 18:17:49,028 INFO L186 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2021-11-25 18:17:49,028 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [13] imperfect sequences [7] total 19 [2021-11-25 18:17:49,029 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1971968725] [2021-11-25 18:17:49,029 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-11-25 18:17:49,029 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2021-11-25 18:17:49,029 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-25 18:17:49,030 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2021-11-25 18:17:49,030 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=89, Invalid=291, Unknown=0, NotChecked=0, Total=380 [2021-11-25 18:17:49,030 INFO L87 Difference]: Start difference. First operand 44 states and 58 transitions. Second operand has 14 states, 9 states have (on average 1.3333333333333333) internal successors, (12), 7 states have internal predecessors, (12), 6 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 6 states have call predecessors, (8), 6 states have call successors, (8) [2021-11-25 18:17:49,373 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-25 18:17:49,373 INFO L93 Difference]: Finished difference Result 65 states and 81 transitions. [2021-11-25 18:17:49,374 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2021-11-25 18:17:49,374 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 9 states have (on average 1.3333333333333333) internal successors, (12), 7 states have internal predecessors, (12), 6 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 6 states have call predecessors, (8), 6 states have call successors, (8) Word has length 38 [2021-11-25 18:17:49,375 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-25 18:17:49,375 INFO L225 Difference]: With dead ends: 65 [2021-11-25 18:17:49,376 INFO L226 Difference]: Without dead ends: 63 [2021-11-25 18:17:49,376 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 80 GetRequests, 52 SyntacticMatches, 10 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 140 ImplicationChecksByTransitivity, 1.5s TimeCoverageRelationStatistics Valid=89, Invalid=291, Unknown=0, NotChecked=0, Total=380 [2021-11-25 18:17:49,377 INFO L933 BasicCegarLoop]: 19 mSDtfsCounter, 42 mSDsluCounter, 32 mSDsCounter, 0 mSdLazyCounter, 190 mSolverCounterSat, 48 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 53 SdHoareTripleChecker+Valid, 47 SdHoareTripleChecker+Invalid, 238 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 48 IncrementalHoareTripleChecker+Valid, 190 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2021-11-25 18:17:49,377 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [53 Valid, 47 Invalid, 238 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [48 Valid, 190 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2021-11-25 18:17:49,378 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 63 states. [2021-11-25 18:17:49,391 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 63 to 61. [2021-11-25 18:17:49,391 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 61 states, 33 states have (on average 1.121212121212121) internal successors, (37), 35 states have internal predecessors, (37), 20 states have call successors, (20), 7 states have call predecessors, (20), 7 states have return successors, (19), 18 states have call predecessors, (19), 19 states have call successors, (19) [2021-11-25 18:17:49,392 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 61 states to 61 states and 76 transitions. [2021-11-25 18:17:49,393 INFO L78 Accepts]: Start accepts. Automaton has 61 states and 76 transitions. Word has length 38 [2021-11-25 18:17:49,393 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-25 18:17:49,393 INFO L470 AbstractCegarLoop]: Abstraction has 61 states and 76 transitions. [2021-11-25 18:17:49,393 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 9 states have (on average 1.3333333333333333) internal successors, (12), 7 states have internal predecessors, (12), 6 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 6 states have call predecessors, (8), 6 states have call successors, (8) [2021-11-25 18:17:49,394 INFO L276 IsEmpty]: Start isEmpty. Operand 61 states and 76 transitions. [2021-11-25 18:17:49,395 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 53 [2021-11-25 18:17:49,395 INFO L506 BasicCegarLoop]: Found error trace [2021-11-25 18:17:49,395 INFO L514 BasicCegarLoop]: trace histogram [6, 5, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-25 18:17:49,428 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2021-11-25 18:17:49,617 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 18:17:49,618 INFO L402 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-25 18:17:49,618 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-25 18:17:49,618 INFO L85 PathProgramCache]: Analyzing trace with hash 434944611, now seen corresponding path program 1 times [2021-11-25 18:17:49,618 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-25 18:17:49,618 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [932847365] [2021-11-25 18:17:49,619 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 18:17:49,619 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-25 18:17:49,635 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-11-25 18:17:49,635 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1036643566] [2021-11-25 18:17:49,635 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 18:17:49,635 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 18:17:49,635 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 [2021-11-25 18:17:49,636 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-25 18:17:49,681 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2021-11-25 18:17:49,743 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-25 18:17:49,746 INFO L263 TraceCheckSpWp]: Trace formula consists of 169 conjuncts, 9 conjunts are in the unsatisfiable core [2021-11-25 18:17:49,748 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-25 18:17:49,882 INFO L134 CoverageAnalysis]: Checked inductivity of 64 backedges. 10 proven. 5 refuted. 0 times theorem prover too weak. 49 trivial. 0 not checked. [2021-11-25 18:17:49,882 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-11-25 18:17:50,067 INFO L134 CoverageAnalysis]: Checked inductivity of 64 backedges. 10 proven. 5 refuted. 0 times theorem prover too weak. 49 trivial. 0 not checked. [2021-11-25 18:17:50,068 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-25 18:17:50,068 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [932847365] [2021-11-25 18:17:50,068 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-11-25 18:17:50,068 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1036643566] [2021-11-25 18:17:50,069 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1036643566] provided 0 perfect and 2 imperfect interpolant sequences [2021-11-25 18:17:50,069 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1943900904] [2021-11-25 18:17:50,072 INFO L159 IcfgInterpreter]: Started Sifa with 27 locations of interest [2021-11-25 18:17:50,072 INFO L166 IcfgInterpreter]: Building call graph [2021-11-25 18:17:50,073 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2021-11-25 18:17:50,073 INFO L176 IcfgInterpreter]: Starting interpretation [2021-11-25 18:17:50,073 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2021-11-25 18:18:06,877 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 8 for LOIs [2021-11-25 18:18:06,883 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 59 for LOIs [2021-11-25 18:18:06,922 INFO L180 IcfgInterpreter]: Interpretation finished [2021-11-25 18:18:09,827 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1775#(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:18:09,827 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2021-11-25 18:18:09,827 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-11-25 18:18:09,827 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 7 [2021-11-25 18:18:09,827 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1684990979] [2021-11-25 18:18:09,827 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-11-25 18:18:09,828 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2021-11-25 18:18:09,828 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-25 18:18:09,828 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2021-11-25 18:18:09,829 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=118, Invalid=434, Unknown=0, NotChecked=0, Total=552 [2021-11-25 18:18:09,829 INFO L87 Difference]: Start difference. First operand 61 states and 76 transitions. Second operand has 7 states, 6 states have (on average 3.0) internal successors, (18), 6 states have internal predecessors, (18), 5 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (10), 4 states have call predecessors, (10), 4 states have call successors, (10) [2021-11-25 18:18:10,018 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-25 18:18:10,019 INFO L93 Difference]: Finished difference Result 103 states and 142 transitions. [2021-11-25 18:18:10,019 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2021-11-25 18:18:10,019 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 6 states have (on average 3.0) internal successors, (18), 6 states have internal predecessors, (18), 5 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (10), 4 states have call predecessors, (10), 4 states have call successors, (10) Word has length 52 [2021-11-25 18:18:10,020 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-25 18:18:10,021 INFO L225 Difference]: With dead ends: 103 [2021-11-25 18:18:10,021 INFO L226 Difference]: Without dead ends: 95 [2021-11-25 18:18:10,022 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 158 GetRequests, 126 SyntacticMatches, 6 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 175 ImplicationChecksByTransitivity, 3.0s TimeCoverageRelationStatistics Valid=153, Invalid=603, Unknown=0, NotChecked=0, Total=756 [2021-11-25 18:18:10,023 INFO L933 BasicCegarLoop]: 52 mSDtfsCounter, 28 mSDsluCounter, 192 mSDsCounter, 0 mSdLazyCounter, 81 mSolverCounterSat, 53 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 33 SdHoareTripleChecker+Valid, 239 SdHoareTripleChecker+Invalid, 134 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 53 IncrementalHoareTripleChecker+Valid, 81 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2021-11-25 18:18:10,023 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [33 Valid, 239 Invalid, 134 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [53 Valid, 81 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2021-11-25 18:18:10,024 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 95 states. [2021-11-25 18:18:10,042 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 95 to 86. [2021-11-25 18:18:10,043 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 86 states, 46 states have (on average 1.1956521739130435) internal successors, (55), 47 states have internal predecessors, (55), 32 states have call successors, (32), 7 states have call predecessors, (32), 7 states have return successors, (31), 31 states have call predecessors, (31), 31 states have call successors, (31) [2021-11-25 18:18:10,044 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 86 states to 86 states and 118 transitions. [2021-11-25 18:18:10,045 INFO L78 Accepts]: Start accepts. Automaton has 86 states and 118 transitions. Word has length 52 [2021-11-25 18:18:10,045 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-25 18:18:10,045 INFO L470 AbstractCegarLoop]: Abstraction has 86 states and 118 transitions. [2021-11-25 18:18:10,045 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 6 states have (on average 3.0) internal successors, (18), 6 states have internal predecessors, (18), 5 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (10), 4 states have call predecessors, (10), 4 states have call successors, (10) [2021-11-25 18:18:10,046 INFO L276 IsEmpty]: Start isEmpty. Operand 86 states and 118 transitions. [2021-11-25 18:18:10,047 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 59 [2021-11-25 18:18:10,047 INFO L506 BasicCegarLoop]: Found error trace [2021-11-25 18:18:10,047 INFO L514 BasicCegarLoop]: trace histogram [6, 6, 5, 5, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-25 18:18:10,076 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2021-11-25 18:18:10,261 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 7 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable5 [2021-11-25 18:18:10,261 INFO L402 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-25 18:18:10,262 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-25 18:18:10,262 INFO L85 PathProgramCache]: Analyzing trace with hash -243308457, now seen corresponding path program 1 times [2021-11-25 18:18:10,262 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-25 18:18:10,262 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1893489618] [2021-11-25 18:18:10,262 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 18:18:10,262 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-25 18:18:10,273 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-11-25 18:18:10,274 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [542697659] [2021-11-25 18:18:10,274 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 18:18:10,274 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 18:18:10,274 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 [2021-11-25 18:18:10,275 INFO L229 MonitoredProcess]: Starting monitored process 8 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-25 18:18:10,277 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2021-11-25 18:18:10,329 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-25 18:18:10,330 INFO L263 TraceCheckSpWp]: Trace formula consists of 182 conjuncts, 14 conjunts are in the unsatisfiable core [2021-11-25 18:18:10,333 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-25 18:18:10,469 INFO L134 CoverageAnalysis]: Checked inductivity of 85 backedges. 20 proven. 7 refuted. 0 times theorem prover too weak. 58 trivial. 0 not checked. [2021-11-25 18:18:10,469 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-11-25 18:18:10,627 INFO L134 CoverageAnalysis]: Checked inductivity of 85 backedges. 20 proven. 7 refuted. 0 times theorem prover too weak. 58 trivial. 0 not checked. [2021-11-25 18:18:10,627 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-25 18:18:10,627 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1893489618] [2021-11-25 18:18:10,627 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-11-25 18:18:10,627 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [542697659] [2021-11-25 18:18:10,628 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [542697659] provided 0 perfect and 2 imperfect interpolant sequences [2021-11-25 18:18:10,628 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1798601164] [2021-11-25 18:18:10,632 INFO L159 IcfgInterpreter]: Started Sifa with 26 locations of interest [2021-11-25 18:18:10,632 INFO L166 IcfgInterpreter]: Building call graph [2021-11-25 18:18:10,632 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2021-11-25 18:18:10,633 INFO L176 IcfgInterpreter]: Starting interpretation [2021-11-25 18:18:10,633 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2021-11-25 18:18:23,734 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 38 for LOIs [2021-11-25 18:18:23,748 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 59 for LOIs [2021-11-25 18:18:23,763 INFO L180 IcfgInterpreter]: Interpretation finished [2021-11-25 18:18:27,742 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSifa [1798601164] provided 1 perfect and 0 imperfect interpolant sequences [2021-11-25 18:18:27,742 INFO L186 FreeRefinementEngine]: Found 1 perfect and 2 imperfect interpolant sequences. [2021-11-25 18:18:27,742 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [16] imperfect sequences [8, 8] total 24 [2021-11-25 18:18:27,742 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [488364500] [2021-11-25 18:18:27,743 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-11-25 18:18:27,743 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2021-11-25 18:18:27,743 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-25 18:18:27,744 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2021-11-25 18:18:27,744 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=118, Invalid=434, Unknown=0, NotChecked=0, Total=552 [2021-11-25 18:18:27,744 INFO L87 Difference]: Start difference. First operand 86 states and 118 transitions. Second operand has 17 states, 11 states have (on average 1.2727272727272727) internal successors, (14), 10 states have internal predecessors, (14), 6 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (10), 7 states have call predecessors, (10), 6 states have call successors, (10) [2021-11-25 18:18:29,091 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-25 18:18:29,091 INFO L93 Difference]: Finished difference Result 105 states and 140 transitions. [2021-11-25 18:18:29,092 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2021-11-25 18:18:29,092 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 11 states have (on average 1.2727272727272727) internal successors, (14), 10 states have internal predecessors, (14), 6 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (10), 7 states have call predecessors, (10), 6 states have call successors, (10) Word has length 58 [2021-11-25 18:18:29,093 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-25 18:18:29,094 INFO L225 Difference]: With dead ends: 105 [2021-11-25 18:18:29,094 INFO L226 Difference]: Without dead ends: 103 [2021-11-25 18:18:29,095 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 175 GetRequests, 133 SyntacticMatches, 17 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 290 ImplicationChecksByTransitivity, 4.8s TimeCoverageRelationStatistics Valid=162, Invalid=540, Unknown=0, NotChecked=0, Total=702 [2021-11-25 18:18:29,096 INFO L933 BasicCegarLoop]: 19 mSDtfsCounter, 74 mSDsluCounter, 35 mSDsCounter, 0 mSdLazyCounter, 200 mSolverCounterSat, 79 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 84 SdHoareTripleChecker+Valid, 50 SdHoareTripleChecker+Invalid, 279 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 79 IncrementalHoareTripleChecker+Valid, 200 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2021-11-25 18:18:29,096 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [84 Valid, 50 Invalid, 279 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [79 Valid, 200 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2021-11-25 18:18:29,097 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 103 states. [2021-11-25 18:18:29,116 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 103 to 103. [2021-11-25 18:18:29,116 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 103 states, 57 states have (on average 1.1754385964912282) internal successors, (67), 58 states have internal predecessors, (67), 36 states have call successors, (36), 9 states have call predecessors, (36), 9 states have return successors, (35), 35 states have call predecessors, (35), 35 states have call successors, (35) [2021-11-25 18:18:29,118 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 103 states to 103 states and 138 transitions. [2021-11-25 18:18:29,119 INFO L78 Accepts]: Start accepts. Automaton has 103 states and 138 transitions. Word has length 58 [2021-11-25 18:18:29,119 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-25 18:18:29,119 INFO L470 AbstractCegarLoop]: Abstraction has 103 states and 138 transitions. [2021-11-25 18:18:29,120 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 11 states have (on average 1.2727272727272727) internal successors, (14), 10 states have internal predecessors, (14), 6 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (10), 7 states have call predecessors, (10), 6 states have call successors, (10) [2021-11-25 18:18:29,120 INFO L276 IsEmpty]: Start isEmpty. Operand 103 states and 138 transitions. [2021-11-25 18:18:29,121 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 61 [2021-11-25 18:18:29,121 INFO L506 BasicCegarLoop]: Found error trace [2021-11-25 18:18:29,121 INFO L514 BasicCegarLoop]: trace histogram [7, 6, 6, 6, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-25 18:18:29,144 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2021-11-25 18:18:29,325 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 8 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable6 [2021-11-25 18:18:29,325 INFO L402 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-25 18:18:29,326 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-25 18:18:29,326 INFO L85 PathProgramCache]: Analyzing trace with hash -331691367, now seen corresponding path program 1 times [2021-11-25 18:18:29,326 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-25 18:18:29,326 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2117299541] [2021-11-25 18:18:29,326 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 18:18:29,326 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-25 18:18:29,336 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-11-25 18:18:29,336 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [612587525] [2021-11-25 18:18:29,336 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 18:18:29,336 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 18:18:29,337 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 [2021-11-25 18:18:29,337 INFO L229 MonitoredProcess]: Starting monitored process 9 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-25 18:18:29,339 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2021-11-25 18:18:29,374 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-25 18:18:29,375 INFO L263 TraceCheckSpWp]: Trace formula consists of 175 conjuncts, 11 conjunts are in the unsatisfiable core [2021-11-25 18:18:29,377 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-25 18:18:29,488 INFO L134 CoverageAnalysis]: Checked inductivity of 106 backedges. 21 proven. 10 refuted. 0 times theorem prover too weak. 75 trivial. 0 not checked. [2021-11-25 18:18:29,489 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-11-25 18:18:29,634 INFO L134 CoverageAnalysis]: Checked inductivity of 106 backedges. 21 proven. 10 refuted. 0 times theorem prover too weak. 75 trivial. 0 not checked. [2021-11-25 18:18:29,634 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-25 18:18:29,635 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2117299541] [2021-11-25 18:18:29,635 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-11-25 18:18:29,635 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [612587525] [2021-11-25 18:18:29,635 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [612587525] provided 0 perfect and 2 imperfect interpolant sequences [2021-11-25 18:18:29,635 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1506612778] [2021-11-25 18:18:29,637 INFO L159 IcfgInterpreter]: Started Sifa with 25 locations of interest [2021-11-25 18:18:29,638 INFO L166 IcfgInterpreter]: Building call graph [2021-11-25 18:18:29,638 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2021-11-25 18:18:29,638 INFO L176 IcfgInterpreter]: Starting interpretation [2021-11-25 18:18:29,638 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2021-11-25 18:18:39,470 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 44 for LOIs [2021-11-25 18:18:39,479 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 59 for LOIs [2021-11-25 18:18:39,492 INFO L180 IcfgInterpreter]: Interpretation finished [2021-11-25 18:18:43,050 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '3154#(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:18:43,050 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2021-11-25 18:18:43,050 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-11-25 18:18:43,050 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 6] total 9 [2021-11-25 18:18:43,050 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [872629581] [2021-11-25 18:18:43,050 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-11-25 18:18:43,051 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2021-11-25 18:18:43,051 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-25 18:18:43,051 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2021-11-25 18:18:43,052 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=120, Invalid=582, Unknown=0, NotChecked=0, Total=702 [2021-11-25 18:18:43,052 INFO L87 Difference]: Start difference. First operand 103 states and 138 transitions. Second operand has 9 states, 9 states have (on average 2.4444444444444446) internal successors, (22), 8 states have internal predecessors, (22), 2 states have call successors, (14), 3 states have call predecessors, (14), 2 states have return successors, (12), 2 states have call predecessors, (12), 2 states have call successors, (12) [2021-11-25 18:18:43,222 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-25 18:18:43,222 INFO L93 Difference]: Finished difference Result 117 states and 153 transitions. [2021-11-25 18:18:43,222 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2021-11-25 18:18:43,223 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 2.4444444444444446) internal successors, (22), 8 states have internal predecessors, (22), 2 states have call successors, (14), 3 states have call predecessors, (14), 2 states have return successors, (12), 2 states have call predecessors, (12), 2 states have call successors, (12) Word has length 60 [2021-11-25 18:18:43,229 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-25 18:18:43,235 INFO L225 Difference]: With dead ends: 117 [2021-11-25 18:18:43,235 INFO L226 Difference]: Without dead ends: 115 [2021-11-25 18:18:43,236 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 180 GetRequests, 143 SyntacticMatches, 10 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 400 ImplicationChecksByTransitivity, 3.6s TimeCoverageRelationStatistics Valid=136, Invalid=676, Unknown=0, NotChecked=0, Total=812 [2021-11-25 18:18:43,237 INFO L933 BasicCegarLoop]: 27 mSDtfsCounter, 18 mSDsluCounter, 71 mSDsCounter, 0 mSdLazyCounter, 72 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 20 SdHoareTripleChecker+Valid, 93 SdHoareTripleChecker+Invalid, 75 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 72 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2021-11-25 18:18:43,237 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [20 Valid, 93 Invalid, 75 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 72 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2021-11-25 18:18:43,238 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 115 states. [2021-11-25 18:18:43,277 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 115 to 115. [2021-11-25 18:18:43,279 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 115 states, 64 states have (on average 1.15625) internal successors, (74), 66 states have internal predecessors, (74), 39 states have call successors, (39), 11 states have call predecessors, (39), 11 states have return successors, (38), 37 states have call predecessors, (38), 38 states have call successors, (38) [2021-11-25 18:18:43,285 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 115 states to 115 states and 151 transitions. [2021-11-25 18:18:43,285 INFO L78 Accepts]: Start accepts. Automaton has 115 states and 151 transitions. Word has length 60 [2021-11-25 18:18:43,286 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-25 18:18:43,286 INFO L470 AbstractCegarLoop]: Abstraction has 115 states and 151 transitions. [2021-11-25 18:18:43,287 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 2.4444444444444446) internal successors, (22), 8 states have internal predecessors, (22), 2 states have call successors, (14), 3 states have call predecessors, (14), 2 states have return successors, (12), 2 states have call predecessors, (12), 2 states have call successors, (12) [2021-11-25 18:18:43,287 INFO L276 IsEmpty]: Start isEmpty. Operand 115 states and 151 transitions. [2021-11-25 18:18:43,293 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 66 [2021-11-25 18:18:43,293 INFO L506 BasicCegarLoop]: Found error trace [2021-11-25 18:18:43,294 INFO L514 BasicCegarLoop]: trace histogram [8, 7, 7, 6, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-25 18:18:43,329 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2021-11-25 18:18:43,509 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,9 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 18:18:43,509 INFO L402 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-25 18:18:43,509 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-25 18:18:43,510 INFO L85 PathProgramCache]: Analyzing trace with hash 1984692712, now seen corresponding path program 2 times [2021-11-25 18:18:43,510 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-25 18:18:43,510 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1752298726] [2021-11-25 18:18:43,510 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 18:18:43,510 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-25 18:18:43,520 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-11-25 18:18:43,521 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1875545706] [2021-11-25 18:18:43,525 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2021-11-25 18:18:43,525 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 18:18:43,525 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 [2021-11-25 18:18:43,526 INFO L229 MonitoredProcess]: Starting monitored process 10 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-25 18:18:43,548 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2021-11-25 18:18:43,578 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2021-11-25 18:18:43,578 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-11-25 18:18:43,579 INFO L263 TraceCheckSpWp]: Trace formula consists of 113 conjuncts, 11 conjunts are in the unsatisfiable core [2021-11-25 18:18:43,581 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-25 18:18:43,756 INFO L134 CoverageAnalysis]: Checked inductivity of 133 backedges. 27 proven. 10 refuted. 0 times theorem prover too weak. 96 trivial. 0 not checked. [2021-11-25 18:18:43,756 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-11-25 18:18:43,903 INFO L134 CoverageAnalysis]: Checked inductivity of 133 backedges. 27 proven. 10 refuted. 0 times theorem prover too weak. 96 trivial. 0 not checked. [2021-11-25 18:18:43,903 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-25 18:18:43,903 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1752298726] [2021-11-25 18:18:43,903 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-11-25 18:18:43,904 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1875545706] [2021-11-25 18:18:43,904 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1875545706] provided 0 perfect and 2 imperfect interpolant sequences [2021-11-25 18:18:43,904 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [121260059] [2021-11-25 18:18:43,906 INFO L159 IcfgInterpreter]: Started Sifa with 25 locations of interest [2021-11-25 18:18:43,907 INFO L166 IcfgInterpreter]: Building call graph [2021-11-25 18:18:43,907 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2021-11-25 18:18:43,907 INFO L176 IcfgInterpreter]: Starting interpretation [2021-11-25 18:18:43,908 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2021-11-25 18:18:49,754 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 39 for LOIs [2021-11-25 18:18:49,833 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 59 for LOIs [2021-11-25 18:18:49,846 INFO L180 IcfgInterpreter]: Interpretation finished [2021-11-25 18:18:53,095 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '3927#(and (<= |#NULL.offset| 0) (= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond) (= __VERIFIER_assert_~cond 0) (<= 0 |#NULL.offset|) (<= 0 |#StackHeapBarrier|) (= |#NULL.base| 0))' at error location [2021-11-25 18:18:53,095 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2021-11-25 18:18:53,095 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-11-25 18:18:53,095 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 6] total 9 [2021-11-25 18:18:53,096 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2103597252] [2021-11-25 18:18:53,096 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-11-25 18:18:53,096 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2021-11-25 18:18:53,097 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-25 18:18:53,097 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2021-11-25 18:18:53,097 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=123, Invalid=579, Unknown=0, NotChecked=0, Total=702 [2021-11-25 18:18:53,098 INFO L87 Difference]: Start difference. First operand 115 states and 151 transitions. Second operand has 9 states, 9 states have (on average 2.4444444444444446) internal successors, (22), 8 states have internal predecessors, (22), 2 states have call successors, (15), 3 states have call predecessors, (15), 2 states have return successors, (13), 2 states have call predecessors, (13), 2 states have call successors, (13) [2021-11-25 18:18:53,314 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-25 18:18:53,314 INFO L93 Difference]: Finished difference Result 122 states and 158 transitions. [2021-11-25 18:18:53,323 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2021-11-25 18:18:53,323 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 2.4444444444444446) internal successors, (22), 8 states have internal predecessors, (22), 2 states have call successors, (15), 3 states have call predecessors, (15), 2 states have return successors, (13), 2 states have call predecessors, (13), 2 states have call successors, (13) Word has length 65 [2021-11-25 18:18:53,324 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-25 18:18:53,325 INFO L225 Difference]: With dead ends: 122 [2021-11-25 18:18:53,325 INFO L226 Difference]: Without dead ends: 120 [2021-11-25 18:18:53,326 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 195 GetRequests, 157 SyntacticMatches, 11 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 432 ImplicationChecksByTransitivity, 3.3s TimeCoverageRelationStatistics Valid=139, Invalid=673, Unknown=0, NotChecked=0, Total=812 [2021-11-25 18:18:53,327 INFO L933 BasicCegarLoop]: 27 mSDtfsCounter, 17 mSDsluCounter, 110 mSDsCounter, 0 mSdLazyCounter, 120 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 19 SdHoareTripleChecker+Valid, 128 SdHoareTripleChecker+Invalid, 123 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 120 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2021-11-25 18:18:53,327 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [19 Valid, 128 Invalid, 123 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 120 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2021-11-25 18:18:53,328 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 120 states. [2021-11-25 18:18:53,355 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 120 to 120. [2021-11-25 18:18:53,356 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 120 states, 67 states have (on average 1.1492537313432836) internal successors, (77), 69 states have internal predecessors, (77), 40 states have call successors, (40), 12 states have call predecessors, (40), 12 states have return successors, (39), 38 states have call predecessors, (39), 39 states have call successors, (39) [2021-11-25 18:18:53,357 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 120 states to 120 states and 156 transitions. [2021-11-25 18:18:53,357 INFO L78 Accepts]: Start accepts. Automaton has 120 states and 156 transitions. Word has length 65 [2021-11-25 18:18:53,358 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-25 18:18:53,358 INFO L470 AbstractCegarLoop]: Abstraction has 120 states and 156 transitions. [2021-11-25 18:18:53,359 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 2.4444444444444446) internal successors, (22), 8 states have internal predecessors, (22), 2 states have call successors, (15), 3 states have call predecessors, (15), 2 states have return successors, (13), 2 states have call predecessors, (13), 2 states have call successors, (13) [2021-11-25 18:18:53,359 INFO L276 IsEmpty]: Start isEmpty. Operand 120 states and 156 transitions. [2021-11-25 18:18:53,360 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 75 [2021-11-25 18:18:53,361 INFO L506 BasicCegarLoop]: Found error trace [2021-11-25 18:18:53,361 INFO L514 BasicCegarLoop]: trace histogram [9, 8, 8, 6, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-25 18:18:53,389 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2021-11-25 18:18:53,569 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,10 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 18:18:53,569 INFO L402 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-25 18:18:53,570 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-25 18:18:53,570 INFO L85 PathProgramCache]: Analyzing trace with hash -2003369438, now seen corresponding path program 1 times [2021-11-25 18:18:53,570 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-25 18:18:53,570 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [901431342] [2021-11-25 18:18:53,570 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 18:18:53,570 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-25 18:18:53,581 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-11-25 18:18:53,582 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [584511590] [2021-11-25 18:18:53,582 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 18:18:53,582 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 18:18:53,582 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 [2021-11-25 18:18:53,585 INFO L229 MonitoredProcess]: Starting monitored process 11 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-25 18:18:53,587 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2021-11-25 18:18:53,634 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-25 18:18:53,635 INFO L263 TraceCheckSpWp]: Trace formula consists of 211 conjuncts, 39 conjunts are in the unsatisfiable core [2021-11-25 18:18:53,637 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-25 18:18:54,163 INFO L134 CoverageAnalysis]: Checked inductivity of 166 backedges. 16 proven. 8 refuted. 0 times theorem prover too weak. 142 trivial. 0 not checked. [2021-11-25 18:18:54,163 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-11-25 18:18:54,768 INFO L134 CoverageAnalysis]: Checked inductivity of 166 backedges. 16 proven. 8 refuted. 0 times theorem prover too weak. 142 trivial. 0 not checked. [2021-11-25 18:18:54,769 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-25 18:18:54,769 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [901431342] [2021-11-25 18:18:54,769 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-11-25 18:18:54,769 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [584511590] [2021-11-25 18:18:54,770 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [584511590] provided 0 perfect and 2 imperfect interpolant sequences [2021-11-25 18:18:54,770 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1128049132] [2021-11-25 18:18:54,772 INFO L159 IcfgInterpreter]: Started Sifa with 27 locations of interest [2021-11-25 18:18:54,773 INFO L166 IcfgInterpreter]: Building call graph [2021-11-25 18:18:54,773 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2021-11-25 18:18:54,774 INFO L176 IcfgInterpreter]: Starting interpretation [2021-11-25 18:18:54,774 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2021-11-25 18:18:59,125 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2021-11-25 18:18:59,128 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 59 for LOIs [2021-11-25 18:18:59,142 INFO L180 IcfgInterpreter]: Interpretation finished [2021-11-25 18:19:30,775 WARN L227 SmtUtils]: Spent 27.84s on a formula simplification. DAG size of input: 185 DAG size of output: 156 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2021-11-25 18:19:48,217 WARN L227 SmtUtils]: Spent 16.71s on a formula simplification. DAG size of input: 96 DAG size of output: 88 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2021-11-25 18:19:59,933 WARN L227 SmtUtils]: Spent 7.57s on a formula simplification that was a NOOP. DAG size: 82 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2021-11-25 18:20:26,097 WARN L227 SmtUtils]: Spent 25.31s on a formula simplification. DAG size of input: 83 DAG size of output: 81 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2021-11-25 18:20:55,099 WARN L227 SmtUtils]: Spent 26.19s on a formula simplification. DAG size of input: 183 DAG size of output: 92 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2021-11-25 18:20:55,100 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '4775#(and (= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond) (= __VERIFIER_assert_~cond 0))' at error location [2021-11-25 18:20:55,100 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2021-11-25 18:20:55,100 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-11-25 18:20:55,101 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 16 [2021-11-25 18:20:55,101 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [65988588] [2021-11-25 18:20:55,101 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-11-25 18:20:55,102 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2021-11-25 18:20:55,102 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-25 18:20:55,102 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2021-11-25 18:20:55,103 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=179, Invalid=1153, Unknown=0, NotChecked=0, Total=1332 [2021-11-25 18:20:55,103 INFO L87 Difference]: Start difference. First operand 120 states and 156 transitions. Second operand has 16 states, 14 states have (on average 2.0714285714285716) internal successors, (29), 15 states have internal predecessors, (29), 9 states have call successors, (26), 2 states have call predecessors, (26), 1 states have return successors, (24), 7 states have call predecessors, (24), 7 states have call successors, (24) [2021-11-25 18:21:04,839 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-25 18:21:04,839 INFO L93 Difference]: Finished difference Result 203 states and 282 transitions. [2021-11-25 18:21:04,840 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2021-11-25 18:21:04,840 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 14 states have (on average 2.0714285714285716) internal successors, (29), 15 states have internal predecessors, (29), 9 states have call successors, (26), 2 states have call predecessors, (26), 1 states have return successors, (24), 7 states have call predecessors, (24), 7 states have call successors, (24) Word has length 74 [2021-11-25 18:21:04,841 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-25 18:21:04,843 INFO L225 Difference]: With dead ends: 203 [2021-11-25 18:21:04,843 INFO L226 Difference]: Without dead ends: 201 [2021-11-25 18:21:04,845 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 239 GetRequests, 183 SyntacticMatches, 2 SemanticMatches, 54 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 858 ImplicationChecksByTransitivity, 121.2s TimeCoverageRelationStatistics Valid=412, Invalid=2668, Unknown=0, NotChecked=0, Total=3080 [2021-11-25 18:21:04,846 INFO L933 BasicCegarLoop]: 72 mSDtfsCounter, 65 mSDsluCounter, 364 mSDsCounter, 0 mSdLazyCounter, 493 mSolverCounterSat, 200 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 69 SdHoareTripleChecker+Valid, 426 SdHoareTripleChecker+Invalid, 693 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 200 IncrementalHoareTripleChecker+Valid, 493 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 4.8s IncrementalHoareTripleChecker+Time [2021-11-25 18:21:04,846 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [69 Valid, 426 Invalid, 693 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [200 Valid, 493 Invalid, 0 Unknown, 0 Unchecked, 4.8s Time] [2021-11-25 18:21:04,847 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 201 states. [2021-11-25 18:21:04,893 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 201 to 191. [2021-11-25 18:21:04,894 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 191 states, 102 states have (on average 1.2156862745098038) internal successors, (124), 104 states have internal predecessors, (124), 73 states have call successors, (73), 15 states have call predecessors, (73), 15 states have return successors, (72), 71 states have call predecessors, (72), 72 states have call successors, (72) [2021-11-25 18:21:04,897 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 191 states to 191 states and 269 transitions. [2021-11-25 18:21:04,897 INFO L78 Accepts]: Start accepts. Automaton has 191 states and 269 transitions. Word has length 74 [2021-11-25 18:21:04,897 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-25 18:21:04,898 INFO L470 AbstractCegarLoop]: Abstraction has 191 states and 269 transitions. [2021-11-25 18:21:04,898 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 14 states have (on average 2.0714285714285716) internal successors, (29), 15 states have internal predecessors, (29), 9 states have call successors, (26), 2 states have call predecessors, (26), 1 states have return successors, (24), 7 states have call predecessors, (24), 7 states have call successors, (24) [2021-11-25 18:21:04,898 INFO L276 IsEmpty]: Start isEmpty. Operand 191 states and 269 transitions. [2021-11-25 18:21:04,899 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 80 [2021-11-25 18:21:04,899 INFO L506 BasicCegarLoop]: Found error trace [2021-11-25 18:21:04,900 INFO L514 BasicCegarLoop]: trace histogram [10, 9, 9, 6, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-25 18:21:04,926 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2021-11-25 18:21:05,113 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2021-11-25 18:21:05,113 INFO L402 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-25 18:21:05,114 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-25 18:21:05,114 INFO L85 PathProgramCache]: Analyzing trace with hash -134461569, now seen corresponding path program 1 times [2021-11-25 18:21:05,114 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-25 18:21:05,114 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [252898875] [2021-11-25 18:21:05,114 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 18:21:05,114 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-25 18:21:05,131 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-11-25 18:21:05,139 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [752267478] [2021-11-25 18:21:05,140 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 18:21:05,140 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 18:21:05,140 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 [2021-11-25 18:21:05,141 INFO L229 MonitoredProcess]: Starting monitored process 12 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-25 18:21:05,157 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2021-11-25 18:21:05,205 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-25 18:21:05,207 INFO L263 TraceCheckSpWp]: Trace formula consists of 220 conjuncts, 30 conjunts are in the unsatisfiable core [2021-11-25 18:21:05,210 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-25 18:21:05,572 INFO L134 CoverageAnalysis]: Checked inductivity of 200 backedges. 35 proven. 15 refuted. 0 times theorem prover too weak. 150 trivial. 0 not checked. [2021-11-25 18:21:05,572 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-11-25 18:21:05,816 INFO L134 CoverageAnalysis]: Checked inductivity of 200 backedges. 39 proven. 7 refuted. 0 times theorem prover too weak. 154 trivial. 0 not checked. [2021-11-25 18:21:05,817 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-25 18:21:05,817 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [252898875] [2021-11-25 18:21:05,817 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-11-25 18:21:05,817 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [752267478] [2021-11-25 18:21:05,817 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [752267478] provided 0 perfect and 2 imperfect interpolant sequences [2021-11-25 18:21:05,817 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [453627430] [2021-11-25 18:21:05,819 INFO L159 IcfgInterpreter]: Started Sifa with 28 locations of interest [2021-11-25 18:21:05,819 INFO L166 IcfgInterpreter]: Building call graph [2021-11-25 18:21:05,820 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2021-11-25 18:21:05,820 INFO L176 IcfgInterpreter]: Starting interpretation [2021-11-25 18:21:05,820 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2021-11-25 18:21:09,923 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2021-11-25 18:21:09,926 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 59 for LOIs [2021-11-25 18:21:09,939 INFO L180 IcfgInterpreter]: Interpretation finished [2021-11-25 18:21:51,291 WARN L227 SmtUtils]: Spent 34.98s on a formula simplification. DAG size of input: 185 DAG size of output: 156 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2021-11-25 18:22:08,375 WARN L227 SmtUtils]: Spent 15.85s on a formula simplification. DAG size of input: 96 DAG size of output: 88 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2021-11-25 18:22:23,628 WARN L227 SmtUtils]: Spent 12.96s on a formula simplification that was a NOOP. DAG size: 82 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2021-11-25 18:22:44,522 WARN L227 SmtUtils]: Spent 19.67s on a formula simplification. DAG size of input: 83 DAG size of output: 81 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2021-11-25 18:23:03,232 WARN L227 SmtUtils]: Spent 15.11s on a formula simplification. DAG size of input: 183 DAG size of output: 92 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2021-11-25 18:23:03,586 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '5939#(and (= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond) (= __VERIFIER_assert_~cond 0))' at error location [2021-11-25 18:23:03,586 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2021-11-25 18:23:03,586 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-11-25 18:23:03,587 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 9] total 15 [2021-11-25 18:23:03,587 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1134046604] [2021-11-25 18:23:03,587 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-11-25 18:23:03,587 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2021-11-25 18:23:03,587 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-25 18:23:03,588 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2021-11-25 18:23:03,588 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=170, Invalid=1090, Unknown=0, NotChecked=0, Total=1260 [2021-11-25 18:23:03,588 INFO L87 Difference]: Start difference. First operand 191 states and 269 transitions. Second operand has 15 states, 13 states have (on average 2.5384615384615383) internal successors, (33), 14 states have internal predecessors, (33), 7 states have call successors, (25), 2 states have call predecessors, (25), 2 states have return successors, (24), 7 states have call predecessors, (24), 7 states have call successors, (24) [2021-11-25 18:23:04,869 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-25 18:23:04,869 INFO L93 Difference]: Finished difference Result 224 states and 306 transitions. [2021-11-25 18:23:04,869 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2021-11-25 18:23:04,870 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 13 states have (on average 2.5384615384615383) internal successors, (33), 14 states have internal predecessors, (33), 7 states have call successors, (25), 2 states have call predecessors, (25), 2 states have return successors, (24), 7 states have call predecessors, (24), 7 states have call successors, (24) Word has length 79 [2021-11-25 18:23:04,870 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-25 18:23:04,872 INFO L225 Difference]: With dead ends: 224 [2021-11-25 18:23:04,872 INFO L226 Difference]: Without dead ends: 218 [2021-11-25 18:23:04,873 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 249 GetRequests, 203 SyntacticMatches, 4 SemanticMatches, 42 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 499 ImplicationChecksByTransitivity, 114.4s TimeCoverageRelationStatistics Valid=238, Invalid=1654, Unknown=0, NotChecked=0, Total=1892 [2021-11-25 18:23:04,874 INFO L933 BasicCegarLoop]: 37 mSDtfsCounter, 36 mSDsluCounter, 362 mSDsCounter, 0 mSdLazyCounter, 469 mSolverCounterSat, 55 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 43 SdHoareTripleChecker+Valid, 383 SdHoareTripleChecker+Invalid, 524 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 55 IncrementalHoareTripleChecker+Valid, 469 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2021-11-25 18:23:04,875 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [43 Valid, 383 Invalid, 524 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [55 Valid, 469 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2021-11-25 18:23:04,875 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 218 states. [2021-11-25 18:23:04,930 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 218 to 216. [2021-11-25 18:23:04,931 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 216 states, 122 states have (on average 1.1639344262295082) internal successors, (142), 125 states have internal predecessors, (142), 75 states have call successors, (75), 18 states have call predecessors, (75), 18 states have return successors, (74), 72 states have call predecessors, (74), 74 states have call successors, (74) [2021-11-25 18:23:04,933 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 216 states to 216 states and 291 transitions. [2021-11-25 18:23:04,934 INFO L78 Accepts]: Start accepts. Automaton has 216 states and 291 transitions. Word has length 79 [2021-11-25 18:23:04,934 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-25 18:23:04,934 INFO L470 AbstractCegarLoop]: Abstraction has 216 states and 291 transitions. [2021-11-25 18:23:04,935 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 13 states have (on average 2.5384615384615383) internal successors, (33), 14 states have internal predecessors, (33), 7 states have call successors, (25), 2 states have call predecessors, (25), 2 states have return successors, (24), 7 states have call predecessors, (24), 7 states have call successors, (24) [2021-11-25 18:23:04,935 INFO L276 IsEmpty]: Start isEmpty. Operand 216 states and 291 transitions. [2021-11-25 18:23:04,936 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 91 [2021-11-25 18:23:04,936 INFO L506 BasicCegarLoop]: Found error trace [2021-11-25 18:23:04,937 INFO L514 BasicCegarLoop]: trace histogram [12, 11, 11, 6, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-25 18:23:04,972 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2021-11-25 18:23:05,153 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2021-11-25 18:23:05,153 INFO L402 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-25 18:23:05,153 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-25 18:23:05,153 INFO L85 PathProgramCache]: Analyzing trace with hash 145896886, now seen corresponding path program 1 times [2021-11-25 18:23:05,154 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-25 18:23:05,154 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [76681137] [2021-11-25 18:23:05,154 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 18:23:05,154 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-25 18:23:05,164 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-11-25 18:23:05,164 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1581322448] [2021-11-25 18:23:05,164 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 18:23:05,164 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 18:23:05,164 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 [2021-11-25 18:23:05,170 INFO L229 MonitoredProcess]: Starting monitored process 13 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-25 18:23:05,171 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2021-11-25 18:23:05,220 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-25 18:23:05,222 INFO L263 TraceCheckSpWp]: Trace formula consists of 242 conjuncts, 45 conjunts are in the unsatisfiable core [2021-11-25 18:23:05,225 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-25 18:23:06,099 INFO L134 CoverageAnalysis]: Checked inductivity of 290 backedges. 59 proven. 35 refuted. 0 times theorem prover too weak. 196 trivial. 0 not checked. [2021-11-25 18:23:06,099 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-11-25 18:23:11,552 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-25 18:23:11,552 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [76681137] [2021-11-25 18:23:11,552 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-11-25 18:23:11,552 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1581322448] [2021-11-25 18:23:11,552 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1581322448] provided 0 perfect and 1 imperfect interpolant sequences [2021-11-25 18:23:11,553 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1589393276] [2021-11-25 18:23:11,555 INFO L159 IcfgInterpreter]: Started Sifa with 26 locations of interest [2021-11-25 18:23:11,555 INFO L166 IcfgInterpreter]: Building call graph [2021-11-25 18:23:11,555 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2021-11-25 18:23:11,556 INFO L176 IcfgInterpreter]: Starting interpretation [2021-11-25 18:23:11,556 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2021-11-25 18:23:15,540 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 30 for LOIs [2021-11-25 18:23:15,548 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 59 for LOIs [2021-11-25 18:23:15,561 INFO L180 IcfgInterpreter]: Interpretation finished [2021-11-25 18:23:49,648 WARN L227 SmtUtils]: Spent 28.13s on a formula simplification. DAG size of input: 181 DAG size of output: 152 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2021-11-25 18:24:28,910 WARN L227 SmtUtils]: Spent 27.49s on a formula simplification that was a NOOP. DAG size: 76 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2021-11-25 18:24:37,046 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '7073#(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:24:37,046 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2021-11-25 18:24:37,046 INFO L186 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2021-11-25 18:24:37,046 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11] total 11 [2021-11-25 18:24:37,047 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [751185200] [2021-11-25 18:24:37,047 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2021-11-25 18:24:37,047 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2021-11-25 18:24:37,047 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-25 18:24:37,048 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2021-11-25 18:24:37,048 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=172, Invalid=1085, Unknown=3, NotChecked=0, Total=1260 [2021-11-25 18:24:37,048 INFO L87 Difference]: Start difference. First operand 216 states and 291 transitions. Second operand has 11 states, 11 states have (on average 2.090909090909091) internal successors, (23), 10 states have internal predecessors, (23), 6 states have call successors, (18), 2 states have call predecessors, (18), 2 states have return successors, (17), 5 states have call predecessors, (17), 6 states have call successors, (17) [2021-11-25 18:24:37,638 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-25 18:24:37,639 INFO L93 Difference]: Finished difference Result 228 states and 301 transitions. [2021-11-25 18:24:37,639 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2021-11-25 18:24:37,639 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 11 states have (on average 2.090909090909091) internal successors, (23), 10 states have internal predecessors, (23), 6 states have call successors, (18), 2 states have call predecessors, (18), 2 states have return successors, (17), 5 states have call predecessors, (17), 6 states have call successors, (17) Word has length 90 [2021-11-25 18:24:37,640 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-25 18:24:37,642 INFO L225 Difference]: With dead ends: 228 [2021-11-25 18:24:37,642 INFO L226 Difference]: Without dead ends: 226 [2021-11-25 18:24:37,643 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 222 GetRequests, 171 SyntacticMatches, 14 SemanticMatches, 37 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 819 ImplicationChecksByTransitivity, 86.8s TimeCoverageRelationStatistics Valid=195, Invalid=1284, Unknown=3, NotChecked=0, Total=1482 [2021-11-25 18:24:37,644 INFO L933 BasicCegarLoop]: 37 mSDtfsCounter, 21 mSDsluCounter, 207 mSDsCounter, 0 mSdLazyCounter, 329 mSolverCounterSat, 24 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 27 SdHoareTripleChecker+Valid, 233 SdHoareTripleChecker+Invalid, 353 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 24 IncrementalHoareTripleChecker+Valid, 329 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2021-11-25 18:24:37,644 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [27 Valid, 233 Invalid, 353 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [24 Valid, 329 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2021-11-25 18:24:37,645 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 226 states. [2021-11-25 18:24:37,700 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 226 to 224. [2021-11-25 18:24:37,701 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 224 states, 128 states have (on average 1.15625) internal successors, (148), 131 states have internal predecessors, (148), 75 states have call successors, (75), 20 states have call predecessors, (75), 20 states have return successors, (74), 72 states have call predecessors, (74), 74 states have call successors, (74) [2021-11-25 18:24:37,703 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 224 states to 224 states and 297 transitions. [2021-11-25 18:24:37,703 INFO L78 Accepts]: Start accepts. Automaton has 224 states and 297 transitions. Word has length 90 [2021-11-25 18:24:37,704 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-25 18:24:37,704 INFO L470 AbstractCegarLoop]: Abstraction has 224 states and 297 transitions. [2021-11-25 18:24:37,705 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 11 states have (on average 2.090909090909091) internal successors, (23), 10 states have internal predecessors, (23), 6 states have call successors, (18), 2 states have call predecessors, (18), 2 states have return successors, (17), 5 states have call predecessors, (17), 6 states have call successors, (17) [2021-11-25 18:24:37,705 INFO L276 IsEmpty]: Start isEmpty. Operand 224 states and 297 transitions. [2021-11-25 18:24:37,706 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 100 [2021-11-25 18:24:37,706 INFO L506 BasicCegarLoop]: Found error trace [2021-11-25 18:24:37,707 INFO L514 BasicCegarLoop]: trace histogram [13, 12, 12, 6, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-25 18:24:37,735 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Forceful destruction successful, exit code 0 [2021-11-25 18:24:37,921 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11,13 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 18:24:37,924 INFO L402 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-25 18:24:37,924 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-25 18:24:37,925 INFO L85 PathProgramCache]: Analyzing trace with hash 2106799636, now seen corresponding path program 2 times [2021-11-25 18:24:37,925 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-25 18:24:37,925 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [553915538] [2021-11-25 18:24:37,925 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 18:24:37,925 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-25 18:24:37,948 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-11-25 18:24:37,953 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [443978064] [2021-11-25 18:24:37,954 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2021-11-25 18:24:37,954 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 18:24:37,954 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 [2021-11-25 18:24:37,955 INFO L229 MonitoredProcess]: Starting monitored process 14 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-25 18:24:37,972 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2021-11-25 18:24:38,010 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2021-11-25 18:24:38,010 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-11-25 18:24:38,011 INFO L263 TraceCheckSpWp]: Trace formula consists of 138 conjuncts, 5 conjunts are in the unsatisfiable core [2021-11-25 18:24:38,013 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-25 18:24:38,144 INFO L134 CoverageAnalysis]: Checked inductivity of 343 backedges. 43 proven. 0 refuted. 0 times theorem prover too weak. 300 trivial. 0 not checked. [2021-11-25 18:24:38,144 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-11-25 18:24:38,144 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-25 18:24:38,144 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [553915538] [2021-11-25 18:24:38,144 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-11-25 18:24:38,144 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [443978064] [2021-11-25 18:24:38,144 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [443978064] provided 1 perfect and 0 imperfect interpolant sequences [2021-11-25 18:24:38,144 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-11-25 18:24:38,144 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2021-11-25 18:24:38,144 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [626262941] [2021-11-25 18:24:38,145 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-11-25 18:24:38,145 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2021-11-25 18:24:38,145 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-25 18:24:38,145 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2021-11-25 18:24:38,145 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2021-11-25 18:24:38,145 INFO L87 Difference]: Start difference. First operand 224 states and 297 transitions. Second operand has 5 states, 5 states have (on average 4.6) internal successors, (23), 5 states have internal predecessors, (23), 3 states have call successors, (15), 2 states have call predecessors, (15), 1 states have return successors, (14), 2 states have call predecessors, (14), 2 states have call successors, (14) [2021-11-25 18:24:38,260 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-25 18:24:38,260 INFO L93 Difference]: Finished difference Result 306 states and 407 transitions. [2021-11-25 18:24:38,260 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2021-11-25 18:24:38,260 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 4.6) internal successors, (23), 5 states have internal predecessors, (23), 3 states have call successors, (15), 2 states have call predecessors, (15), 1 states have return successors, (14), 2 states have call predecessors, (14), 2 states have call successors, (14) Word has length 99 [2021-11-25 18:24:38,261 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-25 18:24:38,262 INFO L225 Difference]: With dead ends: 306 [2021-11-25 18:24:38,262 INFO L226 Difference]: Without dead ends: 209 [2021-11-25 18:24:38,264 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 100 GetRequests, 95 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=15, Invalid=27, Unknown=0, NotChecked=0, Total=42 [2021-11-25 18:24:38,265 INFO L933 BasicCegarLoop]: 47 mSDtfsCounter, 6 mSDsluCounter, 106 mSDsCounter, 0 mSdLazyCounter, 47 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 150 SdHoareTripleChecker+Invalid, 52 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 47 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2021-11-25 18:24:38,265 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [10 Valid, 150 Invalid, 52 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 47 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2021-11-25 18:24:38,266 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 209 states. [2021-11-25 18:24:38,308 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 209 to 184. [2021-11-25 18:24:38,309 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 184 states, 106 states have (on average 1.1132075471698113) internal successors, (118), 109 states have internal predecessors, (118), 57 states have call successors, (57), 20 states have call predecessors, (57), 20 states have return successors, (56), 54 states have call predecessors, (56), 56 states have call successors, (56) [2021-11-25 18:24:38,310 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 184 states to 184 states and 231 transitions. [2021-11-25 18:24:38,310 INFO L78 Accepts]: Start accepts. Automaton has 184 states and 231 transitions. Word has length 99 [2021-11-25 18:24:38,311 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-25 18:24:38,311 INFO L470 AbstractCegarLoop]: Abstraction has 184 states and 231 transitions. [2021-11-25 18:24:38,312 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 4.6) internal successors, (23), 5 states have internal predecessors, (23), 3 states have call successors, (15), 2 states have call predecessors, (15), 1 states have return successors, (14), 2 states have call predecessors, (14), 2 states have call successors, (14) [2021-11-25 18:24:38,312 INFO L276 IsEmpty]: Start isEmpty. Operand 184 states and 231 transitions. [2021-11-25 18:24:38,313 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 106 [2021-11-25 18:24:38,313 INFO L506 BasicCegarLoop]: Found error trace [2021-11-25 18:24:38,314 INFO L514 BasicCegarLoop]: trace histogram [14, 13, 13, 6, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-25 18:24:38,340 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Forceful destruction successful, exit code 0 [2021-11-25 18:24:38,525 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable12,14 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 18:24:38,525 INFO L402 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-25 18:24:38,525 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-25 18:24:38,526 INFO L85 PathProgramCache]: Analyzing trace with hash 173280102, now seen corresponding path program 2 times [2021-11-25 18:24:38,526 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-25 18:24:38,526 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [966319335] [2021-11-25 18:24:38,526 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 18:24:38,526 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-25 18:24:38,535 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-11-25 18:24:38,535 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1156797634] [2021-11-25 18:24:38,535 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2021-11-25 18:24:38,535 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 18:24:38,535 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 [2021-11-25 18:24:38,537 INFO L229 MonitoredProcess]: Starting monitored process 15 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-25 18:24:38,541 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2021-11-25 18:24:38,594 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2021-11-25 18:24:38,594 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-11-25 18:24:38,595 INFO L263 TraceCheckSpWp]: Trace formula consists of 221 conjuncts, 26 conjunts are in the unsatisfiable core [2021-11-25 18:24:38,597 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-25 18:24:38,873 INFO L134 CoverageAnalysis]: Checked inductivity of 402 backedges. 57 proven. 35 refuted. 0 times theorem prover too weak. 310 trivial. 0 not checked. [2021-11-25 18:24:38,873 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-11-25 18:24:39,103 INFO L134 CoverageAnalysis]: Checked inductivity of 402 backedges. 73 proven. 7 refuted. 0 times theorem prover too weak. 322 trivial. 0 not checked. [2021-11-25 18:24:39,103 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-25 18:24:39,103 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [966319335] [2021-11-25 18:24:39,104 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-11-25 18:24:39,104 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1156797634] [2021-11-25 18:24:39,104 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1156797634] provided 0 perfect and 2 imperfect interpolant sequences [2021-11-25 18:24:39,104 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [667766294] [2021-11-25 18:24:39,106 INFO L159 IcfgInterpreter]: Started Sifa with 26 locations of interest [2021-11-25 18:24:39,106 INFO L166 IcfgInterpreter]: Building call graph [2021-11-25 18:24:39,106 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2021-11-25 18:24:39,107 INFO L176 IcfgInterpreter]: Starting interpretation [2021-11-25 18:24:39,107 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2021-11-25 18:24:42,177 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 37 for LOIs [2021-11-25 18:24:42,184 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 59 for LOIs [2021-11-25 18:24:42,197 INFO L180 IcfgInterpreter]: Interpretation finished [2021-11-25 18:25:09,436 WARN L227 SmtUtils]: Spent 24.25s on a formula simplification. DAG size of input: 185 DAG size of output: 156 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2021-11-25 18:25:28,721 WARN L227 SmtUtils]: Spent 18.88s on a formula simplification. DAG size of input: 96 DAG size of output: 88 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2021-11-25 18:26:03,610 WARN L227 SmtUtils]: Spent 27.65s on a formula simplification. DAG size of input: 83 DAG size of output: 81 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2021-11-25 18:26:03,808 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '9495#(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:26:03,808 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2021-11-25 18:26:03,808 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-11-25 18:26:03,808 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 8] total 14 [2021-11-25 18:26:03,809 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2002467518] [2021-11-25 18:26:03,809 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-11-25 18:26:03,809 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2021-11-25 18:26:03,809 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-25 18:26:03,810 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2021-11-25 18:26:03,810 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=154, Invalid=968, Unknown=0, NotChecked=0, Total=1122 [2021-11-25 18:26:03,810 INFO L87 Difference]: Start difference. First operand 184 states and 231 transitions. Second operand has 14 states, 14 states have (on average 2.9285714285714284) internal successors, (41), 13 states have internal predecessors, (41), 8 states have call successors, (26), 2 states have call predecessors, (26), 2 states have return successors, (26), 8 states have call predecessors, (26), 8 states have call successors, (26) [2021-11-25 18:26:05,356 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-25 18:26:05,357 INFO L93 Difference]: Finished difference Result 230 states and 301 transitions. [2021-11-25 18:26:05,357 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2021-11-25 18:26:05,357 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 2.9285714285714284) internal successors, (41), 13 states have internal predecessors, (41), 8 states have call successors, (26), 2 states have call predecessors, (26), 2 states have return successors, (26), 8 states have call predecessors, (26), 8 states have call successors, (26) Word has length 105 [2021-11-25 18:26:05,358 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-25 18:26:05,360 INFO L225 Difference]: With dead ends: 230 [2021-11-25 18:26:05,360 INFO L226 Difference]: Without dead ends: 228 [2021-11-25 18:26:05,361 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 321 GetRequests, 265 SyntacticMatches, 16 SemanticMatches, 40 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 926 ImplicationChecksByTransitivity, 82.7s TimeCoverageRelationStatistics Valid=215, Invalid=1507, Unknown=0, NotChecked=0, Total=1722 [2021-11-25 18:26:05,362 INFO L933 BasicCegarLoop]: 36 mSDtfsCounter, 38 mSDsluCounter, 267 mSDsCounter, 0 mSdLazyCounter, 356 mSolverCounterSat, 60 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 42 SdHoareTripleChecker+Valid, 291 SdHoareTripleChecker+Invalid, 416 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 60 IncrementalHoareTripleChecker+Valid, 356 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2021-11-25 18:26:05,362 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [42 Valid, 291 Invalid, 416 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [60 Valid, 356 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2021-11-25 18:26:05,363 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 228 states. [2021-11-25 18:26:05,409 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 228 to 188. [2021-11-25 18:26:05,410 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 188 states, 109 states have (on average 1.110091743119266) internal successors, (121), 112 states have internal predecessors, (121), 57 states have call successors, (57), 21 states have call predecessors, (57), 21 states have return successors, (56), 54 states have call predecessors, (56), 56 states have call successors, (56) [2021-11-25 18:26:05,412 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 188 states to 188 states and 234 transitions. [2021-11-25 18:26:05,412 INFO L78 Accepts]: Start accepts. Automaton has 188 states and 234 transitions. Word has length 105 [2021-11-25 18:26:05,413 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-25 18:26:05,413 INFO L470 AbstractCegarLoop]: Abstraction has 188 states and 234 transitions. [2021-11-25 18:26:05,413 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 2.9285714285714284) internal successors, (41), 13 states have internal predecessors, (41), 8 states have call successors, (26), 2 states have call predecessors, (26), 2 states have return successors, (26), 8 states have call predecessors, (26), 8 states have call successors, (26) [2021-11-25 18:26:05,413 INFO L276 IsEmpty]: Start isEmpty. Operand 188 states and 234 transitions. [2021-11-25 18:26:05,415 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 108 [2021-11-25 18:26:05,415 INFO L506 BasicCegarLoop]: Found error trace [2021-11-25 18:26:05,415 INFO L514 BasicCegarLoop]: trace histogram [15, 14, 14, 6, 4, 4, 4, 4, 4, 4, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-25 18:26:05,451 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Forceful destruction successful, exit code 0 [2021-11-25 18:26:05,633 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 15 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2021-11-25 18:26:05,633 INFO L402 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-25 18:26:05,634 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-25 18:26:05,634 INFO L85 PathProgramCache]: Analyzing trace with hash -425141716, now seen corresponding path program 3 times [2021-11-25 18:26:05,634 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-25 18:26:05,634 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1899337382] [2021-11-25 18:26:05,634 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 18:26:05,634 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-25 18:26:05,650 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-11-25 18:26:05,650 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2014194496] [2021-11-25 18:26:05,651 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2021-11-25 18:26:05,651 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 18:26:05,651 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 [2021-11-25 18:26:05,652 INFO L229 MonitoredProcess]: Starting monitored process 16 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-25 18:26:05,660 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_f2dd3727-c906-496d-be50-91b3db092945/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2021-11-25 18:26:05,711 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2021-11-25 18:26:05,711 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-11-25 18:26:05,712 INFO L263 TraceCheckSpWp]: Trace formula consists of 230 conjuncts, 44 conjunts are in the unsatisfiable core [2021-11-25 18:26:05,714 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-25 18:26:06,531 INFO L134 CoverageAnalysis]: Checked inductivity of 454 backedges. 51 proven. 48 refuted. 0 times theorem prover too weak. 355 trivial. 0 not checked. [2021-11-25 18:26:06,531 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-11-25 18:26:14,050 INFO L134 CoverageAnalysis]: Checked inductivity of 454 backedges. 51 proven. 42 refuted. 6 times theorem prover too weak. 355 trivial. 0 not checked. [2021-11-25 18:26:14,051 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-25 18:26:14,051 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1899337382] [2021-11-25 18:26:14,051 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-11-25 18:26:14,051 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2014194496] [2021-11-25 18:26:14,051 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2014194496] provided 0 perfect and 2 imperfect interpolant sequences [2021-11-25 18:26:14,051 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [6184454] [2021-11-25 18:26:14,053 INFO L159 IcfgInterpreter]: Started Sifa with 26 locations of interest [2021-11-25 18:26:14,053 INFO L166 IcfgInterpreter]: Building call graph [2021-11-25 18:26:14,053 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2021-11-25 18:26:14,054 INFO L176 IcfgInterpreter]: Starting interpretation [2021-11-25 18:26:14,054 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2021-11-25 18:26:18,011 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 30 for LOIs [2021-11-25 18:26:18,018 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 59 for LOIs [2021-11-25 18:26:18,031 INFO L180 IcfgInterpreter]: Interpretation finished [2021-11-25 18:26:50,983 WARN L227 SmtUtils]: Spent 28.17s on a formula simplification. DAG size of input: 181 DAG size of output: 152 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2021-11-25 18:26:58,303 WARN L227 SmtUtils]: Spent 5.81s on a formula simplification. DAG size of input: 88 DAG size of output: 87 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2021-11-25 18:27:13,644 WARN L227 SmtUtils]: Spent 6.52s on a formula simplification that was a NOOP. DAG size: 77 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2021-11-25 18:27:13,742 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '10831#(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:27:13,742 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2021-11-25 18:27:13,742 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-11-25 18:27:13,742 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 13] total 22 [2021-11-25 18:27:13,742 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1337226429] [2021-11-25 18:27:13,743 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-11-25 18:27:13,743 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2021-11-25 18:27:13,743 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-25 18:27:13,744 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2021-11-25 18:27:13,744 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=228, Invalid=1491, Unknown=3, NotChecked=0, Total=1722 [2021-11-25 18:27:13,745 INFO L87 Difference]: Start difference. First operand 188 states and 234 transitions. Second operand has 22 states, 22 states have (on average 1.8181818181818181) internal successors, (40), 19 states have internal predecessors, (40), 13 states have call successors, (38), 2 states have call predecessors, (38), 2 states have return successors, (36), 11 states have call predecessors, (36), 13 states have call successors, (36) [2021-11-25 18:27:27,240 WARN L227 SmtUtils]: Spent 10.83s on a formula simplification that was a NOOP. DAG size: 77 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2021-11-25 18:27:51,451 WARN L227 SmtUtils]: Spent 16.44s on a formula simplification that was a NOOP. DAG size: 81 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2021-11-25 18:27:53,992 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2021-11-25 18:28:16,077 WARN L227 SmtUtils]: Spent 14.02s on a formula simplification that was a NOOP. DAG size: 64 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2021-11-25 18:28:18,081 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2021-11-25 18:28:20,247 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2021-11-25 18:28:22,250 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2021-11-25 18:29:02,274 WARN L227 SmtUtils]: Spent 37.87s on a formula simplification that was a NOOP. DAG size: 75 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2021-11-25 18:29:04,343 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2021-11-25 18:30:34,696 WARN L227 SmtUtils]: Spent 1.49m on a formula simplification. DAG size of input: 83 DAG size of output: 82 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2021-11-25 18:30:41,725 WARN L227 SmtUtils]: Spent 6.22s on a formula simplification. DAG size of input: 66 DAG size of output: 65 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2021-11-25 18:30:43,879 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2021-11-25 18:30:49,557 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2021-11-25 18:30:51,666 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2021-11-25 18:30:54,625 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2021-11-25 18:30:57,204 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2021-11-25 18:31:03,112 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2021-11-25 18:31:29,881 WARN L227 SmtUtils]: Spent 25.44s on a formula simplification that was a NOOP. DAG size: 86 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate)