./Ultimate.py --spec ../../sv-benchmarks/c/properties/unreach-call.prp --file ../../sv-benchmarks/c/nla-digbench/egcd3-ll.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_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/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_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/config/TaipanReach.xml -i ../../sv-benchmarks/c/nla-digbench/egcd3-ll.c -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/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_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/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 4ef08007570a64191e0df13d14d3e8d62a8022f43f46779ea6f6701a621376be --- Real Ultimate output --- This is Ultimate 0.2.2-hotfix-svcomp22-839c364 [2021-11-25 19:04:17,312 INFO L177 SettingsManager]: Resetting all preferences to default values... [2021-11-25 19:04:17,314 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2021-11-25 19:04:17,358 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2021-11-25 19:04:17,358 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2021-11-25 19:04:17,362 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2021-11-25 19:04:17,365 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2021-11-25 19:04:17,369 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2021-11-25 19:04:17,372 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2021-11-25 19:04:17,380 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2021-11-25 19:04:17,381 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2021-11-25 19:04:17,383 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2021-11-25 19:04:17,383 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2021-11-25 19:04:17,385 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2021-11-25 19:04:17,387 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2021-11-25 19:04:17,389 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2021-11-25 19:04:17,390 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2021-11-25 19:04:17,391 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2021-11-25 19:04:17,393 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2021-11-25 19:04:17,395 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2021-11-25 19:04:17,397 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2021-11-25 19:04:17,399 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2021-11-25 19:04:17,401 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2021-11-25 19:04:17,402 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2021-11-25 19:04:17,406 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2021-11-25 19:04:17,406 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2021-11-25 19:04:17,407 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2021-11-25 19:04:17,408 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2021-11-25 19:04:17,409 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2021-11-25 19:04:17,410 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2021-11-25 19:04:17,410 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2021-11-25 19:04:17,411 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2021-11-25 19:04:17,412 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2021-11-25 19:04:17,414 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2021-11-25 19:04:17,418 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2021-11-25 19:04:17,419 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2021-11-25 19:04:17,420 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2021-11-25 19:04:17,420 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2021-11-25 19:04:17,421 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2021-11-25 19:04:17,422 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2021-11-25 19:04:17,423 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2021-11-25 19:04:17,425 INFO L101 SettingsManager]: Beginning loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/config/svcomp-Reach-32bit-Taipan_Default.epf [2021-11-25 19:04:17,468 INFO L113 SettingsManager]: Loading preferences was successful [2021-11-25 19:04:17,469 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2021-11-25 19:04:17,469 INFO L136 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2021-11-25 19:04:17,470 INFO L138 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2021-11-25 19:04:17,471 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2021-11-25 19:04:17,471 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2021-11-25 19:04:17,471 INFO L138 SettingsManager]: * User list type=DISABLED [2021-11-25 19:04:17,471 INFO L136 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2021-11-25 19:04:17,472 INFO L138 SettingsManager]: * Explicit value domain=true [2021-11-25 19:04:17,472 INFO L138 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2021-11-25 19:04:17,472 INFO L138 SettingsManager]: * Octagon Domain=false [2021-11-25 19:04:17,473 INFO L138 SettingsManager]: * Abstract domain=CompoundDomain [2021-11-25 19:04:17,473 INFO L138 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2021-11-25 19:04:17,473 INFO L138 SettingsManager]: * Use the RCFG-of-the-future interface=true [2021-11-25 19:04:17,473 INFO L138 SettingsManager]: * Interval Domain=false [2021-11-25 19:04:17,474 INFO L136 SettingsManager]: Preferences of Sifa differ from their defaults: [2021-11-25 19:04:17,474 INFO L138 SettingsManager]: * Call Summarizer=TopInputCallSummarizer [2021-11-25 19:04:17,474 INFO L138 SettingsManager]: * Simplification Technique=POLY_PAC [2021-11-25 19:04:17,475 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2021-11-25 19:04:17,475 INFO L138 SettingsManager]: * sizeof long=4 [2021-11-25 19:04:17,476 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2021-11-25 19:04:17,476 INFO L138 SettingsManager]: * sizeof POINTER=4 [2021-11-25 19:04:17,476 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2021-11-25 19:04:17,476 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2021-11-25 19:04:17,477 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2021-11-25 19:04:17,477 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2021-11-25 19:04:17,477 INFO L138 SettingsManager]: * sizeof long double=12 [2021-11-25 19:04:17,477 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2021-11-25 19:04:17,477 INFO L138 SettingsManager]: * Use constant arrays=true [2021-11-25 19:04:17,478 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2021-11-25 19:04:17,478 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2021-11-25 19:04:17,478 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2021-11-25 19:04:17,478 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2021-11-25 19:04:17,479 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2021-11-25 19:04:17,479 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2021-11-25 19:04:17,479 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2021-11-25 19:04:17,479 INFO L138 SettingsManager]: * Trace refinement strategy=SIFA_TAIPAN [2021-11-25 19:04:17,480 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2021-11-25 19:04:17,480 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2021-11-25 19:04:17,480 INFO L138 SettingsManager]: * Trace refinement exception blacklist=NONE [2021-11-25 19:04:17,480 INFO L138 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2021-11-25 19:04:17,480 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_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/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_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/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 -> 4ef08007570a64191e0df13d14d3e8d62a8022f43f46779ea6f6701a621376be [2021-11-25 19:04:17,710 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2021-11-25 19:04:17,734 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2021-11-25 19:04:17,737 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2021-11-25 19:04:17,739 INFO L271 PluginConnector]: Initializing CDTParser... [2021-11-25 19:04:17,740 INFO L275 PluginConnector]: CDTParser initialized [2021-11-25 19:04:17,741 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/../../sv-benchmarks/c/nla-digbench/egcd3-ll.c [2021-11-25 19:04:17,837 INFO L220 CDTParser]: Created temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/data/f8168902d/f67c52a4424e4f7ab3b438388b065a1b/FLAG9aff2a833 [2021-11-25 19:04:18,355 INFO L306 CDTParser]: Found 1 translation units. [2021-11-25 19:04:18,355 INFO L160 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/sv-benchmarks/c/nla-digbench/egcd3-ll.c [2021-11-25 19:04:18,361 INFO L349 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/data/f8168902d/f67c52a4424e4f7ab3b438388b065a1b/FLAG9aff2a833 [2021-11-25 19:04:18,729 INFO L357 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/data/f8168902d/f67c52a4424e4f7ab3b438388b065a1b [2021-11-25 19:04:18,731 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2021-11-25 19:04:18,734 INFO L131 ToolchainWalker]: Walking toolchain with 6 elements. [2021-11-25 19:04:18,735 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2021-11-25 19:04:18,735 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2021-11-25 19:04:18,738 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2021-11-25 19:04:18,739 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 25.11 07:04:18" (1/1) ... [2021-11-25 19:04:18,740 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@2596ae76 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.11 07:04:18, skipping insertion in model container [2021-11-25 19:04:18,740 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 25.11 07:04:18" (1/1) ... [2021-11-25 19:04:18,747 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2021-11-25 19:04:18,763 INFO L178 MainTranslator]: Built tables and reachable declarations [2021-11-25 19:04:18,978 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_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/sv-benchmarks/c/nla-digbench/egcd3-ll.c[490,503] [2021-11-25 19:04:18,995 INFO L209 PostProcessor]: Analyzing one entry point: main [2021-11-25 19:04:19,003 INFO L203 MainTranslator]: Completed pre-run [2021-11-25 19:04:19,015 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_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/sv-benchmarks/c/nla-digbench/egcd3-ll.c[490,503] [2021-11-25 19:04:19,024 INFO L209 PostProcessor]: Analyzing one entry point: main [2021-11-25 19:04:19,037 INFO L208 MainTranslator]: Completed translation [2021-11-25 19:04:19,037 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.11 07:04:19 WrapperNode [2021-11-25 19:04:19,038 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2021-11-25 19:04:19,039 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2021-11-25 19:04:19,039 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2021-11-25 19:04:19,039 INFO L275 PluginConnector]: Boogie Procedure Inliner initialized [2021-11-25 19:04:19,046 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.11 07:04:19" (1/1) ... [2021-11-25 19:04:19,053 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.11 07:04:19" (1/1) ... [2021-11-25 19:04:19,071 INFO L137 Inliner]: procedures = 14, calls = 14, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 78 [2021-11-25 19:04:19,071 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2021-11-25 19:04:19,072 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2021-11-25 19:04:19,072 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2021-11-25 19:04:19,073 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2021-11-25 19:04:19,081 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.11 07:04:19" (1/1) ... [2021-11-25 19:04:19,081 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.11 07:04:19" (1/1) ... [2021-11-25 19:04:19,082 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.11 07:04:19" (1/1) ... [2021-11-25 19:04:19,083 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.11 07:04:19" (1/1) ... [2021-11-25 19:04:19,086 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.11 07:04:19" (1/1) ... [2021-11-25 19:04:19,090 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.11 07:04:19" (1/1) ... [2021-11-25 19:04:19,091 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.11 07:04:19" (1/1) ... [2021-11-25 19:04:19,093 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2021-11-25 19:04:19,094 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2021-11-25 19:04:19,094 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2021-11-25 19:04:19,095 INFO L275 PluginConnector]: RCFGBuilder initialized [2021-11-25 19:04:19,095 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.11 07:04:19" (1/1) ... [2021-11-25 19:04:19,102 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2021-11-25 19:04:19,115 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 [2021-11-25 19:04:19,133 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2021-11-25 19:04:19,152 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2021-11-25 19:04:19,177 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2021-11-25 19:04:19,177 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2021-11-25 19:04:19,178 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2021-11-25 19:04:19,178 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2021-11-25 19:04:19,178 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2021-11-25 19:04:19,178 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2021-11-25 19:04:19,178 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2021-11-25 19:04:19,179 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2021-11-25 19:04:19,245 INFO L236 CfgBuilder]: Building ICFG [2021-11-25 19:04:19,247 INFO L262 CfgBuilder]: Building CFG for each procedure with an implementation [2021-11-25 19:04:19,425 INFO L277 CfgBuilder]: Performing block encoding [2021-11-25 19:04:19,444 INFO L296 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2021-11-25 19:04:19,444 INFO L301 CfgBuilder]: Removed 3 assume(true) statements. [2021-11-25 19:04:19,446 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 25.11 07:04:19 BoogieIcfgContainer [2021-11-25 19:04:19,446 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2021-11-25 19:04:19,448 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2021-11-25 19:04:19,448 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2021-11-25 19:04:19,452 INFO L275 PluginConnector]: TraceAbstraction initialized [2021-11-25 19:04:19,452 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 25.11 07:04:18" (1/3) ... [2021-11-25 19:04:19,453 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7c367150 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 25.11 07:04:19, skipping insertion in model container [2021-11-25 19:04:19,453 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.11 07:04:19" (2/3) ... [2021-11-25 19:04:19,453 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7c367150 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 25.11 07:04:19, skipping insertion in model container [2021-11-25 19:04:19,453 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 25.11 07:04:19" (3/3) ... [2021-11-25 19:04:19,455 INFO L111 eAbstractionObserver]: Analyzing ICFG egcd3-ll.c [2021-11-25 19:04:19,460 INFO L204 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2021-11-25 19:04:19,460 INFO L163 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2021-11-25 19:04:19,506 INFO L338 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2021-11-25 19:04:19,514 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 19:04:19,514 INFO L340 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2021-11-25 19:04:19,530 INFO L276 IsEmpty]: Start isEmpty. Operand has 27 states, 16 states have (on average 1.5) internal successors, (24), 17 states have internal predecessors, (24), 7 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2021-11-25 19:04:19,535 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 14 [2021-11-25 19:04:19,535 INFO L506 BasicCegarLoop]: Found error trace [2021-11-25 19:04:19,536 INFO L514 BasicCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-25 19:04:19,536 INFO L402 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-25 19:04:19,541 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-25 19:04:19,542 INFO L85 PathProgramCache]: Analyzing trace with hash 1524023292, now seen corresponding path program 1 times [2021-11-25 19:04:19,550 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-25 19:04:19,551 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [296014541] [2021-11-25 19:04:19,551 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 19:04:19,552 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-25 19:04:19,691 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-25 19:04:19,760 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2021-11-25 19:04:19,760 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-25 19:04:19,760 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [296014541] [2021-11-25 19:04:19,761 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [296014541] provided 1 perfect and 0 imperfect interpolant sequences [2021-11-25 19:04:19,761 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-11-25 19:04:19,761 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2021-11-25 19:04:19,762 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1791250583] [2021-11-25 19:04:19,763 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-11-25 19:04:19,767 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2021-11-25 19:04:19,767 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-25 19:04:19,803 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2021-11-25 19:04:19,804 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2021-11-25 19:04:19,807 INFO L87 Difference]: Start difference. First operand has 27 states, 16 states have (on average 1.5) internal successors, (24), 17 states have internal predecessors, (24), 7 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) Second operand has 2 states, 2 states have (on average 3.5) internal successors, (7), 2 states have internal predecessors, (7), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2021-11-25 19:04:19,864 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-25 19:04:19,867 INFO L93 Difference]: Finished difference Result 48 states and 74 transitions. [2021-11-25 19:04:19,868 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2021-11-25 19:04:19,869 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 3.5) internal successors, (7), 2 states have internal predecessors, (7), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 13 [2021-11-25 19:04:19,870 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-25 19:04:19,877 INFO L225 Difference]: With dead ends: 48 [2021-11-25 19:04:19,877 INFO L226 Difference]: Without dead ends: 25 [2021-11-25 19:04:19,885 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2021-11-25 19:04:19,890 INFO L933 BasicCegarLoop]: 31 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 3 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 31 SdHoareTripleChecker+Invalid, 5 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 3 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-11-25 19:04:19,894 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [0 Valid, 31 Invalid, 5 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 3 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-11-25 19:04:19,911 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 25 states. [2021-11-25 19:04:19,929 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 25 to 25. [2021-11-25 19:04:19,930 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 25 states, 15 states have (on average 1.2666666666666666) internal successors, (19), 16 states have internal predecessors, (19), 7 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2021-11-25 19:04:19,932 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 25 states to 25 states and 32 transitions. [2021-11-25 19:04:19,933 INFO L78 Accepts]: Start accepts. Automaton has 25 states and 32 transitions. Word has length 13 [2021-11-25 19:04:19,935 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-25 19:04:19,935 INFO L470 AbstractCegarLoop]: Abstraction has 25 states and 32 transitions. [2021-11-25 19:04:19,935 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 3.5) internal successors, (7), 2 states have internal predecessors, (7), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2021-11-25 19:04:19,935 INFO L276 IsEmpty]: Start isEmpty. Operand 25 states and 32 transitions. [2021-11-25 19:04:19,937 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2021-11-25 19:04:19,937 INFO L506 BasicCegarLoop]: Found error trace [2021-11-25 19:04:19,937 INFO L514 BasicCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-25 19:04:19,938 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2021-11-25 19:04:19,938 INFO L402 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-25 19:04:19,939 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-25 19:04:19,939 INFO L85 PathProgramCache]: Analyzing trace with hash 1500233354, now seen corresponding path program 1 times [2021-11-25 19:04:19,940 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-25 19:04:19,940 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [40723846] [2021-11-25 19:04:19,940 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 19:04:19,941 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-25 19:04:19,966 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-11-25 19:04:19,966 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [452413434] [2021-11-25 19:04:19,966 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 19:04:19,967 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 19:04:19,967 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 [2021-11-25 19:04:19,970 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-25 19:04:20,015 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2021-11-25 19:04:20,065 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-25 19:04:20,067 INFO L263 TraceCheckSpWp]: Trace formula consists of 69 conjuncts, 7 conjunts are in the unsatisfiable core [2021-11-25 19:04:20,073 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-25 19:04:20,159 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2021-11-25 19:04:20,160 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-11-25 19:04:20,160 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-25 19:04:20,160 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [40723846] [2021-11-25 19:04:20,160 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-11-25 19:04:20,161 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [452413434] [2021-11-25 19:04:20,161 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [452413434] provided 1 perfect and 0 imperfect interpolant sequences [2021-11-25 19:04:20,161 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-11-25 19:04:20,161 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2021-11-25 19:04:20,162 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1137223199] [2021-11-25 19:04:20,163 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-11-25 19:04:20,163 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2021-11-25 19:04:20,164 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-25 19:04:20,164 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2021-11-25 19:04:20,165 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2021-11-25 19:04:20,165 INFO L87 Difference]: Start difference. First operand 25 states and 32 transitions. Second operand has 5 states, 4 states have (on average 2.25) internal successors, (9), 4 states have internal predecessors, (9), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2021-11-25 19:04:20,228 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-25 19:04:20,228 INFO L93 Difference]: Finished difference Result 44 states and 57 transitions. [2021-11-25 19:04:20,229 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2021-11-25 19:04:20,229 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 2.25) internal successors, (9), 4 states have internal predecessors, (9), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) Word has length 14 [2021-11-25 19:04:20,229 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-25 19:04:20,230 INFO L225 Difference]: With dead ends: 44 [2021-11-25 19:04:20,231 INFO L226 Difference]: Without dead ends: 37 [2021-11-25 19:04:20,231 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 14 GetRequests, 10 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2021-11-25 19:04:20,233 INFO L933 BasicCegarLoop]: 27 mSDtfsCounter, 29 mSDsluCounter, 62 mSDsCounter, 0 mSdLazyCounter, 31 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 33 SdHoareTripleChecker+Valid, 86 SdHoareTripleChecker+Invalid, 40 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 31 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-11-25 19:04:20,234 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [33 Valid, 86 Invalid, 40 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 31 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-11-25 19:04:20,235 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 37 states. [2021-11-25 19:04:20,242 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 37 to 27. [2021-11-25 19:04:20,242 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 27 states, 17 states have (on average 1.2352941176470589) internal successors, (21), 18 states have internal predecessors, (21), 7 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2021-11-25 19:04:20,243 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 27 states to 27 states and 34 transitions. [2021-11-25 19:04:20,244 INFO L78 Accepts]: Start accepts. Automaton has 27 states and 34 transitions. Word has length 14 [2021-11-25 19:04:20,244 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-25 19:04:20,244 INFO L470 AbstractCegarLoop]: Abstraction has 27 states and 34 transitions. [2021-11-25 19:04:20,244 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 2.25) internal successors, (9), 4 states have internal predecessors, (9), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2021-11-25 19:04:20,245 INFO L276 IsEmpty]: Start isEmpty. Operand 27 states and 34 transitions. [2021-11-25 19:04:20,245 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2021-11-25 19:04:20,245 INFO L506 BasicCegarLoop]: Found error trace [2021-11-25 19:04:20,246 INFO L514 BasicCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-25 19:04:20,267 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2021-11-25 19:04:20,451 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 19:04:20,452 INFO L402 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-25 19:04:20,453 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-25 19:04:20,455 INFO L85 PathProgramCache]: Analyzing trace with hash -640281993, now seen corresponding path program 1 times [2021-11-25 19:04:20,455 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-25 19:04:20,457 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1104976829] [2021-11-25 19:04:20,457 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 19:04:20,457 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-25 19:04:20,473 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-11-25 19:04:20,473 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [624008852] [2021-11-25 19:04:20,474 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 19:04:20,474 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 19:04:20,474 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 [2021-11-25 19:04:20,475 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-25 19:04:20,477 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2021-11-25 19:04:20,533 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-25 19:04:20,537 INFO L263 TraceCheckSpWp]: Trace formula consists of 79 conjuncts, 15 conjunts are in the unsatisfiable core [2021-11-25 19:04:20,539 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-25 19:04:20,835 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2021-11-25 19:04:20,836 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-11-25 19:04:20,836 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-25 19:04:20,836 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1104976829] [2021-11-25 19:04:20,836 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-11-25 19:04:20,838 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [624008852] [2021-11-25 19:04:20,838 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [624008852] provided 1 perfect and 0 imperfect interpolant sequences [2021-11-25 19:04:20,838 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-11-25 19:04:20,838 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2021-11-25 19:04:20,838 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [572194811] [2021-11-25 19:04:20,839 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-11-25 19:04:20,840 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2021-11-25 19:04:20,840 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-25 19:04:20,842 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2021-11-25 19:04:20,842 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=16, Invalid=40, Unknown=0, NotChecked=0, Total=56 [2021-11-25 19:04:20,843 INFO L87 Difference]: Start difference. First operand 27 states and 34 transitions. Second operand has 8 states, 6 states have (on average 2.0) internal successors, (12), 6 states have internal predecessors, (12), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2021-11-25 19:04:20,959 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-25 19:04:20,959 INFO L93 Difference]: Finished difference Result 43 states and 55 transitions. [2021-11-25 19:04:20,960 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2021-11-25 19:04:20,960 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 6 states have (on average 2.0) internal successors, (12), 6 states have internal predecessors, (12), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) Word has length 17 [2021-11-25 19:04:20,960 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-25 19:04:20,963 INFO L225 Difference]: With dead ends: 43 [2021-11-25 19:04:20,963 INFO L226 Difference]: Without dead ends: 41 [2021-11-25 19:04:20,964 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 17 GetRequests, 10 SyntacticMatches, 0 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=20, Invalid=52, Unknown=0, NotChecked=0, Total=72 [2021-11-25 19:04:20,968 INFO L933 BasicCegarLoop]: 26 mSDtfsCounter, 30 mSDsluCounter, 107 mSDsCounter, 0 mSdLazyCounter, 61 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 39 SdHoareTripleChecker+Valid, 126 SdHoareTripleChecker+Invalid, 66 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 61 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2021-11-25 19:04:20,970 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [39 Valid, 126 Invalid, 66 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 61 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2021-11-25 19:04:20,972 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 41 states. [2021-11-25 19:04:20,982 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 41 to 40. [2021-11-25 19:04:20,983 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 40 states, 25 states have (on average 1.24) internal successors, (31), 26 states have internal predecessors, (31), 11 states have call successors, (11), 3 states have call predecessors, (11), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2021-11-25 19:04:20,984 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 40 states to 40 states and 52 transitions. [2021-11-25 19:04:20,984 INFO L78 Accepts]: Start accepts. Automaton has 40 states and 52 transitions. Word has length 17 [2021-11-25 19:04:20,985 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-25 19:04:20,985 INFO L470 AbstractCegarLoop]: Abstraction has 40 states and 52 transitions. [2021-11-25 19:04:20,985 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 6 states have (on average 2.0) internal successors, (12), 6 states have internal predecessors, (12), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2021-11-25 19:04:20,985 INFO L276 IsEmpty]: Start isEmpty. Operand 40 states and 52 transitions. [2021-11-25 19:04:20,986 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2021-11-25 19:04:20,986 INFO L506 BasicCegarLoop]: Found error trace [2021-11-25 19:04:20,986 INFO L514 BasicCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-25 19:04:21,020 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2021-11-25 19:04:21,206 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 19:04:21,207 INFO L402 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-25 19:04:21,207 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-25 19:04:21,208 INFO L85 PathProgramCache]: Analyzing trace with hash -377003451, now seen corresponding path program 1 times [2021-11-25 19:04:21,208 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-25 19:04:21,208 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1852903087] [2021-11-25 19:04:21,208 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 19:04:21,208 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-25 19:04:21,223 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-11-25 19:04:21,223 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [907060268] [2021-11-25 19:04:21,223 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 19:04:21,224 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 19:04:21,224 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 [2021-11-25 19:04:21,225 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-25 19:04:21,236 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2021-11-25 19:04:21,280 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-25 19:04:21,281 INFO L263 TraceCheckSpWp]: Trace formula consists of 91 conjuncts, 9 conjunts are in the unsatisfiable core [2021-11-25 19:04:21,282 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-25 19:04:21,367 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2021-11-25 19:04:21,367 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-11-25 19:04:21,479 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2021-11-25 19:04:21,480 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-25 19:04:21,480 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1852903087] [2021-11-25 19:04:21,480 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-11-25 19:04:21,481 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [907060268] [2021-11-25 19:04:21,481 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [907060268] provided 0 perfect and 2 imperfect interpolant sequences [2021-11-25 19:04:21,481 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [751991884] [2021-11-25 19:04:21,503 INFO L159 IcfgInterpreter]: Started Sifa with 16 locations of interest [2021-11-25 19:04:21,503 INFO L166 IcfgInterpreter]: Building call graph [2021-11-25 19:04:21,514 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2021-11-25 19:04:21,519 INFO L176 IcfgInterpreter]: Starting interpretation [2021-11-25 19:04:21,520 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2021-11-25 19:04:22,259 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 65 for LOIs [2021-11-25 19:04:22,297 INFO L180 IcfgInterpreter]: Interpretation finished [2021-11-25 19:04:23,853 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSifa [751991884] provided 1 perfect and 0 imperfect interpolant sequences [2021-11-25 19:04:23,854 INFO L186 FreeRefinementEngine]: Found 1 perfect and 2 imperfect interpolant sequences. [2021-11-25 19:04:23,854 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [7, 7] total 15 [2021-11-25 19:04:23,855 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [833032285] [2021-11-25 19:04:23,855 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-11-25 19:04:23,855 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2021-11-25 19:04:23,855 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-25 19:04:23,856 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2021-11-25 19:04:23,856 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=56, Invalid=154, Unknown=0, NotChecked=0, Total=210 [2021-11-25 19:04:23,857 INFO L87 Difference]: Start difference. First operand 40 states and 52 transitions. Second operand has 10 states, 7 states have (on average 1.7142857142857142) internal successors, (12), 6 states have internal predecessors, (12), 3 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2021-11-25 19:04:24,047 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-25 19:04:24,048 INFO L93 Difference]: Finished difference Result 68 states and 92 transitions. [2021-11-25 19:04:24,048 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2021-11-25 19:04:24,048 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 7 states have (on average 1.7142857142857142) internal successors, (12), 6 states have internal predecessors, (12), 3 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 19 [2021-11-25 19:04:24,049 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-25 19:04:24,050 INFO L225 Difference]: With dead ends: 68 [2021-11-25 19:04:24,050 INFO L226 Difference]: Without dead ends: 61 [2021-11-25 19:04:24,050 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 55 GetRequests, 39 SyntacticMatches, 3 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10 ImplicationChecksByTransitivity, 1.6s TimeCoverageRelationStatistics Valid=56, Invalid=154, Unknown=0, NotChecked=0, Total=210 [2021-11-25 19:04:24,052 INFO L933 BasicCegarLoop]: 24 mSDtfsCounter, 51 mSDsluCounter, 31 mSDsCounter, 0 mSdLazyCounter, 55 mSolverCounterSat, 22 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 59 SdHoareTripleChecker+Valid, 55 SdHoareTripleChecker+Invalid, 108 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 22 IncrementalHoareTripleChecker+Valid, 55 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 31 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2021-11-25 19:04:24,052 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [59 Valid, 55 Invalid, 108 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [22 Valid, 55 Invalid, 0 Unknown, 31 Unchecked, 0.2s Time] [2021-11-25 19:04:24,053 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 61 states. [2021-11-25 19:04:24,069 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 61 to 47. [2021-11-25 19:04:24,070 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 47 states, 32 states have (on average 1.25) internal successors, (40), 33 states have internal predecessors, (40), 11 states have call successors, (11), 3 states have call predecessors, (11), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2021-11-25 19:04:24,071 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 47 states to 47 states and 61 transitions. [2021-11-25 19:04:24,071 INFO L78 Accepts]: Start accepts. Automaton has 47 states and 61 transitions. Word has length 19 [2021-11-25 19:04:24,072 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-25 19:04:24,072 INFO L470 AbstractCegarLoop]: Abstraction has 47 states and 61 transitions. [2021-11-25 19:04:24,072 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 7 states have (on average 1.7142857142857142) internal successors, (12), 6 states have internal predecessors, (12), 3 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2021-11-25 19:04:24,072 INFO L276 IsEmpty]: Start isEmpty. Operand 47 states and 61 transitions. [2021-11-25 19:04:24,073 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2021-11-25 19:04:24,073 INFO L506 BasicCegarLoop]: Found error trace [2021-11-25 19:04:24,073 INFO L514 BasicCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-25 19:04:24,109 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2021-11-25 19:04:24,287 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 19:04:24,288 INFO L402 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-25 19:04:24,288 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-25 19:04:24,288 INFO L85 PathProgramCache]: Analyzing trace with hash 1954095958, now seen corresponding path program 1 times [2021-11-25 19:04:24,288 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-25 19:04:24,288 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [704362332] [2021-11-25 19:04:24,288 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 19:04:24,289 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-25 19:04:24,301 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-11-25 19:04:24,301 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1961324785] [2021-11-25 19:04:24,302 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 19:04:24,302 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 19:04:24,302 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 [2021-11-25 19:04:24,308 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-25 19:04:24,323 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2021-11-25 19:04:24,346 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-25 19:04:24,347 INFO L263 TraceCheckSpWp]: Trace formula consists of 88 conjuncts, 19 conjunts are in the unsatisfiable core [2021-11-25 19:04:24,349 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-25 19:04:24,567 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 3 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2021-11-25 19:04:24,567 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-11-25 19:04:24,567 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-25 19:04:24,567 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [704362332] [2021-11-25 19:04:24,567 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-11-25 19:04:24,568 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1961324785] [2021-11-25 19:04:24,568 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1961324785] provided 1 perfect and 0 imperfect interpolant sequences [2021-11-25 19:04:24,568 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-11-25 19:04:24,568 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [10] imperfect sequences [] total 10 [2021-11-25 19:04:24,568 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [704846389] [2021-11-25 19:04:24,568 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-11-25 19:04:24,569 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2021-11-25 19:04:24,569 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-25 19:04:24,569 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2021-11-25 19:04:24,570 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=24, Invalid=66, Unknown=0, NotChecked=0, Total=90 [2021-11-25 19:04:24,570 INFO L87 Difference]: Start difference. First operand 47 states and 61 transitions. Second operand has 10 states, 8 states have (on average 1.875) internal successors, (15), 8 states have internal predecessors, (15), 2 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 3 states have call predecessors, (3), 2 states have call successors, (3) [2021-11-25 19:04:24,813 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-25 19:04:24,813 INFO L93 Difference]: Finished difference Result 62 states and 80 transitions. [2021-11-25 19:04:24,814 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2021-11-25 19:04:24,815 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 8 states have (on average 1.875) internal successors, (15), 8 states have internal predecessors, (15), 2 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 3 states have call predecessors, (3), 2 states have call successors, (3) Word has length 22 [2021-11-25 19:04:24,815 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-25 19:04:24,816 INFO L225 Difference]: With dead ends: 62 [2021-11-25 19:04:24,816 INFO L226 Difference]: Without dead ends: 60 [2021-11-25 19:04:24,817 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 25 GetRequests, 13 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 17 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=49, Invalid=133, Unknown=0, NotChecked=0, Total=182 [2021-11-25 19:04:24,818 INFO L933 BasicCegarLoop]: 28 mSDtfsCounter, 68 mSDsluCounter, 121 mSDsCounter, 0 mSdLazyCounter, 137 mSolverCounterSat, 31 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 73 SdHoareTripleChecker+Valid, 142 SdHoareTripleChecker+Invalid, 168 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 31 IncrementalHoareTripleChecker+Valid, 137 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2021-11-25 19:04:24,818 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [73 Valid, 142 Invalid, 168 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [31 Valid, 137 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2021-11-25 19:04:24,819 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 60 states. [2021-11-25 19:04:24,832 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 60 to 51. [2021-11-25 19:04:24,833 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 51 states, 35 states have (on average 1.2285714285714286) internal successors, (43), 36 states have internal predecessors, (43), 11 states have call successors, (11), 4 states have call predecessors, (11), 4 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2021-11-25 19:04:24,834 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 51 states to 51 states and 64 transitions. [2021-11-25 19:04:24,834 INFO L78 Accepts]: Start accepts. Automaton has 51 states and 64 transitions. Word has length 22 [2021-11-25 19:04:24,834 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-25 19:04:24,835 INFO L470 AbstractCegarLoop]: Abstraction has 51 states and 64 transitions. [2021-11-25 19:04:24,835 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 8 states have (on average 1.875) internal successors, (15), 8 states have internal predecessors, (15), 2 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 3 states have call predecessors, (3), 2 states have call successors, (3) [2021-11-25 19:04:24,835 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 64 transitions. [2021-11-25 19:04:24,836 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2021-11-25 19:04:24,836 INFO L506 BasicCegarLoop]: Found error trace [2021-11-25 19:04:24,836 INFO L514 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-25 19:04:24,873 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2021-11-25 19:04:25,063 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 19:04:25,064 INFO L402 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-25 19:04:25,064 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-25 19:04:25,064 INFO L85 PathProgramCache]: Analyzing trace with hash -632778532, now seen corresponding path program 1 times [2021-11-25 19:04:25,064 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-25 19:04:25,064 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1937053644] [2021-11-25 19:04:25,064 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 19:04:25,064 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-25 19:04:25,073 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-11-25 19:04:25,073 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [428576330] [2021-11-25 19:04:25,073 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 19:04:25,073 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 19:04:25,074 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 [2021-11-25 19:04:25,087 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-25 19:04:25,102 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2021-11-25 19:04:25,144 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-25 19:04:25,145 INFO L263 TraceCheckSpWp]: Trace formula consists of 101 conjuncts, 20 conjunts are in the unsatisfiable core [2021-11-25 19:04:25,147 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-25 19:04:25,346 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 5 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2021-11-25 19:04:25,347 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-11-25 19:04:25,459 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2021-11-25 19:04:25,459 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-25 19:04:25,459 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1937053644] [2021-11-25 19:04:25,459 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-11-25 19:04:25,460 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [428576330] [2021-11-25 19:04:25,460 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [428576330] provided 0 perfect and 2 imperfect interpolant sequences [2021-11-25 19:04:25,460 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [802618125] [2021-11-25 19:04:25,463 INFO L159 IcfgInterpreter]: Started Sifa with 17 locations of interest [2021-11-25 19:04:25,463 INFO L166 IcfgInterpreter]: Building call graph [2021-11-25 19:04:25,463 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2021-11-25 19:04:25,464 INFO L176 IcfgInterpreter]: Starting interpretation [2021-11-25 19:04:25,464 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2021-11-25 19:04:26,722 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 43 for LOIs [2021-11-25 19:04:26,735 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 65 for LOIs [2021-11-25 19:04:26,767 INFO L180 IcfgInterpreter]: Interpretation finished [2021-11-25 19:04:28,679 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSifa [802618125] provided 1 perfect and 0 imperfect interpolant sequences [2021-11-25 19:04:28,679 INFO L186 FreeRefinementEngine]: Found 1 perfect and 2 imperfect interpolant sequences. [2021-11-25 19:04:28,680 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [12] imperfect sequences [8, 6] total 21 [2021-11-25 19:04:28,680 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [906540586] [2021-11-25 19:04:28,680 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-11-25 19:04:28,680 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2021-11-25 19:04:28,680 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-25 19:04:28,681 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2021-11-25 19:04:28,681 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=78, Invalid=342, Unknown=0, NotChecked=0, Total=420 [2021-11-25 19:04:28,681 INFO L87 Difference]: Start difference. First operand 51 states and 64 transitions. Second operand has 13 states, 10 states have (on average 1.3) internal successors, (13), 8 states have internal predecessors, (13), 3 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2021-11-25 19:04:29,291 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-25 19:04:29,291 INFO L93 Difference]: Finished difference Result 93 states and 123 transitions. [2021-11-25 19:04:29,292 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2021-11-25 19:04:29,292 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 10 states have (on average 1.3) internal successors, (13), 8 states have internal predecessors, (13), 3 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 22 [2021-11-25 19:04:29,292 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-25 19:04:29,294 INFO L225 Difference]: With dead ends: 93 [2021-11-25 19:04:29,294 INFO L226 Difference]: Without dead ends: 91 [2021-11-25 19:04:29,295 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 65 GetRequests, 42 SyntacticMatches, 3 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 83 ImplicationChecksByTransitivity, 2.2s TimeCoverageRelationStatistics Valid=88, Invalid=374, Unknown=0, NotChecked=0, Total=462 [2021-11-25 19:04:29,296 INFO L933 BasicCegarLoop]: 19 mSDtfsCounter, 70 mSDsluCounter, 35 mSDsCounter, 0 mSdLazyCounter, 127 mSolverCounterSat, 52 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 82 SdHoareTripleChecker+Valid, 54 SdHoareTripleChecker+Invalid, 222 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 52 IncrementalHoareTripleChecker+Valid, 127 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 43 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2021-11-25 19:04:29,297 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [82 Valid, 54 Invalid, 222 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [52 Valid, 127 Invalid, 0 Unknown, 43 Unchecked, 0.3s Time] [2021-11-25 19:04:29,297 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 91 states. [2021-11-25 19:04:29,323 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 91 to 85. [2021-11-25 19:04:29,324 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 85 states, 50 states have (on average 1.2) internal successors, (60), 53 states have internal predecessors, (60), 27 states have call successors, (27), 7 states have call predecessors, (27), 7 states have return successors, (26), 24 states have call predecessors, (26), 26 states have call successors, (26) [2021-11-25 19:04:29,326 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 85 states to 85 states and 113 transitions. [2021-11-25 19:04:29,326 INFO L78 Accepts]: Start accepts. Automaton has 85 states and 113 transitions. Word has length 22 [2021-11-25 19:04:29,326 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-25 19:04:29,326 INFO L470 AbstractCegarLoop]: Abstraction has 85 states and 113 transitions. [2021-11-25 19:04:29,327 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 10 states have (on average 1.3) internal successors, (13), 8 states have internal predecessors, (13), 3 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2021-11-25 19:04:29,327 INFO L276 IsEmpty]: Start isEmpty. Operand 85 states and 113 transitions. [2021-11-25 19:04:29,328 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 45 [2021-11-25 19:04:29,329 INFO L506 BasicCegarLoop]: Found error trace [2021-11-25 19:04:29,329 INFO L514 BasicCegarLoop]: trace histogram [5, 4, 4, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-25 19:04:29,355 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2021-11-25 19:04:29,543 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable5 [2021-11-25 19:04:29,544 INFO L402 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-25 19:04:29,544 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-25 19:04:29,544 INFO L85 PathProgramCache]: Analyzing trace with hash -143636076, now seen corresponding path program 1 times [2021-11-25 19:04:29,544 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-25 19:04:29,544 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1292478659] [2021-11-25 19:04:29,544 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 19:04:29,545 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-25 19:04:29,554 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-11-25 19:04:29,554 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [547411480] [2021-11-25 19:04:29,554 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 19:04:29,554 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 19:04:29,555 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 [2021-11-25 19:04:29,555 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-25 19:04:29,578 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2021-11-25 19:04:29,631 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-25 19:04:29,633 INFO L263 TraceCheckSpWp]: Trace formula consists of 139 conjuncts, 51 conjunts are in the unsatisfiable core [2021-11-25 19:04:29,636 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-25 19:04:30,193 INFO L134 CoverageAnalysis]: Checked inductivity of 38 backedges. 6 proven. 18 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2021-11-25 19:04:30,193 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-11-25 19:04:54,308 WARN L227 SmtUtils]: Spent 15.31s on a formula simplification that was a NOOP. DAG size: 72 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2021-11-25 19:04:54,310 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-25 19:04:54,310 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1292478659] [2021-11-25 19:04:54,311 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-11-25 19:04:54,311 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [547411480] [2021-11-25 19:04:54,311 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [547411480] provided 0 perfect and 1 imperfect interpolant sequences [2021-11-25 19:04:54,311 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [2065716699] [2021-11-25 19:04:54,313 INFO L159 IcfgInterpreter]: Started Sifa with 25 locations of interest [2021-11-25 19:04:54,314 INFO L166 IcfgInterpreter]: Building call graph [2021-11-25 19:04:54,314 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2021-11-25 19:04:54,314 INFO L176 IcfgInterpreter]: Starting interpretation [2021-11-25 19:04:54,314 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2021-11-25 19:05:05,020 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 10 for LOIs [2021-11-25 19:05:05,032 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 65 for LOIs [2021-11-25 19:05:05,057 INFO L180 IcfgInterpreter]: Interpretation finished [2021-11-25 19:05:30,396 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1666#(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 19:05:30,396 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2021-11-25 19:05:30,396 INFO L186 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2021-11-25 19:05:30,396 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13] total 13 [2021-11-25 19:05:30,396 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2119281563] [2021-11-25 19:05:30,397 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2021-11-25 19:05:30,397 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2021-11-25 19:05:30,397 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-25 19:05:30,398 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2021-11-25 19:05:30,399 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=167, Invalid=1311, Unknown=4, NotChecked=0, Total=1482 [2021-11-25 19:05:30,399 INFO L87 Difference]: Start difference. First operand 85 states and 113 transitions. Second operand has 13 states, 12 states have (on average 2.0) internal successors, (24), 12 states have internal predecessors, (24), 4 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (6), 2 states have call predecessors, (6), 3 states have call successors, (6) [2021-11-25 19:05:30,925 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-25 19:05:30,925 INFO L93 Difference]: Finished difference Result 123 states and 163 transitions. [2021-11-25 19:05:30,926 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2021-11-25 19:05:30,926 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 12 states have (on average 2.0) internal successors, (24), 12 states have internal predecessors, (24), 4 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (6), 2 states have call predecessors, (6), 3 states have call successors, (6) Word has length 44 [2021-11-25 19:05:30,926 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-25 19:05:30,929 INFO L225 Difference]: With dead ends: 123 [2021-11-25 19:05:30,929 INFO L226 Difference]: Without dead ends: 120 [2021-11-25 19:05:30,930 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 118 GetRequests, 74 SyntacticMatches, 3 SemanticMatches, 41 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 528 ImplicationChecksByTransitivity, 45.1s TimeCoverageRelationStatistics Valid=198, Invalid=1604, Unknown=4, NotChecked=0, Total=1806 [2021-11-25 19:05:30,931 INFO L933 BasicCegarLoop]: 33 mSDtfsCounter, 41 mSDsluCounter, 285 mSDsCounter, 0 mSdLazyCounter, 510 mSolverCounterSat, 26 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 58 SdHoareTripleChecker+Valid, 305 SdHoareTripleChecker+Invalid, 536 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 26 IncrementalHoareTripleChecker+Valid, 510 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2021-11-25 19:05:30,931 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [58 Valid, 305 Invalid, 536 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [26 Valid, 510 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2021-11-25 19:05:30,932 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 120 states. [2021-11-25 19:05:30,961 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 120 to 109. [2021-11-25 19:05:30,961 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 109 states, 68 states have (on average 1.2058823529411764) internal successors, (82), 70 states have internal predecessors, (82), 31 states have call successors, (31), 9 states have call predecessors, (31), 9 states have return successors, (30), 29 states have call predecessors, (30), 30 states have call successors, (30) [2021-11-25 19:05:30,963 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 109 states to 109 states and 143 transitions. [2021-11-25 19:05:30,964 INFO L78 Accepts]: Start accepts. Automaton has 109 states and 143 transitions. Word has length 44 [2021-11-25 19:05:30,964 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-25 19:05:30,964 INFO L470 AbstractCegarLoop]: Abstraction has 109 states and 143 transitions. [2021-11-25 19:05:30,964 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 12 states have (on average 2.0) internal successors, (24), 12 states have internal predecessors, (24), 4 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (6), 2 states have call predecessors, (6), 3 states have call successors, (6) [2021-11-25 19:05:30,965 INFO L276 IsEmpty]: Start isEmpty. Operand 109 states and 143 transitions. [2021-11-25 19:05:30,967 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 48 [2021-11-25 19:05:30,967 INFO L506 BasicCegarLoop]: Found error trace [2021-11-25 19:05:30,970 INFO L514 BasicCegarLoop]: trace histogram [5, 4, 4, 3, 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] [2021-11-25 19:05:31,006 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2021-11-25 19:05:31,191 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,7 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 19:05:31,192 INFO L402 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-25 19:05:31,192 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-25 19:05:31,192 INFO L85 PathProgramCache]: Analyzing trace with hash 227774145, now seen corresponding path program 1 times [2021-11-25 19:05:31,192 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-25 19:05:31,192 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1729914890] [2021-11-25 19:05:31,192 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 19:05:31,192 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-25 19:05:31,201 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-11-25 19:05:31,205 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1843365792] [2021-11-25 19:05:31,205 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 19:05:31,205 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 19:05:31,206 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 [2021-11-25 19:05:31,207 INFO L229 MonitoredProcess]: Starting monitored process 8 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-25 19:05:31,226 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2021-11-25 19:05:31,254 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-25 19:05:31,255 INFO L263 TraceCheckSpWp]: Trace formula consists of 149 conjuncts, 4 conjunts are in the unsatisfiable core [2021-11-25 19:05:31,257 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-25 19:05:31,341 INFO L134 CoverageAnalysis]: Checked inductivity of 44 backedges. 14 proven. 0 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2021-11-25 19:05:31,342 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-11-25 19:05:31,342 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-25 19:05:31,342 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1729914890] [2021-11-25 19:05:31,342 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-11-25 19:05:31,342 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1843365792] [2021-11-25 19:05:31,342 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1843365792] provided 1 perfect and 0 imperfect interpolant sequences [2021-11-25 19:05:31,342 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-11-25 19:05:31,342 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2021-11-25 19:05:31,342 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [307151669] [2021-11-25 19:05:31,343 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-11-25 19:05:31,343 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2021-11-25 19:05:31,343 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-25 19:05:31,346 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2021-11-25 19:05:31,346 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2021-11-25 19:05:31,347 INFO L87 Difference]: Start difference. First operand 109 states and 143 transitions. Second operand has 5 states, 5 states have (on average 4.2) internal successors, (21), 5 states have internal predecessors, (21), 3 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2021-11-25 19:05:31,405 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-25 19:05:31,405 INFO L93 Difference]: Finished difference Result 187 states and 255 transitions. [2021-11-25 19:05:31,405 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2021-11-25 19:05:31,406 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 4.2) internal successors, (21), 5 states have internal predecessors, (21), 3 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) Word has length 47 [2021-11-25 19:05:31,406 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-25 19:05:31,407 INFO L225 Difference]: With dead ends: 187 [2021-11-25 19:05:31,408 INFO L226 Difference]: Without dead ends: 138 [2021-11-25 19:05:31,409 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 48 GetRequests, 44 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=12, Invalid=18, Unknown=0, NotChecked=0, Total=30 [2021-11-25 19:05:31,409 INFO L933 BasicCegarLoop]: 31 mSDtfsCounter, 3 mSDsluCounter, 46 mSDsCounter, 0 mSdLazyCounter, 41 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3 SdHoareTripleChecker+Valid, 75 SdHoareTripleChecker+Invalid, 43 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 41 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-11-25 19:05:31,410 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [3 Valid, 75 Invalid, 43 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 41 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-11-25 19:05:31,410 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 138 states. [2021-11-25 19:05:31,441 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 138 to 131. [2021-11-25 19:05:31,442 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 131 states, 78 states have (on average 1.2179487179487178) internal successors, (95), 79 states have internal predecessors, (95), 43 states have call successors, (43), 9 states have call predecessors, (43), 9 states have return successors, (42), 42 states have call predecessors, (42), 42 states have call successors, (42) [2021-11-25 19:05:31,447 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 131 states to 131 states and 180 transitions. [2021-11-25 19:05:31,447 INFO L78 Accepts]: Start accepts. Automaton has 131 states and 180 transitions. Word has length 47 [2021-11-25 19:05:31,447 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-25 19:05:31,447 INFO L470 AbstractCegarLoop]: Abstraction has 131 states and 180 transitions. [2021-11-25 19:05:31,448 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 4.2) internal successors, (21), 5 states have internal predecessors, (21), 3 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2021-11-25 19:05:31,448 INFO L276 IsEmpty]: Start isEmpty. Operand 131 states and 180 transitions. [2021-11-25 19:05:31,450 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 50 [2021-11-25 19:05:31,450 INFO L506 BasicCegarLoop]: Found error trace [2021-11-25 19:05:31,450 INFO L514 BasicCegarLoop]: trace histogram [5, 4, 4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-25 19:05:31,473 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2021-11-25 19:05:31,653 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,8 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 19:05:31,654 INFO L402 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-25 19:05:31,654 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-25 19:05:31,654 INFO L85 PathProgramCache]: Analyzing trace with hash -1330500229, now seen corresponding path program 2 times [2021-11-25 19:05:31,655 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-25 19:05:31,655 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1716500718] [2021-11-25 19:05:31,655 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 19:05:31,655 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-25 19:05:31,664 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-11-25 19:05:31,664 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1806580097] [2021-11-25 19:05:31,664 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2021-11-25 19:05:31,665 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 19:05:31,665 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 [2021-11-25 19:05:31,665 INFO L229 MonitoredProcess]: Starting monitored process 9 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-25 19:05:31,673 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2021-11-25 19:05:31,715 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2021-11-25 19:05:31,715 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-11-25 19:05:31,716 INFO L263 TraceCheckSpWp]: Trace formula consists of 113 conjuncts, 5 conjunts are in the unsatisfiable core [2021-11-25 19:05:31,718 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-25 19:05:31,805 INFO L134 CoverageAnalysis]: Checked inductivity of 47 backedges. 19 proven. 0 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2021-11-25 19:05:31,805 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-11-25 19:05:31,806 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-25 19:05:31,806 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1716500718] [2021-11-25 19:05:31,806 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-11-25 19:05:31,806 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1806580097] [2021-11-25 19:05:31,806 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1806580097] provided 1 perfect and 0 imperfect interpolant sequences [2021-11-25 19:05:31,806 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-11-25 19:05:31,806 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2021-11-25 19:05:31,807 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2065199758] [2021-11-25 19:05:31,807 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-11-25 19:05:31,807 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2021-11-25 19:05:31,807 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-25 19:05:31,808 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2021-11-25 19:05:31,808 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2021-11-25 19:05:31,808 INFO L87 Difference]: Start difference. First operand 131 states and 180 transitions. Second operand has 5 states, 5 states have (on average 5.0) internal successors, (25), 5 states have internal predecessors, (25), 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 19:05:31,933 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-25 19:05:31,933 INFO L93 Difference]: Finished difference Result 215 states and 307 transitions. [2021-11-25 19:05:31,934 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2021-11-25 19:05:31,934 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 5.0) internal successors, (25), 5 states have internal predecessors, (25), 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 49 [2021-11-25 19:05:31,934 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-25 19:05:31,936 INFO L225 Difference]: With dead ends: 215 [2021-11-25 19:05:31,936 INFO L226 Difference]: Without dead ends: 166 [2021-11-25 19:05:31,938 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 51 GetRequests, 46 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 19:05:31,938 INFO L933 BasicCegarLoop]: 43 mSDtfsCounter, 18 mSDsluCounter, 87 mSDsCounter, 0 mSdLazyCounter, 62 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 22 SdHoareTripleChecker+Valid, 127 SdHoareTripleChecker+Invalid, 71 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 62 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2021-11-25 19:05:31,939 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [22 Valid, 127 Invalid, 71 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 62 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2021-11-25 19:05:31,939 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 166 states. [2021-11-25 19:05:31,975 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 166 to 135. [2021-11-25 19:05:31,976 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 135 states, 82 states have (on average 1.1951219512195121) internal successors, (98), 83 states have internal predecessors, (98), 43 states have call successors, (43), 9 states have call predecessors, (43), 9 states have return successors, (42), 42 states have call predecessors, (42), 42 states have call successors, (42) [2021-11-25 19:05:31,977 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 135 states to 135 states and 183 transitions. [2021-11-25 19:05:31,978 INFO L78 Accepts]: Start accepts. Automaton has 135 states and 183 transitions. Word has length 49 [2021-11-25 19:05:31,978 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-25 19:05:31,978 INFO L470 AbstractCegarLoop]: Abstraction has 135 states and 183 transitions. [2021-11-25 19:05:31,978 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 5.0) internal successors, (25), 5 states have internal predecessors, (25), 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 19:05:31,979 INFO L276 IsEmpty]: Start isEmpty. Operand 135 states and 183 transitions. [2021-11-25 19:05:31,980 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 50 [2021-11-25 19:05:31,980 INFO L506 BasicCegarLoop]: Found error trace [2021-11-25 19:05:31,981 INFO L514 BasicCegarLoop]: trace histogram [5, 4, 4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-25 19:05:32,017 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2021-11-25 19:05:32,199 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,9 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 19:05:32,200 INFO L402 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-25 19:05:32,200 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-25 19:05:32,200 INFO L85 PathProgramCache]: Analyzing trace with hash 601289743, now seen corresponding path program 3 times [2021-11-25 19:05:32,200 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-25 19:05:32,200 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1084213864] [2021-11-25 19:05:32,200 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 19:05:32,200 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-25 19:05:32,209 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-11-25 19:05:32,209 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2120191775] [2021-11-25 19:05:32,210 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2021-11-25 19:05:32,210 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 19:05:32,210 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 [2021-11-25 19:05:32,211 INFO L229 MonitoredProcess]: Starting monitored process 10 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-25 19:05:32,224 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2021-11-25 19:05:32,260 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2021-11-25 19:05:32,261 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-11-25 19:05:32,261 INFO L263 TraceCheckSpWp]: Trace formula consists of 134 conjuncts, 8 conjunts are in the unsatisfiable core [2021-11-25 19:05:32,263 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-25 19:05:32,362 INFO L134 CoverageAnalysis]: Checked inductivity of 47 backedges. 16 proven. 5 refuted. 0 times theorem prover too weak. 26 trivial. 0 not checked. [2021-11-25 19:05:32,362 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-11-25 19:05:32,441 INFO L134 CoverageAnalysis]: Checked inductivity of 47 backedges. 16 proven. 5 refuted. 0 times theorem prover too weak. 26 trivial. 0 not checked. [2021-11-25 19:05:32,441 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-25 19:05:32,441 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1084213864] [2021-11-25 19:05:32,441 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-11-25 19:05:32,441 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2120191775] [2021-11-25 19:05:32,442 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2120191775] provided 0 perfect and 2 imperfect interpolant sequences [2021-11-25 19:05:32,442 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [875105305] [2021-11-25 19:05:32,444 INFO L159 IcfgInterpreter]: Started Sifa with 25 locations of interest [2021-11-25 19:05:32,444 INFO L166 IcfgInterpreter]: Building call graph [2021-11-25 19:05:32,444 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2021-11-25 19:05:32,444 INFO L176 IcfgInterpreter]: Starting interpretation [2021-11-25 19:05:32,445 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2021-11-25 19:05:42,391 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2021-11-25 19:05:42,393 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 65 for LOIs [2021-11-25 19:05:42,414 INFO L180 IcfgInterpreter]: Interpretation finished [2021-11-25 19:05:52,455 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '3680#(and (= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond) (= __VERIFIER_assert_~cond 0))' at error location [2021-11-25 19:05:52,455 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2021-11-25 19:05:52,455 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-11-25 19:05:52,455 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 8 [2021-11-25 19:05:52,456 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1704307605] [2021-11-25 19:05:52,456 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-11-25 19:05:52,456 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2021-11-25 19:05:52,456 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-25 19:05:52,457 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2021-11-25 19:05:52,457 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=81, Invalid=569, Unknown=0, NotChecked=0, Total=650 [2021-11-25 19:05:52,457 INFO L87 Difference]: Start difference. First operand 135 states and 183 transitions. Second operand has 8 states, 8 states have (on average 3.25) internal successors, (26), 8 states have internal predecessors, (26), 3 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2021-11-25 19:05:52,815 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-25 19:05:52,816 INFO L93 Difference]: Finished difference Result 215 states and 304 transitions. [2021-11-25 19:05:52,816 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2021-11-25 19:05:52,816 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 3.25) internal successors, (26), 8 states have internal predecessors, (26), 3 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) Word has length 49 [2021-11-25 19:05:52,817 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-25 19:05:52,819 INFO L225 Difference]: With dead ends: 215 [2021-11-25 19:05:52,819 INFO L226 Difference]: Without dead ends: 208 [2021-11-25 19:05:52,820 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 161 GetRequests, 125 SyntacticMatches, 1 SemanticMatches, 35 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 245 ImplicationChecksByTransitivity, 10.2s TimeCoverageRelationStatistics Valid=161, Invalid=1171, Unknown=0, NotChecked=0, Total=1332 [2021-11-25 19:05:52,821 INFO L933 BasicCegarLoop]: 67 mSDtfsCounter, 47 mSDsluCounter, 224 mSDsCounter, 0 mSdLazyCounter, 189 mSolverCounterSat, 75 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 51 SdHoareTripleChecker+Valid, 285 SdHoareTripleChecker+Invalid, 264 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 75 IncrementalHoareTripleChecker+Valid, 189 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2021-11-25 19:05:52,821 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [51 Valid, 285 Invalid, 264 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [75 Valid, 189 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2021-11-25 19:05:52,822 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 208 states. [2021-11-25 19:05:52,862 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 208 to 153. [2021-11-25 19:05:52,863 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 153 states, 92 states have (on average 1.1956521739130435) internal successors, (110), 93 states have internal predecessors, (110), 51 states have call successors, (51), 9 states have call predecessors, (51), 9 states have return successors, (50), 50 states have call predecessors, (50), 50 states have call successors, (50) [2021-11-25 19:05:52,865 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 153 states to 153 states and 211 transitions. [2021-11-25 19:05:52,865 INFO L78 Accepts]: Start accepts. Automaton has 153 states and 211 transitions. Word has length 49 [2021-11-25 19:05:52,865 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-25 19:05:52,865 INFO L470 AbstractCegarLoop]: Abstraction has 153 states and 211 transitions. [2021-11-25 19:05:52,866 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 3.25) internal successors, (26), 8 states have internal predecessors, (26), 3 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2021-11-25 19:05:52,866 INFO L276 IsEmpty]: Start isEmpty. Operand 153 states and 211 transitions. [2021-11-25 19:05:52,867 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 55 [2021-11-25 19:05:52,867 INFO L506 BasicCegarLoop]: Found error trace [2021-11-25 19:05:52,867 INFO L514 BasicCegarLoop]: trace histogram [8, 7, 7, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-25 19:05:52,910 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2021-11-25 19:05:53,095 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2021-11-25 19:05:53,096 INFO L402 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-25 19:05:53,096 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-25 19:05:53,096 INFO L85 PathProgramCache]: Analyzing trace with hash 583515831, now seen corresponding path program 1 times [2021-11-25 19:05:53,096 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-25 19:05:53,096 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1523226430] [2021-11-25 19:05:53,096 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 19:05:53,096 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-25 19:05:53,105 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-11-25 19:05:53,105 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [867557975] [2021-11-25 19:05:53,106 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 19:05:53,106 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 19:05:53,106 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 [2021-11-25 19:05:53,107 INFO L229 MonitoredProcess]: Starting monitored process 11 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-25 19:05:53,112 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2021-11-25 19:05:53,145 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-25 19:05:53,146 INFO L263 TraceCheckSpWp]: Trace formula consists of 148 conjuncts, 19 conjunts are in the unsatisfiable core [2021-11-25 19:05:53,148 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-25 19:05:53,330 INFO L134 CoverageAnalysis]: Checked inductivity of 105 backedges. 15 proven. 5 refuted. 0 times theorem prover too weak. 85 trivial. 0 not checked. [2021-11-25 19:05:53,331 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-11-25 19:05:53,477 INFO L134 CoverageAnalysis]: Checked inductivity of 105 backedges. 14 proven. 0 refuted. 0 times theorem prover too weak. 91 trivial. 0 not checked. [2021-11-25 19:05:53,477 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-25 19:05:53,477 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1523226430] [2021-11-25 19:05:53,477 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-11-25 19:05:53,478 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [867557975] [2021-11-25 19:05:53,478 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [867557975] provided 1 perfect and 1 imperfect interpolant sequences [2021-11-25 19:05:53,478 INFO L186 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2021-11-25 19:05:53,478 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [9] total 10 [2021-11-25 19:05:53,478 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1974747287] [2021-11-25 19:05:53,479 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-11-25 19:05:53,479 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2021-11-25 19:05:53,479 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-25 19:05:53,480 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2021-11-25 19:05:53,480 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=21, Invalid=69, Unknown=0, NotChecked=0, Total=90 [2021-11-25 19:05:53,480 INFO L87 Difference]: Start difference. First operand 153 states and 211 transitions. Second operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2021-11-25 19:05:53,549 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-25 19:05:53,549 INFO L93 Difference]: Finished difference Result 167 states and 222 transitions. [2021-11-25 19:05:53,549 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2021-11-25 19:05:53,549 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) Word has length 54 [2021-11-25 19:05:53,550 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-25 19:05:53,551 INFO L225 Difference]: With dead ends: 167 [2021-11-25 19:05:53,551 INFO L226 Difference]: Without dead ends: 165 [2021-11-25 19:05:53,551 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 107 GetRequests, 96 SyntacticMatches, 2 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 12 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=25, Invalid=85, Unknown=0, NotChecked=0, Total=110 [2021-11-25 19:05:53,552 INFO L933 BasicCegarLoop]: 28 mSDtfsCounter, 9 mSDsluCounter, 67 mSDsCounter, 0 mSdLazyCounter, 47 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 9 SdHoareTripleChecker+Valid, 90 SdHoareTripleChecker+Invalid, 47 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 47 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-11-25 19:05:53,552 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [9 Valid, 90 Invalid, 47 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 47 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-11-25 19:05:53,553 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 165 states. [2021-11-25 19:05:53,590 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 165 to 165. [2021-11-25 19:05:53,591 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 165 states, 101 states have (on average 1.1782178217821782) internal successors, (119), 102 states have internal predecessors, (119), 51 states have call successors, (51), 12 states have call predecessors, (51), 12 states have return successors, (50), 50 states have call predecessors, (50), 50 states have call successors, (50) [2021-11-25 19:05:53,593 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 165 states to 165 states and 220 transitions. [2021-11-25 19:05:53,593 INFO L78 Accepts]: Start accepts. Automaton has 165 states and 220 transitions. Word has length 54 [2021-11-25 19:05:53,593 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-25 19:05:53,593 INFO L470 AbstractCegarLoop]: Abstraction has 165 states and 220 transitions. [2021-11-25 19:05:53,593 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2021-11-25 19:05:53,594 INFO L276 IsEmpty]: Start isEmpty. Operand 165 states and 220 transitions. [2021-11-25 19:05:53,595 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 53 [2021-11-25 19:05:53,595 INFO L506 BasicCegarLoop]: Found error trace [2021-11-25 19:05:53,595 INFO L514 BasicCegarLoop]: trace histogram [5, 4, 4, 4, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-25 19:05:53,620 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2021-11-25 19:05:53,807 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2021-11-25 19:05:53,807 INFO L402 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-25 19:05:53,808 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-25 19:05:53,808 INFO L85 PathProgramCache]: Analyzing trace with hash -1948306734, now seen corresponding path program 2 times [2021-11-25 19:05:53,808 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-25 19:05:53,808 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1944764496] [2021-11-25 19:05:53,808 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 19:05:53,808 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-25 19:05:53,816 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-11-25 19:05:53,816 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [149892601] [2021-11-25 19:05:53,816 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2021-11-25 19:05:53,816 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 19:05:53,817 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 [2021-11-25 19:05:53,817 INFO L229 MonitoredProcess]: Starting monitored process 12 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-25 19:05:53,820 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2021-11-25 19:05:53,872 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2021-11-25 19:05:53,872 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-11-25 19:05:53,873 INFO L263 TraceCheckSpWp]: Trace formula consists of 144 conjuncts, 40 conjunts are in the unsatisfiable core [2021-11-25 19:05:53,875 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-25 19:05:54,391 INFO L134 CoverageAnalysis]: Checked inductivity of 55 backedges. 8 proven. 21 refuted. 0 times theorem prover too weak. 26 trivial. 0 not checked. [2021-11-25 19:05:54,392 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-11-25 19:05:55,084 INFO L134 CoverageAnalysis]: Checked inductivity of 55 backedges. 10 proven. 19 refuted. 0 times theorem prover too weak. 26 trivial. 0 not checked. [2021-11-25 19:05:55,085 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-25 19:05:55,085 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1944764496] [2021-11-25 19:05:55,085 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-11-25 19:05:55,085 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [149892601] [2021-11-25 19:05:55,085 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [149892601] provided 0 perfect and 2 imperfect interpolant sequences [2021-11-25 19:05:55,085 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [20259899] [2021-11-25 19:05:55,087 INFO L159 IcfgInterpreter]: Started Sifa with 24 locations of interest [2021-11-25 19:05:55,087 INFO L166 IcfgInterpreter]: Building call graph [2021-11-25 19:05:55,088 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2021-11-25 19:05:55,088 INFO L176 IcfgInterpreter]: Starting interpretation [2021-11-25 19:05:55,088 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2021-11-25 19:06:02,901 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 39 for LOIs [2021-11-25 19:06:02,909 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 65 for LOIs [2021-11-25 19:06:02,929 INFO L180 IcfgInterpreter]: Interpretation finished [2021-11-25 19:06:16,598 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '5474#(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 19:06:16,598 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2021-11-25 19:06:16,599 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-11-25 19:06:16,599 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13] total 22 [2021-11-25 19:06:16,599 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [151860738] [2021-11-25 19:06:16,599 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-11-25 19:06:16,600 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2021-11-25 19:06:16,600 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-25 19:06:16,600 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2021-11-25 19:06:16,601 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=219, Invalid=1341, Unknown=0, NotChecked=0, Total=1560 [2021-11-25 19:06:16,601 INFO L87 Difference]: Start difference. First operand 165 states and 220 transitions. Second operand has 22 states, 22 states have (on average 2.272727272727273) internal successors, (50), 21 states have internal predecessors, (50), 5 states have call successors, (12), 2 states have call predecessors, (12), 1 states have return successors, (10), 3 states have call predecessors, (10), 3 states have call successors, (10) [2021-11-25 19:06:27,330 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-25 19:06:27,330 INFO L93 Difference]: Finished difference Result 296 states and 407 transitions. [2021-11-25 19:06:27,331 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 25 states. [2021-11-25 19:06:27,331 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 22 states have (on average 2.272727272727273) internal successors, (50), 21 states have internal predecessors, (50), 5 states have call successors, (12), 2 states have call predecessors, (12), 1 states have return successors, (10), 3 states have call predecessors, (10), 3 states have call successors, (10) Word has length 52 [2021-11-25 19:06:27,331 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-25 19:06:27,333 INFO L225 Difference]: With dead ends: 296 [2021-11-25 19:06:27,333 INFO L226 Difference]: Without dead ends: 294 [2021-11-25 19:06:27,335 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 173 GetRequests, 113 SyntacticMatches, 3 SemanticMatches, 57 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 867 ImplicationChecksByTransitivity, 21.3s TimeCoverageRelationStatistics Valid=487, Invalid=2935, Unknown=0, NotChecked=0, Total=3422 [2021-11-25 19:06:27,336 INFO L933 BasicCegarLoop]: 58 mSDtfsCounter, 162 mSDsluCounter, 371 mSDsCounter, 0 mSdLazyCounter, 626 mSolverCounterSat, 245 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 3.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 162 SdHoareTripleChecker+Valid, 417 SdHoareTripleChecker+Invalid, 871 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 245 IncrementalHoareTripleChecker+Valid, 626 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 3.6s IncrementalHoareTripleChecker+Time [2021-11-25 19:06:27,336 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [162 Valid, 417 Invalid, 871 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [245 Valid, 626 Invalid, 0 Unknown, 0 Unchecked, 3.6s Time] [2021-11-25 19:06:27,337 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 294 states. [2021-11-25 19:06:27,403 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 294 to 227. [2021-11-25 19:06:27,404 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 227 states, 140 states have (on average 1.1857142857142857) internal successors, (166), 141 states have internal predecessors, (166), 71 states have call successors, (71), 15 states have call predecessors, (71), 15 states have return successors, (70), 70 states have call predecessors, (70), 70 states have call successors, (70) [2021-11-25 19:06:27,406 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 227 states to 227 states and 307 transitions. [2021-11-25 19:06:27,406 INFO L78 Accepts]: Start accepts. Automaton has 227 states and 307 transitions. Word has length 52 [2021-11-25 19:06:27,406 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-25 19:06:27,407 INFO L470 AbstractCegarLoop]: Abstraction has 227 states and 307 transitions. [2021-11-25 19:06:27,407 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 22 states have (on average 2.272727272727273) internal successors, (50), 21 states have internal predecessors, (50), 5 states have call successors, (12), 2 states have call predecessors, (12), 1 states have return successors, (10), 3 states have call predecessors, (10), 3 states have call successors, (10) [2021-11-25 19:06:27,407 INFO L276 IsEmpty]: Start isEmpty. Operand 227 states and 307 transitions. [2021-11-25 19:06:27,408 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 58 [2021-11-25 19:06:27,408 INFO L506 BasicCegarLoop]: Found error trace [2021-11-25 19:06:27,408 INFO L514 BasicCegarLoop]: trace histogram [7, 6, 6, 3, 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] [2021-11-25 19:06:27,436 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Ended with exit code 0 [2021-11-25 19:06:27,622 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11,12 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 19:06:27,622 INFO L402 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-25 19:06:27,623 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-25 19:06:27,623 INFO L85 PathProgramCache]: Analyzing trace with hash 1501893325, now seen corresponding path program 3 times [2021-11-25 19:06:27,623 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-25 19:06:27,623 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2118599324] [2021-11-25 19:06:27,623 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 19:06:27,623 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-25 19:06:27,642 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-11-25 19:06:27,642 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [262019133] [2021-11-25 19:06:27,642 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2021-11-25 19:06:27,643 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 19:06:27,643 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 [2021-11-25 19:06:27,644 INFO L229 MonitoredProcess]: Starting monitored process 13 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-25 19:06:27,644 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2021-11-25 19:06:27,681 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2021-11-25 19:06:27,682 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-11-25 19:06:27,682 INFO L263 TraceCheckSpWp]: Trace formula consists of 140 conjuncts, 12 conjunts are in the unsatisfiable core [2021-11-25 19:06:27,684 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-25 19:06:27,825 INFO L134 CoverageAnalysis]: Checked inductivity of 86 backedges. 18 proven. 6 refuted. 0 times theorem prover too weak. 62 trivial. 0 not checked. [2021-11-25 19:06:27,826 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-11-25 19:06:27,927 INFO L134 CoverageAnalysis]: Checked inductivity of 86 backedges. 20 proven. 0 refuted. 0 times theorem prover too weak. 66 trivial. 0 not checked. [2021-11-25 19:06:27,927 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-25 19:06:27,927 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2118599324] [2021-11-25 19:06:27,927 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-11-25 19:06:27,927 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [262019133] [2021-11-25 19:06:27,927 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [262019133] provided 1 perfect and 1 imperfect interpolant sequences [2021-11-25 19:06:27,927 INFO L186 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2021-11-25 19:06:27,927 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [8] total 9 [2021-11-25 19:06:27,927 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1301935003] [2021-11-25 19:06:27,928 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-11-25 19:06:27,928 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2021-11-25 19:06:27,928 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-25 19:06:27,928 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2021-11-25 19:06:27,929 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2021-11-25 19:06:27,929 INFO L87 Difference]: Start difference. First operand 227 states and 307 transitions. Second operand has 5 states, 5 states have (on average 4.4) internal successors, (22), 4 states have internal predecessors, (22), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2021-11-25 19:06:28,037 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-25 19:06:28,037 INFO L93 Difference]: Finished difference Result 256 states and 350 transitions. [2021-11-25 19:06:28,037 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2021-11-25 19:06:28,038 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 4.4) internal successors, (22), 4 states have internal predecessors, (22), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) Word has length 57 [2021-11-25 19:06:28,038 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-25 19:06:28,040 INFO L225 Difference]: With dead ends: 256 [2021-11-25 19:06:28,040 INFO L226 Difference]: Without dead ends: 254 [2021-11-25 19:06:28,041 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 113 GetRequests, 104 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 19:06:28,041 INFO L933 BasicCegarLoop]: 28 mSDtfsCounter, 8 mSDsluCounter, 72 mSDsCounter, 0 mSdLazyCounter, 50 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 95 SdHoareTripleChecker+Invalid, 50 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 50 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2021-11-25 19:06:28,042 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [10 Valid, 95 Invalid, 50 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 50 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2021-11-25 19:06:28,043 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 254 states. [2021-11-25 19:06:28,117 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 254 to 249. [2021-11-25 19:06:28,118 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 249 states, 149 states have (on average 1.1946308724832215) internal successors, (178), 150 states have internal predecessors, (178), 83 states have call successors, (83), 16 states have call predecessors, (83), 16 states have return successors, (82), 82 states have call predecessors, (82), 82 states have call successors, (82) [2021-11-25 19:06:28,120 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 249 states to 249 states and 343 transitions. [2021-11-25 19:06:28,121 INFO L78 Accepts]: Start accepts. Automaton has 249 states and 343 transitions. Word has length 57 [2021-11-25 19:06:28,121 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-25 19:06:28,121 INFO L470 AbstractCegarLoop]: Abstraction has 249 states and 343 transitions. [2021-11-25 19:06:28,121 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 4.4) internal successors, (22), 4 states have internal predecessors, (22), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2021-11-25 19:06:28,122 INFO L276 IsEmpty]: Start isEmpty. Operand 249 states and 343 transitions. [2021-11-25 19:06:28,122 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 58 [2021-11-25 19:06:28,123 INFO L506 BasicCegarLoop]: Found error trace [2021-11-25 19:06:28,123 INFO L514 BasicCegarLoop]: trace histogram [6, 5, 5, 4, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-25 19:06:28,159 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Forceful destruction successful, exit code 0 [2021-11-25 19:06:28,343 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable12,13 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 19:06:28,344 INFO L402 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-25 19:06:28,344 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-25 19:06:28,344 INFO L85 PathProgramCache]: Analyzing trace with hash -697498661, now seen corresponding path program 4 times [2021-11-25 19:06:28,344 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-25 19:06:28,344 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [841446462] [2021-11-25 19:06:28,344 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 19:06:28,344 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-25 19:06:28,352 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-11-25 19:06:28,353 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1501365448] [2021-11-25 19:06:28,353 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2021-11-25 19:06:28,353 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 19:06:28,353 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 [2021-11-25 19:06:28,354 INFO L229 MonitoredProcess]: Starting monitored process 14 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-25 19:06:28,376 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2021-11-25 19:06:28,414 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-25 19:06:28,416 INFO L263 TraceCheckSpWp]: Trace formula consists of 180 conjuncts, 56 conjunts are in the unsatisfiable core [2021-11-25 19:06:28,418 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-25 19:06:29,159 INFO L134 CoverageAnalysis]: Checked inductivity of 74 backedges. 10 proven. 22 refuted. 0 times theorem prover too weak. 42 trivial. 0 not checked. [2021-11-25 19:06:29,159 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-11-25 19:06:30,889 INFO L134 CoverageAnalysis]: Checked inductivity of 74 backedges. 14 proven. 18 refuted. 0 times theorem prover too weak. 42 trivial. 0 not checked. [2021-11-25 19:06:30,889 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-25 19:06:30,890 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [841446462] [2021-11-25 19:06:30,890 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-11-25 19:06:30,890 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1501365448] [2021-11-25 19:06:30,890 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1501365448] provided 0 perfect and 2 imperfect interpolant sequences [2021-11-25 19:06:30,890 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [759224497] [2021-11-25 19:06:30,892 INFO L159 IcfgInterpreter]: Started Sifa with 24 locations of interest [2021-11-25 19:06:30,893 INFO L166 IcfgInterpreter]: Building call graph [2021-11-25 19:06:30,893 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2021-11-25 19:06:30,893 INFO L176 IcfgInterpreter]: Starting interpretation [2021-11-25 19:06:30,893 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2021-11-25 19:06:38,368 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 37 for LOIs [2021-11-25 19:06:38,377 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 65 for LOIs [2021-11-25 19:06:38,397 INFO L180 IcfgInterpreter]: Interpretation finished [2021-11-25 19:06:51,815 WARN L838 $PredicateComparison]: unable to prove that (and (<= 0 |c_#NULL.base|) (<= |c_ULTIMATE.start_main_~a~0#1| 2147483647) (let ((.cse0 (= |c_ULTIMATE.start_main_~d~0#1| 1)) (.cse1 (not (= (ite (= (* |c_ULTIMATE.start_main_~b~0#1| |c_ULTIMATE.start_main_~d~0#1|) |c_ULTIMATE.start_main_~v~0#1|) 1 0) 0))) (.cse2 (not (= (ite (= (+ (* |c_ULTIMATE.start_main_~k~0#1| |c_ULTIMATE.start_main_~b~0#1|) |c_ULTIMATE.start_main_~c~0#1|) |c_ULTIMATE.start_main_~a~0#1|) 1 0) 0))) (.cse3 (not (= (ite (= |c_ULTIMATE.start_main_~a~0#1| (+ (* |c_ULTIMATE.start_main_~x~0#1| |c_ULTIMATE.start_main_~p~0#1|) (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~r~0#1|))) 1 0) 0))) (.cse4 (not (= (ite (= |c_ULTIMATE.start_main_~b~0#1| (+ (* |c_ULTIMATE.start_main_~x~0#1| |c_ULTIMATE.start_main_~q~0#1|) (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~s~0#1|))) 1 0) 0)))) (or (and .cse0 .cse1 .cse2 .cse3 .cse4 (= |c_#NULL.offset| 0) (= |c_#NULL.base| 0)) (and .cse0 .cse1 .cse2 (= |c_ULTIMATE.start_main_~k~0#1| 0) .cse3 .cse4))) (<= |c_ULTIMATE.start_main_~x~0#1| 2147483647) (<= |c_ULTIMATE.start_main_~c~0#1| 2147483647) (<= |c_#NULL.offset| 0) (<= 0 (+ |c_ULTIMATE.start_main_~x~0#1| 2147483648)) (<= 1 |c_ULTIMATE.start_main_~d~0#1|) (<= |c_ULTIMATE.start_main_~b~0#1| 2147483647) (<= |c_#NULL.base| 0) (<= |c_ULTIMATE.start_main_~d~0#1| 1) (<= 0 (+ |c_ULTIMATE.start_main_~y~0#1| 2147483648)) (<= |c_ULTIMATE.start_main_~y~0#1| 2147483647) (<= 0 |c_#NULL.offset|) (<= |c_ULTIMATE.start_main_~v~0#1| 2147483647) (<= 0 |c_#StackHeapBarrier|) (< |c_ULTIMATE.start_main_~c~0#1| (* 2 |c_ULTIMATE.start_main_~v~0#1|))) is different from false [2021-11-25 19:06:52,481 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '7834#(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 19:06:52,481 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2021-11-25 19:06:52,481 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-11-25 19:06:52,482 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 13] total 23 [2021-11-25 19:06:52,482 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2101467824] [2021-11-25 19:06:52,482 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-11-25 19:06:52,482 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2021-11-25 19:06:52,483 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-25 19:06:52,483 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2021-11-25 19:06:52,484 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=192, Invalid=1371, Unknown=1, NotChecked=76, Total=1640 [2021-11-25 19:06:52,484 INFO L87 Difference]: Start difference. First operand 249 states and 343 transitions. Second operand has 23 states, 23 states have (on average 2.217391304347826) internal successors, (51), 22 states have internal predecessors, (51), 6 states have call successors, (16), 2 states have call predecessors, (16), 1 states have return successors, (14), 6 states have call predecessors, (14), 6 states have call successors, (14) [2021-11-25 19:07:28,079 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-25 19:07:28,079 INFO L93 Difference]: Finished difference Result 350 states and 483 transitions. [2021-11-25 19:07:28,079 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 31 states. [2021-11-25 19:07:28,080 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 23 states have (on average 2.217391304347826) internal successors, (51), 22 states have internal predecessors, (51), 6 states have call successors, (16), 2 states have call predecessors, (16), 1 states have return successors, (14), 6 states have call predecessors, (14), 6 states have call successors, (14) Word has length 57 [2021-11-25 19:07:28,080 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-25 19:07:28,083 INFO L225 Difference]: With dead ends: 350 [2021-11-25 19:07:28,083 INFO L226 Difference]: Without dead ends: 348 [2021-11-25 19:07:28,087 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 195 GetRequests, 127 SyntacticMatches, 3 SemanticMatches, 65 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 1200 ImplicationChecksByTransitivity, 34.1s TimeCoverageRelationStatistics Valid=638, Invalid=3655, Unknown=1, NotChecked=128, Total=4422 [2021-11-25 19:07:28,087 INFO L933 BasicCegarLoop]: 54 mSDtfsCounter, 186 mSDsluCounter, 396 mSDsCounter, 0 mSdLazyCounter, 809 mSolverCounterSat, 371 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 16.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 186 SdHoareTripleChecker+Valid, 436 SdHoareTripleChecker+Invalid, 1180 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 371 IncrementalHoareTripleChecker+Valid, 809 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 17.0s IncrementalHoareTripleChecker+Time [2021-11-25 19:07:28,093 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [186 Valid, 436 Invalid, 1180 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [371 Valid, 809 Invalid, 0 Unknown, 0 Unchecked, 17.0s Time] [2021-11-25 19:07:28,094 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 348 states. [2021-11-25 19:07:28,178 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 348 to 296. [2021-11-25 19:07:28,179 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 296 states, 177 states have (on average 1.192090395480226) internal successors, (211), 178 states have internal predecessors, (211), 99 states have call successors, (99), 19 states have call predecessors, (99), 19 states have return successors, (98), 98 states have call predecessors, (98), 98 states have call successors, (98) [2021-11-25 19:07:28,181 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 296 states to 296 states and 408 transitions. [2021-11-25 19:07:28,181 INFO L78 Accepts]: Start accepts. Automaton has 296 states and 408 transitions. Word has length 57 [2021-11-25 19:07:28,182 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-25 19:07:28,182 INFO L470 AbstractCegarLoop]: Abstraction has 296 states and 408 transitions. [2021-11-25 19:07:28,182 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 23 states have (on average 2.217391304347826) internal successors, (51), 22 states have internal predecessors, (51), 6 states have call successors, (16), 2 states have call predecessors, (16), 1 states have return successors, (14), 6 states have call predecessors, (14), 6 states have call successors, (14) [2021-11-25 19:07:28,182 INFO L276 IsEmpty]: Start isEmpty. Operand 296 states and 408 transitions. [2021-11-25 19:07:28,183 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 67 [2021-11-25 19:07:28,184 INFO L506 BasicCegarLoop]: Found error trace [2021-11-25 19:07:28,184 INFO L514 BasicCegarLoop]: trace histogram [9, 8, 8, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-25 19:07:28,210 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Forceful destruction successful, exit code 0 [2021-11-25 19:07:28,395 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2021-11-25 19:07:28,396 INFO L402 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-25 19:07:28,396 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-25 19:07:28,396 INFO L85 PathProgramCache]: Analyzing trace with hash 67703573, now seen corresponding path program 1 times [2021-11-25 19:07:28,396 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-25 19:07:28,396 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [874020160] [2021-11-25 19:07:28,396 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 19:07:28,396 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-25 19:07:28,404 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-11-25 19:07:28,404 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [7740117] [2021-11-25 19:07:28,404 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 19:07:28,404 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 19:07:28,404 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 [2021-11-25 19:07:28,407 INFO L229 MonitoredProcess]: Starting monitored process 15 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-25 19:07:28,414 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2021-11-25 19:07:28,456 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-25 19:07:28,457 INFO L263 TraceCheckSpWp]: Trace formula consists of 181 conjuncts, 54 conjunts are in the unsatisfiable core [2021-11-25 19:07:28,460 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-25 19:07:29,212 INFO L134 CoverageAnalysis]: Checked inductivity of 140 backedges. 30 proven. 17 refuted. 0 times theorem prover too weak. 93 trivial. 0 not checked. [2021-11-25 19:07:29,212 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-11-25 19:07:35,547 INFO L134 CoverageAnalysis]: Checked inductivity of 140 backedges. 30 proven. 17 refuted. 0 times theorem prover too weak. 93 trivial. 0 not checked. [2021-11-25 19:07:35,547 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-25 19:07:35,547 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [874020160] [2021-11-25 19:07:35,547 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-11-25 19:07:35,547 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [7740117] [2021-11-25 19:07:35,547 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [7740117] provided 0 perfect and 2 imperfect interpolant sequences [2021-11-25 19:07:35,547 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [307278] [2021-11-25 19:07:35,550 INFO L159 IcfgInterpreter]: Started Sifa with 25 locations of interest [2021-11-25 19:07:35,550 INFO L166 IcfgInterpreter]: Building call graph [2021-11-25 19:07:35,550 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2021-11-25 19:07:35,550 INFO L176 IcfgInterpreter]: Starting interpretation [2021-11-25 19:07:35,551 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2021-11-25 19:07:41,238 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2021-11-25 19:07:41,241 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 65 for LOIs [2021-11-25 19:07:41,261 INFO L180 IcfgInterpreter]: Interpretation finished [2021-11-25 19:08:07,030 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '9327#(and (= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond) (= __VERIFIER_assert_~cond 0))' at error location [2021-11-25 19:08:07,031 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2021-11-25 19:08:07,031 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-11-25 19:08:07,031 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 15] total 24 [2021-11-25 19:08:07,031 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1608736159] [2021-11-25 19:08:07,031 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-11-25 19:08:07,031 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 24 states [2021-11-25 19:08:07,031 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-25 19:08:07,032 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2021-11-25 19:08:07,032 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=180, Invalid=1459, Unknown=1, NotChecked=0, Total=1640 [2021-11-25 19:08:07,032 INFO L87 Difference]: Start difference. First operand 296 states and 408 transitions. Second operand has 24 states, 22 states have (on average 1.9545454545454546) internal successors, (43), 23 states have internal predecessors, (43), 8 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (18), 6 states have call predecessors, (18), 6 states have call successors, (18) [2021-11-25 19:08:18,212 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.08s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2021-11-25 19:09:06,719 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-25 19:09:06,719 INFO L93 Difference]: Finished difference Result 514 states and 737 transitions. [2021-11-25 19:09:06,720 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 52 states. [2021-11-25 19:09:06,720 INFO L78 Accepts]: Start accepts. Automaton has has 24 states, 22 states have (on average 1.9545454545454546) internal successors, (43), 23 states have internal predecessors, (43), 8 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (18), 6 states have call predecessors, (18), 6 states have call successors, (18) Word has length 66 [2021-11-25 19:09:06,720 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-25 19:09:06,724 INFO L225 Difference]: With dead ends: 514 [2021-11-25 19:09:06,724 INFO L226 Difference]: Without dead ends: 506 [2021-11-25 19:09:06,727 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 242 GetRequests, 155 SyntacticMatches, 3 SemanticMatches, 84 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2209 ImplicationChecksByTransitivity, 77.5s TimeCoverageRelationStatistics Valid=1055, Invalid=6238, Unknown=17, NotChecked=0, Total=7310 [2021-11-25 19:09:06,727 INFO L933 BasicCegarLoop]: 42 mSDtfsCounter, 160 mSDsluCounter, 577 mSDsCounter, 0 mSdLazyCounter, 1356 mSolverCounterSat, 393 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 9.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 160 SdHoareTripleChecker+Valid, 599 SdHoareTripleChecker+Invalid, 1749 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 393 IncrementalHoareTripleChecker+Valid, 1356 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 10.0s IncrementalHoareTripleChecker+Time [2021-11-25 19:09:06,728 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [160 Valid, 599 Invalid, 1749 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [393 Valid, 1356 Invalid, 0 Unknown, 0 Unchecked, 10.0s Time] [2021-11-25 19:09:06,729 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 506 states. [2021-11-25 19:09:06,896 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 506 to 469. [2021-11-25 19:09:06,897 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 469 states, 283 states have (on average 1.215547703180212) internal successors, (344), 284 states have internal predecessors, (344), 163 states have call successors, (163), 22 states have call predecessors, (163), 22 states have return successors, (162), 162 states have call predecessors, (162), 162 states have call successors, (162) [2021-11-25 19:09:06,909 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 469 states to 469 states and 669 transitions. [2021-11-25 19:09:06,911 INFO L78 Accepts]: Start accepts. Automaton has 469 states and 669 transitions. Word has length 66 [2021-11-25 19:09:06,911 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-25 19:09:06,912 INFO L470 AbstractCegarLoop]: Abstraction has 469 states and 669 transitions. [2021-11-25 19:09:06,912 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 24 states, 22 states have (on average 1.9545454545454546) internal successors, (43), 23 states have internal predecessors, (43), 8 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (18), 6 states have call predecessors, (18), 6 states have call successors, (18) [2021-11-25 19:09:06,912 INFO L276 IsEmpty]: Start isEmpty. Operand 469 states and 669 transitions. [2021-11-25 19:09:06,916 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 78 [2021-11-25 19:09:06,916 INFO L506 BasicCegarLoop]: Found error trace [2021-11-25 19:09:06,916 INFO L514 BasicCegarLoop]: trace histogram [9, 8, 8, 5, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-25 19:09:06,942 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Ended with exit code 0 [2021-11-25 19:09:07,131 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 15 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2021-11-25 19:09:07,132 INFO L402 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-25 19:09:07,132 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-25 19:09:07,132 INFO L85 PathProgramCache]: Analyzing trace with hash 1639756131, now seen corresponding path program 5 times [2021-11-25 19:09:07,132 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-25 19:09:07,132 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1737093132] [2021-11-25 19:09:07,132 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 19:09:07,132 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-25 19:09:07,140 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-11-25 19:09:07,140 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1988585507] [2021-11-25 19:09:07,140 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2021-11-25 19:09:07,141 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 19:09:07,141 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 [2021-11-25 19:09:07,142 INFO L229 MonitoredProcess]: Starting monitored process 16 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-25 19:09:07,150 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2021-11-25 19:09:07,195 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2021-11-25 19:09:07,195 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-11-25 19:09:07,196 INFO L263 TraceCheckSpWp]: Trace formula consists of 174 conjuncts, 55 conjunts are in the unsatisfiable core [2021-11-25 19:09:07,198 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-25 19:09:07,931 INFO L134 CoverageAnalysis]: Checked inductivity of 168 backedges. 16 proven. 38 refuted. 0 times theorem prover too weak. 114 trivial. 0 not checked. [2021-11-25 19:09:07,931 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-11-25 19:09:09,445 INFO L134 CoverageAnalysis]: Checked inductivity of 168 backedges. 16 proven. 38 refuted. 0 times theorem prover too weak. 114 trivial. 0 not checked. [2021-11-25 19:09:09,445 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-25 19:09:09,445 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1737093132] [2021-11-25 19:09:09,445 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-11-25 19:09:09,445 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1988585507] [2021-11-25 19:09:09,446 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1988585507] provided 0 perfect and 2 imperfect interpolant sequences [2021-11-25 19:09:09,446 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1498767052] [2021-11-25 19:09:09,448 INFO L159 IcfgInterpreter]: Started Sifa with 24 locations of interest [2021-11-25 19:09:09,448 INFO L166 IcfgInterpreter]: Building call graph [2021-11-25 19:09:09,448 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2021-11-25 19:09:09,448 INFO L176 IcfgInterpreter]: Starting interpretation [2021-11-25 19:09:09,448 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2021-11-25 19:09:14,020 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 37 for LOIs [2021-11-25 19:09:14,029 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 65 for LOIs [2021-11-25 19:09:14,048 INFO L180 IcfgInterpreter]: Interpretation finished [2021-11-25 19:09:27,086 WARN L227 SmtUtils]: Spent 5.14s on a formula simplification. DAG size of input: 64 DAG size of output: 63 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2021-11-25 19:09:27,314 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '11473#(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 19:09:27,315 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2021-11-25 19:09:27,315 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-11-25 19:09:27,315 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 15] total 26 [2021-11-25 19:09:27,315 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1538723541] [2021-11-25 19:09:27,315 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-11-25 19:09:27,315 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 26 states [2021-11-25 19:09:27,316 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-25 19:09:27,316 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2021-11-25 19:09:27,317 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=250, Invalid=1642, Unknown=0, NotChecked=0, Total=1892 [2021-11-25 19:09:27,317 INFO L87 Difference]: Start difference. First operand 469 states and 669 transitions. Second operand has 26 states, 26 states have (on average 2.3076923076923075) internal successors, (60), 25 states have internal predecessors, (60), 7 states have call successors, (20), 2 states have call predecessors, (20), 1 states have return successors, (18), 5 states have call predecessors, (18), 5 states have call successors, (18) [2021-11-25 19:10:39,650 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-25 19:10:39,650 INFO L93 Difference]: Finished difference Result 650 states and 934 transitions. [2021-11-25 19:10:39,650 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 52 states. [2021-11-25 19:10:39,650 INFO L78 Accepts]: Start accepts. Automaton has has 26 states, 26 states have (on average 2.3076923076923075) internal successors, (60), 25 states have internal predecessors, (60), 7 states have call successors, (20), 2 states have call predecessors, (20), 1 states have return successors, (18), 5 states have call predecessors, (18), 5 states have call successors, (18) Word has length 77 [2021-11-25 19:10:39,651 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-25 19:10:39,655 INFO L225 Difference]: With dead ends: 650 [2021-11-25 19:10:39,656 INFO L226 Difference]: Without dead ends: 648 [2021-11-25 19:10:39,659 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 275 GetRequests, 186 SyntacticMatches, 1 SemanticMatches, 88 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2555 ImplicationChecksByTransitivity, 70.2s TimeCoverageRelationStatistics Valid=1253, Invalid=6756, Unknown=1, NotChecked=0, Total=8010 [2021-11-25 19:10:39,659 INFO L933 BasicCegarLoop]: 78 mSDtfsCounter, 445 mSDsluCounter, 485 mSDsCounter, 0 mSdLazyCounter, 1164 mSolverCounterSat, 704 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 16.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 445 SdHoareTripleChecker+Valid, 550 SdHoareTripleChecker+Invalid, 1868 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 704 IncrementalHoareTripleChecker+Valid, 1164 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 16.5s IncrementalHoareTripleChecker+Time [2021-11-25 19:10:39,660 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [445 Valid, 550 Invalid, 1868 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [704 Valid, 1164 Invalid, 0 Unknown, 0 Unchecked, 16.5s Time] [2021-11-25 19:10:39,661 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 648 states. [2021-11-25 19:10:39,967 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 648 to 557. [2021-11-25 19:10:39,968 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 557 states, 334 states have (on average 1.218562874251497) internal successors, (407), 335 states have internal predecessors, (407), 199 states have call successors, (199), 23 states have call predecessors, (199), 23 states have return successors, (198), 198 states have call predecessors, (198), 198 states have call successors, (198) [2021-11-25 19:10:39,974 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 557 states to 557 states and 804 transitions. [2021-11-25 19:10:39,975 INFO L78 Accepts]: Start accepts. Automaton has 557 states and 804 transitions. Word has length 77 [2021-11-25 19:10:39,975 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-25 19:10:39,975 INFO L470 AbstractCegarLoop]: Abstraction has 557 states and 804 transitions. [2021-11-25 19:10:39,976 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 26 states, 26 states have (on average 2.3076923076923075) internal successors, (60), 25 states have internal predecessors, (60), 7 states have call successors, (20), 2 states have call predecessors, (20), 1 states have return successors, (18), 5 states have call predecessors, (18), 5 states have call successors, (18) [2021-11-25 19:10:39,976 INFO L276 IsEmpty]: Start isEmpty. Operand 557 states and 804 transitions. [2021-11-25 19:10:39,978 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 94 [2021-11-25 19:10:39,978 INFO L506 BasicCegarLoop]: Found error trace [2021-11-25 19:10:39,978 INFO L514 BasicCegarLoop]: trace histogram [13, 12, 12, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-25 19:10:40,011 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Forceful destruction successful, exit code 0 [2021-11-25 19:10:40,203 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable15,16 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 19:10:40,203 INFO L402 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-25 19:10:40,204 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-25 19:10:40,204 INFO L85 PathProgramCache]: Analyzing trace with hash 448820177, now seen corresponding path program 2 times [2021-11-25 19:10:40,204 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-25 19:10:40,204 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [706433237] [2021-11-25 19:10:40,204 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 19:10:40,204 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-25 19:10:40,221 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-11-25 19:10:40,222 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1295252382] [2021-11-25 19:10:40,222 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2021-11-25 19:10:40,222 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 19:10:40,222 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 [2021-11-25 19:10:40,223 INFO L229 MonitoredProcess]: Starting monitored process 17 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-25 19:10:40,242 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2021-11-25 19:10:40,311 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2021-11-25 19:10:40,312 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-11-25 19:10:40,313 INFO L263 TraceCheckSpWp]: Trace formula consists of 158 conjuncts, 64 conjunts are in the unsatisfiable core [2021-11-25 19:10:40,316 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-25 19:10:41,280 INFO L134 CoverageAnalysis]: Checked inductivity of 321 backedges. 68 proven. 14 refuted. 0 times theorem prover too weak. 239 trivial. 0 not checked. [2021-11-25 19:10:41,280 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-11-25 19:10:42,617 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-25 19:10:42,617 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [706433237] [2021-11-25 19:10:42,617 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-11-25 19:10:42,617 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1295252382] [2021-11-25 19:10:42,617 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1295252382] provided 0 perfect and 1 imperfect interpolant sequences [2021-11-25 19:10:42,618 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1767663092] [2021-11-25 19:10:42,620 INFO L159 IcfgInterpreter]: Started Sifa with 25 locations of interest [2021-11-25 19:10:42,620 INFO L166 IcfgInterpreter]: Building call graph [2021-11-25 19:10:42,620 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2021-11-25 19:10:42,620 INFO L176 IcfgInterpreter]: Starting interpretation [2021-11-25 19:10:42,621 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2021-11-25 19:10:52,314 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2021-11-25 19:10:52,317 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 65 for LOIs [2021-11-25 19:10:52,342 INFO L180 IcfgInterpreter]: Interpretation finished [2021-11-25 19:11:21,520 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '13899#(and (= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond) (= __VERIFIER_assert_~cond 0))' at error location [2021-11-25 19:11:21,520 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2021-11-25 19:11:21,520 INFO L186 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2021-11-25 19:11:21,520 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15] total 15 [2021-11-25 19:11:21,520 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1091921775] [2021-11-25 19:11:21,520 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2021-11-25 19:11:21,521 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2021-11-25 19:11:21,521 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-25 19:11:21,521 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2021-11-25 19:11:21,522 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=149, Invalid=1256, Unknown=1, NotChecked=0, Total=1406 [2021-11-25 19:11:21,522 INFO L87 Difference]: Start difference. First operand 557 states and 804 transitions. Second operand has 15 states, 14 states have (on average 2.2857142857142856) internal successors, (32), 14 states have internal predecessors, (32), 4 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (10), 4 states have call predecessors, (10), 3 states have call successors, (10) [2021-11-25 19:11:22,696 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-25 19:11:22,696 INFO L93 Difference]: Finished difference Result 634 states and 910 transitions. [2021-11-25 19:11:22,696 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2021-11-25 19:11:22,696 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 14 states have (on average 2.2857142857142856) internal successors, (32), 14 states have internal predecessors, (32), 4 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (10), 4 states have call predecessors, (10), 3 states have call successors, (10) Word has length 93 [2021-11-25 19:11:22,697 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-25 19:11:22,702 INFO L225 Difference]: With dead ends: 634 [2021-11-25 19:11:22,703 INFO L226 Difference]: Without dead ends: 627 [2021-11-25 19:11:22,704 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 227 GetRequests, 179 SyntacticMatches, 5 SemanticMatches, 43 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 561 ImplicationChecksByTransitivity, 30.6s TimeCoverageRelationStatistics Valid=217, Invalid=1762, Unknown=1, NotChecked=0, Total=1980 [2021-11-25 19:11:22,705 INFO L933 BasicCegarLoop]: 34 mSDtfsCounter, 79 mSDsluCounter, 287 mSDsCounter, 0 mSdLazyCounter, 645 mSolverCounterSat, 72 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 91 SdHoareTripleChecker+Valid, 307 SdHoareTripleChecker+Invalid, 717 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 72 IncrementalHoareTripleChecker+Valid, 645 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.8s IncrementalHoareTripleChecker+Time [2021-11-25 19:11:22,706 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [91 Valid, 307 Invalid, 717 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [72 Valid, 645 Invalid, 0 Unknown, 0 Unchecked, 0.8s Time] [2021-11-25 19:11:22,707 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 627 states. [2021-11-25 19:11:22,926 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 627 to 609. [2021-11-25 19:11:22,927 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 609 states, 359 states have (on average 1.2200557103064067) internal successors, (438), 361 states have internal predecessors, (438), 223 states have call successors, (223), 26 states have call predecessors, (223), 26 states have return successors, (222), 221 states have call predecessors, (222), 222 states have call successors, (222) [2021-11-25 19:11:22,931 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 609 states to 609 states and 883 transitions. [2021-11-25 19:11:22,931 INFO L78 Accepts]: Start accepts. Automaton has 609 states and 883 transitions. Word has length 93 [2021-11-25 19:11:22,932 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-25 19:11:22,932 INFO L470 AbstractCegarLoop]: Abstraction has 609 states and 883 transitions. [2021-11-25 19:11:22,932 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 14 states have (on average 2.2857142857142856) internal successors, (32), 14 states have internal predecessors, (32), 4 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (10), 4 states have call predecessors, (10), 3 states have call successors, (10) [2021-11-25 19:11:22,932 INFO L276 IsEmpty]: Start isEmpty. Operand 609 states and 883 transitions. [2021-11-25 19:11:22,934 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 97 [2021-11-25 19:11:22,935 INFO L506 BasicCegarLoop]: Found error trace [2021-11-25 19:11:22,935 INFO L514 BasicCegarLoop]: trace histogram [13, 12, 12, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-25 19:11:22,968 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Forceful destruction successful, exit code 0 [2021-11-25 19:11:23,163 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 17 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable16 [2021-11-25 19:11:23,163 INFO L402 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-25 19:11:23,164 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-25 19:11:23,164 INFO L85 PathProgramCache]: Analyzing trace with hash 276561641, now seen corresponding path program 3 times [2021-11-25 19:11:23,164 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-25 19:11:23,164 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2056593448] [2021-11-25 19:11:23,164 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 19:11:23,164 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-25 19:11:23,182 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-11-25 19:11:23,190 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2004111994] [2021-11-25 19:11:23,190 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2021-11-25 19:11:23,190 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 19:11:23,190 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 [2021-11-25 19:11:23,191 INFO L229 MonitoredProcess]: Starting monitored process 18 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-25 19:11:23,211 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Waiting until timeout for monitored process [2021-11-25 19:11:23,268 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2021-11-25 19:11:23,269 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-11-25 19:11:23,271 INFO L263 TraceCheckSpWp]: Trace formula consists of 224 conjuncts, 93 conjunts are in the unsatisfiable core [2021-11-25 19:11:23,274 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-25 19:11:24,424 INFO L134 CoverageAnalysis]: Checked inductivity of 328 backedges. 68 proven. 90 refuted. 0 times theorem prover too weak. 170 trivial. 0 not checked. [2021-11-25 19:11:24,425 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-11-25 19:12:34,740 INFO L134 CoverageAnalysis]: Checked inductivity of 328 backedges. 87 proven. 67 refuted. 0 times theorem prover too weak. 174 trivial. 0 not checked. [2021-11-25 19:12:34,741 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-25 19:12:34,741 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2056593448] [2021-11-25 19:12:34,741 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-11-25 19:12:34,741 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2004111994] [2021-11-25 19:12:34,741 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2004111994] provided 0 perfect and 2 imperfect interpolant sequences [2021-11-25 19:12:34,742 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1001103589] [2021-11-25 19:12:34,744 INFO L159 IcfgInterpreter]: Started Sifa with 25 locations of interest [2021-11-25 19:12:34,744 INFO L166 IcfgInterpreter]: Building call graph [2021-11-25 19:12:34,744 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2021-11-25 19:12:34,744 INFO L176 IcfgInterpreter]: Starting interpretation [2021-11-25 19:12:34,745 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2021-11-25 19:12:40,713 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2021-11-25 19:12:40,716 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 65 for LOIs [2021-11-25 19:12:40,740 INFO L180 IcfgInterpreter]: Interpretation finished [2021-11-25 19:13:44,764 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '16510#(and (= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond) (= __VERIFIER_assert_~cond 0))' at error location [2021-11-25 19:13:44,764 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2021-11-25 19:13:44,764 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-11-25 19:13:44,764 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 16] total 29 [2021-11-25 19:13:44,764 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [485098919] [2021-11-25 19:13:44,764 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-11-25 19:13:44,765 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 29 states [2021-11-25 19:13:44,765 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-25 19:13:44,765 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 29 interpolants. [2021-11-25 19:13:44,766 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=238, Invalid=1824, Unknown=8, NotChecked=0, Total=2070 [2021-11-25 19:13:44,766 INFO L87 Difference]: Start difference. First operand 609 states and 883 transitions. Second operand has 29 states, 25 states have (on average 2.4) internal successors, (60), 25 states have internal predecessors, (60), 12 states have call successors, (28), 2 states have call predecessors, (28), 2 states have return successors, (26), 10 states have call predecessors, (26), 10 states have call successors, (26) [2021-11-25 19:13:49,273 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 19:13:51,332 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 19:14:23,185 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 19:14:25,924 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2021-11-25 19:14:29,431 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2021-11-25 19:14:55,668 WARN L227 SmtUtils]: Spent 7.30s on a formula simplification that was a NOOP. DAG size: 73 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2021-11-25 19:14:58,586 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 19:15:14,460 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 19:15:16,465 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 19:15:36,319 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 19:15:41,504 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-25 19:15:41,504 INFO L93 Difference]: Finished difference Result 742 states and 1066 transitions. [2021-11-25 19:15:41,505 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 46 states. [2021-11-25 19:15:41,505 INFO L78 Accepts]: Start accepts. Automaton has has 29 states, 25 states have (on average 2.4) internal successors, (60), 25 states have internal predecessors, (60), 12 states have call successors, (28), 2 states have call predecessors, (28), 2 states have return successors, (26), 10 states have call predecessors, (26), 10 states have call successors, (26) Word has length 96 [2021-11-25 19:15:41,505 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-25 19:15:41,510 INFO L225 Difference]: With dead ends: 742 [2021-11-25 19:15:41,510 INFO L226 Difference]: Without dead ends: 734 [2021-11-25 19:15:41,513 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 339 GetRequests, 259 SyntacticMatches, 4 SemanticMatches, 76 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1665 ImplicationChecksByTransitivity, 154.0s TimeCoverageRelationStatistics Valid=871, Invalid=5102, Unknown=33, NotChecked=0, Total=6006 [2021-11-25 19:15:41,514 INFO L933 BasicCegarLoop]: 44 mSDtfsCounter, 226 mSDsluCounter, 762 mSDsCounter, 0 mSdLazyCounter, 2119 mSolverCounterSat, 537 mSolverCounterUnsat, 8 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 30.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 238 SdHoareTripleChecker+Valid, 783 SdHoareTripleChecker+Invalid, 2664 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 537 IncrementalHoareTripleChecker+Valid, 2119 IncrementalHoareTripleChecker+Invalid, 8 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 30.4s IncrementalHoareTripleChecker+Time [2021-11-25 19:15:41,514 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [238 Valid, 783 Invalid, 2664 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [537 Valid, 2119 Invalid, 8 Unknown, 0 Unchecked, 30.4s Time] [2021-11-25 19:15:41,515 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 734 states. [2021-11-25 19:15:41,825 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 734 to 676. [2021-11-25 19:15:41,827 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 676 states, 398 states have (on average 1.2236180904522613) internal successors, (487), 399 states have internal predecessors, (487), 247 states have call successors, (247), 30 states have call predecessors, (247), 30 states have return successors, (246), 246 states have call predecessors, (246), 246 states have call successors, (246) [2021-11-25 19:15:41,832 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 676 states to 676 states and 980 transitions. [2021-11-25 19:15:41,832 INFO L78 Accepts]: Start accepts. Automaton has 676 states and 980 transitions. Word has length 96 [2021-11-25 19:15:41,832 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-25 19:15:41,833 INFO L470 AbstractCegarLoop]: Abstraction has 676 states and 980 transitions. [2021-11-25 19:15:41,833 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 29 states, 25 states have (on average 2.4) internal successors, (60), 25 states have internal predecessors, (60), 12 states have call successors, (28), 2 states have call predecessors, (28), 2 states have return successors, (26), 10 states have call predecessors, (26), 10 states have call successors, (26) [2021-11-25 19:15:41,833 INFO L276 IsEmpty]: Start isEmpty. Operand 676 states and 980 transitions. [2021-11-25 19:15:41,836 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 102 [2021-11-25 19:15:41,836 INFO L506 BasicCegarLoop]: Found error trace [2021-11-25 19:15:41,836 INFO L514 BasicCegarLoop]: trace histogram [13, 12, 12, 5, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-25 19:15:41,884 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Forceful destruction successful, exit code 0 [2021-11-25 19:15:42,051 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 18 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable17 [2021-11-25 19:15:42,052 INFO L402 AbstractCegarLoop]: === Iteration 19 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-25 19:15:42,052 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-25 19:15:42,052 INFO L85 PathProgramCache]: Analyzing trace with hash -2060320742, now seen corresponding path program 4 times [2021-11-25 19:15:42,052 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-25 19:15:42,052 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [421483781] [2021-11-25 19:15:42,052 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 19:15:42,053 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-25 19:15:42,069 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-11-25 19:15:42,069 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1896610396] [2021-11-25 19:15:42,069 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2021-11-25 19:15:42,069 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 19:15:42,070 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 [2021-11-25 19:15:42,070 INFO L229 MonitoredProcess]: Starting monitored process 19 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-25 19:15:42,090 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Waiting until timeout for monitored process [2021-11-25 19:15:42,145 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-25 19:15:42,148 INFO L263 TraceCheckSpWp]: Trace formula consists of 273 conjuncts, 86 conjunts are in the unsatisfiable core [2021-11-25 19:15:42,151 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-25 19:15:43,320 INFO L134 CoverageAnalysis]: Checked inductivity of 344 backedges. 50 proven. 61 refuted. 0 times theorem prover too weak. 233 trivial. 0 not checked. [2021-11-25 19:15:43,320 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-11-25 19:15:45,305 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-25 19:15:45,305 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [421483781] [2021-11-25 19:15:45,305 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-11-25 19:15:45,305 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1896610396] [2021-11-25 19:15:45,305 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1896610396] provided 0 perfect and 1 imperfect interpolant sequences [2021-11-25 19:15:45,305 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1273508582] [2021-11-25 19:15:45,307 INFO L159 IcfgInterpreter]: Started Sifa with 25 locations of interest [2021-11-25 19:15:45,307 INFO L166 IcfgInterpreter]: Building call graph [2021-11-25 19:15:45,307 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2021-11-25 19:15:45,307 INFO L176 IcfgInterpreter]: Starting interpretation [2021-11-25 19:15:45,307 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2021-11-25 19:15:54,324 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2021-11-25 19:15:54,328 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 65 for LOIs [2021-11-25 19:15:54,348 INFO L180 IcfgInterpreter]: Interpretation finished [2021-11-25 19:16:15,724 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '19264#(and (= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond) (= __VERIFIER_assert_~cond 0))' at error location [2021-11-25 19:16:15,725 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2021-11-25 19:16:15,725 INFO L186 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2021-11-25 19:16:15,725 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [20] total 20 [2021-11-25 19:16:15,725 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [668342438] [2021-11-25 19:16:15,725 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2021-11-25 19:16:15,725 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2021-11-25 19:16:15,725 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-25 19:16:15,726 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2021-11-25 19:16:15,726 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=138, Invalid=1502, Unknown=0, NotChecked=0, Total=1640 [2021-11-25 19:16:15,726 INFO L87 Difference]: Start difference. First operand 676 states and 980 transitions. Second operand has 20 states, 19 states have (on average 2.1578947368421053) internal successors, (41), 19 states have internal predecessors, (41), 6 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (14), 5 states have call predecessors, (14), 5 states have call successors, (14) [2021-11-25 19:16:18,425 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-25 19:16:18,426 INFO L93 Difference]: Finished difference Result 799 states and 1150 transitions. [2021-11-25 19:16:18,426 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2021-11-25 19:16:18,426 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 19 states have (on average 2.1578947368421053) internal successors, (41), 19 states have internal predecessors, (41), 6 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (14), 5 states have call predecessors, (14), 5 states have call successors, (14) Word has length 101 [2021-11-25 19:16:18,427 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-25 19:16:18,432 INFO L225 Difference]: With dead ends: 799 [2021-11-25 19:16:18,432 INFO L226 Difference]: Without dead ends: 796 [2021-11-25 19:16:18,433 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 235 GetRequests, 180 SyntacticMatches, 5 SemanticMatches, 50 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 606 ImplicationChecksByTransitivity, 24.8s TimeCoverageRelationStatistics Valid=213, Invalid=2439, Unknown=0, NotChecked=0, Total=2652 [2021-11-25 19:16:18,434 INFO L933 BasicCegarLoop]: 51 mSDtfsCounter, 97 mSDsluCounter, 631 mSDsCounter, 0 mSdLazyCounter, 1290 mSolverCounterSat, 117 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 113 SdHoareTripleChecker+Valid, 665 SdHoareTripleChecker+Invalid, 1407 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 117 IncrementalHoareTripleChecker+Valid, 1290 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.0s IncrementalHoareTripleChecker+Time [2021-11-25 19:16:18,435 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [113 Valid, 665 Invalid, 1407 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [117 Valid, 1290 Invalid, 0 Unknown, 0 Unchecked, 1.0s Time] [2021-11-25 19:16:18,436 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 796 states. [2021-11-25 19:16:18,792 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 796 to 778. [2021-11-25 19:16:18,793 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 778 states, 453 states have (on average 1.2251655629139073) internal successors, (555), 454 states have internal predecessors, (555), 287 states have call successors, (287), 37 states have call predecessors, (287), 37 states have return successors, (286), 286 states have call predecessors, (286), 286 states have call successors, (286) [2021-11-25 19:16:18,797 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 778 states to 778 states and 1128 transitions. [2021-11-25 19:16:18,797 INFO L78 Accepts]: Start accepts. Automaton has 778 states and 1128 transitions. Word has length 101 [2021-11-25 19:16:18,798 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-25 19:16:18,798 INFO L470 AbstractCegarLoop]: Abstraction has 778 states and 1128 transitions. [2021-11-25 19:16:18,798 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 19 states have (on average 2.1578947368421053) internal successors, (41), 19 states have internal predecessors, (41), 6 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (14), 5 states have call predecessors, (14), 5 states have call successors, (14) [2021-11-25 19:16:18,798 INFO L276 IsEmpty]: Start isEmpty. Operand 778 states and 1128 transitions. [2021-11-25 19:16:18,800 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 105 [2021-11-25 19:16:18,800 INFO L506 BasicCegarLoop]: Found error trace [2021-11-25 19:16:18,800 INFO L514 BasicCegarLoop]: trace histogram [15, 14, 14, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-25 19:16:18,820 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Forceful destruction successful, exit code 0 [2021-11-25 19:16:19,000 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable18,19 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 19:16:19,001 INFO L402 AbstractCegarLoop]: === Iteration 20 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-25 19:16:19,001 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-25 19:16:19,001 INFO L85 PathProgramCache]: Analyzing trace with hash -1508635023, now seen corresponding path program 1 times [2021-11-25 19:16:19,001 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-25 19:16:19,001 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [393136477] [2021-11-25 19:16:19,001 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 19:16:19,002 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-25 19:16:19,008 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-11-25 19:16:19,009 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [706258403] [2021-11-25 19:16:19,009 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 19:16:19,009 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 19:16:19,009 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 [2021-11-25 19:16:19,010 INFO L229 MonitoredProcess]: Starting monitored process 20 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-25 19:16:19,017 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Waiting until timeout for monitored process [2021-11-25 19:16:19,064 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-25 19:16:19,065 INFO L263 TraceCheckSpWp]: Trace formula consists of 257 conjuncts, 26 conjunts are in the unsatisfiable core [2021-11-25 19:16:19,067 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-25 19:16:19,330 INFO L134 CoverageAnalysis]: Checked inductivity of 439 backedges. 91 proven. 17 refuted. 0 times theorem prover too weak. 331 trivial. 0 not checked. [2021-11-25 19:16:19,330 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-11-25 19:16:19,541 INFO L134 CoverageAnalysis]: Checked inductivity of 439 backedges. 85 proven. 8 refuted. 0 times theorem prover too weak. 346 trivial. 0 not checked. [2021-11-25 19:16:19,541 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-25 19:16:19,541 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [393136477] [2021-11-25 19:16:19,541 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-11-25 19:16:19,541 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [706258403] [2021-11-25 19:16:19,541 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [706258403] provided 0 perfect and 2 imperfect interpolant sequences [2021-11-25 19:16:19,542 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [399846277] [2021-11-25 19:16:19,543 INFO L159 IcfgInterpreter]: Started Sifa with 24 locations of interest [2021-11-25 19:16:19,543 INFO L166 IcfgInterpreter]: Building call graph [2021-11-25 19:16:19,544 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2021-11-25 19:16:19,544 INFO L176 IcfgInterpreter]: Starting interpretation [2021-11-25 19:16:19,544 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2021-11-25 19:16:26,030 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 37 for LOIs [2021-11-25 19:16:26,039 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 65 for LOIs [2021-11-25 19:16:26,059 INFO L180 IcfgInterpreter]: Interpretation finished [2021-11-25 19:16:34,423 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '22449#(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 19:16:34,424 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2021-11-25 19:16:34,424 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-11-25 19:16:34,424 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 8] total 13 [2021-11-25 19:16:34,424 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1578216762] [2021-11-25 19:16:34,425 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-11-25 19:16:34,425 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2021-11-25 19:16:34,425 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-25 19:16:34,426 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2021-11-25 19:16:34,426 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=127, Invalid=803, Unknown=0, NotChecked=0, Total=930 [2021-11-25 19:16:34,426 INFO L87 Difference]: Start difference. First operand 778 states and 1128 transitions. Second operand has 13 states, 13 states have (on average 3.1538461538461537) internal successors, (41), 12 states have internal predecessors, (41), 5 states have call successors, (22), 2 states have call predecessors, (22), 2 states have return successors, (21), 7 states have call predecessors, (21), 5 states have call successors, (21) [2021-11-25 19:16:35,392 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-25 19:16:35,392 INFO L93 Difference]: Finished difference Result 1006 states and 1483 transitions. [2021-11-25 19:16:35,393 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2021-11-25 19:16:35,393 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 3.1538461538461537) internal successors, (41), 12 states have internal predecessors, (41), 5 states have call successors, (22), 2 states have call predecessors, (22), 2 states have return successors, (21), 7 states have call predecessors, (21), 5 states have call successors, (21) Word has length 104 [2021-11-25 19:16:35,393 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-25 19:16:35,408 INFO L225 Difference]: With dead ends: 1006 [2021-11-25 19:16:35,409 INFO L226 Difference]: Without dead ends: 1004 [2021-11-25 19:16:35,410 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 317 GetRequests, 282 SyntacticMatches, 1 SemanticMatches, 34 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 352 ImplicationChecksByTransitivity, 8.5s TimeCoverageRelationStatistics Valid=164, Invalid=1096, Unknown=0, NotChecked=0, Total=1260 [2021-11-25 19:16:35,411 INFO L933 BasicCegarLoop]: 26 mSDtfsCounter, 22 mSDsluCounter, 160 mSDsCounter, 0 mSdLazyCounter, 274 mSolverCounterSat, 41 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 25 SdHoareTripleChecker+Valid, 174 SdHoareTripleChecker+Invalid, 315 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 41 IncrementalHoareTripleChecker+Valid, 274 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2021-11-25 19:16:35,411 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [25 Valid, 174 Invalid, 315 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [41 Valid, 274 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2021-11-25 19:16:35,412 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1004 states. [2021-11-25 19:16:35,853 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1004 to 758. [2021-11-25 19:16:35,855 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 758 states, 446 states have (on average 1.2174887892376682) internal successors, (543), 447 states have internal predecessors, (543), 271 states have call successors, (271), 40 states have call predecessors, (271), 40 states have return successors, (270), 270 states have call predecessors, (270), 270 states have call successors, (270) [2021-11-25 19:16:35,860 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 758 states to 758 states and 1084 transitions. [2021-11-25 19:16:35,860 INFO L78 Accepts]: Start accepts. Automaton has 758 states and 1084 transitions. Word has length 104 [2021-11-25 19:16:35,861 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-25 19:16:35,861 INFO L470 AbstractCegarLoop]: Abstraction has 758 states and 1084 transitions. [2021-11-25 19:16:35,861 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 3.1538461538461537) internal successors, (41), 12 states have internal predecessors, (41), 5 states have call successors, (22), 2 states have call predecessors, (22), 2 states have return successors, (21), 7 states have call predecessors, (21), 5 states have call successors, (21) [2021-11-25 19:16:35,861 INFO L276 IsEmpty]: Start isEmpty. Operand 758 states and 1084 transitions. [2021-11-25 19:16:35,864 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 105 [2021-11-25 19:16:35,864 INFO L506 BasicCegarLoop]: Found error trace [2021-11-25 19:16:35,864 INFO L514 BasicCegarLoop]: trace histogram [14, 13, 13, 5, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-25 19:16:35,901 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Forceful destruction successful, exit code 0 [2021-11-25 19:16:36,079 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable19,20 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 19:16:36,079 INFO L402 AbstractCegarLoop]: === Iteration 21 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-25 19:16:36,080 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-25 19:16:36,080 INFO L85 PathProgramCache]: Analyzing trace with hash 1852640491, now seen corresponding path program 2 times [2021-11-25 19:16:36,080 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-25 19:16:36,080 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2035504844] [2021-11-25 19:16:36,080 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 19:16:36,080 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-25 19:16:36,088 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-11-25 19:16:36,088 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [713421771] [2021-11-25 19:16:36,088 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2021-11-25 19:16:36,089 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 19:16:36,089 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 [2021-11-25 19:16:36,093 INFO L229 MonitoredProcess]: Starting monitored process 21 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-25 19:16:36,098 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_8b883fc3-6d9b-4be8-82c8-2c7aabad2fa3/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Waiting until timeout for monitored process [2021-11-25 19:16:36,173 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2021-11-25 19:16:36,173 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-11-25 19:16:36,175 INFO L263 TraceCheckSpWp]: Trace formula consists of 198 conjuncts, 85 conjunts are in the unsatisfiable core [2021-11-25 19:16:36,177 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-25 19:16:37,665 INFO L134 CoverageAnalysis]: Checked inductivity of 395 backedges. 90 proven. 57 refuted. 0 times theorem prover too weak. 248 trivial. 0 not checked. [2021-11-25 19:16:37,666 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-11-25 19:16:47,896 INFO L134 CoverageAnalysis]: Checked inductivity of 395 backedges. 91 proven. 56 refuted. 0 times theorem prover too weak. 248 trivial. 0 not checked. [2021-11-25 19:16:47,896 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-25 19:16:47,897 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2035504844] [2021-11-25 19:16:47,897 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-11-25 19:16:47,897 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [713421771] [2021-11-25 19:16:47,897 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [713421771] provided 0 perfect and 2 imperfect interpolant sequences [2021-11-25 19:16:47,897 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [375265461] [2021-11-25 19:16:47,899 INFO L159 IcfgInterpreter]: Started Sifa with 24 locations of interest [2021-11-25 19:16:47,899 INFO L166 IcfgInterpreter]: Building call graph [2021-11-25 19:16:47,899 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2021-11-25 19:16:47,900 INFO L176 IcfgInterpreter]: Starting interpretation [2021-11-25 19:16:47,900 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2021-11-25 19:16:55,788 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 37 for LOIs [2021-11-25 19:16:55,796 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 65 for LOIs [2021-11-25 19:16:55,815 INFO L180 IcfgInterpreter]: Interpretation finished [2021-11-25 19:17:30,374 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '25947#(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 19:17:30,374 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2021-11-25 19:17:30,374 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-11-25 19:17:30,374 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 20] total 35 [2021-11-25 19:17:30,374 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1737199549] [2021-11-25 19:17:30,374 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-11-25 19:17:30,375 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 35 states [2021-11-25 19:17:30,375 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-25 19:17:30,375 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 35 interpolants. [2021-11-25 19:17:30,376 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=385, Invalid=2366, Unknown=5, NotChecked=0, Total=2756 [2021-11-25 19:17:30,376 INFO L87 Difference]: Start difference. First operand 758 states and 1084 transitions. Second operand has 35 states, 33 states have (on average 2.121212121212121) internal successors, (70), 32 states have internal predecessors, (70), 12 states have call successors, (32), 2 states have call predecessors, (32), 2 states have return successors, (30), 11 states have call predecessors, (30), 10 states have call successors, (30) [2021-11-25 19:17:44,632 WARN L227 SmtUtils]: Spent 7.79s on a formula simplification. DAG size of input: 68 DAG size of output: 67 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2021-11-25 19:17:48,148 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2021-11-25 19:17:58,150 WARN L227 SmtUtils]: Spent 7.41s on a formula simplification. DAG size of input: 72 DAG size of output: 69 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate)