./Ultimate.py --spec ../../sv-benchmarks/c/properties/unreach-call.prp --file ../../sv-benchmarks/c/combinations/Problem05_label42+token_ring.15.cil.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 0f8a17c6 Calling Ultimate with: /usr/bin/java -Dosgi.configuration.area=/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0b5144a0-1643-4e1f-a076-c0786a462db5/bin/utaipan-UbGMyvGFUs/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0b5144a0-1643-4e1f-a076-c0786a462db5/bin/utaipan-UbGMyvGFUs/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0b5144a0-1643-4e1f-a076-c0786a462db5/bin/utaipan-UbGMyvGFUs/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0b5144a0-1643-4e1f-a076-c0786a462db5/bin/utaipan-UbGMyvGFUs/config/TaipanReach.xml -i ../../sv-benchmarks/c/combinations/Problem05_label42+token_ring.15.cil.c -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0b5144a0-1643-4e1f-a076-c0786a462db5/bin/utaipan-UbGMyvGFUs/config/svcomp-Reach-32bit-Taipan_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0b5144a0-1643-4e1f-a076-c0786a462db5/bin/utaipan-UbGMyvGFUs --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 4859a4cdb98a3caca502aed15b30b6d563e2037c3c786a209b1853d003f6e66c --- Real Ultimate output --- This is Ultimate 0.2.1-dev-0f8a17c [2021-11-19 14:03:15,364 INFO L177 SettingsManager]: Resetting all preferences to default values... [2021-11-19 14:03:15,367 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2021-11-19 14:03:15,396 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2021-11-19 14:03:15,397 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2021-11-19 14:03:15,399 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2021-11-19 14:03:15,401 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2021-11-19 14:03:15,403 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2021-11-19 14:03:15,406 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2021-11-19 14:03:15,407 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2021-11-19 14:03:15,408 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2021-11-19 14:03:15,410 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2021-11-19 14:03:15,410 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2021-11-19 14:03:15,412 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2021-11-19 14:03:15,413 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2021-11-19 14:03:15,415 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2021-11-19 14:03:15,416 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2021-11-19 14:03:15,417 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2021-11-19 14:03:15,419 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2021-11-19 14:03:15,422 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2021-11-19 14:03:15,424 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2021-11-19 14:03:15,425 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2021-11-19 14:03:15,427 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2021-11-19 14:03:15,428 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2021-11-19 14:03:15,432 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2021-11-19 14:03:15,433 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2021-11-19 14:03:15,433 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2021-11-19 14:03:15,434 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2021-11-19 14:03:15,435 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2021-11-19 14:03:15,436 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2021-11-19 14:03:15,437 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2021-11-19 14:03:15,438 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2021-11-19 14:03:15,439 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2021-11-19 14:03:15,440 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2021-11-19 14:03:15,441 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2021-11-19 14:03:15,442 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2021-11-19 14:03:15,443 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2021-11-19 14:03:15,443 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2021-11-19 14:03:15,443 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2021-11-19 14:03:15,444 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2021-11-19 14:03:15,445 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2021-11-19 14:03:15,446 INFO L101 SettingsManager]: Beginning loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0b5144a0-1643-4e1f-a076-c0786a462db5/bin/utaipan-UbGMyvGFUs/config/svcomp-Reach-32bit-Taipan_Default.epf [2021-11-19 14:03:15,472 INFO L113 SettingsManager]: Loading preferences was successful [2021-11-19 14:03:15,473 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2021-11-19 14:03:15,473 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2021-11-19 14:03:15,474 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2021-11-19 14:03:15,474 INFO L138 SettingsManager]: * User list type=DISABLED [2021-11-19 14:03:15,474 INFO L136 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2021-11-19 14:03:15,475 INFO L138 SettingsManager]: * Explicit value domain=true [2021-11-19 14:03:15,475 INFO L138 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2021-11-19 14:03:15,475 INFO L138 SettingsManager]: * Octagon Domain=false [2021-11-19 14:03:15,476 INFO L138 SettingsManager]: * Abstract domain=CompoundDomain [2021-11-19 14:03:15,476 INFO L138 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2021-11-19 14:03:15,476 INFO L138 SettingsManager]: * Use the RCFG-of-the-future interface=true [2021-11-19 14:03:15,476 INFO L138 SettingsManager]: * Interval Domain=false [2021-11-19 14:03:15,477 INFO L136 SettingsManager]: Preferences of Sifa differ from their defaults: [2021-11-19 14:03:15,477 INFO L138 SettingsManager]: * Call Summarizer=TopInputCallSummarizer [2021-11-19 14:03:15,477 INFO L138 SettingsManager]: * Simplification Technique=SIMPLIFY_QUICK [2021-11-19 14:03:15,478 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2021-11-19 14:03:15,479 INFO L138 SettingsManager]: * sizeof long=4 [2021-11-19 14:03:15,479 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2021-11-19 14:03:15,479 INFO L138 SettingsManager]: * sizeof POINTER=4 [2021-11-19 14:03:15,480 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2021-11-19 14:03:15,480 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2021-11-19 14:03:15,480 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2021-11-19 14:03:15,480 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2021-11-19 14:03:15,481 INFO L138 SettingsManager]: * Adapt memory model on pointer casts if necessary=true [2021-11-19 14:03:15,481 INFO L138 SettingsManager]: * sizeof long double=12 [2021-11-19 14:03:15,481 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2021-11-19 14:03:15,482 INFO L138 SettingsManager]: * Use constant arrays=true [2021-11-19 14:03:15,482 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2021-11-19 14:03:15,482 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2021-11-19 14:03:15,483 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2021-11-19 14:03:15,483 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2021-11-19 14:03:15,483 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2021-11-19 14:03:15,484 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2021-11-19 14:03:15,484 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2021-11-19 14:03:15,484 INFO L138 SettingsManager]: * Trace refinement strategy=SIFA_TAIPAN [2021-11-19 14:03:15,484 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2021-11-19 14:03:15,485 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2021-11-19 14:03:15,485 INFO L138 SettingsManager]: * Trace refinement exception blacklist=NONE [2021-11-19 14:03:15,485 INFO L138 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2021-11-19 14:03:15,486 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_0b5144a0-1643-4e1f-a076-c0786a462db5/bin/utaipan-UbGMyvGFUs/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_0b5144a0-1643-4e1f-a076-c0786a462db5/bin/utaipan-UbGMyvGFUs 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 -> 4859a4cdb98a3caca502aed15b30b6d563e2037c3c786a209b1853d003f6e66c [2021-11-19 14:03:15,765 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2021-11-19 14:03:15,807 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2021-11-19 14:03:15,810 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2021-11-19 14:03:15,812 INFO L271 PluginConnector]: Initializing CDTParser... [2021-11-19 14:03:15,812 INFO L275 PluginConnector]: CDTParser initialized [2021-11-19 14:03:15,814 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0b5144a0-1643-4e1f-a076-c0786a462db5/bin/utaipan-UbGMyvGFUs/../../sv-benchmarks/c/combinations/Problem05_label42+token_ring.15.cil.c [2021-11-19 14:03:15,883 INFO L220 CDTParser]: Created temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0b5144a0-1643-4e1f-a076-c0786a462db5/bin/utaipan-UbGMyvGFUs/data/e9d02391d/f58d0f5f5e094f478c2c5f763a0f0859/FLAG751fed30b [2021-11-19 14:03:16,921 INFO L306 CDTParser]: Found 1 translation units. [2021-11-19 14:03:16,922 INFO L160 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0b5144a0-1643-4e1f-a076-c0786a462db5/sv-benchmarks/c/combinations/Problem05_label42+token_ring.15.cil.c [2021-11-19 14:03:16,970 INFO L349 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0b5144a0-1643-4e1f-a076-c0786a462db5/bin/utaipan-UbGMyvGFUs/data/e9d02391d/f58d0f5f5e094f478c2c5f763a0f0859/FLAG751fed30b [2021-11-19 14:03:17,259 INFO L357 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0b5144a0-1643-4e1f-a076-c0786a462db5/bin/utaipan-UbGMyvGFUs/data/e9d02391d/f58d0f5f5e094f478c2c5f763a0f0859 [2021-11-19 14:03:17,263 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2021-11-19 14:03:17,265 INFO L131 ToolchainWalker]: Walking toolchain with 6 elements. [2021-11-19 14:03:17,269 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2021-11-19 14:03:17,269 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2021-11-19 14:03:17,272 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2021-11-19 14:03:17,273 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 19.11 02:03:17" (1/1) ... [2021-11-19 14:03:17,274 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@41597722 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 02:03:17, skipping insertion in model container [2021-11-19 14:03:17,274 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 19.11 02:03:17" (1/1) ... [2021-11-19 14:03:17,282 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2021-11-19 14:03:17,644 INFO L178 MainTranslator]: Built tables and reachable declarations [2021-11-19 14:03:20,043 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_0b5144a0-1643-4e1f-a076-c0786a462db5/sv-benchmarks/c/combinations/Problem05_label42+token_ring.15.cil.c[378560,378573] [2021-11-19 14:03:20,077 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_0b5144a0-1643-4e1f-a076-c0786a462db5/sv-benchmarks/c/combinations/Problem05_label42+token_ring.15.cil.c[383339,383352] [2021-11-19 14:03:20,497 INFO L207 PostProcessor]: Analyzing one entry point: main [2021-11-19 14:03:20,512 INFO L203 MainTranslator]: Completed pre-run [2021-11-19 14:03:21,960 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_0b5144a0-1643-4e1f-a076-c0786a462db5/sv-benchmarks/c/combinations/Problem05_label42+token_ring.15.cil.c[378560,378573] [2021-11-19 14:03:21,987 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_0b5144a0-1643-4e1f-a076-c0786a462db5/sv-benchmarks/c/combinations/Problem05_label42+token_ring.15.cil.c[383339,383352] [2021-11-19 14:03:22,033 INFO L207 PostProcessor]: Analyzing one entry point: main [2021-11-19 14:03:22,118 INFO L208 MainTranslator]: Completed translation [2021-11-19 14:03:22,119 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 02:03:22 WrapperNode [2021-11-19 14:03:22,120 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2021-11-19 14:03:22,121 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2021-11-19 14:03:22,121 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2021-11-19 14:03:22,122 INFO L275 PluginConnector]: Boogie Procedure Inliner initialized [2021-11-19 14:03:22,131 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 02:03:22" (1/1) ... [2021-11-19 14:03:22,238 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 02:03:22" (1/1) ... [2021-11-19 14:03:22,722 INFO L137 Inliner]: procedures = 70, calls = 81, calls flagged for inlining = 47, calls inlined = 47, statements flattened = 13260 [2021-11-19 14:03:22,723 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2021-11-19 14:03:22,724 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2021-11-19 14:03:22,724 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2021-11-19 14:03:22,724 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2021-11-19 14:03:22,733 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 02:03:22" (1/1) ... [2021-11-19 14:03:22,734 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 02:03:22" (1/1) ... [2021-11-19 14:03:22,813 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 02:03:22" (1/1) ... [2021-11-19 14:03:22,814 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 02:03:22" (1/1) ... [2021-11-19 14:03:23,152 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 02:03:22" (1/1) ... [2021-11-19 14:03:23,235 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 02:03:22" (1/1) ... [2021-11-19 14:03:23,257 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 02:03:22" (1/1) ... [2021-11-19 14:03:23,377 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2021-11-19 14:03:23,378 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2021-11-19 14:03:23,379 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2021-11-19 14:03:23,379 INFO L275 PluginConnector]: RCFGBuilder initialized [2021-11-19 14:03:23,380 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 02:03:22" (1/1) ... [2021-11-19 14:03:23,388 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2021-11-19 14:03:23,402 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0b5144a0-1643-4e1f-a076-c0786a462db5/bin/utaipan-UbGMyvGFUs/z3 [2021-11-19 14:03:23,429 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0b5144a0-1643-4e1f-a076-c0786a462db5/bin/utaipan-UbGMyvGFUs/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2021-11-19 14:03:23,511 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0b5144a0-1643-4e1f-a076-c0786a462db5/bin/utaipan-UbGMyvGFUs/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2021-11-19 14:03:23,565 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2021-11-19 14:03:23,566 INFO L130 BoogieDeclarations]: Found specification of procedure activate_threads [2021-11-19 14:03:23,566 INFO L138 BoogieDeclarations]: Found implementation of procedure activate_threads [2021-11-19 14:03:23,566 INFO L130 BoogieDeclarations]: Found specification of procedure immediate_notify [2021-11-19 14:03:23,566 INFO L138 BoogieDeclarations]: Found implementation of procedure immediate_notify [2021-11-19 14:03:23,566 INFO L130 BoogieDeclarations]: Found specification of procedure update_channels [2021-11-19 14:03:23,567 INFO L138 BoogieDeclarations]: Found implementation of procedure update_channels [2021-11-19 14:03:23,567 INFO L130 BoogieDeclarations]: Found specification of procedure error [2021-11-19 14:03:23,567 INFO L138 BoogieDeclarations]: Found implementation of procedure error [2021-11-19 14:03:23,567 INFO L130 BoogieDeclarations]: Found specification of procedure fire_delta_events [2021-11-19 14:03:23,578 INFO L138 BoogieDeclarations]: Found implementation of procedure fire_delta_events [2021-11-19 14:03:23,578 INFO L130 BoogieDeclarations]: Found specification of procedure exists_runnable_thread [2021-11-19 14:03:23,579 INFO L138 BoogieDeclarations]: Found implementation of procedure exists_runnable_thread [2021-11-19 14:03:23,579 INFO L130 BoogieDeclarations]: Found specification of procedure reset_delta_events [2021-11-19 14:03:23,579 INFO L138 BoogieDeclarations]: Found implementation of procedure reset_delta_events [2021-11-19 14:03:23,579 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2021-11-19 14:03:23,580 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2021-11-19 14:03:23,580 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2021-11-19 14:03:23,877 INFO L236 CfgBuilder]: Building ICFG [2021-11-19 14:03:23,880 INFO L262 CfgBuilder]: Building CFG for each procedure with an implementation [2021-11-19 14:03:32,475 INFO L277 CfgBuilder]: Performing block encoding [2021-11-19 14:03:35,506 INFO L296 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2021-11-19 14:03:35,506 INFO L301 CfgBuilder]: Removed 17 assume(true) statements. [2021-11-19 14:03:35,511 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 19.11 02:03:35 BoogieIcfgContainer [2021-11-19 14:03:35,511 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2021-11-19 14:03:35,513 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2021-11-19 14:03:35,513 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2021-11-19 14:03:35,516 INFO L275 PluginConnector]: TraceAbstraction initialized [2021-11-19 14:03:35,517 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 19.11 02:03:17" (1/3) ... [2021-11-19 14:03:35,518 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7197fe3a and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 19.11 02:03:35, skipping insertion in model container [2021-11-19 14:03:35,518 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 02:03:22" (2/3) ... [2021-11-19 14:03:35,518 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7197fe3a and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 19.11 02:03:35, skipping insertion in model container [2021-11-19 14:03:35,518 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 19.11 02:03:35" (3/3) ... [2021-11-19 14:03:35,520 INFO L111 eAbstractionObserver]: Analyzing ICFG Problem05_label42+token_ring.15.cil.c [2021-11-19 14:03:35,525 INFO L204 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2021-11-19 14:03:35,525 INFO L163 ceAbstractionStarter]: Applying trace abstraction to program that has 2 error locations. [2021-11-19 14:03:35,579 INFO L338 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2021-11-19 14:03:35,586 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-19 14:03:35,586 INFO L340 AbstractCegarLoop]: Starting to check reachability of 2 error locations. [2021-11-19 14:03:35,646 INFO L276 IsEmpty]: Start isEmpty. Operand has 1848 states, 1809 states have (on average 1.9541182974018796) internal successors, (3535), 1814 states have internal predecessors, (3535), 29 states have call successors, (29), 7 states have call predecessors, (29), 7 states have return successors, (29), 28 states have call predecessors, (29), 29 states have call successors, (29) [2021-11-19 14:03:35,657 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 72 [2021-11-19 14:03:35,658 INFO L506 BasicCegarLoop]: Found error trace [2021-11-19 14:03:35,658 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 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-19 14:03:35,659 INFO L402 AbstractCegarLoop]: === Iteration 1 === Targeting errorErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, errorErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-19 14:03:35,664 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-19 14:03:35,665 INFO L85 PathProgramCache]: Analyzing trace with hash 1505574162, now seen corresponding path program 1 times [2021-11-19 14:03:35,674 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-19 14:03:35,674 INFO L332 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1444719326] [2021-11-19 14:03:35,675 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-19 14:03:35,676 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-19 14:03:35,887 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-19 14:03:36,130 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-11-19 14:03:36,131 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-19 14:03:36,131 INFO L332 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1444719326] [2021-11-19 14:03:36,132 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1444719326] provided 1 perfect and 0 imperfect interpolant sequences [2021-11-19 14:03:36,132 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-11-19 14:03:36,132 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2021-11-19 14:03:36,134 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2075971719] [2021-11-19 14:03:36,135 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-11-19 14:03:36,140 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2021-11-19 14:03:36,141 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-19 14:03:36,190 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2021-11-19 14:03:36,191 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2021-11-19 14:03:36,200 INFO L87 Difference]: Start difference. First operand has 1848 states, 1809 states have (on average 1.9541182974018796) internal successors, (3535), 1814 states have internal predecessors, (3535), 29 states have call successors, (29), 7 states have call predecessors, (29), 7 states have return successors, (29), 28 states have call predecessors, (29), 29 states have call successors, (29) Second operand has 4 states, 4 states have (on average 15.0) internal successors, (60), 4 states have internal predecessors, (60), 2 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2021-11-19 14:03:37,368 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-19 14:03:37,368 INFO L93 Difference]: Finished difference Result 3877 states and 7503 transitions. [2021-11-19 14:03:37,370 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2021-11-19 14:03:37,372 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 15.0) internal successors, (60), 4 states have internal predecessors, (60), 2 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 71 [2021-11-19 14:03:37,373 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-19 14:03:37,409 INFO L225 Difference]: With dead ends: 3877 [2021-11-19 14:03:37,410 INFO L226 Difference]: Without dead ends: 2028 [2021-11-19 14:03:37,424 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2021-11-19 14:03:37,433 INFO L933 BasicCegarLoop]: 3549 mSDtfsCounter, 3820 mSDsluCounter, 3759 mSDsCounter, 0 mSdLazyCounter, 744 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3820 SdHoareTripleChecker+Valid, 6994 SdHoareTripleChecker+Invalid, 758 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 744 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.9s IncrementalHoareTripleChecker+Time [2021-11-19 14:03:37,434 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [3820 Valid, 6994 Invalid, 758 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 744 Invalid, 0 Unknown, 0 Unchecked, 0.9s Time] [2021-11-19 14:03:37,458 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2028 states. [2021-11-19 14:03:37,585 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2028 to 2027. [2021-11-19 14:03:37,592 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 2027 states, 1961 states have (on average 1.9163691993880674) internal successors, (3758), 1965 states have internal predecessors, (3758), 52 states have call successors, (52), 13 states have call predecessors, (52), 12 states have return successors, (50), 49 states have call predecessors, (50), 50 states have call successors, (50) [2021-11-19 14:03:37,608 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 2027 states to 2027 states and 3860 transitions. [2021-11-19 14:03:37,609 INFO L78 Accepts]: Start accepts. Automaton has 2027 states and 3860 transitions. Word has length 71 [2021-11-19 14:03:37,610 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-19 14:03:37,610 INFO L470 AbstractCegarLoop]: Abstraction has 2027 states and 3860 transitions. [2021-11-19 14:03:37,611 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 15.0) internal successors, (60), 4 states have internal predecessors, (60), 2 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2021-11-19 14:03:37,611 INFO L276 IsEmpty]: Start isEmpty. Operand 2027 states and 3860 transitions. [2021-11-19 14:03:37,621 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 145 [2021-11-19 14:03:37,622 INFO L506 BasicCegarLoop]: Found error trace [2021-11-19 14:03:37,622 INFO L514 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-19 14:03:37,623 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2021-11-19 14:03:37,623 INFO L402 AbstractCegarLoop]: === Iteration 2 === Targeting errorErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, errorErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-19 14:03:37,624 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-19 14:03:37,624 INFO L85 PathProgramCache]: Analyzing trace with hash 1340033364, now seen corresponding path program 1 times [2021-11-19 14:03:37,624 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-19 14:03:37,625 INFO L332 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1724767734] [2021-11-19 14:03:37,625 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-19 14:03:37,625 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-19 14:03:37,668 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-19 14:03:37,812 INFO L134 CoverageAnalysis]: Checked inductivity of 53 backedges. 0 proven. 42 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2021-11-19 14:03:37,813 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-19 14:03:37,813 INFO L332 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1724767734] [2021-11-19 14:03:37,813 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1724767734] provided 0 perfect and 1 imperfect interpolant sequences [2021-11-19 14:03:37,814 INFO L332 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [208491694] [2021-11-19 14:03:37,814 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-19 14:03:37,814 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-19 14:03:37,814 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0b5144a0-1643-4e1f-a076-c0786a462db5/bin/utaipan-UbGMyvGFUs/z3 [2021-11-19 14:03:37,836 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0b5144a0-1643-4e1f-a076-c0786a462db5/bin/utaipan-UbGMyvGFUs/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-19 14:03:37,854 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0b5144a0-1643-4e1f-a076-c0786a462db5/bin/utaipan-UbGMyvGFUs/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2021-11-19 14:03:38,126 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-19 14:03:38,133 INFO L263 TraceCheckSpWp]: Trace formula consists of 1123 conjuncts, 2 conjunts are in the unsatisfiable core [2021-11-19 14:03:38,151 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-19 14:03:38,489 INFO L134 CoverageAnalysis]: Checked inductivity of 53 backedges. 29 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2021-11-19 14:03:38,489 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-11-19 14:03:38,807 INFO L134 CoverageAnalysis]: Checked inductivity of 53 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 38 trivial. 0 not checked. [2021-11-19 14:03:38,808 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [208491694] provided 1 perfect and 1 imperfect interpolant sequences [2021-11-19 14:03:38,808 INFO L186 FreeRefinementEngine]: Found 1 perfect and 2 imperfect interpolant sequences. [2021-11-19 14:03:38,808 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [5, 4] total 7 [2021-11-19 14:03:38,809 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1995143293] [2021-11-19 14:03:38,810 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-11-19 14:03:38,811 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2021-11-19 14:03:38,811 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-19 14:03:38,811 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2021-11-19 14:03:38,812 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2021-11-19 14:03:38,812 INFO L87 Difference]: Start difference. First operand 2027 states and 3860 transitions. Second operand has 3 states, 3 states have (on average 35.666666666666664) internal successors, (107), 2 states have internal predecessors, (107), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2021-11-19 14:03:39,404 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-19 14:03:39,404 INFO L93 Difference]: Finished difference Result 2782 states and 5049 transitions. [2021-11-19 14:03:39,405 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2021-11-19 14:03:39,405 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 35.666666666666664) internal successors, (107), 2 states have internal predecessors, (107), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 144 [2021-11-19 14:03:39,406 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-19 14:03:39,425 INFO L225 Difference]: With dead ends: 2782 [2021-11-19 14:03:39,425 INFO L226 Difference]: Without dead ends: 2401 [2021-11-19 14:03:39,428 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 291 GetRequests, 285 SyntacticMatches, 1 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2021-11-19 14:03:39,429 INFO L933 BasicCegarLoop]: 3376 mSDtfsCounter, 3533 mSDsluCounter, 294 mSDsCounter, 0 mSdLazyCounter, 322 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3533 SdHoareTripleChecker+Valid, 3624 SdHoareTripleChecker+Invalid, 324 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 322 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2021-11-19 14:03:39,430 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [3533 Valid, 3624 Invalid, 324 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 322 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2021-11-19 14:03:39,435 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2401 states. [2021-11-19 14:03:39,533 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2401 to 2395. [2021-11-19 14:03:39,539 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 2395 states, 2273 states have (on average 1.86229652441707) internal successors, (4233), 2278 states have internal predecessors, (4233), 96 states have call successors, (96), 25 states have call predecessors, (96), 24 states have return successors, (94), 92 states have call predecessors, (94), 94 states have call successors, (94) [2021-11-19 14:03:39,557 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 2395 states to 2395 states and 4423 transitions. [2021-11-19 14:03:39,557 INFO L78 Accepts]: Start accepts. Automaton has 2395 states and 4423 transitions. Word has length 144 [2021-11-19 14:03:39,558 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-19 14:03:39,558 INFO L470 AbstractCegarLoop]: Abstraction has 2395 states and 4423 transitions. [2021-11-19 14:03:39,559 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 35.666666666666664) internal successors, (107), 2 states have internal predecessors, (107), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2021-11-19 14:03:39,559 INFO L276 IsEmpty]: Start isEmpty. Operand 2395 states and 4423 transitions. [2021-11-19 14:03:39,563 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 145 [2021-11-19 14:03:39,563 INFO L506 BasicCegarLoop]: Found error trace [2021-11-19 14:03:39,564 INFO L514 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-19 14:03:39,605 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0b5144a0-1643-4e1f-a076-c0786a462db5/bin/utaipan-UbGMyvGFUs/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2021-11-19 14:03:39,787 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0b5144a0-1643-4e1f-a076-c0786a462db5/bin/utaipan-UbGMyvGFUs/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-19 14:03:39,787 INFO L402 AbstractCegarLoop]: === Iteration 3 === Targeting errorErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, errorErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-19 14:03:39,788 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-19 14:03:39,788 INFO L85 PathProgramCache]: Analyzing trace with hash 353351058, now seen corresponding path program 1 times [2021-11-19 14:03:39,788 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-19 14:03:39,788 INFO L332 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [554327494] [2021-11-19 14:03:39,788 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-19 14:03:39,789 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-19 14:03:39,825 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-19 14:03:39,934 INFO L134 CoverageAnalysis]: Checked inductivity of 53 backedges. 0 proven. 42 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2021-11-19 14:03:39,934 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-19 14:03:39,934 INFO L332 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [554327494] [2021-11-19 14:03:39,934 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [554327494] provided 0 perfect and 1 imperfect interpolant sequences [2021-11-19 14:03:39,935 INFO L332 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [878562613] [2021-11-19 14:03:39,935 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-19 14:03:39,935 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-19 14:03:39,935 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0b5144a0-1643-4e1f-a076-c0786a462db5/bin/utaipan-UbGMyvGFUs/z3 [2021-11-19 14:03:39,940 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0b5144a0-1643-4e1f-a076-c0786a462db5/bin/utaipan-UbGMyvGFUs/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-19 14:03:39,957 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0b5144a0-1643-4e1f-a076-c0786a462db5/bin/utaipan-UbGMyvGFUs/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2021-11-19 14:03:40,181 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-19 14:03:40,187 INFO L263 TraceCheckSpWp]: Trace formula consists of 1117 conjuncts, 2 conjunts are in the unsatisfiable core [2021-11-19 14:03:40,194 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-19 14:03:40,441 INFO L134 CoverageAnalysis]: Checked inductivity of 53 backedges. 35 proven. 0 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2021-11-19 14:03:40,441 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-11-19 14:03:40,705 INFO L134 CoverageAnalysis]: Checked inductivity of 53 backedges. 0 proven. 9 refuted. 0 times theorem prover too weak. 44 trivial. 0 not checked. [2021-11-19 14:03:40,706 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [878562613] provided 1 perfect and 1 imperfect interpolant sequences [2021-11-19 14:03:40,706 INFO L186 FreeRefinementEngine]: Found 1 perfect and 2 imperfect interpolant sequences. [2021-11-19 14:03:40,706 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [5, 4] total 7 [2021-11-19 14:03:40,707 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2120990392] [2021-11-19 14:03:40,707 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-11-19 14:03:40,708 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2021-11-19 14:03:40,708 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-19 14:03:40,708 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2021-11-19 14:03:40,709 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2021-11-19 14:03:40,709 INFO L87 Difference]: Start difference. First operand 2395 states and 4423 transitions. Second operand has 3 states, 3 states have (on average 37.666666666666664) internal successors, (113), 2 states have internal predecessors, (113), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2021-11-19 14:03:41,398 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-19 14:03:41,398 INFO L93 Difference]: Finished difference Result 3880 states and 6758 transitions. [2021-11-19 14:03:41,399 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2021-11-19 14:03:41,399 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 37.666666666666664) internal successors, (113), 2 states have internal predecessors, (113), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 144 [2021-11-19 14:03:41,400 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-19 14:03:41,427 INFO L225 Difference]: With dead ends: 3880 [2021-11-19 14:03:41,427 INFO L226 Difference]: Without dead ends: 3131 [2021-11-19 14:03:41,433 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 291 GetRequests, 285 SyntacticMatches, 1 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2021-11-19 14:03:41,437 INFO L933 BasicCegarLoop]: 3334 mSDtfsCounter, 3527 mSDsluCounter, 294 mSDsCounter, 0 mSdLazyCounter, 319 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3527 SdHoareTripleChecker+Valid, 3582 SdHoareTripleChecker+Invalid, 321 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 319 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2021-11-19 14:03:41,439 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [3527 Valid, 3582 Invalid, 321 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 319 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2021-11-19 14:03:41,445 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 3131 states. [2021-11-19 14:03:41,571 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 3131 to 3123. [2021-11-19 14:03:41,580 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 3123 states, 2891 states have (on average 1.7886544448287789) internal successors, (5171), 2898 states have internal predecessors, (5171), 182 states have call successors, (182), 49 states have call predecessors, (182), 48 states have return successors, (180), 176 states have call predecessors, (180), 180 states have call successors, (180) [2021-11-19 14:03:41,601 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3123 states to 3123 states and 5533 transitions. [2021-11-19 14:03:41,602 INFO L78 Accepts]: Start accepts. Automaton has 3123 states and 5533 transitions. Word has length 144 [2021-11-19 14:03:41,604 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-19 14:03:41,604 INFO L470 AbstractCegarLoop]: Abstraction has 3123 states and 5533 transitions. [2021-11-19 14:03:41,605 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 37.666666666666664) internal successors, (113), 2 states have internal predecessors, (113), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2021-11-19 14:03:41,605 INFO L276 IsEmpty]: Start isEmpty. Operand 3123 states and 5533 transitions. [2021-11-19 14:03:41,611 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 145 [2021-11-19 14:03:41,611 INFO L506 BasicCegarLoop]: Found error trace [2021-11-19 14:03:41,611 INFO L514 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-19 14:03:41,650 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0b5144a0-1643-4e1f-a076-c0786a462db5/bin/utaipan-UbGMyvGFUs/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2021-11-19 14:03:41,834 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0b5144a0-1643-4e1f-a076-c0786a462db5/bin/utaipan-UbGMyvGFUs/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-19 14:03:41,835 INFO L402 AbstractCegarLoop]: === Iteration 4 === Targeting errorErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, errorErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-19 14:03:41,835 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-19 14:03:41,836 INFO L85 PathProgramCache]: Analyzing trace with hash -249714608, now seen corresponding path program 1 times [2021-11-19 14:03:41,836 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-19 14:03:41,836 INFO L332 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [843157365] [2021-11-19 14:03:41,836 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-19 14:03:41,837 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-19 14:03:41,863 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-19 14:03:41,943 INFO L134 CoverageAnalysis]: Checked inductivity of 53 backedges. 0 proven. 42 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2021-11-19 14:03:41,944 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-19 14:03:41,944 INFO L332 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [843157365] [2021-11-19 14:03:41,944 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [843157365] provided 0 perfect and 1 imperfect interpolant sequences [2021-11-19 14:03:41,949 INFO L332 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [20478552] [2021-11-19 14:03:41,949 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-19 14:03:41,950 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-19 14:03:41,950 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0b5144a0-1643-4e1f-a076-c0786a462db5/bin/utaipan-UbGMyvGFUs/z3 [2021-11-19 14:03:41,955 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0b5144a0-1643-4e1f-a076-c0786a462db5/bin/utaipan-UbGMyvGFUs/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-19 14:03:41,961 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0b5144a0-1643-4e1f-a076-c0786a462db5/bin/utaipan-UbGMyvGFUs/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2021-11-19 14:03:42,198 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-19 14:03:42,203 INFO L263 TraceCheckSpWp]: Trace formula consists of 1111 conjuncts, 2 conjunts are in the unsatisfiable core [2021-11-19 14:03:42,208 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-19 14:03:42,427 INFO L134 CoverageAnalysis]: Checked inductivity of 53 backedges. 11 proven. 0 refuted. 0 times theorem prover too weak. 42 trivial. 0 not checked. [2021-11-19 14:03:42,428 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-11-19 14:03:42,678 INFO L134 CoverageAnalysis]: Checked inductivity of 53 backedges. 0 proven. 33 refuted. 0 times theorem prover too weak. 20 trivial. 0 not checked. [2021-11-19 14:03:42,678 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [20478552] provided 1 perfect and 1 imperfect interpolant sequences [2021-11-19 14:03:42,679 INFO L186 FreeRefinementEngine]: Found 1 perfect and 2 imperfect interpolant sequences. [2021-11-19 14:03:42,679 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [5, 4] total 7 [2021-11-19 14:03:42,679 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [45937520] [2021-11-19 14:03:42,679 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-11-19 14:03:42,680 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2021-11-19 14:03:42,680 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-19 14:03:42,682 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2021-11-19 14:03:42,686 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2021-11-19 14:03:42,686 INFO L87 Difference]: Start difference. First operand 3123 states and 5533 transitions. Second operand has 3 states, 3 states have (on average 29.666666666666668) internal successors, (89), 2 states have internal predecessors, (89), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2021-11-19 14:03:43,356 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-19 14:03:43,356 INFO L93 Difference]: Finished difference Result 6052 states and 10126 transitions. [2021-11-19 14:03:43,357 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2021-11-19 14:03:43,357 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 29.666666666666668) internal successors, (89), 2 states have internal predecessors, (89), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 144 [2021-11-19 14:03:43,358 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-19 14:03:43,399 INFO L225 Difference]: With dead ends: 6052 [2021-11-19 14:03:43,399 INFO L226 Difference]: Without dead ends: 4575 [2021-11-19 14:03:43,410 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 291 GetRequests, 285 SyntacticMatches, 1 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2021-11-19 14:03:43,420 INFO L933 BasicCegarLoop]: 3374 mSDtfsCounter, 3551 mSDsluCounter, 294 mSDsCounter, 0 mSdLazyCounter, 322 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3551 SdHoareTripleChecker+Valid, 3622 SdHoareTripleChecker+Invalid, 324 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 322 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2021-11-19 14:03:43,424 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [3551 Valid, 3622 Invalid, 324 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 322 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2021-11-19 14:03:43,436 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 4575 states. [2021-11-19 14:03:43,623 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 4575 to 4563. [2021-11-19 14:03:43,634 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 4563 states, 4115 states have (on average 1.7066828675577157) internal successors, (7023), 4126 states have internal predecessors, (7023), 350 states have call successors, (350), 97 states have call predecessors, (350), 96 states have return successors, (348), 340 states have call predecessors, (348), 348 states have call successors, (348) [2021-11-19 14:03:43,664 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 4563 states to 4563 states and 7721 transitions. [2021-11-19 14:03:43,666 INFO L78 Accepts]: Start accepts. Automaton has 4563 states and 7721 transitions. Word has length 144 [2021-11-19 14:03:43,666 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-19 14:03:43,666 INFO L470 AbstractCegarLoop]: Abstraction has 4563 states and 7721 transitions. [2021-11-19 14:03:43,667 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 29.666666666666668) internal successors, (89), 2 states have internal predecessors, (89), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2021-11-19 14:03:43,667 INFO L276 IsEmpty]: Start isEmpty. Operand 4563 states and 7721 transitions. [2021-11-19 14:03:43,679 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 145 [2021-11-19 14:03:43,679 INFO L506 BasicCegarLoop]: Found error trace [2021-11-19 14:03:43,680 INFO L514 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-19 14:03:43,722 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0b5144a0-1643-4e1f-a076-c0786a462db5/bin/utaipan-UbGMyvGFUs/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2021-11-19 14:03:43,894 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0b5144a0-1643-4e1f-a076-c0786a462db5/bin/utaipan-UbGMyvGFUs/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-19 14:03:43,895 INFO L402 AbstractCegarLoop]: === Iteration 5 === Targeting errorErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, errorErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-19 14:03:43,895 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-19 14:03:43,896 INFO L85 PathProgramCache]: Analyzing trace with hash 2060370190, now seen corresponding path program 1 times [2021-11-19 14:03:43,896 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-19 14:03:43,896 INFO L332 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [493705693] [2021-11-19 14:03:43,896 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-19 14:03:43,896 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-19 14:03:43,943 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-19 14:03:44,017 INFO L134 CoverageAnalysis]: Checked inductivity of 53 backedges. 0 proven. 42 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2021-11-19 14:03:44,017 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-19 14:03:44,018 INFO L332 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [493705693] [2021-11-19 14:03:44,018 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [493705693] provided 0 perfect and 1 imperfect interpolant sequences [2021-11-19 14:03:44,018 INFO L332 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1711384018] [2021-11-19 14:03:44,018 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-19 14:03:44,019 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-19 14:03:44,019 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0b5144a0-1643-4e1f-a076-c0786a462db5/bin/utaipan-UbGMyvGFUs/z3 [2021-11-19 14:03:44,020 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0b5144a0-1643-4e1f-a076-c0786a462db5/bin/utaipan-UbGMyvGFUs/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-19 14:03:44,040 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0b5144a0-1643-4e1f-a076-c0786a462db5/bin/utaipan-UbGMyvGFUs/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2021-11-19 14:03:44,292 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-19 14:03:44,297 INFO L263 TraceCheckSpWp]: Trace formula consists of 1105 conjuncts, 2 conjunts are in the unsatisfiable core [2021-11-19 14:03:44,301 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-19 14:03:44,533 INFO L134 CoverageAnalysis]: Checked inductivity of 53 backedges. 17 proven. 0 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2021-11-19 14:03:44,533 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-11-19 14:03:44,786 INFO L134 CoverageAnalysis]: Checked inductivity of 53 backedges. 0 proven. 27 refuted. 0 times theorem prover too weak. 26 trivial. 0 not checked. [2021-11-19 14:03:44,786 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1711384018] provided 1 perfect and 1 imperfect interpolant sequences [2021-11-19 14:03:44,786 INFO L186 FreeRefinementEngine]: Found 1 perfect and 2 imperfect interpolant sequences. [2021-11-19 14:03:44,787 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [5, 4] total 7 [2021-11-19 14:03:44,787 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1962803729] [2021-11-19 14:03:44,787 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-11-19 14:03:44,788 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2021-11-19 14:03:44,788 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-19 14:03:44,788 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2021-11-19 14:03:44,789 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2021-11-19 14:03:44,789 INFO L87 Difference]: Start difference. First operand 4563 states and 7721 transitions. Second operand has 3 states, 3 states have (on average 31.666666666666668) internal successors, (95), 2 states have internal predecessors, (95), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2021-11-19 14:03:45,579 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-19 14:03:45,579 INFO L93 Difference]: Finished difference Result 10348 states and 16762 transitions. [2021-11-19 14:03:45,580 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2021-11-19 14:03:45,581 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 31.666666666666668) internal successors, (95), 2 states have internal predecessors, (95), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 144 [2021-11-19 14:03:45,582 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-19 14:03:45,653 INFO L225 Difference]: With dead ends: 10348 [2021-11-19 14:03:45,653 INFO L226 Difference]: Without dead ends: 7431 [2021-11-19 14:03:45,671 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 291 GetRequests, 285 SyntacticMatches, 1 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2021-11-19 14:03:45,672 INFO L933 BasicCegarLoop]: 3334 mSDtfsCounter, 3545 mSDsluCounter, 294 mSDsCounter, 0 mSdLazyCounter, 319 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3545 SdHoareTripleChecker+Valid, 3582 SdHoareTripleChecker+Invalid, 321 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 319 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2021-11-19 14:03:45,674 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [3545 Valid, 3582 Invalid, 321 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 319 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2021-11-19 14:03:45,688 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 7431 states. [2021-11-19 14:03:46,180 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 7431 to 7411. [2021-11-19 14:03:46,209 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 7411 states, 6539 states have (on average 1.6331243309374521) internal successors, (10679), 6558 states have internal predecessors, (10679), 678 states have call successors, (678), 193 states have call predecessors, (678), 192 states have return successors, (676), 660 states have call predecessors, (676), 676 states have call successors, (676) [2021-11-19 14:03:46,254 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 7411 states to 7411 states and 12033 transitions. [2021-11-19 14:03:46,255 INFO L78 Accepts]: Start accepts. Automaton has 7411 states and 12033 transitions. Word has length 144 [2021-11-19 14:03:46,256 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-19 14:03:46,256 INFO L470 AbstractCegarLoop]: Abstraction has 7411 states and 12033 transitions. [2021-11-19 14:03:46,257 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 31.666666666666668) internal successors, (95), 2 states have internal predecessors, (95), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2021-11-19 14:03:46,257 INFO L276 IsEmpty]: Start isEmpty. Operand 7411 states and 12033 transitions. [2021-11-19 14:03:46,274 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 145 [2021-11-19 14:03:46,275 INFO L506 BasicCegarLoop]: Found error trace [2021-11-19 14:03:46,275 INFO L514 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-19 14:03:46,322 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0b5144a0-1643-4e1f-a076-c0786a462db5/bin/utaipan-UbGMyvGFUs/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2021-11-19 14:03:46,498 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0b5144a0-1643-4e1f-a076-c0786a462db5/bin/utaipan-UbGMyvGFUs/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-19 14:03:46,499 INFO L402 AbstractCegarLoop]: === Iteration 6 === Targeting errorErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, errorErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-19 14:03:46,499 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-19 14:03:46,499 INFO L85 PathProgramCache]: Analyzing trace with hash 41467980, now seen corresponding path program 1 times [2021-11-19 14:03:46,500 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-19 14:03:46,500 INFO L332 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [141147567] [2021-11-19 14:03:46,500 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-19 14:03:46,500 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-19 14:03:46,527 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-19 14:03:46,631 INFO L134 CoverageAnalysis]: Checked inductivity of 53 backedges. 0 proven. 42 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2021-11-19 14:03:46,631 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-19 14:03:46,632 INFO L332 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [141147567] [2021-11-19 14:03:46,632 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [141147567] provided 0 perfect and 1 imperfect interpolant sequences [2021-11-19 14:03:46,632 INFO L332 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1387078932] [2021-11-19 14:03:46,632 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-19 14:03:46,633 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-19 14:03:46,633 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0b5144a0-1643-4e1f-a076-c0786a462db5/bin/utaipan-UbGMyvGFUs/z3 [2021-11-19 14:03:46,634 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0b5144a0-1643-4e1f-a076-c0786a462db5/bin/utaipan-UbGMyvGFUs/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-19 14:03:46,654 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0b5144a0-1643-4e1f-a076-c0786a462db5/bin/utaipan-UbGMyvGFUs/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2021-11-19 14:03:46,924 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-19 14:03:46,930 INFO L263 TraceCheckSpWp]: Trace formula consists of 1099 conjuncts, 2 conjunts are in the unsatisfiable core [2021-11-19 14:03:46,935 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-19 14:03:47,210 INFO L134 CoverageAnalysis]: Checked inductivity of 53 backedges. 8 proven. 0 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2021-11-19 14:03:47,211 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-11-19 14:03:47,502 INFO L134 CoverageAnalysis]: Checked inductivity of 53 backedges. 0 proven. 36 refuted. 0 times theorem prover too weak. 17 trivial. 0 not checked. [2021-11-19 14:03:47,503 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1387078932] provided 1 perfect and 1 imperfect interpolant sequences [2021-11-19 14:03:47,503 INFO L186 FreeRefinementEngine]: Found 1 perfect and 2 imperfect interpolant sequences. [2021-11-19 14:03:47,503 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [5, 4] total 7 [2021-11-19 14:03:47,504 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1084945257] [2021-11-19 14:03:47,504 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-11-19 14:03:47,504 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2021-11-19 14:03:47,505 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-19 14:03:47,505 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2021-11-19 14:03:47,505 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2021-11-19 14:03:47,506 INFO L87 Difference]: Start difference. First operand 7411 states and 12033 transitions. Second operand has 3 states, 3 states have (on average 28.666666666666668) internal successors, (86), 2 states have internal predecessors, (86), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2021-11-19 14:03:48,480 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-19 14:03:48,483 INFO L93 Difference]: Finished difference Result 18844 states and 29834 transitions. [2021-11-19 14:03:48,483 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2021-11-19 14:03:48,484 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 28.666666666666668) internal successors, (86), 2 states have internal predecessors, (86), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 144 [2021-11-19 14:03:48,484 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-19 14:03:48,595 INFO L225 Difference]: With dead ends: 18844 [2021-11-19 14:03:48,596 INFO L226 Difference]: Without dead ends: 13079 [2021-11-19 14:03:48,635 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 291 GetRequests, 285 SyntacticMatches, 1 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2021-11-19 14:03:48,636 INFO L933 BasicCegarLoop]: 3334 mSDtfsCounter, 3554 mSDsluCounter, 294 mSDsCounter, 0 mSdLazyCounter, 319 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3554 SdHoareTripleChecker+Valid, 3582 SdHoareTripleChecker+Invalid, 321 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 319 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2021-11-19 14:03:48,637 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [3554 Valid, 3582 Invalid, 321 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 319 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2021-11-19 14:03:48,664 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 13079 states. [2021-11-19 14:03:49,459 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 13079 to 13043. [2021-11-19 14:03:49,479 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 13043 states, 11339 states have (on average 1.578181497486551) internal successors, (17895), 11374 states have internal predecessors, (17895), 1318 states have call successors, (1318), 385 states have call predecessors, (1318), 384 states have return successors, (1316), 1284 states have call predecessors, (1316), 1316 states have call successors, (1316) [2021-11-19 14:03:49,543 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 13043 states to 13043 states and 20529 transitions. [2021-11-19 14:03:49,545 INFO L78 Accepts]: Start accepts. Automaton has 13043 states and 20529 transitions. Word has length 144 [2021-11-19 14:03:49,545 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-19 14:03:49,546 INFO L470 AbstractCegarLoop]: Abstraction has 13043 states and 20529 transitions. [2021-11-19 14:03:49,546 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 28.666666666666668) internal successors, (86), 2 states have internal predecessors, (86), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2021-11-19 14:03:49,546 INFO L276 IsEmpty]: Start isEmpty. Operand 13043 states and 20529 transitions. [2021-11-19 14:03:49,584 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 145 [2021-11-19 14:03:49,585 INFO L506 BasicCegarLoop]: Found error trace [2021-11-19 14:03:49,585 INFO L514 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-19 14:03:49,632 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0b5144a0-1643-4e1f-a076-c0786a462db5/bin/utaipan-UbGMyvGFUs/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2021-11-19 14:03:49,811 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0b5144a0-1643-4e1f-a076-c0786a462db5/bin/utaipan-UbGMyvGFUs/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-19 14:03:49,811 INFO L402 AbstractCegarLoop]: === Iteration 7 === Targeting errorErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, errorErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-19 14:03:49,811 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-19 14:03:49,812 INFO L85 PathProgramCache]: Analyzing trace with hash 1516701390, now seen corresponding path program 1 times [2021-11-19 14:03:49,812 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-19 14:03:49,812 INFO L332 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [129327647] [2021-11-19 14:03:49,812 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-19 14:03:49,812 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-19 14:03:49,857 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-19 14:03:49,946 INFO L134 CoverageAnalysis]: Checked inductivity of 53 backedges. 0 proven. 42 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2021-11-19 14:03:49,947 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-19 14:03:49,947 INFO L332 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [129327647] [2021-11-19 14:03:49,947 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [129327647] provided 0 perfect and 1 imperfect interpolant sequences [2021-11-19 14:03:49,947 INFO L332 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1855187473] [2021-11-19 14:03:49,948 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-19 14:03:49,948 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-19 14:03:49,948 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0b5144a0-1643-4e1f-a076-c0786a462db5/bin/utaipan-UbGMyvGFUs/z3 [2021-11-19 14:03:49,949 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0b5144a0-1643-4e1f-a076-c0786a462db5/bin/utaipan-UbGMyvGFUs/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-19 14:03:49,970 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0b5144a0-1643-4e1f-a076-c0786a462db5/bin/utaipan-UbGMyvGFUs/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2021-11-19 14:03:50,214 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-19 14:03:50,220 INFO L263 TraceCheckSpWp]: Trace formula consists of 1093 conjuncts, 2 conjunts are in the unsatisfiable core [2021-11-19 14:03:50,226 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-19 14:03:50,541 INFO L134 CoverageAnalysis]: Checked inductivity of 53 backedges. 38 proven. 0 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2021-11-19 14:03:50,542 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-11-19 14:03:50,845 INFO L134 CoverageAnalysis]: Checked inductivity of 53 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 47 trivial. 0 not checked. [2021-11-19 14:03:50,846 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1855187473] provided 1 perfect and 1 imperfect interpolant sequences [2021-11-19 14:03:50,846 INFO L186 FreeRefinementEngine]: Found 1 perfect and 2 imperfect interpolant sequences. [2021-11-19 14:03:50,846 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [5, 4] total 7 [2021-11-19 14:03:50,847 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [484003966] [2021-11-19 14:03:50,847 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-11-19 14:03:50,848 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2021-11-19 14:03:50,848 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-19 14:03:50,849 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2021-11-19 14:03:50,849 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2021-11-19 14:03:50,849 INFO L87 Difference]: Start difference. First operand 13043 states and 20529 transitions. Second operand has 3 states, 3 states have (on average 38.666666666666664) internal successors, (116), 2 states have internal predecessors, (116), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2021-11-19 14:03:52,181 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-19 14:03:52,184 INFO L93 Difference]: Finished difference Result 35644 states and 55578 transitions. [2021-11-19 14:03:52,185 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2021-11-19 14:03:52,185 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 38.666666666666664) internal successors, (116), 2 states have internal predecessors, (116), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 144 [2021-11-19 14:03:52,187 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-19 14:03:52,311 INFO L225 Difference]: With dead ends: 35644 [2021-11-19 14:03:52,311 INFO L226 Difference]: Without dead ends: 24247 [2021-11-19 14:03:52,525 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 291 GetRequests, 285 SyntacticMatches, 1 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2021-11-19 14:03:52,526 INFO L933 BasicCegarLoop]: 3334 mSDtfsCounter, 3524 mSDsluCounter, 294 mSDsCounter, 0 mSdLazyCounter, 319 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3524 SdHoareTripleChecker+Valid, 3582 SdHoareTripleChecker+Invalid, 321 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 319 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2021-11-19 14:03:52,529 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [3524 Valid, 3582 Invalid, 321 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 319 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2021-11-19 14:03:52,558 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 24247 states. [2021-11-19 14:03:53,371 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 24247 to 24179. [2021-11-19 14:03:53,417 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 24179 states, 20843 states have (on average 1.5417646212157559) internal successors, (32135), 20910 states have internal predecessors, (32135), 2566 states have call successors, (2566), 769 states have call predecessors, (2566), 768 states have return successors, (2564), 2500 states have call predecessors, (2564), 2564 states have call successors, (2564) [2021-11-19 14:03:53,525 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24179 states to 24179 states and 37265 transitions. [2021-11-19 14:03:53,528 INFO L78 Accepts]: Start accepts. Automaton has 24179 states and 37265 transitions. Word has length 144 [2021-11-19 14:03:53,529 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-19 14:03:53,529 INFO L470 AbstractCegarLoop]: Abstraction has 24179 states and 37265 transitions. [2021-11-19 14:03:53,529 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 38.666666666666664) internal successors, (116), 2 states have internal predecessors, (116), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2021-11-19 14:03:53,530 INFO L276 IsEmpty]: Start isEmpty. Operand 24179 states and 37265 transitions. [2021-11-19 14:03:53,690 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 145 [2021-11-19 14:03:53,690 INFO L506 BasicCegarLoop]: Found error trace [2021-11-19 14:03:53,691 INFO L514 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-19 14:03:53,730 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0b5144a0-1643-4e1f-a076-c0786a462db5/bin/utaipan-UbGMyvGFUs/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2021-11-19 14:03:53,911 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,7 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0b5144a0-1643-4e1f-a076-c0786a462db5/bin/utaipan-UbGMyvGFUs/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-19 14:03:53,912 INFO L402 AbstractCegarLoop]: === Iteration 8 === Targeting errorErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, errorErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-19 14:03:53,912 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-19 14:03:53,912 INFO L85 PathProgramCache]: Analyzing trace with hash 780549328, now seen corresponding path program 1 times [2021-11-19 14:03:53,912 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-19 14:03:53,913 INFO L332 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [54287967] [2021-11-19 14:03:53,913 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-19 14:03:53,913 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-19 14:03:53,953 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-19 14:03:54,025 INFO L134 CoverageAnalysis]: Checked inductivity of 53 backedges. 0 proven. 42 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2021-11-19 14:03:54,025 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-19 14:03:54,025 INFO L332 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [54287967] [2021-11-19 14:03:54,026 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [54287967] provided 0 perfect and 1 imperfect interpolant sequences [2021-11-19 14:03:54,026 INFO L332 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [952914563] [2021-11-19 14:03:54,026 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-19 14:03:54,026 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-19 14:03:54,027 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0b5144a0-1643-4e1f-a076-c0786a462db5/bin/utaipan-UbGMyvGFUs/z3 [2021-11-19 14:03:54,031 INFO L229 MonitoredProcess]: Starting monitored process 8 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0b5144a0-1643-4e1f-a076-c0786a462db5/bin/utaipan-UbGMyvGFUs/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-19 14:03:54,050 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0b5144a0-1643-4e1f-a076-c0786a462db5/bin/utaipan-UbGMyvGFUs/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2021-11-19 14:03:54,266 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-19 14:03:54,272 INFO L263 TraceCheckSpWp]: Trace formula consists of 1087 conjuncts, 2 conjunts are in the unsatisfiable core [2021-11-19 14:03:54,275 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-19 14:03:54,484 INFO L134 CoverageAnalysis]: Checked inductivity of 53 backedges. 23 proven. 0 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2021-11-19 14:03:54,485 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-11-19 14:03:54,699 INFO L134 CoverageAnalysis]: Checked inductivity of 53 backedges. 0 proven. 21 refuted. 0 times theorem prover too weak. 32 trivial. 0 not checked. [2021-11-19 14:03:54,699 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [952914563] provided 1 perfect and 1 imperfect interpolant sequences [2021-11-19 14:03:54,699 INFO L186 FreeRefinementEngine]: Found 1 perfect and 2 imperfect interpolant sequences. [2021-11-19 14:03:54,700 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [5, 4] total 7 [2021-11-19 14:03:54,700 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1684415193] [2021-11-19 14:03:54,700 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-11-19 14:03:54,701 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2021-11-19 14:03:54,701 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-19 14:03:54,701 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2021-11-19 14:03:54,702 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2021-11-19 14:03:54,702 INFO L87 Difference]: Start difference. First operand 24179 states and 37265 transitions. Second operand has 3 states, 3 states have (on average 33.666666666666664) internal successors, (101), 2 states have internal predecessors, (101), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2021-11-19 14:03:56,425 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-19 14:03:56,426 INFO L93 Difference]: Finished difference Result 68860 states and 106266 transitions. [2021-11-19 14:03:56,426 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2021-11-19 14:03:56,427 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 33.666666666666664) internal successors, (101), 2 states have internal predecessors, (101), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 144 [2021-11-19 14:03:56,427 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-19 14:03:56,649 INFO L225 Difference]: With dead ends: 68860 [2021-11-19 14:03:56,649 INFO L226 Difference]: Without dead ends: 46327 [2021-11-19 14:03:56,735 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 291 GetRequests, 285 SyntacticMatches, 1 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2021-11-19 14:03:56,736 INFO L933 BasicCegarLoop]: 3334 mSDtfsCounter, 3539 mSDsluCounter, 294 mSDsCounter, 0 mSdLazyCounter, 319 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3539 SdHoareTripleChecker+Valid, 3582 SdHoareTripleChecker+Invalid, 321 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 319 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2021-11-19 14:03:56,736 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [3539 Valid, 3582 Invalid, 321 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 319 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2021-11-19 14:03:56,790 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 46327 states. [2021-11-19 14:03:58,827 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 46327 to 46195. [2021-11-19 14:03:58,903 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 46195 states, 39659 states have (on average 1.5187221059532514) internal successors, (60231), 39790 states have internal predecessors, (60231), 4998 states have call successors, (4998), 1537 states have call predecessors, (4998), 1536 states have return successors, (4996), 4868 states have call predecessors, (4996), 4996 states have call successors, (4996) [2021-11-19 14:03:59,169 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 46195 states to 46195 states and 70225 transitions. [2021-11-19 14:03:59,176 INFO L78 Accepts]: Start accepts. Automaton has 46195 states and 70225 transitions. Word has length 144 [2021-11-19 14:03:59,176 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-19 14:03:59,176 INFO L470 AbstractCegarLoop]: Abstraction has 46195 states and 70225 transitions. [2021-11-19 14:03:59,177 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 33.666666666666664) internal successors, (101), 2 states have internal predecessors, (101), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2021-11-19 14:03:59,177 INFO L276 IsEmpty]: Start isEmpty. Operand 46195 states and 70225 transitions. [2021-11-19 14:03:59,306 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 145 [2021-11-19 14:03:59,306 INFO L506 BasicCegarLoop]: Found error trace [2021-11-19 14:03:59,306 INFO L514 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-19 14:03:59,354 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0b5144a0-1643-4e1f-a076-c0786a462db5/bin/utaipan-UbGMyvGFUs/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2021-11-19 14:03:59,535 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,8 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0b5144a0-1643-4e1f-a076-c0786a462db5/bin/utaipan-UbGMyvGFUs/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-19 14:03:59,535 INFO L402 AbstractCegarLoop]: === Iteration 9 === Targeting errorErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, errorErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-19 14:03:59,535 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-19 14:03:59,536 INFO L85 PathProgramCache]: Analyzing trace with hash 1081606798, now seen corresponding path program 1 times [2021-11-19 14:03:59,536 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-19 14:03:59,536 INFO L332 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2050746161] [2021-11-19 14:03:59,536 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-19 14:03:59,536 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-19 14:03:59,603 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-19 14:04:00,086 INFO L134 CoverageAnalysis]: Checked inductivity of 53 backedges. 7 proven. 0 refuted. 0 times theorem prover too weak. 46 trivial. 0 not checked. [2021-11-19 14:04:00,086 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-19 14:04:00,087 INFO L332 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2050746161] [2021-11-19 14:04:00,087 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2050746161] provided 1 perfect and 0 imperfect interpolant sequences [2021-11-19 14:04:00,087 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-11-19 14:04:00,087 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2021-11-19 14:04:00,088 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1408574068] [2021-11-19 14:04:00,088 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-11-19 14:04:00,088 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2021-11-19 14:04:00,089 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-19 14:04:00,089 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2021-11-19 14:04:00,089 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2021-11-19 14:04:00,090 INFO L87 Difference]: Start difference. First operand 46195 states and 70225 transitions. Second operand has 6 states, 6 states have (on average 13.833333333333334) internal successors, (83), 6 states have internal predecessors, (83), 4 states have call successors, (9), 3 states have call predecessors, (9), 2 states have return successors, (8), 4 states have call predecessors, (8), 4 states have call successors, (8) [2021-11-19 14:04:05,381 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-19 14:04:05,382 INFO L93 Difference]: Finished difference Result 158075 states and 238040 transitions. [2021-11-19 14:04:05,382 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2021-11-19 14:04:05,383 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 13.833333333333334) internal successors, (83), 6 states have internal predecessors, (83), 4 states have call successors, (9), 3 states have call predecessors, (9), 2 states have return successors, (8), 4 states have call predecessors, (8), 4 states have call successors, (8) Word has length 144 [2021-11-19 14:04:05,384 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-19 14:04:06,201 INFO L225 Difference]: With dead ends: 158075 [2021-11-19 14:04:06,201 INFO L226 Difference]: Without dead ends: 113527 [2021-11-19 14:04:06,345 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 21 GetRequests, 12 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=41, Invalid=69, Unknown=0, NotChecked=0, Total=110 [2021-11-19 14:04:06,348 INFO L933 BasicCegarLoop]: 3345 mSDtfsCounter, 4497 mSDsluCounter, 7143 mSDsCounter, 0 mSdLazyCounter, 956 mSolverCounterSat, 156 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4519 SdHoareTripleChecker+Valid, 9963 SdHoareTripleChecker+Invalid, 1112 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 156 IncrementalHoareTripleChecker+Valid, 956 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.0s IncrementalHoareTripleChecker+Time [2021-11-19 14:04:06,348 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [4519 Valid, 9963 Invalid, 1112 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [156 Valid, 956 Invalid, 0 Unknown, 0 Unchecked, 1.0s Time] [2021-11-19 14:04:06,463 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 113527 states. [2021-11-19 14:04:10,232 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 113527 to 89203. [2021-11-19 14:04:10,346 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 89203 states, 76395 states have (on average 1.5038549643301262) internal successors, (114887), 76654 states have internal predecessors, (114887), 9734 states have call successors, (9734), 3073 states have call predecessors, (9734), 3072 states have return successors, (9732), 9476 states have call predecessors, (9732), 9732 states have call successors, (9732) [2021-11-19 14:04:10,777 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 89203 states to 89203 states and 134353 transitions. [2021-11-19 14:04:10,790 INFO L78 Accepts]: Start accepts. Automaton has 89203 states and 134353 transitions. Word has length 144 [2021-11-19 14:04:10,792 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-19 14:04:10,792 INFO L470 AbstractCegarLoop]: Abstraction has 89203 states and 134353 transitions. [2021-11-19 14:04:10,792 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 13.833333333333334) internal successors, (83), 6 states have internal predecessors, (83), 4 states have call successors, (9), 3 states have call predecessors, (9), 2 states have return successors, (8), 4 states have call predecessors, (8), 4 states have call successors, (8) [2021-11-19 14:04:10,793 INFO L276 IsEmpty]: Start isEmpty. Operand 89203 states and 134353 transitions. [2021-11-19 14:04:11,433 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 168 [2021-11-19 14:04:11,434 INFO L506 BasicCegarLoop]: Found error trace [2021-11-19 14:04:11,434 INFO L514 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-19 14:04:11,434 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8 [2021-11-19 14:04:11,434 INFO L402 AbstractCegarLoop]: === Iteration 10 === Targeting errorErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, errorErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-19 14:04:11,435 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-19 14:04:11,435 INFO L85 PathProgramCache]: Analyzing trace with hash 124723034, now seen corresponding path program 1 times [2021-11-19 14:04:11,435 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-19 14:04:11,436 INFO L332 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [433077331] [2021-11-19 14:04:11,436 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-19 14:04:11,436 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-19 14:04:11,479 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-19 14:04:11,570 INFO L134 CoverageAnalysis]: Checked inductivity of 80 backedges. 10 proven. 44 refuted. 0 times theorem prover too weak. 26 trivial. 0 not checked. [2021-11-19 14:04:11,570 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-19 14:04:11,570 INFO L332 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [433077331] [2021-11-19 14:04:11,571 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [433077331] provided 0 perfect and 1 imperfect interpolant sequences [2021-11-19 14:04:11,571 INFO L332 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1043867558] [2021-11-19 14:04:11,571 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-19 14:04:11,571 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-19 14:04:11,572 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0b5144a0-1643-4e1f-a076-c0786a462db5/bin/utaipan-UbGMyvGFUs/z3 [2021-11-19 14:04:11,573 INFO L229 MonitoredProcess]: Starting monitored process 9 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0b5144a0-1643-4e1f-a076-c0786a462db5/bin/utaipan-UbGMyvGFUs/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-19 14:04:11,593 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0b5144a0-1643-4e1f-a076-c0786a462db5/bin/utaipan-UbGMyvGFUs/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2021-11-19 14:04:11,872 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-19 14:04:11,877 INFO L263 TraceCheckSpWp]: Trace formula consists of 1123 conjuncts, 2 conjunts are in the unsatisfiable core [2021-11-19 14:04:11,882 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-19 14:04:12,189 INFO L134 CoverageAnalysis]: Checked inductivity of 80 backedges. 29 proven. 0 refuted. 0 times theorem prover too weak. 51 trivial. 0 not checked. [2021-11-19 14:04:12,189 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-11-19 14:04:12,484 INFO L134 CoverageAnalysis]: Checked inductivity of 80 backedges. 25 proven. 0 refuted. 0 times theorem prover too weak. 55 trivial. 0 not checked. [2021-11-19 14:04:12,485 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1043867558] provided 2 perfect and 0 imperfect interpolant sequences [2021-11-19 14:04:12,485 INFO L186 FreeRefinementEngine]: Found 2 perfect and 1 imperfect interpolant sequences. [2021-11-19 14:04:12,485 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3, 3] imperfect sequences [6] total 8 [2021-11-19 14:04:12,485 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [266228222] [2021-11-19 14:04:12,485 INFO L85 oduleStraightlineAll]: Using 2 perfect interpolants to construct interpolant automaton [2021-11-19 14:04:12,486 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2021-11-19 14:04:12,486 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-19 14:04:12,486 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2021-11-19 14:04:12,487 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=41, Unknown=0, NotChecked=0, Total=56 [2021-11-19 14:04:12,487 INFO L87 Difference]: Start difference. First operand 89203 states and 134353 transitions. Second operand has 4 states, 4 states have (on average 30.0) internal successors, (120), 4 states have internal predecessors, (120), 4 states have call successors, (10), 3 states have call predecessors, (10), 2 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) [2021-11-19 14:04:17,075 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-19 14:04:17,075 INFO L93 Difference]: Finished difference Result 159991 states and 243796 transitions. [2021-11-19 14:04:17,081 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2021-11-19 14:04:17,081 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 30.0) internal successors, (120), 4 states have internal predecessors, (120), 4 states have call successors, (10), 3 states have call predecessors, (10), 2 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) Word has length 167 [2021-11-19 14:04:17,081 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-19 14:04:17,698 INFO L225 Difference]: With dead ends: 159991 [2021-11-19 14:04:17,698 INFO L226 Difference]: Without dead ends: 115187 [2021-11-19 14:04:17,804 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 340 GetRequests, 334 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=15, Invalid=41, Unknown=0, NotChecked=0, Total=56 [2021-11-19 14:04:17,805 INFO L933 BasicCegarLoop]: 3456 mSDtfsCounter, 271 mSDsluCounter, 3589 mSDsCounter, 0 mSdLazyCounter, 566 mSolverCounterSat, 20 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 271 SdHoareTripleChecker+Valid, 6786 SdHoareTripleChecker+Invalid, 586 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 20 IncrementalHoareTripleChecker+Valid, 566 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2021-11-19 14:04:17,805 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [271 Valid, 6786 Invalid, 586 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [20 Valid, 566 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2021-11-19 14:04:17,913 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 115187 states. [2021-11-19 14:04:21,462 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 115187 to 106227. [2021-11-19 14:04:21,551 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 106227 states, 92907 states have (on average 1.5451903516419645) internal successors, (143559), 93166 states have internal predecessors, (143559), 9990 states have call successors, (9990), 3329 states have call predecessors, (9990), 3328 states have return successors, (9988), 9732 states have call predecessors, (9988), 9988 states have call successors, (9988) [2021-11-19 14:04:22,434 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 106227 states to 106227 states and 163537 transitions. [2021-11-19 14:04:22,448 INFO L78 Accepts]: Start accepts. Automaton has 106227 states and 163537 transitions. Word has length 167 [2021-11-19 14:04:22,449 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-19 14:04:22,449 INFO L470 AbstractCegarLoop]: Abstraction has 106227 states and 163537 transitions. [2021-11-19 14:04:22,450 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 30.0) internal successors, (120), 4 states have internal predecessors, (120), 4 states have call successors, (10), 3 states have call predecessors, (10), 2 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) [2021-11-19 14:04:22,450 INFO L276 IsEmpty]: Start isEmpty. Operand 106227 states and 163537 transitions. [2021-11-19 14:04:22,754 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 221 [2021-11-19 14:04:22,755 INFO L506 BasicCegarLoop]: Found error trace [2021-11-19 14:04:22,755 INFO L514 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-19 14:04:22,793 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0b5144a0-1643-4e1f-a076-c0786a462db5/bin/utaipan-UbGMyvGFUs/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2021-11-19 14:04:22,982 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0b5144a0-1643-4e1f-a076-c0786a462db5/bin/utaipan-UbGMyvGFUs/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2021-11-19 14:04:22,983 INFO L402 AbstractCegarLoop]: === Iteration 11 === Targeting errorErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, errorErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-19 14:04:22,983 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-19 14:04:22,983 INFO L85 PathProgramCache]: Analyzing trace with hash -1607564969, now seen corresponding path program 1 times [2021-11-19 14:04:22,984 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-19 14:04:22,984 INFO L332 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1755831924] [2021-11-19 14:04:22,984 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-19 14:04:22,984 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-19 14:04:23,035 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-19 14:04:23,145 INFO L134 CoverageAnalysis]: Checked inductivity of 169 backedges. 10 proven. 87 refuted. 0 times theorem prover too weak. 72 trivial. 0 not checked. [2021-11-19 14:04:23,146 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-19 14:04:23,146 INFO L332 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1755831924] [2021-11-19 14:04:23,146 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1755831924] provided 0 perfect and 1 imperfect interpolant sequences [2021-11-19 14:04:23,146 INFO L332 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1097539259] [2021-11-19 14:04:23,147 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-19 14:04:23,147 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-19 14:04:23,147 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0b5144a0-1643-4e1f-a076-c0786a462db5/bin/utaipan-UbGMyvGFUs/z3 [2021-11-19 14:04:23,151 INFO L229 MonitoredProcess]: Starting monitored process 10 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0b5144a0-1643-4e1f-a076-c0786a462db5/bin/utaipan-UbGMyvGFUs/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-19 14:04:23,173 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0b5144a0-1643-4e1f-a076-c0786a462db5/bin/utaipan-UbGMyvGFUs/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2021-11-19 14:04:23,458 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-19 14:04:23,462 INFO L263 TraceCheckSpWp]: Trace formula consists of 1405 conjuncts, 2 conjunts are in the unsatisfiable core [2021-11-19 14:04:23,469 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-19 14:04:23,963 INFO L134 CoverageAnalysis]: Checked inductivity of 169 backedges. 105 proven. 0 refuted. 0 times theorem prover too weak. 64 trivial. 0 not checked. [2021-11-19 14:04:23,963 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-11-19 14:04:24,414 INFO L134 CoverageAnalysis]: Checked inductivity of 169 backedges. 12 proven. 0 refuted. 0 times theorem prover too weak. 157 trivial. 0 not checked. [2021-11-19 14:04:24,414 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1097539259] provided 2 perfect and 0 imperfect interpolant sequences [2021-11-19 14:04:24,414 INFO L186 FreeRefinementEngine]: Found 2 perfect and 1 imperfect interpolant sequences. [2021-11-19 14:04:24,415 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2, 3] imperfect sequences [6] total 7 [2021-11-19 14:04:24,415 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [877709567] [2021-11-19 14:04:24,415 INFO L85 oduleStraightlineAll]: Using 2 perfect interpolants to construct interpolant automaton [2021-11-19 14:04:24,416 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2021-11-19 14:04:24,416 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-19 14:04:24,417 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2021-11-19 14:04:24,417 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=12, Invalid=30, Unknown=0, NotChecked=0, Total=42 [2021-11-19 14:04:24,417 INFO L87 Difference]: Start difference. First operand 106227 states and 163537 transitions. Second operand has 3 states, 3 states have (on average 63.0) internal successors, (189), 3 states have internal predecessors, (189), 3 states have call successors, (20), 3 states have call predecessors, (20), 3 states have return successors, (19), 3 states have call predecessors, (19), 3 states have call successors, (19) [2021-11-19 14:04:31,603 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-19 14:04:31,603 INFO L93 Difference]: Finished difference Result 313852 states and 487642 transitions. [2021-11-19 14:04:31,604 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2021-11-19 14:04:31,604 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 63.0) internal successors, (189), 3 states have internal predecessors, (189), 3 states have call successors, (20), 3 states have call predecessors, (20), 3 states have return successors, (19), 3 states have call predecessors, (19), 3 states have call successors, (19) Word has length 220 [2021-11-19 14:04:31,604 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-19 14:04:32,444 INFO L225 Difference]: With dead ends: 313852 [2021-11-19 14:04:32,444 INFO L226 Difference]: Without dead ends: 209271 [2021-11-19 14:04:32,623 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 446 GetRequests, 440 SyntacticMatches, 1 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=12, Invalid=30, Unknown=0, NotChecked=0, Total=42 [2021-11-19 14:04:32,624 INFO L933 BasicCegarLoop]: 3334 mSDtfsCounter, 3475 mSDsluCounter, 294 mSDsCounter, 0 mSdLazyCounter, 319 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3475 SdHoareTripleChecker+Valid, 3582 SdHoareTripleChecker+Invalid, 321 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 319 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2021-11-19 14:04:32,624 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [3475 Valid, 3582 Invalid, 321 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 319 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2021-11-19 14:04:32,785 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 209271 states.