java -Xmx8000000000 -jar /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/data -tc ../../../trunk/examples/toolchains/AutomizerCInline.xml -s ../../../trunk/examples/settings/default/taipan/svcomp-Reach-64bit-Taipan_Default.epf -i ../../../trunk/examples/svcomp/loop-acceleration/diamond_true-unreach-call1_true-termination.i -------------------------------------------------------------------------------- This is Ultimate 0.1.23-1dbac8b [2018-10-27 04:08:41,384 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-10-27 04:08:41,386 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-10-27 04:08:41,398 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-10-27 04:08:41,398 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-10-27 04:08:41,399 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-10-27 04:08:41,400 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-10-27 04:08:41,402 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-10-27 04:08:41,404 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-10-27 04:08:41,404 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-10-27 04:08:41,405 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-10-27 04:08:41,406 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-10-27 04:08:41,407 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-10-27 04:08:41,408 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-10-27 04:08:41,409 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-10-27 04:08:41,409 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-10-27 04:08:41,410 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-10-27 04:08:41,412 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-10-27 04:08:41,414 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-10-27 04:08:41,415 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-10-27 04:08:41,416 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-10-27 04:08:41,418 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-10-27 04:08:41,420 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-10-27 04:08:41,420 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-10-27 04:08:41,420 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-10-27 04:08:41,421 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-10-27 04:08:41,422 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-10-27 04:08:41,423 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-10-27 04:08:41,424 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-10-27 04:08:41,425 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-10-27 04:08:41,425 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-10-27 04:08:41,426 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-10-27 04:08:41,426 INFO L177 SettingsManager]: ReqParser provides no preferences, ignoring... [2018-10-27 04:08:41,426 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-10-27 04:08:41,427 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-10-27 04:08:41,428 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-10-27 04:08:41,428 INFO L98 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/../../../trunk/examples/settings/default/taipan/svcomp-Reach-64bit-Taipan_Default.epf [2018-10-27 04:08:41,458 INFO L110 SettingsManager]: Loading preferences was successful [2018-10-27 04:08:41,458 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-10-27 04:08:41,459 INFO L131 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2018-10-27 04:08:41,459 INFO L133 SettingsManager]: * User list type=DISABLED [2018-10-27 04:08:41,459 INFO L133 SettingsManager]: * calls to implemented procedures=false [2018-10-27 04:08:41,459 INFO L131 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2018-10-27 04:08:41,460 INFO L133 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2018-10-27 04:08:41,460 INFO L133 SettingsManager]: * Abstract domain=CompoundDomain [2018-10-27 04:08:41,460 INFO L133 SettingsManager]: * Log string format=TERM [2018-10-27 04:08:41,460 INFO L133 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2018-10-27 04:08:41,460 INFO L133 SettingsManager]: * Use the RCFG-of-the-future interface=true [2018-10-27 04:08:41,461 INFO L133 SettingsManager]: * Interval Domain=false [2018-10-27 04:08:41,462 INFO L131 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2018-10-27 04:08:41,462 INFO L133 SettingsManager]: * Overapproximate operations on floating types=true [2018-10-27 04:08:41,462 INFO L133 SettingsManager]: * Check division by zero=IGNORE [2018-10-27 04:08:41,462 INFO L133 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2018-10-27 04:08:41,462 INFO L133 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2018-10-27 04:08:41,463 INFO L133 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2018-10-27 04:08:41,464 INFO L133 SettingsManager]: * Check if freed pointer was valid=false [2018-10-27 04:08:41,464 INFO L133 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2018-10-27 04:08:41,465 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-10-27 04:08:41,465 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-10-27 04:08:41,465 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-10-27 04:08:41,465 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-10-27 04:08:41,465 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-10-27 04:08:41,466 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-10-27 04:08:41,466 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-10-27 04:08:41,466 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-10-27 04:08:41,466 INFO L133 SettingsManager]: * Trace refinement strategy=TAIPAN [2018-10-27 04:08:41,467 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-10-27 04:08:41,467 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-10-27 04:08:41,467 INFO L133 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2018-10-27 04:08:41,467 INFO L133 SettingsManager]: * To the following directory=dump/ [2018-10-27 04:08:41,467 INFO L133 SettingsManager]: * Abstract interpretation Mode=USE_PREDICATES [2018-10-27 04:08:41,528 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2018-10-27 04:08:41,542 INFO L258 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-10-27 04:08:41,546 INFO L214 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2018-10-27 04:08:41,548 INFO L271 PluginConnector]: Initializing CDTParser... [2018-10-27 04:08:41,548 INFO L276 PluginConnector]: CDTParser initialized [2018-10-27 04:08:41,549 INFO L418 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/../../../trunk/examples/svcomp/loop-acceleration/diamond_true-unreach-call1_true-termination.i [2018-10-27 04:08:41,610 INFO L218 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/data/4706d9a13/f44ff24db74f4b33a0156e4358c3a2a0/FLAG5362ae73f [2018-10-27 04:08:42,014 INFO L298 CDTParser]: Found 1 translation units. [2018-10-27 04:08:42,015 INFO L158 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/loop-acceleration/diamond_true-unreach-call1_true-termination.i [2018-10-27 04:08:42,022 INFO L346 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/data/4706d9a13/f44ff24db74f4b33a0156e4358c3a2a0/FLAG5362ae73f [2018-10-27 04:08:42,037 INFO L354 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/data/4706d9a13/f44ff24db74f4b33a0156e4358c3a2a0 [2018-10-27 04:08:42,048 INFO L296 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2018-10-27 04:08:42,049 INFO L131 ToolchainWalker]: Walking toolchain with 5 elements. [2018-10-27 04:08:42,050 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2018-10-27 04:08:42,050 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2018-10-27 04:08:42,054 INFO L276 PluginConnector]: CACSL2BoogieTranslator initialized [2018-10-27 04:08:42,055 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 27.10 04:08:42" (1/1) ... [2018-10-27 04:08:42,058 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@401f344f and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.10 04:08:42, skipping insertion in model container [2018-10-27 04:08:42,058 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 27.10 04:08:42" (1/1) ... [2018-10-27 04:08:42,069 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2018-10-27 04:08:42,090 INFO L174 MainTranslator]: Built tables and reachable declarations [2018-10-27 04:08:42,274 INFO L202 PostProcessor]: Analyzing one entry point: main [2018-10-27 04:08:42,278 INFO L189 MainTranslator]: Completed pre-run [2018-10-27 04:08:42,299 INFO L202 PostProcessor]: Analyzing one entry point: main [2018-10-27 04:08:42,316 INFO L193 MainTranslator]: Completed translation [2018-10-27 04:08:42,316 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.10 04:08:42 WrapperNode [2018-10-27 04:08:42,317 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2018-10-27 04:08:42,318 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2018-10-27 04:08:42,318 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2018-10-27 04:08:42,318 INFO L276 PluginConnector]: Boogie Procedure Inliner initialized [2018-10-27 04:08:42,327 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.10 04:08:42" (1/1) ... [2018-10-27 04:08:42,332 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.10 04:08:42" (1/1) ... [2018-10-27 04:08:42,336 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2018-10-27 04:08:42,337 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2018-10-27 04:08:42,337 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2018-10-27 04:08:42,337 INFO L276 PluginConnector]: Boogie Preprocessor initialized [2018-10-27 04:08:42,344 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.10 04:08:42" (1/1) ... [2018-10-27 04:08:42,344 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.10 04:08:42" (1/1) ... [2018-10-27 04:08:42,345 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.10 04:08:42" (1/1) ... [2018-10-27 04:08:42,345 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.10 04:08:42" (1/1) ... [2018-10-27 04:08:42,348 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.10 04:08:42" (1/1) ... [2018-10-27 04:08:42,356 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.10 04:08:42" (1/1) ... [2018-10-27 04:08:42,357 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.10 04:08:42" (1/1) ... [2018-10-27 04:08:42,358 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2018-10-27 04:08:42,359 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2018-10-27 04:08:42,359 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2018-10-27 04:08:42,359 INFO L276 PluginConnector]: RCFGBuilder initialized [2018-10-27 04:08:42,360 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.10 04:08:42" (1/1) ... No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-10-27 04:08:42,482 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2018-10-27 04:08:42,482 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2018-10-27 04:08:42,482 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2018-10-27 04:08:42,482 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2018-10-27 04:08:42,482 INFO L130 BoogieDeclarations]: Found specification of procedure main [2018-10-27 04:08:42,483 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2018-10-27 04:08:42,483 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2018-10-27 04:08:42,483 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2018-10-27 04:08:42,674 INFO L341 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2018-10-27 04:08:42,674 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 27.10 04:08:42 BoogieIcfgContainer [2018-10-27 04:08:42,675 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2018-10-27 04:08:42,675 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2018-10-27 04:08:42,676 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2018-10-27 04:08:42,679 INFO L276 PluginConnector]: TraceAbstraction initialized [2018-10-27 04:08:42,679 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 27.10 04:08:42" (1/3) ... [2018-10-27 04:08:42,680 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@47919b5 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 27.10 04:08:42, skipping insertion in model container [2018-10-27 04:08:42,680 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.10 04:08:42" (2/3) ... [2018-10-27 04:08:42,680 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@47919b5 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 27.10 04:08:42, skipping insertion in model container [2018-10-27 04:08:42,680 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 27.10 04:08:42" (3/3) ... [2018-10-27 04:08:42,682 INFO L112 eAbstractionObserver]: Analyzing ICFG diamond_true-unreach-call1_true-termination.i [2018-10-27 04:08:42,691 INFO L136 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-10-27 04:08:42,698 INFO L148 ceAbstractionStarter]: Appying trace abstraction to program that has 1 error locations. [2018-10-27 04:08:42,712 INFO L257 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2018-10-27 04:08:42,745 INFO L382 AbstractCegarLoop]: Interprodecural is true [2018-10-27 04:08:42,745 INFO L383 AbstractCegarLoop]: Hoare is true [2018-10-27 04:08:42,745 INFO L384 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-10-27 04:08:42,745 INFO L385 AbstractCegarLoop]: Backedges is STRAIGHT_LINE [2018-10-27 04:08:42,746 INFO L386 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-10-27 04:08:42,746 INFO L387 AbstractCegarLoop]: Difference is false [2018-10-27 04:08:42,746 INFO L388 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-10-27 04:08:42,746 INFO L393 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-10-27 04:08:42,764 INFO L276 IsEmpty]: Start isEmpty. Operand 19 states. [2018-10-27 04:08:42,770 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 11 [2018-10-27 04:08:42,770 INFO L367 BasicCegarLoop]: Found error trace [2018-10-27 04:08:42,771 INFO L375 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-27 04:08:42,773 INFO L424 AbstractCegarLoop]: === Iteration 1 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-27 04:08:42,778 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-27 04:08:42,779 INFO L82 PathProgramCache]: Analyzing trace with hash 1713253442, now seen corresponding path program 1 times [2018-10-27 04:08:42,781 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-27 04:08:42,827 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 04:08:42,827 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-27 04:08:42,827 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 04:08:42,827 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-27 04:08:42,852 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-27 04:08:42,876 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:08:42,878 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-10-27 04:08:42,878 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2018-10-27 04:08:42,878 INFO L258 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-10-27 04:08:42,883 INFO L460 AbstractCegarLoop]: Interpolant automaton has 2 states [2018-10-27 04:08:42,898 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2018-10-27 04:08:42,898 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2018-10-27 04:08:42,901 INFO L87 Difference]: Start difference. First operand 19 states. Second operand 2 states. [2018-10-27 04:08:42,922 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-27 04:08:42,923 INFO L93 Difference]: Finished difference Result 30 states and 34 transitions. [2018-10-27 04:08:42,923 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2018-10-27 04:08:42,924 INFO L78 Accepts]: Start accepts. Automaton has 2 states. Word has length 10 [2018-10-27 04:08:42,925 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-27 04:08:42,933 INFO L225 Difference]: With dead ends: 30 [2018-10-27 04:08:42,933 INFO L226 Difference]: Without dead ends: 13 [2018-10-27 04:08:42,936 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2018-10-27 04:08:42,955 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 13 states. [2018-10-27 04:08:42,972 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-10-27 04:08:42,974 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 13 states. [2018-10-27 04:08:42,974 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 13 states to 13 states and 14 transitions. [2018-10-27 04:08:42,976 INFO L78 Accepts]: Start accepts. Automaton has 13 states and 14 transitions. Word has length 10 [2018-10-27 04:08:42,977 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-27 04:08:42,977 INFO L481 AbstractCegarLoop]: Abstraction has 13 states and 14 transitions. [2018-10-27 04:08:42,977 INFO L482 AbstractCegarLoop]: Interpolant automaton has 2 states. [2018-10-27 04:08:42,977 INFO L276 IsEmpty]: Start isEmpty. Operand 13 states and 14 transitions. [2018-10-27 04:08:42,978 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2018-10-27 04:08:42,978 INFO L367 BasicCegarLoop]: Found error trace [2018-10-27 04:08:42,978 INFO L375 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-27 04:08:42,979 INFO L424 AbstractCegarLoop]: === Iteration 2 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-27 04:08:42,979 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-27 04:08:42,979 INFO L82 PathProgramCache]: Analyzing trace with hash 1144102878, now seen corresponding path program 1 times [2018-10-27 04:08:42,979 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-27 04:08:42,981 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 04:08:42,981 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-27 04:08:42,981 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 04:08:42,981 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-27 04:08:43,009 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-27 04:08:43,194 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:08:43,195 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-10-27 04:08:43,195 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-10-27 04:08:43,195 INFO L258 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-10-27 04:08:43,197 INFO L460 AbstractCegarLoop]: Interpolant automaton has 3 states [2018-10-27 04:08:43,197 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2018-10-27 04:08:43,198 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-10-27 04:08:43,198 INFO L87 Difference]: Start difference. First operand 13 states and 14 transitions. Second operand 3 states. [2018-10-27 04:08:43,302 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-27 04:08:43,303 INFO L93 Difference]: Finished difference Result 21 states and 23 transitions. [2018-10-27 04:08:43,303 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-10-27 04:08:43,304 INFO L78 Accepts]: Start accepts. Automaton has 3 states. Word has length 11 [2018-10-27 04:08:43,305 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-27 04:08:43,311 INFO L225 Difference]: With dead ends: 21 [2018-10-27 04:08:43,311 INFO L226 Difference]: Without dead ends: 16 [2018-10-27 04:08:43,312 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-10-27 04:08:43,313 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 16 states. [2018-10-27 04:08:43,321 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 16 to 15. [2018-10-27 04:08:43,322 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 15 states. [2018-10-27 04:08:43,322 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 15 states to 15 states and 16 transitions. [2018-10-27 04:08:43,323 INFO L78 Accepts]: Start accepts. Automaton has 15 states and 16 transitions. Word has length 11 [2018-10-27 04:08:43,323 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-27 04:08:43,323 INFO L481 AbstractCegarLoop]: Abstraction has 15 states and 16 transitions. [2018-10-27 04:08:43,323 INFO L482 AbstractCegarLoop]: Interpolant automaton has 3 states. [2018-10-27 04:08:43,323 INFO L276 IsEmpty]: Start isEmpty. Operand 15 states and 16 transitions. [2018-10-27 04:08:43,332 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2018-10-27 04:08:43,332 INFO L367 BasicCegarLoop]: Found error trace [2018-10-27 04:08:43,332 INFO L375 BasicCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-27 04:08:43,333 INFO L424 AbstractCegarLoop]: === Iteration 3 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-27 04:08:43,333 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-27 04:08:43,333 INFO L82 PathProgramCache]: Analyzing trace with hash -2056921797, now seen corresponding path program 1 times [2018-10-27 04:08:43,333 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-27 04:08:43,334 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 04:08:43,338 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-27 04:08:43,339 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 04:08:43,339 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-27 04:08:43,370 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-27 04:08:43,524 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:08:43,524 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-27 04:08:43,524 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-10-27 04:08:43,526 INFO L200 CegarAbsIntRunner]: Running AI on error trace of length 15 with the following transitions: [2018-10-27 04:08:43,529 INFO L202 CegarAbsIntRunner]: [0], [4], [8], [12], [14], [17], [26], [29], [31], [37], [38], [39], [41] [2018-10-27 04:08:43,578 INFO L148 AbstractInterpreter]: Using domain PoormanAbstractDomain with backing domain CompoundDomain [CongruenceDomain, OctagonDomain] [2018-10-27 04:08:43,579 INFO L101 FixpointEngine]: Starting fixpoint engine with domain PoormanAbstractDomain (maxUnwinding=3, maxParallelStates=2) [2018-10-27 04:08:43,681 WARN L79 EvaluatorLogger]: Possible loss of precision. Operator ARITHMOD has no precise implementation. [2018-10-27 04:08:44,198 INFO L263 AbstractInterpreter]: Some error location(s) were reachable [2018-10-27 04:08:44,200 INFO L272 AbstractInterpreter]: Visited 13 different actions 77 times. Merged at 4 different actions 34 times. Widened at 1 different actions 5 times. Found 1 fixpoints after 1 different actions. Largest state had 3 variables. [2018-10-27 04:08:44,240 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-27 04:08:44,242 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: Unknown [2018-10-27 04:08:44,242 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-27 04:08:44,242 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/z3 Starting monitored process 2 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 2 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-27 04:08:44,255 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-27 04:08:44,255 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-10-27 04:08:44,281 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-27 04:08:44,289 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-27 04:08:44,367 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:08:44,367 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-10-27 04:08:44,491 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:08:44,512 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-10-27 04:08:44,512 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4, 4] total 6 [2018-10-27 04:08:44,512 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-10-27 04:08:44,513 INFO L460 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-10-27 04:08:44,513 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-10-27 04:08:44,514 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=17, Unknown=0, NotChecked=0, Total=30 [2018-10-27 04:08:44,514 INFO L87 Difference]: Start difference. First operand 15 states and 16 transitions. Second operand 4 states. [2018-10-27 04:08:44,617 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-27 04:08:44,617 INFO L93 Difference]: Finished difference Result 24 states and 27 transitions. [2018-10-27 04:08:44,618 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-10-27 04:08:44,618 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 14 [2018-10-27 04:08:44,618 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-27 04:08:44,619 INFO L225 Difference]: With dead ends: 24 [2018-10-27 04:08:44,619 INFO L226 Difference]: Without dead ends: 19 [2018-10-27 04:08:44,620 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 32 GetRequests, 26 SyntacticMatches, 2 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=13, Invalid=17, Unknown=0, NotChecked=0, Total=30 [2018-10-27 04:08:44,621 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 19 states. [2018-10-27 04:08:44,624 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 19 to 18. [2018-10-27 04:08:44,624 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 18 states. [2018-10-27 04:08:44,625 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 18 states to 18 states and 20 transitions. [2018-10-27 04:08:44,626 INFO L78 Accepts]: Start accepts. Automaton has 18 states and 20 transitions. Word has length 14 [2018-10-27 04:08:44,626 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-27 04:08:44,626 INFO L481 AbstractCegarLoop]: Abstraction has 18 states and 20 transitions. [2018-10-27 04:08:44,627 INFO L482 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-10-27 04:08:44,627 INFO L276 IsEmpty]: Start isEmpty. Operand 18 states and 20 transitions. [2018-10-27 04:08:44,627 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2018-10-27 04:08:44,628 INFO L367 BasicCegarLoop]: Found error trace [2018-10-27 04:08:44,630 INFO L375 BasicCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-27 04:08:44,631 INFO L424 AbstractCegarLoop]: === Iteration 4 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-27 04:08:44,631 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-27 04:08:44,631 INFO L82 PathProgramCache]: Analyzing trace with hash -281914435, now seen corresponding path program 1 times [2018-10-27 04:08:44,631 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-27 04:08:44,632 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 04:08:44,632 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-27 04:08:44,635 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 04:08:44,635 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-27 04:08:44,656 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-27 04:08:44,807 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:08:44,808 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-27 04:08:44,808 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-10-27 04:08:44,808 INFO L200 CegarAbsIntRunner]: Running AI on error trace of length 15 with the following transitions: [2018-10-27 04:08:44,808 INFO L202 CegarAbsIntRunner]: [0], [4], [8], [12], [14], [19], [26], [29], [31], [37], [38], [39], [41] [2018-10-27 04:08:44,810 INFO L148 AbstractInterpreter]: Using domain PoormanAbstractDomain with backing domain CompoundDomain [CongruenceDomain, OctagonDomain] [2018-10-27 04:08:44,810 INFO L101 FixpointEngine]: Starting fixpoint engine with domain PoormanAbstractDomain (maxUnwinding=3, maxParallelStates=2) [2018-10-27 04:08:44,815 WARN L79 EvaluatorLogger]: Possible loss of precision. Operator ARITHMOD has no precise implementation. [2018-10-27 04:08:45,089 INFO L263 AbstractInterpreter]: Some error location(s) were reachable [2018-10-27 04:08:45,089 INFO L272 AbstractInterpreter]: Visited 13 different actions 77 times. Merged at 4 different actions 34 times. Widened at 1 different actions 5 times. Found 1 fixpoints after 1 different actions. Largest state had 4 variables. [2018-10-27 04:08:45,126 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-27 04:08:45,126 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: Unknown [2018-10-27 04:08:45,126 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-27 04:08:45,127 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/z3 Starting monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-27 04:08:45,142 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-27 04:08:45,142 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-10-27 04:08:45,169 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-27 04:08:45,171 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-27 04:08:45,242 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:08:45,242 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-10-27 04:08:45,515 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:08:45,544 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-10-27 04:08:45,544 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4, 4] total 6 [2018-10-27 04:08:45,544 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-10-27 04:08:45,545 INFO L460 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-10-27 04:08:45,545 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-10-27 04:08:45,545 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=17, Unknown=0, NotChecked=0, Total=30 [2018-10-27 04:08:45,546 INFO L87 Difference]: Start difference. First operand 18 states and 20 transitions. Second operand 4 states. [2018-10-27 04:08:45,656 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-27 04:08:45,657 INFO L93 Difference]: Finished difference Result 26 states and 29 transitions. [2018-10-27 04:08:45,658 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-10-27 04:08:45,658 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 14 [2018-10-27 04:08:45,658 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-27 04:08:45,659 INFO L225 Difference]: With dead ends: 26 [2018-10-27 04:08:45,660 INFO L226 Difference]: Without dead ends: 21 [2018-10-27 04:08:45,660 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 32 GetRequests, 26 SyntacticMatches, 2 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=13, Invalid=17, Unknown=0, NotChecked=0, Total=30 [2018-10-27 04:08:45,661 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 21 states. [2018-10-27 04:08:45,664 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 21 to 18. [2018-10-27 04:08:45,664 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 18 states. [2018-10-27 04:08:45,665 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 18 states to 18 states and 20 transitions. [2018-10-27 04:08:45,665 INFO L78 Accepts]: Start accepts. Automaton has 18 states and 20 transitions. Word has length 14 [2018-10-27 04:08:45,666 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-27 04:08:45,666 INFO L481 AbstractCegarLoop]: Abstraction has 18 states and 20 transitions. [2018-10-27 04:08:45,666 INFO L482 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-10-27 04:08:45,666 INFO L276 IsEmpty]: Start isEmpty. Operand 18 states and 20 transitions. [2018-10-27 04:08:45,666 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2018-10-27 04:08:45,666 INFO L367 BasicCegarLoop]: Found error trace [2018-10-27 04:08:45,667 INFO L375 BasicCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-27 04:08:45,667 INFO L424 AbstractCegarLoop]: === Iteration 5 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-27 04:08:45,667 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-27 04:08:45,667 INFO L82 PathProgramCache]: Analyzing trace with hash 1670825662, now seen corresponding path program 2 times [2018-10-27 04:08:45,667 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-27 04:08:45,668 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 04:08:45,669 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-27 04:08:45,669 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 04:08:45,669 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-27 04:08:45,679 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-27 04:08:45,930 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:08:45,930 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-27 04:08:45,930 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-10-27 04:08:45,931 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-10-27 04:08:45,931 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-10-27 04:08:45,931 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-27 04:08:45,931 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/z3 Starting monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-27 04:08:45,948 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-10-27 04:08:45,949 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST2 (IT: FPandBP) [2018-10-27 04:08:46,003 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2018-10-27 04:08:46,003 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-27 04:08:46,006 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-27 04:08:46,075 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:08:46,075 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-10-27 04:08:46,161 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:08:46,188 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-10-27 04:08:46,188 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5, 5] total 8 [2018-10-27 04:08:46,188 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-10-27 04:08:46,189 INFO L460 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-10-27 04:08:46,189 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-10-27 04:08:46,189 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=22, Invalid=34, Unknown=0, NotChecked=0, Total=56 [2018-10-27 04:08:46,190 INFO L87 Difference]: Start difference. First operand 18 states and 20 transitions. Second operand 5 states. [2018-10-27 04:08:46,363 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-27 04:08:46,363 INFO L93 Difference]: Finished difference Result 29 states and 33 transitions. [2018-10-27 04:08:46,364 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-10-27 04:08:46,364 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 17 [2018-10-27 04:08:46,364 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-27 04:08:46,365 INFO L225 Difference]: With dead ends: 29 [2018-10-27 04:08:46,365 INFO L226 Difference]: Without dead ends: 24 [2018-10-27 04:08:46,366 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 39 GetRequests, 31 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=22, Invalid=34, Unknown=0, NotChecked=0, Total=56 [2018-10-27 04:08:46,366 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 24 states. [2018-10-27 04:08:46,369 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 24 to 21. [2018-10-27 04:08:46,369 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 21 states. [2018-10-27 04:08:46,370 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 21 states to 21 states and 24 transitions. [2018-10-27 04:08:46,370 INFO L78 Accepts]: Start accepts. Automaton has 21 states and 24 transitions. Word has length 17 [2018-10-27 04:08:46,371 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-27 04:08:46,371 INFO L481 AbstractCegarLoop]: Abstraction has 21 states and 24 transitions. [2018-10-27 04:08:46,371 INFO L482 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-10-27 04:08:46,371 INFO L276 IsEmpty]: Start isEmpty. Operand 21 states and 24 transitions. [2018-10-27 04:08:46,372 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2018-10-27 04:08:46,372 INFO L367 BasicCegarLoop]: Found error trace [2018-10-27 04:08:46,372 INFO L375 BasicCegarLoop]: trace histogram [3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-27 04:08:46,372 INFO L424 AbstractCegarLoop]: === Iteration 6 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-27 04:08:46,373 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-27 04:08:46,373 INFO L82 PathProgramCache]: Analyzing trace with hash -849134272, now seen corresponding path program 1 times [2018-10-27 04:08:46,373 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-27 04:08:46,374 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 04:08:46,374 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-27 04:08:46,374 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 04:08:46,374 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-27 04:08:46,384 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-27 04:08:46,482 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:08:46,483 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-27 04:08:46,483 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-10-27 04:08:46,483 INFO L200 CegarAbsIntRunner]: Running AI on error trace of length 18 with the following transitions: [2018-10-27 04:08:46,483 INFO L202 CegarAbsIntRunner]: [0], [4], [8], [12], [14], [17], [19], [26], [29], [31], [37], [38], [39], [41] [2018-10-27 04:08:46,485 INFO L148 AbstractInterpreter]: Using domain PoormanAbstractDomain with backing domain CompoundDomain [CongruenceDomain, OctagonDomain] [2018-10-27 04:08:46,485 INFO L101 FixpointEngine]: Starting fixpoint engine with domain PoormanAbstractDomain (maxUnwinding=3, maxParallelStates=2) [2018-10-27 04:08:46,489 WARN L79 EvaluatorLogger]: Possible loss of precision. Operator ARITHMOD has no precise implementation. [2018-10-27 04:08:46,700 INFO L263 AbstractInterpreter]: Some error location(s) were reachable [2018-10-27 04:08:46,700 INFO L272 AbstractInterpreter]: Visited 14 different actions 87 times. Merged at 5 different actions 34 times. Widened at 1 different actions 5 times. Found 11 fixpoints after 2 different actions. Largest state had 4 variables. [2018-10-27 04:08:46,738 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-27 04:08:46,738 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: Unknown [2018-10-27 04:08:46,738 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-27 04:08:46,739 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/z3 Starting monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-27 04:08:46,756 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-27 04:08:46,756 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-10-27 04:08:46,784 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-27 04:08:46,786 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-27 04:08:47,038 WARN L179 SmtUtils]: Spent 142.00 ms on a formula simplification. DAG size of input: 19 DAG size of output: 5 [2018-10-27 04:08:47,052 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 7 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:08:47,053 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-10-27 04:08:47,179 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 7 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:08:47,205 INFO L312 seRefinementStrategy]: Constructing automaton from 2 perfect and 1 imperfect interpolant sequences. [2018-10-27 04:08:47,206 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [3, 3] imperfect sequences [5] total 6 [2018-10-27 04:08:47,206 INFO L258 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-10-27 04:08:47,206 INFO L460 AbstractCegarLoop]: Interpolant automaton has 3 states [2018-10-27 04:08:47,206 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2018-10-27 04:08:47,207 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2018-10-27 04:08:47,207 INFO L87 Difference]: Start difference. First operand 21 states and 24 transitions. Second operand 3 states. [2018-10-27 04:08:47,223 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-27 04:08:47,223 INFO L93 Difference]: Finished difference Result 35 states and 41 transitions. [2018-10-27 04:08:47,224 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-10-27 04:08:47,224 INFO L78 Accepts]: Start accepts. Automaton has 3 states. Word has length 17 [2018-10-27 04:08:47,224 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-27 04:08:47,226 INFO L225 Difference]: With dead ends: 35 [2018-10-27 04:08:47,226 INFO L226 Difference]: Without dead ends: 27 [2018-10-27 04:08:47,226 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 39 GetRequests, 33 SyntacticMatches, 2 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2018-10-27 04:08:47,227 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 27 states. [2018-10-27 04:08:47,232 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 27 to 26. [2018-10-27 04:08:47,232 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 26 states. [2018-10-27 04:08:47,233 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 29 transitions. [2018-10-27 04:08:47,233 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 29 transitions. Word has length 17 [2018-10-27 04:08:47,233 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-27 04:08:47,233 INFO L481 AbstractCegarLoop]: Abstraction has 26 states and 29 transitions. [2018-10-27 04:08:47,233 INFO L482 AbstractCegarLoop]: Interpolant automaton has 3 states. [2018-10-27 04:08:47,234 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 29 transitions. [2018-10-27 04:08:47,234 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2018-10-27 04:08:47,234 INFO L367 BasicCegarLoop]: Found error trace [2018-10-27 04:08:47,235 INFO L375 BasicCegarLoop]: trace histogram [3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-27 04:08:47,235 INFO L424 AbstractCegarLoop]: === Iteration 7 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-27 04:08:47,235 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-27 04:08:47,235 INFO L82 PathProgramCache]: Analyzing trace with hash 1277798652, now seen corresponding path program 2 times [2018-10-27 04:08:47,235 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-27 04:08:47,236 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 04:08:47,236 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-27 04:08:47,237 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 04:08:47,237 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-27 04:08:47,246 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-27 04:08:47,484 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:08:47,485 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-27 04:08:47,485 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-10-27 04:08:47,485 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-10-27 04:08:47,485 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-10-27 04:08:47,485 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-27 04:08:47,485 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/z3 Starting monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-27 04:08:47,493 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-10-27 04:08:47,493 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST2 (IT: FPandBP) [2018-10-27 04:08:47,518 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2018-10-27 04:08:47,518 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-27 04:08:47,520 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-27 04:08:47,784 WARN L179 SmtUtils]: Spent 161.00 ms on a formula simplification. DAG size of input: 19 DAG size of output: 6 [2018-10-27 04:08:47,802 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 7 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:08:47,802 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-10-27 04:08:47,892 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 7 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:08:47,916 INFO L312 seRefinementStrategy]: Constructing automaton from 2 perfect and 1 imperfect interpolant sequences. [2018-10-27 04:08:47,916 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [3, 3] imperfect sequences [5] total 6 [2018-10-27 04:08:47,916 INFO L258 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-10-27 04:08:47,916 INFO L460 AbstractCegarLoop]: Interpolant automaton has 3 states [2018-10-27 04:08:47,917 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2018-10-27 04:08:47,917 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2018-10-27 04:08:47,917 INFO L87 Difference]: Start difference. First operand 26 states and 29 transitions. Second operand 3 states. [2018-10-27 04:08:47,937 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-27 04:08:47,937 INFO L93 Difference]: Finished difference Result 35 states and 38 transitions. [2018-10-27 04:08:47,938 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-10-27 04:08:47,938 INFO L78 Accepts]: Start accepts. Automaton has 3 states. Word has length 17 [2018-10-27 04:08:47,938 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-27 04:08:47,938 INFO L225 Difference]: With dead ends: 35 [2018-10-27 04:08:47,939 INFO L226 Difference]: Without dead ends: 27 [2018-10-27 04:08:47,939 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 39 GetRequests, 33 SyntacticMatches, 2 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2018-10-27 04:08:47,939 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 27 states. [2018-10-27 04:08:47,943 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 27 to 26. [2018-10-27 04:08:47,944 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 26 states. [2018-10-27 04:08:47,944 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 28 transitions. [2018-10-27 04:08:47,945 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 28 transitions. Word has length 17 [2018-10-27 04:08:47,945 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-27 04:08:47,945 INFO L481 AbstractCegarLoop]: Abstraction has 26 states and 28 transitions. [2018-10-27 04:08:47,945 INFO L482 AbstractCegarLoop]: Interpolant automaton has 3 states. [2018-10-27 04:08:47,945 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 28 transitions. [2018-10-27 04:08:47,946 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2018-10-27 04:08:47,946 INFO L367 BasicCegarLoop]: Found error trace [2018-10-27 04:08:47,946 INFO L375 BasicCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-27 04:08:47,946 INFO L424 AbstractCegarLoop]: === Iteration 8 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-27 04:08:47,947 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-27 04:08:47,947 INFO L82 PathProgramCache]: Analyzing trace with hash -1242161282, now seen corresponding path program 2 times [2018-10-27 04:08:47,947 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-27 04:08:47,948 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 04:08:47,948 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-27 04:08:47,948 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 04:08:47,948 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-27 04:08:47,957 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-27 04:08:48,021 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:08:48,022 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-27 04:08:48,022 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-10-27 04:08:48,022 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-10-27 04:08:48,022 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-10-27 04:08:48,022 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-27 04:08:48,022 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/z3 Starting monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-27 04:08:48,039 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-10-27 04:08:48,039 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST2 (IT: FPandBP) [2018-10-27 04:09:00,084 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2018-10-27 04:09:00,084 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-27 04:09:00,087 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-27 04:09:00,134 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:09:00,134 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-10-27 04:09:00,220 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:09:00,241 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-10-27 04:09:00,242 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5, 5] total 8 [2018-10-27 04:09:00,242 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-10-27 04:09:00,242 INFO L460 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-10-27 04:09:00,242 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-10-27 04:09:00,243 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=22, Invalid=34, Unknown=0, NotChecked=0, Total=56 [2018-10-27 04:09:00,243 INFO L87 Difference]: Start difference. First operand 26 states and 28 transitions. Second operand 5 states. [2018-10-27 04:09:00,299 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-27 04:09:00,300 INFO L93 Difference]: Finished difference Result 35 states and 37 transitions. [2018-10-27 04:09:00,300 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-10-27 04:09:00,301 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 17 [2018-10-27 04:09:00,301 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-27 04:09:00,301 INFO L225 Difference]: With dead ends: 35 [2018-10-27 04:09:00,301 INFO L226 Difference]: Without dead ends: 30 [2018-10-27 04:09:00,302 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 39 GetRequests, 31 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=22, Invalid=34, Unknown=0, NotChecked=0, Total=56 [2018-10-27 04:09:00,302 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 30 states. [2018-10-27 04:09:00,306 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 30 to 29. [2018-10-27 04:09:00,306 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 29 states. [2018-10-27 04:09:00,307 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 29 states to 29 states and 31 transitions. [2018-10-27 04:09:00,307 INFO L78 Accepts]: Start accepts. Automaton has 29 states and 31 transitions. Word has length 17 [2018-10-27 04:09:00,307 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-27 04:09:00,307 INFO L481 AbstractCegarLoop]: Abstraction has 29 states and 31 transitions. [2018-10-27 04:09:00,307 INFO L482 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-10-27 04:09:00,308 INFO L276 IsEmpty]: Start isEmpty. Operand 29 states and 31 transitions. [2018-10-27 04:09:00,308 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2018-10-27 04:09:00,308 INFO L367 BasicCegarLoop]: Found error trace [2018-10-27 04:09:00,309 INFO L375 BasicCegarLoop]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-27 04:09:00,309 INFO L424 AbstractCegarLoop]: === Iteration 9 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-27 04:09:00,309 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-27 04:09:00,309 INFO L82 PathProgramCache]: Analyzing trace with hash 26004059, now seen corresponding path program 3 times [2018-10-27 04:09:00,309 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-27 04:09:00,310 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 04:09:00,310 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-27 04:09:00,310 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 04:09:00,311 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-27 04:09:00,319 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-27 04:09:00,504 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:09:00,504 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-27 04:09:00,504 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-10-27 04:09:00,504 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-10-27 04:09:00,505 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-10-27 04:09:00,505 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-27 04:09:00,505 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/z3 Starting monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-27 04:09:00,515 INFO L103 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-10-27 04:09:00,515 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder TERMS_WITH_SMALL_CONSTANTS_FIRST (IT: FPandBP) [2018-10-27 04:09:00,553 INFO L249 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-10-27 04:09:00,553 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-27 04:09:00,555 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-27 04:09:00,570 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:09:00,570 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-10-27 04:09:00,694 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:09:00,724 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-10-27 04:09:00,724 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6, 6] total 10 [2018-10-27 04:09:00,724 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-10-27 04:09:00,725 INFO L460 AbstractCegarLoop]: Interpolant automaton has 6 states [2018-10-27 04:09:00,725 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2018-10-27 04:09:00,725 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=57, Unknown=0, NotChecked=0, Total=90 [2018-10-27 04:09:00,725 INFO L87 Difference]: Start difference. First operand 29 states and 31 transitions. Second operand 6 states. [2018-10-27 04:09:00,835 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-27 04:09:00,836 INFO L93 Difference]: Finished difference Result 38 states and 40 transitions. [2018-10-27 04:09:00,837 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-10-27 04:09:00,837 INFO L78 Accepts]: Start accepts. Automaton has 6 states. Word has length 20 [2018-10-27 04:09:00,837 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-27 04:09:00,838 INFO L225 Difference]: With dead ends: 38 [2018-10-27 04:09:00,838 INFO L226 Difference]: Without dead ends: 33 [2018-10-27 04:09:00,839 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 46 GetRequests, 36 SyntacticMatches, 2 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=33, Invalid=57, Unknown=0, NotChecked=0, Total=90 [2018-10-27 04:09:00,839 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 33 states. [2018-10-27 04:09:00,843 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 33 to 32. [2018-10-27 04:09:00,843 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 32 states. [2018-10-27 04:09:00,844 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 34 transitions. [2018-10-27 04:09:00,844 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 34 transitions. Word has length 20 [2018-10-27 04:09:00,845 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-27 04:09:00,845 INFO L481 AbstractCegarLoop]: Abstraction has 32 states and 34 transitions. [2018-10-27 04:09:00,845 INFO L482 AbstractCegarLoop]: Interpolant automaton has 6 states. [2018-10-27 04:09:00,845 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 34 transitions. [2018-10-27 04:09:00,846 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2018-10-27 04:09:00,846 INFO L367 BasicCegarLoop]: Found error trace [2018-10-27 04:09:00,846 INFO L375 BasicCegarLoop]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-27 04:09:00,846 INFO L424 AbstractCegarLoop]: === Iteration 10 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-27 04:09:00,846 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-27 04:09:00,846 INFO L82 PathProgramCache]: Analyzing trace with hash 821178397, now seen corresponding path program 3 times [2018-10-27 04:09:00,847 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-27 04:09:00,847 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 04:09:00,847 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-27 04:09:00,848 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 04:09:00,848 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-27 04:09:00,856 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-27 04:09:01,280 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:09:01,281 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-27 04:09:01,281 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-10-27 04:09:01,281 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-10-27 04:09:01,281 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-10-27 04:09:01,281 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-27 04:09:01,282 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/z3 Starting monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-27 04:09:01,293 INFO L103 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-10-27 04:09:01,294 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder TERMS_WITH_SMALL_CONSTANTS_FIRST (IT: FPandBP) [2018-10-27 04:09:01,317 INFO L249 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-10-27 04:09:01,318 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-27 04:09:01,320 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-27 04:09:01,332 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:09:01,332 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-10-27 04:09:01,751 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:09:01,771 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-10-27 04:09:01,771 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6, 6] total 10 [2018-10-27 04:09:01,772 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-10-27 04:09:01,772 INFO L460 AbstractCegarLoop]: Interpolant automaton has 6 states [2018-10-27 04:09:01,772 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2018-10-27 04:09:01,772 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=57, Unknown=0, NotChecked=0, Total=90 [2018-10-27 04:09:01,773 INFO L87 Difference]: Start difference. First operand 32 states and 34 transitions. Second operand 6 states. [2018-10-27 04:09:01,842 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-27 04:09:01,843 INFO L93 Difference]: Finished difference Result 41 states and 43 transitions. [2018-10-27 04:09:01,843 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-10-27 04:09:01,844 INFO L78 Accepts]: Start accepts. Automaton has 6 states. Word has length 20 [2018-10-27 04:09:01,844 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-27 04:09:01,845 INFO L225 Difference]: With dead ends: 41 [2018-10-27 04:09:01,845 INFO L226 Difference]: Without dead ends: 36 [2018-10-27 04:09:01,846 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 46 GetRequests, 36 SyntacticMatches, 2 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=33, Invalid=57, Unknown=0, NotChecked=0, Total=90 [2018-10-27 04:09:01,846 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 36 states. [2018-10-27 04:09:01,850 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 36 to 35. [2018-10-27 04:09:01,851 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 35 states. [2018-10-27 04:09:01,851 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 35 states to 35 states and 37 transitions. [2018-10-27 04:09:01,851 INFO L78 Accepts]: Start accepts. Automaton has 35 states and 37 transitions. Word has length 20 [2018-10-27 04:09:01,852 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-27 04:09:01,852 INFO L481 AbstractCegarLoop]: Abstraction has 35 states and 37 transitions. [2018-10-27 04:09:01,852 INFO L482 AbstractCegarLoop]: Interpolant automaton has 6 states. [2018-10-27 04:09:01,852 INFO L276 IsEmpty]: Start isEmpty. Operand 35 states and 37 transitions. [2018-10-27 04:09:01,853 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2018-10-27 04:09:01,853 INFO L367 BasicCegarLoop]: Found error trace [2018-10-27 04:09:01,853 INFO L375 BasicCegarLoop]: trace histogram [5, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-27 04:09:01,853 INFO L424 AbstractCegarLoop]: === Iteration 11 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-27 04:09:01,853 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-27 04:09:01,854 INFO L82 PathProgramCache]: Analyzing trace with hash 427509150, now seen corresponding path program 4 times [2018-10-27 04:09:01,854 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-27 04:09:01,854 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 04:09:01,855 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-27 04:09:01,855 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 04:09:01,855 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-27 04:09:01,862 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-27 04:09:02,183 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:09:02,183 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-27 04:09:02,184 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-10-27 04:09:02,184 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-10-27 04:09:02,184 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-10-27 04:09:02,184 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-27 04:09:02,184 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/z3 Starting monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-27 04:09:02,201 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-27 04:09:02,201 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-10-27 04:09:02,209 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-27 04:09:02,211 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-27 04:09:02,219 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:09:02,219 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-10-27 04:09:03,010 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:09:03,030 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-10-27 04:09:03,030 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 12 [2018-10-27 04:09:03,030 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-10-27 04:09:03,031 INFO L460 AbstractCegarLoop]: Interpolant automaton has 7 states [2018-10-27 04:09:03,031 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2018-10-27 04:09:03,031 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=46, Invalid=86, Unknown=0, NotChecked=0, Total=132 [2018-10-27 04:09:03,032 INFO L87 Difference]: Start difference. First operand 35 states and 37 transitions. Second operand 7 states. [2018-10-27 04:09:03,133 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-27 04:09:03,133 INFO L93 Difference]: Finished difference Result 44 states and 46 transitions. [2018-10-27 04:09:03,135 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-10-27 04:09:03,136 INFO L78 Accepts]: Start accepts. Automaton has 7 states. Word has length 23 [2018-10-27 04:09:03,136 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-27 04:09:03,137 INFO L225 Difference]: With dead ends: 44 [2018-10-27 04:09:03,137 INFO L226 Difference]: Without dead ends: 39 [2018-10-27 04:09:03,137 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 53 GetRequests, 41 SyntacticMatches, 2 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=46, Invalid=86, Unknown=0, NotChecked=0, Total=132 [2018-10-27 04:09:03,138 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 39 states. [2018-10-27 04:09:03,146 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 39 to 38. [2018-10-27 04:09:03,146 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 38 states. [2018-10-27 04:09:03,147 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 38 states to 38 states and 40 transitions. [2018-10-27 04:09:03,147 INFO L78 Accepts]: Start accepts. Automaton has 38 states and 40 transitions. Word has length 23 [2018-10-27 04:09:03,147 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-27 04:09:03,147 INFO L481 AbstractCegarLoop]: Abstraction has 38 states and 40 transitions. [2018-10-27 04:09:03,147 INFO L482 AbstractCegarLoop]: Interpolant automaton has 7 states. [2018-10-27 04:09:03,148 INFO L276 IsEmpty]: Start isEmpty. Operand 38 states and 40 transitions. [2018-10-27 04:09:03,148 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2018-10-27 04:09:03,148 INFO L367 BasicCegarLoop]: Found error trace [2018-10-27 04:09:03,149 INFO L375 BasicCegarLoop]: trace histogram [5, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-27 04:09:03,149 INFO L424 AbstractCegarLoop]: === Iteration 12 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-27 04:09:03,149 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-27 04:09:03,149 INFO L82 PathProgramCache]: Analyzing trace with hash 201615134, now seen corresponding path program 4 times [2018-10-27 04:09:03,149 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-27 04:09:03,150 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 04:09:03,150 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-27 04:09:03,150 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 04:09:03,150 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-27 04:09:03,158 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-27 04:09:03,312 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:09:03,313 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-27 04:09:03,313 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-10-27 04:09:03,313 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-10-27 04:09:03,313 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-10-27 04:09:03,313 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-27 04:09:03,314 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/z3 Starting monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-27 04:09:03,323 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-27 04:09:03,324 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-10-27 04:09:03,333 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-27 04:09:03,335 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-27 04:09:03,370 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:09:03,370 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-10-27 04:09:03,801 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:09:03,821 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-10-27 04:09:03,821 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 12 [2018-10-27 04:09:03,822 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-10-27 04:09:03,822 INFO L460 AbstractCegarLoop]: Interpolant automaton has 7 states [2018-10-27 04:09:03,822 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2018-10-27 04:09:03,822 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=46, Invalid=86, Unknown=0, NotChecked=0, Total=132 [2018-10-27 04:09:03,823 INFO L87 Difference]: Start difference. First operand 38 states and 40 transitions. Second operand 7 states. [2018-10-27 04:09:03,966 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-27 04:09:03,967 INFO L93 Difference]: Finished difference Result 47 states and 49 transitions. [2018-10-27 04:09:03,967 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-10-27 04:09:03,967 INFO L78 Accepts]: Start accepts. Automaton has 7 states. Word has length 23 [2018-10-27 04:09:03,968 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-27 04:09:03,968 INFO L225 Difference]: With dead ends: 47 [2018-10-27 04:09:03,969 INFO L226 Difference]: Without dead ends: 42 [2018-10-27 04:09:03,969 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 53 GetRequests, 41 SyntacticMatches, 2 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=46, Invalid=86, Unknown=0, NotChecked=0, Total=132 [2018-10-27 04:09:03,970 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 42 states. [2018-10-27 04:09:03,974 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 42 to 41. [2018-10-27 04:09:03,974 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 41 states. [2018-10-27 04:09:03,975 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 41 states to 41 states and 43 transitions. [2018-10-27 04:09:03,975 INFO L78 Accepts]: Start accepts. Automaton has 41 states and 43 transitions. Word has length 23 [2018-10-27 04:09:03,975 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-27 04:09:03,975 INFO L481 AbstractCegarLoop]: Abstraction has 41 states and 43 transitions. [2018-10-27 04:09:03,975 INFO L482 AbstractCegarLoop]: Interpolant automaton has 7 states. [2018-10-27 04:09:03,975 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 43 transitions. [2018-10-27 04:09:03,976 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2018-10-27 04:09:03,976 INFO L367 BasicCegarLoop]: Found error trace [2018-10-27 04:09:03,976 INFO L375 BasicCegarLoop]: trace histogram [6, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-27 04:09:03,977 INFO L424 AbstractCegarLoop]: === Iteration 13 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-27 04:09:03,977 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-27 04:09:03,977 INFO L82 PathProgramCache]: Analyzing trace with hash 181755771, now seen corresponding path program 5 times [2018-10-27 04:09:03,977 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-27 04:09:03,978 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 04:09:03,978 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-27 04:09:03,978 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 04:09:03,978 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-27 04:09:03,985 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-27 04:09:04,253 INFO L134 CoverageAnalysis]: Checked inductivity of 40 backedges. 0 proven. 40 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:09:04,254 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-27 04:09:04,254 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-10-27 04:09:04,254 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-10-27 04:09:04,254 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-10-27 04:09:04,254 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-27 04:09:04,254 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/z3 Starting monitored process 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-27 04:09:04,261 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-10-27 04:09:04,261 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST2 (IT: FPandBP) [2018-10-27 04:09:04,281 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2018-10-27 04:09:04,281 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-27 04:09:04,283 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-27 04:09:04,344 INFO L134 CoverageAnalysis]: Checked inductivity of 40 backedges. 0 proven. 40 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:09:04,344 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-10-27 04:09:04,659 INFO L134 CoverageAnalysis]: Checked inductivity of 40 backedges. 0 proven. 40 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:09:04,679 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-10-27 04:09:04,679 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 8] total 14 [2018-10-27 04:09:04,679 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-10-27 04:09:04,680 INFO L460 AbstractCegarLoop]: Interpolant automaton has 8 states [2018-10-27 04:09:04,680 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2018-10-27 04:09:04,680 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=61, Invalid=121, Unknown=0, NotChecked=0, Total=182 [2018-10-27 04:09:04,681 INFO L87 Difference]: Start difference. First operand 41 states and 43 transitions. Second operand 8 states. [2018-10-27 04:09:04,782 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-27 04:09:04,783 INFO L93 Difference]: Finished difference Result 50 states and 52 transitions. [2018-10-27 04:09:04,783 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-10-27 04:09:04,783 INFO L78 Accepts]: Start accepts. Automaton has 8 states. Word has length 26 [2018-10-27 04:09:04,784 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-27 04:09:04,784 INFO L225 Difference]: With dead ends: 50 [2018-10-27 04:09:04,785 INFO L226 Difference]: Without dead ends: 45 [2018-10-27 04:09:04,786 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 60 GetRequests, 46 SyntacticMatches, 2 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=61, Invalid=121, Unknown=0, NotChecked=0, Total=182 [2018-10-27 04:09:04,786 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 45 states. [2018-10-27 04:09:04,791 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 45 to 44. [2018-10-27 04:09:04,791 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 44 states. [2018-10-27 04:09:04,792 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 44 states to 44 states and 46 transitions. [2018-10-27 04:09:04,792 INFO L78 Accepts]: Start accepts. Automaton has 44 states and 46 transitions. Word has length 26 [2018-10-27 04:09:04,793 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-27 04:09:04,793 INFO L481 AbstractCegarLoop]: Abstraction has 44 states and 46 transitions. [2018-10-27 04:09:04,793 INFO L482 AbstractCegarLoop]: Interpolant automaton has 8 states. [2018-10-27 04:09:04,793 INFO L276 IsEmpty]: Start isEmpty. Operand 44 states and 46 transitions. [2018-10-27 04:09:04,794 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2018-10-27 04:09:04,794 INFO L367 BasicCegarLoop]: Found error trace [2018-10-27 04:09:04,794 INFO L375 BasicCegarLoop]: trace histogram [6, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-27 04:09:04,794 INFO L424 AbstractCegarLoop]: === Iteration 14 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-27 04:09:04,795 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-27 04:09:04,795 INFO L82 PathProgramCache]: Analyzing trace with hash -1733081987, now seen corresponding path program 5 times [2018-10-27 04:09:04,795 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-27 04:09:04,796 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 04:09:04,796 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-27 04:09:04,796 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 04:09:04,796 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-27 04:09:04,803 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-27 04:09:04,957 INFO L134 CoverageAnalysis]: Checked inductivity of 40 backedges. 0 proven. 40 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:09:04,957 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-27 04:09:04,957 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-10-27 04:09:04,957 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-10-27 04:09:04,958 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-10-27 04:09:04,958 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-27 04:09:04,958 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/z3 Starting monitored process 13 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 13 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-27 04:09:04,966 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-10-27 04:09:04,966 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST2 (IT: FPandBP) [2018-10-27 04:09:29,032 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2018-10-27 04:09:29,032 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-27 04:09:29,034 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-27 04:09:29,701 INFO L134 CoverageAnalysis]: Checked inductivity of 40 backedges. 14 proven. 0 refuted. 0 times theorem prover too weak. 26 trivial. 0 not checked. [2018-10-27 04:09:29,701 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-10-27 04:09:44,078 WARN L832 $PredicateComparison]: unable to prove that (forall ((main_~x~0 Int) (v_prenex_1 Int)) (let ((.cse1 (+ main_~x~0 1)) (.cse0 (mod v_prenex_1 2))) (or (= .cse0 (mod .cse1 2)) (= .cse0 0) (< (mod .cse1 4294967296) 99) (<= 99 (mod main_~x~0 4294967296)) (= 0 (mod (+ .cse0 4294967294) 4294967296))))) is different from false [2018-10-27 04:09:46,087 WARN L854 $PredicateComparison]: unable to prove that (forall ((main_~x~0 Int) (v_prenex_1 Int)) (let ((.cse1 (+ main_~x~0 1)) (.cse0 (mod v_prenex_1 2))) (or (= .cse0 (mod .cse1 2)) (= .cse0 0) (< (mod .cse1 4294967296) 99) (<= 99 (mod main_~x~0 4294967296)) (= 0 (mod (+ .cse0 4294967294) 4294967296))))) is different from true [2018-10-27 04:09:46,095 INFO L134 CoverageAnalysis]: Checked inductivity of 40 backedges. 17 proven. 0 refuted. 0 times theorem prover too weak. 22 trivial. 1 not checked. [2018-10-27 04:09:46,116 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 2 imperfect interpolant sequences. [2018-10-27 04:09:46,116 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [7] imperfect sequences [8, 8] total 19 [2018-10-27 04:09:46,116 INFO L258 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-10-27 04:09:46,117 INFO L460 AbstractCegarLoop]: Interpolant automaton has 7 states [2018-10-27 04:09:46,117 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2018-10-27 04:09:46,117 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=61, Invalid=244, Unknown=5, NotChecked=32, Total=342 [2018-10-27 04:09:46,118 INFO L87 Difference]: Start difference. First operand 44 states and 46 transitions. Second operand 7 states. [2018-10-27 04:09:48,261 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-27 04:09:48,261 INFO L93 Difference]: Finished difference Result 49 states and 50 transitions. [2018-10-27 04:09:48,261 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-10-27 04:09:48,262 INFO L78 Accepts]: Start accepts. Automaton has 7 states. Word has length 26 [2018-10-27 04:09:48,262 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-27 04:09:48,262 INFO L225 Difference]: With dead ends: 49 [2018-10-27 04:09:48,262 INFO L226 Difference]: Without dead ends: 30 [2018-10-27 04:09:48,263 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 62 GetRequests, 42 SyntacticMatches, 1 SemanticMatches, 19 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 26 ImplicationChecksByTransitivity, 14.9s TimeCoverageRelationStatistics Valid=72, Invalid=306, Unknown=6, NotChecked=36, Total=420 [2018-10-27 04:09:48,263 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 30 states. [2018-10-27 04:09:48,266 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 30 to 30. [2018-10-27 04:09:48,266 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 30 states. [2018-10-27 04:09:48,267 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 30 states to 30 states and 30 transitions. [2018-10-27 04:09:48,267 INFO L78 Accepts]: Start accepts. Automaton has 30 states and 30 transitions. Word has length 26 [2018-10-27 04:09:48,267 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-27 04:09:48,267 INFO L481 AbstractCegarLoop]: Abstraction has 30 states and 30 transitions. [2018-10-27 04:09:48,267 INFO L482 AbstractCegarLoop]: Interpolant automaton has 7 states. [2018-10-27 04:09:48,267 INFO L276 IsEmpty]: Start isEmpty. Operand 30 states and 30 transitions. [2018-10-27 04:09:48,268 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2018-10-27 04:09:48,268 INFO L367 BasicCegarLoop]: Found error trace [2018-10-27 04:09:48,268 INFO L375 BasicCegarLoop]: trace histogram [7, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-27 04:09:48,268 INFO L424 AbstractCegarLoop]: === Iteration 15 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-27 04:09:48,269 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-27 04:09:48,269 INFO L82 PathProgramCache]: Analyzing trace with hash 1862081662, now seen corresponding path program 6 times [2018-10-27 04:09:48,269 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-27 04:09:48,270 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 04:09:48,270 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-27 04:09:48,270 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 04:09:48,270 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-27 04:09:48,277 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-27 04:09:48,464 INFO L134 CoverageAnalysis]: Checked inductivity of 57 backedges. 0 proven. 57 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:09:48,464 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-27 04:09:48,464 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-10-27 04:09:48,464 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-10-27 04:09:48,465 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-10-27 04:09:48,465 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-27 04:09:48,465 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/z3 Starting monitored process 14 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 14 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-27 04:09:48,474 INFO L103 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-10-27 04:09:48,474 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder TERMS_WITH_SMALL_CONSTANTS_FIRST (IT: FPandBP) [2018-10-27 04:09:48,498 INFO L249 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-10-27 04:09:48,498 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-27 04:09:48,500 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-27 04:09:48,558 INFO L134 CoverageAnalysis]: Checked inductivity of 57 backedges. 0 proven. 57 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:09:48,559 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-10-27 04:09:51,141 INFO L134 CoverageAnalysis]: Checked inductivity of 57 backedges. 0 proven. 57 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:09:51,161 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-10-27 04:09:51,162 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9, 9] total 16 [2018-10-27 04:09:51,162 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-10-27 04:09:51,162 INFO L460 AbstractCegarLoop]: Interpolant automaton has 9 states [2018-10-27 04:09:51,162 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2018-10-27 04:09:51,162 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=78, Invalid=162, Unknown=0, NotChecked=0, Total=240 [2018-10-27 04:09:51,163 INFO L87 Difference]: Start difference. First operand 30 states and 30 transitions. Second operand 9 states. [2018-10-27 04:09:51,417 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-27 04:09:51,417 INFO L93 Difference]: Finished difference Result 39 states and 39 transitions. [2018-10-27 04:09:51,418 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-10-27 04:09:51,418 INFO L78 Accepts]: Start accepts. Automaton has 9 states. Word has length 29 [2018-10-27 04:09:51,418 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-27 04:09:51,419 INFO L225 Difference]: With dead ends: 39 [2018-10-27 04:09:51,419 INFO L226 Difference]: Without dead ends: 34 [2018-10-27 04:09:51,419 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 67 GetRequests, 51 SyntacticMatches, 2 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 2.7s TimeCoverageRelationStatistics Valid=78, Invalid=162, Unknown=0, NotChecked=0, Total=240 [2018-10-27 04:09:51,420 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 34 states. [2018-10-27 04:09:51,422 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 34 to 33. [2018-10-27 04:09:51,423 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 33 states. [2018-10-27 04:09:51,423 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 33 states to 33 states and 33 transitions. [2018-10-27 04:09:51,423 INFO L78 Accepts]: Start accepts. Automaton has 33 states and 33 transitions. Word has length 29 [2018-10-27 04:09:51,424 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-27 04:09:51,424 INFO L481 AbstractCegarLoop]: Abstraction has 33 states and 33 transitions. [2018-10-27 04:09:51,424 INFO L482 AbstractCegarLoop]: Interpolant automaton has 9 states. [2018-10-27 04:09:51,424 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 33 transitions. [2018-10-27 04:09:51,424 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2018-10-27 04:09:51,425 INFO L367 BasicCegarLoop]: Found error trace [2018-10-27 04:09:51,425 INFO L375 BasicCegarLoop]: trace histogram [8, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-27 04:09:51,425 INFO L424 AbstractCegarLoop]: === Iteration 16 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-27 04:09:51,425 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-27 04:09:51,425 INFO L82 PathProgramCache]: Analyzing trace with hash -1688101733, now seen corresponding path program 7 times [2018-10-27 04:09:51,425 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-27 04:09:51,426 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 04:09:51,426 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-27 04:09:51,426 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 04:09:51,427 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-27 04:09:51,434 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-27 04:09:51,725 INFO L134 CoverageAnalysis]: Checked inductivity of 77 backedges. 0 proven. 77 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:09:51,726 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-27 04:09:51,726 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-10-27 04:09:51,726 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-10-27 04:09:51,726 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-10-27 04:09:51,726 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-27 04:09:51,726 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/z3 Starting monitored process 15 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 15 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-27 04:09:51,734 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-27 04:09:51,734 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-10-27 04:09:51,745 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-27 04:09:51,746 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-27 04:09:51,760 INFO L134 CoverageAnalysis]: Checked inductivity of 77 backedges. 0 proven. 77 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:09:51,761 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-10-27 04:09:52,962 INFO L134 CoverageAnalysis]: Checked inductivity of 77 backedges. 0 proven. 77 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:09:52,985 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-10-27 04:09:52,985 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10, 10] total 18 [2018-10-27 04:09:52,985 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-10-27 04:09:52,986 INFO L460 AbstractCegarLoop]: Interpolant automaton has 10 states [2018-10-27 04:09:52,986 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2018-10-27 04:09:52,986 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=97, Invalid=209, Unknown=0, NotChecked=0, Total=306 [2018-10-27 04:09:52,986 INFO L87 Difference]: Start difference. First operand 33 states and 33 transitions. Second operand 10 states. [2018-10-27 04:09:53,122 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-27 04:09:53,122 INFO L93 Difference]: Finished difference Result 42 states and 42 transitions. [2018-10-27 04:09:53,123 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-10-27 04:09:53,123 INFO L78 Accepts]: Start accepts. Automaton has 10 states. Word has length 32 [2018-10-27 04:09:53,124 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-27 04:09:53,124 INFO L225 Difference]: With dead ends: 42 [2018-10-27 04:09:53,124 INFO L226 Difference]: Without dead ends: 37 [2018-10-27 04:09:53,125 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 74 GetRequests, 56 SyntacticMatches, 2 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 1.4s TimeCoverageRelationStatistics Valid=97, Invalid=209, Unknown=0, NotChecked=0, Total=306 [2018-10-27 04:09:53,125 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 37 states. [2018-10-27 04:09:53,128 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 37 to 36. [2018-10-27 04:09:53,128 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 36 states. [2018-10-27 04:09:53,129 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 36 states to 36 states and 36 transitions. [2018-10-27 04:09:53,129 INFO L78 Accepts]: Start accepts. Automaton has 36 states and 36 transitions. Word has length 32 [2018-10-27 04:09:53,130 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-27 04:09:53,130 INFO L481 AbstractCegarLoop]: Abstraction has 36 states and 36 transitions. [2018-10-27 04:09:53,130 INFO L482 AbstractCegarLoop]: Interpolant automaton has 10 states. [2018-10-27 04:09:53,130 INFO L276 IsEmpty]: Start isEmpty. Operand 36 states and 36 transitions. [2018-10-27 04:09:53,130 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2018-10-27 04:09:53,131 INFO L367 BasicCegarLoop]: Found error trace [2018-10-27 04:09:53,131 INFO L375 BasicCegarLoop]: trace histogram [9, 8, 8, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-27 04:09:53,131 INFO L424 AbstractCegarLoop]: === Iteration 17 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-27 04:09:53,131 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-27 04:09:53,131 INFO L82 PathProgramCache]: Analyzing trace with hash -1631958178, now seen corresponding path program 8 times [2018-10-27 04:09:53,131 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-27 04:09:53,132 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 04:09:53,132 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-27 04:09:53,132 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 04:09:53,133 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-27 04:09:53,139 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-27 04:09:53,316 INFO L134 CoverageAnalysis]: Checked inductivity of 100 backedges. 0 proven. 100 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:09:53,317 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-27 04:09:53,317 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-10-27 04:09:53,317 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-10-27 04:09:53,317 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-10-27 04:09:53,317 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-27 04:09:53,318 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/z3 Starting monitored process 16 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 16 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-27 04:09:53,330 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-10-27 04:09:53,330 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST2 (IT: FPandBP) [2018-10-27 04:09:56,515 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 9 check-sat command(s) [2018-10-27 04:09:56,515 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-27 04:09:56,519 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-27 04:09:56,548 INFO L134 CoverageAnalysis]: Checked inductivity of 100 backedges. 0 proven. 100 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:09:56,548 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-10-27 04:09:58,979 INFO L134 CoverageAnalysis]: Checked inductivity of 100 backedges. 0 proven. 100 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:09:59,000 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-10-27 04:09:59,000 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11, 11] total 20 [2018-10-27 04:09:59,000 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-10-27 04:09:59,000 INFO L460 AbstractCegarLoop]: Interpolant automaton has 11 states [2018-10-27 04:09:59,001 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2018-10-27 04:09:59,001 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=118, Invalid=262, Unknown=0, NotChecked=0, Total=380 [2018-10-27 04:09:59,001 INFO L87 Difference]: Start difference. First operand 36 states and 36 transitions. Second operand 11 states. [2018-10-27 04:09:59,173 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-27 04:09:59,174 INFO L93 Difference]: Finished difference Result 45 states and 45 transitions. [2018-10-27 04:09:59,175 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-10-27 04:09:59,175 INFO L78 Accepts]: Start accepts. Automaton has 11 states. Word has length 35 [2018-10-27 04:09:59,175 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-27 04:09:59,176 INFO L225 Difference]: With dead ends: 45 [2018-10-27 04:09:59,176 INFO L226 Difference]: Without dead ends: 40 [2018-10-27 04:09:59,176 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 81 GetRequests, 61 SyntacticMatches, 2 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 2.5s TimeCoverageRelationStatistics Valid=118, Invalid=262, Unknown=0, NotChecked=0, Total=380 [2018-10-27 04:09:59,176 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 40 states. [2018-10-27 04:09:59,181 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 40 to 39. [2018-10-27 04:09:59,181 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 39 states. [2018-10-27 04:09:59,181 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 39 states to 39 states and 39 transitions. [2018-10-27 04:09:59,182 INFO L78 Accepts]: Start accepts. Automaton has 39 states and 39 transitions. Word has length 35 [2018-10-27 04:09:59,182 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-27 04:09:59,182 INFO L481 AbstractCegarLoop]: Abstraction has 39 states and 39 transitions. [2018-10-27 04:09:59,182 INFO L482 AbstractCegarLoop]: Interpolant automaton has 11 states. [2018-10-27 04:09:59,182 INFO L276 IsEmpty]: Start isEmpty. Operand 39 states and 39 transitions. [2018-10-27 04:09:59,183 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2018-10-27 04:09:59,183 INFO L367 BasicCegarLoop]: Found error trace [2018-10-27 04:09:59,183 INFO L375 BasicCegarLoop]: trace histogram [10, 9, 9, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-27 04:09:59,183 INFO L424 AbstractCegarLoop]: === Iteration 18 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-27 04:09:59,184 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-27 04:09:59,184 INFO L82 PathProgramCache]: Analyzing trace with hash 198410683, now seen corresponding path program 9 times [2018-10-27 04:09:59,184 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-27 04:09:59,184 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 04:09:59,185 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-27 04:09:59,185 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 04:09:59,185 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-27 04:09:59,192 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-27 04:09:59,440 INFO L134 CoverageAnalysis]: Checked inductivity of 126 backedges. 0 proven. 126 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:09:59,440 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-27 04:09:59,440 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-10-27 04:09:59,440 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-10-27 04:09:59,440 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-10-27 04:09:59,440 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-27 04:09:59,440 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/z3 Starting monitored process 17 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 17 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-27 04:09:59,448 INFO L103 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-10-27 04:09:59,448 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder TERMS_WITH_SMALL_CONSTANTS_FIRST (IT: FPandBP) [2018-10-27 04:09:59,461 INFO L249 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-10-27 04:09:59,461 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-27 04:09:59,463 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-27 04:09:59,480 INFO L134 CoverageAnalysis]: Checked inductivity of 126 backedges. 0 proven. 126 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:09:59,480 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-10-27 04:10:04,876 INFO L134 CoverageAnalysis]: Checked inductivity of 126 backedges. 0 proven. 126 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:10:04,897 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-10-27 04:10:04,897 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12, 12] total 22 [2018-10-27 04:10:04,897 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-10-27 04:10:04,897 INFO L460 AbstractCegarLoop]: Interpolant automaton has 12 states [2018-10-27 04:10:04,898 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2018-10-27 04:10:04,898 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=141, Invalid=321, Unknown=0, NotChecked=0, Total=462 [2018-10-27 04:10:04,898 INFO L87 Difference]: Start difference. First operand 39 states and 39 transitions. Second operand 12 states. [2018-10-27 04:10:05,277 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-27 04:10:05,277 INFO L93 Difference]: Finished difference Result 48 states and 48 transitions. [2018-10-27 04:10:05,278 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2018-10-27 04:10:05,278 INFO L78 Accepts]: Start accepts. Automaton has 12 states. Word has length 38 [2018-10-27 04:10:05,278 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-27 04:10:05,279 INFO L225 Difference]: With dead ends: 48 [2018-10-27 04:10:05,279 INFO L226 Difference]: Without dead ends: 43 [2018-10-27 04:10:05,280 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 88 GetRequests, 66 SyntacticMatches, 2 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 5.6s TimeCoverageRelationStatistics Valid=141, Invalid=321, Unknown=0, NotChecked=0, Total=462 [2018-10-27 04:10:05,280 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 43 states. [2018-10-27 04:10:05,284 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 43 to 42. [2018-10-27 04:10:05,284 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 42 states. [2018-10-27 04:10:05,285 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 42 states to 42 states and 42 transitions. [2018-10-27 04:10:05,285 INFO L78 Accepts]: Start accepts. Automaton has 42 states and 42 transitions. Word has length 38 [2018-10-27 04:10:05,286 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-27 04:10:05,286 INFO L481 AbstractCegarLoop]: Abstraction has 42 states and 42 transitions. [2018-10-27 04:10:05,286 INFO L482 AbstractCegarLoop]: Interpolant automaton has 12 states. [2018-10-27 04:10:05,286 INFO L276 IsEmpty]: Start isEmpty. Operand 42 states and 42 transitions. [2018-10-27 04:10:05,287 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 42 [2018-10-27 04:10:05,287 INFO L367 BasicCegarLoop]: Found error trace [2018-10-27 04:10:05,287 INFO L375 BasicCegarLoop]: trace histogram [11, 10, 10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-27 04:10:05,287 INFO L424 AbstractCegarLoop]: === Iteration 19 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-27 04:10:05,288 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-27 04:10:05,288 INFO L82 PathProgramCache]: Analyzing trace with hash -187641282, now seen corresponding path program 10 times [2018-10-27 04:10:05,288 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-27 04:10:05,289 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 04:10:05,289 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-27 04:10:05,289 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 04:10:05,289 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-27 04:10:05,297 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-27 04:10:05,498 INFO L134 CoverageAnalysis]: Checked inductivity of 155 backedges. 0 proven. 155 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:10:05,499 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-27 04:10:05,499 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-10-27 04:10:05,499 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-10-27 04:10:05,499 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-10-27 04:10:05,499 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-27 04:10:05,499 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/z3 Starting monitored process 18 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 18 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-27 04:10:05,506 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-27 04:10:05,506 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-10-27 04:10:05,521 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-27 04:10:05,523 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-27 04:10:05,556 INFO L134 CoverageAnalysis]: Checked inductivity of 155 backedges. 0 proven. 155 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:10:05,556 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-10-27 04:10:07,417 INFO L134 CoverageAnalysis]: Checked inductivity of 155 backedges. 0 proven. 155 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:10:07,438 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-10-27 04:10:07,438 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13, 13] total 24 [2018-10-27 04:10:07,438 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-10-27 04:10:07,438 INFO L460 AbstractCegarLoop]: Interpolant automaton has 13 states [2018-10-27 04:10:07,439 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2018-10-27 04:10:07,439 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=166, Invalid=386, Unknown=0, NotChecked=0, Total=552 [2018-10-27 04:10:07,439 INFO L87 Difference]: Start difference. First operand 42 states and 42 transitions. Second operand 13 states. [2018-10-27 04:10:07,638 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-27 04:10:07,638 INFO L93 Difference]: Finished difference Result 51 states and 51 transitions. [2018-10-27 04:10:07,640 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2018-10-27 04:10:07,640 INFO L78 Accepts]: Start accepts. Automaton has 13 states. Word has length 41 [2018-10-27 04:10:07,640 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-27 04:10:07,641 INFO L225 Difference]: With dead ends: 51 [2018-10-27 04:10:07,641 INFO L226 Difference]: Without dead ends: 46 [2018-10-27 04:10:07,641 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 95 GetRequests, 71 SyntacticMatches, 2 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 2.0s TimeCoverageRelationStatistics Valid=166, Invalid=386, Unknown=0, NotChecked=0, Total=552 [2018-10-27 04:10:07,642 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 46 states. [2018-10-27 04:10:07,645 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 46 to 45. [2018-10-27 04:10:07,645 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 45 states. [2018-10-27 04:10:07,646 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 45 states to 45 states and 45 transitions. [2018-10-27 04:10:07,646 INFO L78 Accepts]: Start accepts. Automaton has 45 states and 45 transitions. Word has length 41 [2018-10-27 04:10:07,646 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-27 04:10:07,646 INFO L481 AbstractCegarLoop]: Abstraction has 45 states and 45 transitions. [2018-10-27 04:10:07,646 INFO L482 AbstractCegarLoop]: Interpolant automaton has 13 states. [2018-10-27 04:10:07,646 INFO L276 IsEmpty]: Start isEmpty. Operand 45 states and 45 transitions. [2018-10-27 04:10:07,647 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 45 [2018-10-27 04:10:07,647 INFO L367 BasicCegarLoop]: Found error trace [2018-10-27 04:10:07,647 INFO L375 BasicCegarLoop]: trace histogram [12, 11, 11, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-27 04:10:07,647 INFO L424 AbstractCegarLoop]: === Iteration 20 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-27 04:10:07,648 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-27 04:10:07,648 INFO L82 PathProgramCache]: Analyzing trace with hash 860688091, now seen corresponding path program 11 times [2018-10-27 04:10:07,648 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-27 04:10:07,648 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 04:10:07,649 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-27 04:10:07,649 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 04:10:07,649 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-27 04:10:07,656 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-27 04:10:07,868 INFO L134 CoverageAnalysis]: Checked inductivity of 187 backedges. 0 proven. 187 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:10:07,868 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-27 04:10:07,868 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-10-27 04:10:07,869 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-10-27 04:10:07,869 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-10-27 04:10:07,869 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-27 04:10:07,869 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/z3 Starting monitored process 19 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 19 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-27 04:10:07,877 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-10-27 04:10:07,877 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST2 (IT: FPandBP) [2018-10-27 04:10:14,162 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 12 check-sat command(s) [2018-10-27 04:10:14,163 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-27 04:10:14,235 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-27 04:10:14,253 INFO L134 CoverageAnalysis]: Checked inductivity of 187 backedges. 0 proven. 187 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:10:14,253 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-10-27 04:10:19,995 INFO L134 CoverageAnalysis]: Checked inductivity of 187 backedges. 0 proven. 187 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:10:20,017 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-10-27 04:10:20,017 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 14, 14] total 26 [2018-10-27 04:10:20,017 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-10-27 04:10:20,018 INFO L460 AbstractCegarLoop]: Interpolant automaton has 14 states [2018-10-27 04:10:20,018 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2018-10-27 04:10:20,018 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=193, Invalid=457, Unknown=0, NotChecked=0, Total=650 [2018-10-27 04:10:20,018 INFO L87 Difference]: Start difference. First operand 45 states and 45 transitions. Second operand 14 states. [2018-10-27 04:10:20,310 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-27 04:10:20,310 INFO L93 Difference]: Finished difference Result 54 states and 54 transitions. [2018-10-27 04:10:20,311 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2018-10-27 04:10:20,311 INFO L78 Accepts]: Start accepts. Automaton has 14 states. Word has length 44 [2018-10-27 04:10:20,311 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-27 04:10:20,312 INFO L225 Difference]: With dead ends: 54 [2018-10-27 04:10:20,312 INFO L226 Difference]: Without dead ends: 49 [2018-10-27 04:10:20,313 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 102 GetRequests, 76 SyntacticMatches, 2 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 5.9s TimeCoverageRelationStatistics Valid=193, Invalid=457, Unknown=0, NotChecked=0, Total=650 [2018-10-27 04:10:20,313 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 49 states. [2018-10-27 04:10:20,317 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 49 to 48. [2018-10-27 04:10:20,317 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 48 states. [2018-10-27 04:10:20,318 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 48 states to 48 states and 48 transitions. [2018-10-27 04:10:20,318 INFO L78 Accepts]: Start accepts. Automaton has 48 states and 48 transitions. Word has length 44 [2018-10-27 04:10:20,318 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-27 04:10:20,318 INFO L481 AbstractCegarLoop]: Abstraction has 48 states and 48 transitions. [2018-10-27 04:10:20,319 INFO L482 AbstractCegarLoop]: Interpolant automaton has 14 states. [2018-10-27 04:10:20,319 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 48 transitions. [2018-10-27 04:10:20,319 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 48 [2018-10-27 04:10:20,319 INFO L367 BasicCegarLoop]: Found error trace [2018-10-27 04:10:20,320 INFO L375 BasicCegarLoop]: trace histogram [13, 12, 12, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-27 04:10:20,320 INFO L424 AbstractCegarLoop]: === Iteration 21 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-27 04:10:20,320 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-27 04:10:20,320 INFO L82 PathProgramCache]: Analyzing trace with hash -1361137378, now seen corresponding path program 12 times [2018-10-27 04:10:20,320 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-27 04:10:20,321 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 04:10:20,321 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-27 04:10:20,321 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 04:10:20,321 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-27 04:10:20,329 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-27 04:10:20,528 INFO L134 CoverageAnalysis]: Checked inductivity of 222 backedges. 0 proven. 222 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:10:20,528 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-27 04:10:20,528 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-10-27 04:10:20,528 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-10-27 04:10:20,528 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-10-27 04:10:20,529 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-27 04:10:20,529 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/z3 Starting monitored process 20 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 20 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-27 04:10:20,536 INFO L103 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-10-27 04:10:20,537 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder TERMS_WITH_SMALL_CONSTANTS_FIRST (IT: FPandBP) [2018-10-27 04:10:20,554 INFO L249 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-10-27 04:10:20,554 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-27 04:10:20,555 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-27 04:10:20,626 INFO L134 CoverageAnalysis]: Checked inductivity of 222 backedges. 0 proven. 222 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:10:20,626 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-10-27 04:10:26,188 INFO L134 CoverageAnalysis]: Checked inductivity of 222 backedges. 0 proven. 222 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:10:26,208 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-10-27 04:10:26,208 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 15, 15] total 28 [2018-10-27 04:10:26,208 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-10-27 04:10:26,209 INFO L460 AbstractCegarLoop]: Interpolant automaton has 15 states [2018-10-27 04:10:26,209 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2018-10-27 04:10:26,209 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=222, Invalid=534, Unknown=0, NotChecked=0, Total=756 [2018-10-27 04:10:26,209 INFO L87 Difference]: Start difference. First operand 48 states and 48 transitions. Second operand 15 states. [2018-10-27 04:10:26,537 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-27 04:10:26,537 INFO L93 Difference]: Finished difference Result 57 states and 57 transitions. [2018-10-27 04:10:26,538 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2018-10-27 04:10:26,538 INFO L78 Accepts]: Start accepts. Automaton has 15 states. Word has length 47 [2018-10-27 04:10:26,538 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-27 04:10:26,539 INFO L225 Difference]: With dead ends: 57 [2018-10-27 04:10:26,539 INFO L226 Difference]: Without dead ends: 52 [2018-10-27 04:10:26,540 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 109 GetRequests, 81 SyntacticMatches, 2 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 5.7s TimeCoverageRelationStatistics Valid=222, Invalid=534, Unknown=0, NotChecked=0, Total=756 [2018-10-27 04:10:26,540 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 52 states. [2018-10-27 04:10:26,546 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 52 to 51. [2018-10-27 04:10:26,546 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 51 states. [2018-10-27 04:10:26,546 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 51 states to 51 states and 51 transitions. [2018-10-27 04:10:26,547 INFO L78 Accepts]: Start accepts. Automaton has 51 states and 51 transitions. Word has length 47 [2018-10-27 04:10:26,547 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-27 04:10:26,547 INFO L481 AbstractCegarLoop]: Abstraction has 51 states and 51 transitions. [2018-10-27 04:10:26,547 INFO L482 AbstractCegarLoop]: Interpolant automaton has 15 states. [2018-10-27 04:10:26,547 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 51 transitions. [2018-10-27 04:10:26,548 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2018-10-27 04:10:26,548 INFO L367 BasicCegarLoop]: Found error trace [2018-10-27 04:10:26,548 INFO L375 BasicCegarLoop]: trace histogram [14, 13, 13, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-27 04:10:26,548 INFO L424 AbstractCegarLoop]: === Iteration 22 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-27 04:10:26,549 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-27 04:10:26,549 INFO L82 PathProgramCache]: Analyzing trace with hash -2022685701, now seen corresponding path program 13 times [2018-10-27 04:10:26,549 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-27 04:10:26,550 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 04:10:26,550 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-27 04:10:26,550 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 04:10:26,550 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-27 04:10:26,559 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-27 04:10:27,034 INFO L134 CoverageAnalysis]: Checked inductivity of 260 backedges. 0 proven. 260 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:10:27,034 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-27 04:10:27,034 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-10-27 04:10:27,035 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-10-27 04:10:27,035 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-10-27 04:10:27,035 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-27 04:10:27,035 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/z3 Starting monitored process 21 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 21 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-27 04:10:27,042 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-27 04:10:27,042 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-10-27 04:10:27,058 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-27 04:10:27,060 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-27 04:10:27,081 INFO L134 CoverageAnalysis]: Checked inductivity of 260 backedges. 0 proven. 260 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:10:27,081 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-10-27 04:10:31,812 INFO L134 CoverageAnalysis]: Checked inductivity of 260 backedges. 0 proven. 260 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:10:31,833 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-10-27 04:10:31,833 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16, 16] total 30 [2018-10-27 04:10:31,833 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-10-27 04:10:31,833 INFO L460 AbstractCegarLoop]: Interpolant automaton has 16 states [2018-10-27 04:10:31,833 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2018-10-27 04:10:31,834 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=253, Invalid=617, Unknown=0, NotChecked=0, Total=870 [2018-10-27 04:10:31,834 INFO L87 Difference]: Start difference. First operand 51 states and 51 transitions. Second operand 16 states. [2018-10-27 04:10:32,175 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-27 04:10:32,175 INFO L93 Difference]: Finished difference Result 60 states and 60 transitions. [2018-10-27 04:10:32,176 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2018-10-27 04:10:32,176 INFO L78 Accepts]: Start accepts. Automaton has 16 states. Word has length 50 [2018-10-27 04:10:32,177 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-27 04:10:32,177 INFO L225 Difference]: With dead ends: 60 [2018-10-27 04:10:32,177 INFO L226 Difference]: Without dead ends: 55 [2018-10-27 04:10:32,178 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 116 GetRequests, 86 SyntacticMatches, 2 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 5.1s TimeCoverageRelationStatistics Valid=253, Invalid=617, Unknown=0, NotChecked=0, Total=870 [2018-10-27 04:10:32,178 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 55 states. [2018-10-27 04:10:32,181 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 55 to 54. [2018-10-27 04:10:32,181 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 54 states. [2018-10-27 04:10:32,182 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 54 transitions. [2018-10-27 04:10:32,182 INFO L78 Accepts]: Start accepts. Automaton has 54 states and 54 transitions. Word has length 50 [2018-10-27 04:10:32,182 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-27 04:10:32,182 INFO L481 AbstractCegarLoop]: Abstraction has 54 states and 54 transitions. [2018-10-27 04:10:32,182 INFO L482 AbstractCegarLoop]: Interpolant automaton has 16 states. [2018-10-27 04:10:32,183 INFO L276 IsEmpty]: Start isEmpty. Operand 54 states and 54 transitions. [2018-10-27 04:10:32,183 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 54 [2018-10-27 04:10:32,183 INFO L367 BasicCegarLoop]: Found error trace [2018-10-27 04:10:32,183 INFO L375 BasicCegarLoop]: trace histogram [15, 14, 14, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-27 04:10:32,184 INFO L424 AbstractCegarLoop]: === Iteration 23 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-27 04:10:32,184 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-27 04:10:32,184 INFO L82 PathProgramCache]: Analyzing trace with hash -603854850, now seen corresponding path program 14 times [2018-10-27 04:10:32,184 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-27 04:10:32,185 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 04:10:32,185 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-27 04:10:32,185 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 04:10:32,185 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-27 04:10:32,192 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-27 04:10:32,619 INFO L134 CoverageAnalysis]: Checked inductivity of 301 backedges. 0 proven. 301 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:10:32,619 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-27 04:10:32,619 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-10-27 04:10:32,619 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-10-27 04:10:32,620 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-10-27 04:10:32,620 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-27 04:10:32,620 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/z3 Starting monitored process 22 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 22 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-27 04:10:32,627 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-10-27 04:10:32,627 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST2 (IT: FPandBP) [2018-10-27 04:11:01,109 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 15 check-sat command(s) [2018-10-27 04:11:01,110 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-27 04:11:01,159 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-27 04:11:01,180 INFO L134 CoverageAnalysis]: Checked inductivity of 301 backedges. 0 proven. 301 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:11:01,180 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-10-27 04:11:05,041 INFO L134 CoverageAnalysis]: Checked inductivity of 301 backedges. 0 proven. 301 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:11:05,062 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-10-27 04:11:05,062 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 17, 17] total 32 [2018-10-27 04:11:05,062 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-10-27 04:11:05,062 INFO L460 AbstractCegarLoop]: Interpolant automaton has 17 states [2018-10-27 04:11:05,063 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2018-10-27 04:11:05,063 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=286, Invalid=706, Unknown=0, NotChecked=0, Total=992 [2018-10-27 04:11:05,063 INFO L87 Difference]: Start difference. First operand 54 states and 54 transitions. Second operand 17 states. [2018-10-27 04:11:05,550 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-27 04:11:05,551 INFO L93 Difference]: Finished difference Result 63 states and 63 transitions. [2018-10-27 04:11:05,552 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2018-10-27 04:11:05,552 INFO L78 Accepts]: Start accepts. Automaton has 17 states. Word has length 53 [2018-10-27 04:11:05,553 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-27 04:11:05,553 INFO L225 Difference]: With dead ends: 63 [2018-10-27 04:11:05,554 INFO L226 Difference]: Without dead ends: 58 [2018-10-27 04:11:05,555 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 123 GetRequests, 91 SyntacticMatches, 2 SemanticMatches, 30 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 4.2s TimeCoverageRelationStatistics Valid=286, Invalid=706, Unknown=0, NotChecked=0, Total=992 [2018-10-27 04:11:05,555 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 58 states. [2018-10-27 04:11:05,559 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 58 to 57. [2018-10-27 04:11:05,559 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 57 states. [2018-10-27 04:11:05,559 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 57 states to 57 states and 57 transitions. [2018-10-27 04:11:05,559 INFO L78 Accepts]: Start accepts. Automaton has 57 states and 57 transitions. Word has length 53 [2018-10-27 04:11:05,560 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-27 04:11:05,560 INFO L481 AbstractCegarLoop]: Abstraction has 57 states and 57 transitions. [2018-10-27 04:11:05,560 INFO L482 AbstractCegarLoop]: Interpolant automaton has 17 states. [2018-10-27 04:11:05,560 INFO L276 IsEmpty]: Start isEmpty. Operand 57 states and 57 transitions. [2018-10-27 04:11:05,561 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 57 [2018-10-27 04:11:05,561 INFO L367 BasicCegarLoop]: Found error trace [2018-10-27 04:11:05,561 INFO L375 BasicCegarLoop]: trace histogram [16, 15, 15, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-27 04:11:05,561 INFO L424 AbstractCegarLoop]: === Iteration 24 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-27 04:11:05,561 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-27 04:11:05,561 INFO L82 PathProgramCache]: Analyzing trace with hash 1012867355, now seen corresponding path program 15 times [2018-10-27 04:11:05,562 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-27 04:11:05,562 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 04:11:05,562 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-27 04:11:05,562 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 04:11:05,563 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-27 04:11:05,571 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-27 04:11:06,164 INFO L134 CoverageAnalysis]: Checked inductivity of 345 backedges. 0 proven. 345 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:11:06,165 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-27 04:11:06,165 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-10-27 04:11:06,165 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-10-27 04:11:06,165 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-10-27 04:11:06,165 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-27 04:11:06,165 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/z3 Starting monitored process 23 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 23 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-27 04:11:06,183 INFO L103 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-10-27 04:11:06,183 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder TERMS_WITH_SMALL_CONSTANTS_FIRST (IT: FPandBP) [2018-10-27 04:11:06,216 INFO L249 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-10-27 04:11:06,216 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-27 04:11:06,217 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-27 04:11:06,236 INFO L134 CoverageAnalysis]: Checked inductivity of 345 backedges. 0 proven. 345 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:11:06,236 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-10-27 04:11:13,626 INFO L134 CoverageAnalysis]: Checked inductivity of 345 backedges. 0 proven. 345 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:11:13,646 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-10-27 04:11:13,647 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 18, 18] total 34 [2018-10-27 04:11:13,647 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-10-27 04:11:13,647 INFO L460 AbstractCegarLoop]: Interpolant automaton has 18 states [2018-10-27 04:11:13,647 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2018-10-27 04:11:13,648 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=321, Invalid=801, Unknown=0, NotChecked=0, Total=1122 [2018-10-27 04:11:13,648 INFO L87 Difference]: Start difference. First operand 57 states and 57 transitions. Second operand 18 states. [2018-10-27 04:11:14,087 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-27 04:11:14,087 INFO L93 Difference]: Finished difference Result 66 states and 66 transitions. [2018-10-27 04:11:14,087 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2018-10-27 04:11:14,088 INFO L78 Accepts]: Start accepts. Automaton has 18 states. Word has length 56 [2018-10-27 04:11:14,088 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-27 04:11:14,089 INFO L225 Difference]: With dead ends: 66 [2018-10-27 04:11:14,089 INFO L226 Difference]: Without dead ends: 61 [2018-10-27 04:11:14,090 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 130 GetRequests, 96 SyntacticMatches, 2 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 7.9s TimeCoverageRelationStatistics Valid=321, Invalid=801, Unknown=0, NotChecked=0, Total=1122 [2018-10-27 04:11:14,090 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 61 states. [2018-10-27 04:11:14,093 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 61 to 60. [2018-10-27 04:11:14,094 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 60 states. [2018-10-27 04:11:14,094 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 60 states to 60 states and 60 transitions. [2018-10-27 04:11:14,094 INFO L78 Accepts]: Start accepts. Automaton has 60 states and 60 transitions. Word has length 56 [2018-10-27 04:11:14,095 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-27 04:11:14,095 INFO L481 AbstractCegarLoop]: Abstraction has 60 states and 60 transitions. [2018-10-27 04:11:14,095 INFO L482 AbstractCegarLoop]: Interpolant automaton has 18 states. [2018-10-27 04:11:14,095 INFO L276 IsEmpty]: Start isEmpty. Operand 60 states and 60 transitions. [2018-10-27 04:11:14,096 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 60 [2018-10-27 04:11:14,096 INFO L367 BasicCegarLoop]: Found error trace [2018-10-27 04:11:14,096 INFO L375 BasicCegarLoop]: trace histogram [17, 16, 16, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-27 04:11:14,096 INFO L424 AbstractCegarLoop]: === Iteration 25 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-27 04:11:14,096 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-27 04:11:14,096 INFO L82 PathProgramCache]: Analyzing trace with hash 1020819166, now seen corresponding path program 16 times [2018-10-27 04:11:14,097 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-27 04:11:14,097 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 04:11:14,097 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-27 04:11:14,098 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 04:11:14,098 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-27 04:11:14,106 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-27 04:11:14,976 INFO L134 CoverageAnalysis]: Checked inductivity of 392 backedges. 0 proven. 392 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:11:14,976 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-27 04:11:14,976 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-10-27 04:11:14,976 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-10-27 04:11:14,976 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-10-27 04:11:14,976 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-27 04:11:14,977 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/z3 Starting monitored process 24 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 24 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-27 04:11:14,984 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-27 04:11:14,984 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-10-27 04:11:15,004 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-27 04:11:15,006 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-27 04:11:15,031 INFO L134 CoverageAnalysis]: Checked inductivity of 392 backedges. 0 proven. 392 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:11:15,031 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-10-27 04:11:23,649 INFO L134 CoverageAnalysis]: Checked inductivity of 392 backedges. 0 proven. 392 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:11:23,669 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-10-27 04:11:23,669 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 19, 19] total 36 [2018-10-27 04:11:23,669 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-10-27 04:11:23,669 INFO L460 AbstractCegarLoop]: Interpolant automaton has 19 states [2018-10-27 04:11:23,670 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2018-10-27 04:11:23,670 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=358, Invalid=902, Unknown=0, NotChecked=0, Total=1260 [2018-10-27 04:11:23,670 INFO L87 Difference]: Start difference. First operand 60 states and 60 transitions. Second operand 19 states. [2018-10-27 04:11:24,216 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-27 04:11:24,216 INFO L93 Difference]: Finished difference Result 69 states and 69 transitions. [2018-10-27 04:11:24,216 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2018-10-27 04:11:24,217 INFO L78 Accepts]: Start accepts. Automaton has 19 states. Word has length 59 [2018-10-27 04:11:24,217 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-27 04:11:24,218 INFO L225 Difference]: With dead ends: 69 [2018-10-27 04:11:24,218 INFO L226 Difference]: Without dead ends: 64 [2018-10-27 04:11:24,218 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 137 GetRequests, 101 SyntacticMatches, 2 SemanticMatches, 34 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 9.4s TimeCoverageRelationStatistics Valid=358, Invalid=902, Unknown=0, NotChecked=0, Total=1260 [2018-10-27 04:11:24,219 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 64 states. [2018-10-27 04:11:24,221 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 64 to 63. [2018-10-27 04:11:24,221 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 63 states. [2018-10-27 04:11:24,221 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 63 states to 63 states and 63 transitions. [2018-10-27 04:11:24,222 INFO L78 Accepts]: Start accepts. Automaton has 63 states and 63 transitions. Word has length 59 [2018-10-27 04:11:24,222 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-27 04:11:24,222 INFO L481 AbstractCegarLoop]: Abstraction has 63 states and 63 transitions. [2018-10-27 04:11:24,222 INFO L482 AbstractCegarLoop]: Interpolant automaton has 19 states. [2018-10-27 04:11:24,222 INFO L276 IsEmpty]: Start isEmpty. Operand 63 states and 63 transitions. [2018-10-27 04:11:24,223 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 63 [2018-10-27 04:11:24,223 INFO L367 BasicCegarLoop]: Found error trace [2018-10-27 04:11:24,223 INFO L375 BasicCegarLoop]: trace histogram [18, 17, 17, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-27 04:11:24,223 INFO L424 AbstractCegarLoop]: === Iteration 26 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-27 04:11:24,223 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-27 04:11:24,224 INFO L82 PathProgramCache]: Analyzing trace with hash 1690019387, now seen corresponding path program 17 times [2018-10-27 04:11:24,224 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-27 04:11:24,224 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 04:11:24,224 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-27 04:11:24,225 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 04:11:24,225 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-27 04:11:24,235 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-27 04:11:24,659 INFO L134 CoverageAnalysis]: Checked inductivity of 442 backedges. 0 proven. 442 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:11:24,659 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-27 04:11:24,659 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-10-27 04:11:24,659 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-10-27 04:11:24,659 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-10-27 04:11:24,659 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-27 04:11:24,660 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/z3 Starting monitored process 25 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 25 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-27 04:11:24,667 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-10-27 04:11:24,667 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST2 (IT: FPandBP) [2018-10-27 04:11:45,240 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 18 check-sat command(s) [2018-10-27 04:11:45,240 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-27 04:11:45,323 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-27 04:11:45,345 INFO L134 CoverageAnalysis]: Checked inductivity of 442 backedges. 0 proven. 442 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:11:45,345 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-10-27 04:11:52,788 INFO L134 CoverageAnalysis]: Checked inductivity of 442 backedges. 0 proven. 442 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:11:52,808 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-10-27 04:11:52,809 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 20, 20] total 38 [2018-10-27 04:11:52,809 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-10-27 04:11:52,809 INFO L460 AbstractCegarLoop]: Interpolant automaton has 20 states [2018-10-27 04:11:52,810 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2018-10-27 04:11:52,810 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=397, Invalid=1009, Unknown=0, NotChecked=0, Total=1406 [2018-10-27 04:11:52,810 INFO L87 Difference]: Start difference. First operand 63 states and 63 transitions. Second operand 20 states. [2018-10-27 04:11:53,455 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-27 04:11:53,455 INFO L93 Difference]: Finished difference Result 72 states and 72 transitions. [2018-10-27 04:11:53,456 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2018-10-27 04:11:53,456 INFO L78 Accepts]: Start accepts. Automaton has 20 states. Word has length 62 [2018-10-27 04:11:53,456 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-27 04:11:53,457 INFO L225 Difference]: With dead ends: 72 [2018-10-27 04:11:53,457 INFO L226 Difference]: Without dead ends: 67 [2018-10-27 04:11:53,458 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 144 GetRequests, 106 SyntacticMatches, 2 SemanticMatches, 36 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 7.8s TimeCoverageRelationStatistics Valid=397, Invalid=1009, Unknown=0, NotChecked=0, Total=1406 [2018-10-27 04:11:53,458 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 67 states. [2018-10-27 04:11:53,462 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 67 to 66. [2018-10-27 04:11:53,462 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 66 states. [2018-10-27 04:11:53,462 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 66 states to 66 states and 66 transitions. [2018-10-27 04:11:53,462 INFO L78 Accepts]: Start accepts. Automaton has 66 states and 66 transitions. Word has length 62 [2018-10-27 04:11:53,462 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-27 04:11:53,462 INFO L481 AbstractCegarLoop]: Abstraction has 66 states and 66 transitions. [2018-10-27 04:11:53,462 INFO L482 AbstractCegarLoop]: Interpolant automaton has 20 states. [2018-10-27 04:11:53,462 INFO L276 IsEmpty]: Start isEmpty. Operand 66 states and 66 transitions. [2018-10-27 04:11:53,463 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 66 [2018-10-27 04:11:53,463 INFO L367 BasicCegarLoop]: Found error trace [2018-10-27 04:11:53,463 INFO L375 BasicCegarLoop]: trace histogram [19, 18, 18, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-27 04:11:53,463 INFO L424 AbstractCegarLoop]: === Iteration 27 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-27 04:11:53,463 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-27 04:11:53,464 INFO L82 PathProgramCache]: Analyzing trace with hash 595615166, now seen corresponding path program 18 times [2018-10-27 04:11:53,464 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-27 04:11:53,464 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 04:11:53,464 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-27 04:11:53,464 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 04:11:53,464 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-27 04:11:53,473 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-27 04:11:53,794 INFO L134 CoverageAnalysis]: Checked inductivity of 495 backedges. 0 proven. 495 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:11:53,795 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-27 04:11:53,795 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-10-27 04:11:53,795 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-10-27 04:11:53,795 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-10-27 04:11:53,795 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-27 04:11:53,795 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/z3 Starting monitored process 26 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 26 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-27 04:11:53,802 INFO L103 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-10-27 04:11:53,802 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder TERMS_WITH_SMALL_CONSTANTS_FIRST (IT: FPandBP) [2018-10-27 04:11:53,820 INFO L249 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-10-27 04:11:53,820 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-27 04:11:53,822 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-27 04:11:53,856 INFO L134 CoverageAnalysis]: Checked inductivity of 495 backedges. 0 proven. 495 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:11:53,857 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-10-27 04:12:04,062 INFO L134 CoverageAnalysis]: Checked inductivity of 495 backedges. 0 proven. 495 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:12:04,081 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-10-27 04:12:04,081 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [21, 21, 21] total 40 [2018-10-27 04:12:04,081 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-10-27 04:12:04,082 INFO L460 AbstractCegarLoop]: Interpolant automaton has 21 states [2018-10-27 04:12:04,082 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2018-10-27 04:12:04,083 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=438, Invalid=1122, Unknown=0, NotChecked=0, Total=1560 [2018-10-27 04:12:04,083 INFO L87 Difference]: Start difference. First operand 66 states and 66 transitions. Second operand 21 states. [2018-10-27 04:12:04,660 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-27 04:12:04,660 INFO L93 Difference]: Finished difference Result 75 states and 75 transitions. [2018-10-27 04:12:04,661 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2018-10-27 04:12:04,661 INFO L78 Accepts]: Start accepts. Automaton has 21 states. Word has length 65 [2018-10-27 04:12:04,661 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-27 04:12:04,661 INFO L225 Difference]: With dead ends: 75 [2018-10-27 04:12:04,661 INFO L226 Difference]: Without dead ends: 70 [2018-10-27 04:12:04,662 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 151 GetRequests, 111 SyntacticMatches, 2 SemanticMatches, 38 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 10.4s TimeCoverageRelationStatistics Valid=438, Invalid=1122, Unknown=0, NotChecked=0, Total=1560 [2018-10-27 04:12:04,662 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 70 states. [2018-10-27 04:12:04,665 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 70 to 69. [2018-10-27 04:12:04,665 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 69 states. [2018-10-27 04:12:04,666 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 69 states to 69 states and 69 transitions. [2018-10-27 04:12:04,666 INFO L78 Accepts]: Start accepts. Automaton has 69 states and 69 transitions. Word has length 65 [2018-10-27 04:12:04,666 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-27 04:12:04,666 INFO L481 AbstractCegarLoop]: Abstraction has 69 states and 69 transitions. [2018-10-27 04:12:04,666 INFO L482 AbstractCegarLoop]: Interpolant automaton has 21 states. [2018-10-27 04:12:04,666 INFO L276 IsEmpty]: Start isEmpty. Operand 69 states and 69 transitions. [2018-10-27 04:12:04,667 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 69 [2018-10-27 04:12:04,667 INFO L367 BasicCegarLoop]: Found error trace [2018-10-27 04:12:04,667 INFO L375 BasicCegarLoop]: trace histogram [20, 19, 19, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-27 04:12:04,667 INFO L424 AbstractCegarLoop]: === Iteration 28 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-27 04:12:04,667 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-27 04:12:04,667 INFO L82 PathProgramCache]: Analyzing trace with hash 296211291, now seen corresponding path program 19 times [2018-10-27 04:12:04,667 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-27 04:12:04,668 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 04:12:04,668 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-27 04:12:04,668 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 04:12:04,668 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-27 04:12:04,677 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-27 04:12:05,764 INFO L134 CoverageAnalysis]: Checked inductivity of 551 backedges. 0 proven. 551 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:12:05,765 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-27 04:12:05,765 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-10-27 04:12:05,765 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-10-27 04:12:05,765 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-10-27 04:12:05,765 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-27 04:12:05,765 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/z3 Starting monitored process 27 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 27 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-27 04:12:05,774 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-27 04:12:05,774 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-10-27 04:12:05,794 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-27 04:12:05,796 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-27 04:12:05,873 INFO L134 CoverageAnalysis]: Checked inductivity of 551 backedges. 0 proven. 551 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:12:05,874 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-10-27 04:12:20,248 INFO L134 CoverageAnalysis]: Checked inductivity of 551 backedges. 0 proven. 551 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:12:20,268 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-10-27 04:12:20,268 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 22, 22] total 42 [2018-10-27 04:12:20,268 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-10-27 04:12:20,268 INFO L460 AbstractCegarLoop]: Interpolant automaton has 22 states [2018-10-27 04:12:20,269 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2018-10-27 04:12:20,269 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=481, Invalid=1241, Unknown=0, NotChecked=0, Total=1722 [2018-10-27 04:12:20,269 INFO L87 Difference]: Start difference. First operand 69 states and 69 transitions. Second operand 22 states. [2018-10-27 04:12:20,864 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-27 04:12:20,864 INFO L93 Difference]: Finished difference Result 78 states and 78 transitions. [2018-10-27 04:12:20,865 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2018-10-27 04:12:20,865 INFO L78 Accepts]: Start accepts. Automaton has 22 states. Word has length 68 [2018-10-27 04:12:20,865 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-27 04:12:20,866 INFO L225 Difference]: With dead ends: 78 [2018-10-27 04:12:20,866 INFO L226 Difference]: Without dead ends: 73 [2018-10-27 04:12:20,867 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 158 GetRequests, 116 SyntacticMatches, 2 SemanticMatches, 40 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 15.4s TimeCoverageRelationStatistics Valid=481, Invalid=1241, Unknown=0, NotChecked=0, Total=1722 [2018-10-27 04:12:20,867 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 73 states. [2018-10-27 04:12:20,871 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 73 to 72. [2018-10-27 04:12:20,871 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 72 states. [2018-10-27 04:12:20,871 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 72 states to 72 states and 72 transitions. [2018-10-27 04:12:20,871 INFO L78 Accepts]: Start accepts. Automaton has 72 states and 72 transitions. Word has length 68 [2018-10-27 04:12:20,871 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-27 04:12:20,871 INFO L481 AbstractCegarLoop]: Abstraction has 72 states and 72 transitions. [2018-10-27 04:12:20,871 INFO L482 AbstractCegarLoop]: Interpolant automaton has 22 states. [2018-10-27 04:12:20,872 INFO L276 IsEmpty]: Start isEmpty. Operand 72 states and 72 transitions. [2018-10-27 04:12:20,872 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 72 [2018-10-27 04:12:20,872 INFO L367 BasicCegarLoop]: Found error trace [2018-10-27 04:12:20,872 INFO L375 BasicCegarLoop]: trace histogram [21, 20, 20, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-27 04:12:20,872 INFO L424 AbstractCegarLoop]: === Iteration 29 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-27 04:12:20,873 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-27 04:12:20,873 INFO L82 PathProgramCache]: Analyzing trace with hash 1402444958, now seen corresponding path program 20 times [2018-10-27 04:12:20,873 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-27 04:12:20,873 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 04:12:20,874 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-27 04:12:20,874 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 04:12:20,874 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-27 04:12:20,883 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-27 04:12:21,461 INFO L134 CoverageAnalysis]: Checked inductivity of 610 backedges. 0 proven. 610 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:12:21,461 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-27 04:12:21,461 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-10-27 04:12:21,461 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-10-27 04:12:21,461 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-10-27 04:12:21,462 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-27 04:12:21,462 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/z3 Starting monitored process 28 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 28 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-27 04:12:21,472 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-10-27 04:12:21,472 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST2 (IT: FPandBP) [2018-10-27 04:12:44,489 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 21 check-sat command(s) [2018-10-27 04:12:44,489 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-27 04:12:44,523 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-27 04:12:44,641 INFO L134 CoverageAnalysis]: Checked inductivity of 610 backedges. 0 proven. 610 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:12:44,641 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-10-27 04:12:47,310 WARN L854 $PredicateComparison]: unable to prove that (or (< (mod (+ c_main_~x~0 8) 4294967296) 99) (<= 99 (mod (+ c_main_~x~0 6) 4294967296))) is different from true [2018-10-27 04:12:49,188 WARN L179 SmtUtils]: Spent 135.00 ms on a formula simplification that was a NOOP. DAG size: 12 [2018-10-27 04:12:51,468 WARN L179 SmtUtils]: Spent 1.08 s on a formula simplification that was a NOOP. DAG size: 12 [2018-10-27 04:12:54,573 WARN L179 SmtUtils]: Spent 112.00 ms on a formula simplification that was a NOOP. DAG size: 12 [2018-10-27 04:12:56,475 WARN L179 SmtUtils]: Spent 125.00 ms on a formula simplification that was a NOOP. DAG size: 12 [2018-10-27 04:12:57,782 INFO L134 CoverageAnalysis]: Checked inductivity of 610 backedges. 0 proven. 591 refuted. 0 times theorem prover too weak. 0 trivial. 19 not checked. [2018-10-27 04:12:57,804 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-10-27 04:12:57,804 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [23, 23, 25] total 46 [2018-10-27 04:12:57,804 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-10-27 04:12:57,804 INFO L460 AbstractCegarLoop]: Interpolant automaton has 23 states [2018-10-27 04:12:57,805 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2018-10-27 04:12:57,805 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=552, Invalid=1430, Unknown=2, NotChecked=86, Total=2070 [2018-10-27 04:12:57,806 INFO L87 Difference]: Start difference. First operand 72 states and 72 transitions. Second operand 23 states. [2018-10-27 04:12:58,429 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-27 04:12:58,429 INFO L93 Difference]: Finished difference Result 81 states and 81 transitions. [2018-10-27 04:12:58,430 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2018-10-27 04:12:58,430 INFO L78 Accepts]: Start accepts. Automaton has 23 states. Word has length 71 [2018-10-27 04:12:58,430 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-27 04:12:58,431 INFO L225 Difference]: With dead ends: 81 [2018-10-27 04:12:58,431 INFO L226 Difference]: Without dead ends: 76 [2018-10-27 04:12:58,433 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 165 GetRequests, 111 SyntacticMatches, 10 SemanticMatches, 44 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 22 ImplicationChecksByTransitivity, 13.7s TimeCoverageRelationStatistics Valid=552, Invalid=1430, Unknown=2, NotChecked=86, Total=2070 [2018-10-27 04:12:58,433 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 76 states. [2018-10-27 04:12:58,438 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 76 to 75. [2018-10-27 04:12:58,438 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 75 states. [2018-10-27 04:12:58,438 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 75 states to 75 states and 75 transitions. [2018-10-27 04:12:58,438 INFO L78 Accepts]: Start accepts. Automaton has 75 states and 75 transitions. Word has length 71 [2018-10-27 04:12:58,439 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-27 04:12:58,439 INFO L481 AbstractCegarLoop]: Abstraction has 75 states and 75 transitions. [2018-10-27 04:12:58,439 INFO L482 AbstractCegarLoop]: Interpolant automaton has 23 states. [2018-10-27 04:12:58,439 INFO L276 IsEmpty]: Start isEmpty. Operand 75 states and 75 transitions. [2018-10-27 04:12:58,439 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 75 [2018-10-27 04:12:58,440 INFO L367 BasicCegarLoop]: Found error trace [2018-10-27 04:12:58,440 INFO L375 BasicCegarLoop]: trace histogram [22, 21, 21, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-27 04:12:58,440 INFO L424 AbstractCegarLoop]: === Iteration 30 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-27 04:12:58,440 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-27 04:12:58,440 INFO L82 PathProgramCache]: Analyzing trace with hash 1925556347, now seen corresponding path program 21 times [2018-10-27 04:12:58,440 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-27 04:12:58,441 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 04:12:58,441 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-27 04:12:58,441 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 04:12:58,441 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-27 04:12:58,451 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-27 04:12:58,886 INFO L134 CoverageAnalysis]: Checked inductivity of 672 backedges. 0 proven. 672 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:12:58,887 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-27 04:12:58,887 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-10-27 04:12:58,887 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-10-27 04:12:58,887 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-10-27 04:12:58,887 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-27 04:12:58,887 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/z3 Starting monitored process 29 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 29 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-27 04:12:58,897 INFO L103 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-10-27 04:12:58,897 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder TERMS_WITH_SMALL_CONSTANTS_FIRST (IT: FPandBP) [2018-10-27 04:12:58,919 INFO L249 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-10-27 04:12:58,919 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-27 04:12:58,921 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-27 04:12:58,943 INFO L134 CoverageAnalysis]: Checked inductivity of 672 backedges. 0 proven. 672 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:12:58,943 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-10-27 04:13:14,990 INFO L134 CoverageAnalysis]: Checked inductivity of 672 backedges. 0 proven. 672 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:13:15,009 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-10-27 04:13:15,010 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [24, 24, 24] total 46 [2018-10-27 04:13:15,010 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-10-27 04:13:15,010 INFO L460 AbstractCegarLoop]: Interpolant automaton has 24 states [2018-10-27 04:13:15,010 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2018-10-27 04:13:15,011 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=573, Invalid=1496, Unknown=1, NotChecked=0, Total=2070 [2018-10-27 04:13:15,011 INFO L87 Difference]: Start difference. First operand 75 states and 75 transitions. Second operand 24 states. [2018-10-27 04:13:15,694 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-27 04:13:15,694 INFO L93 Difference]: Finished difference Result 84 states and 84 transitions. [2018-10-27 04:13:15,694 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2018-10-27 04:13:15,695 INFO L78 Accepts]: Start accepts. Automaton has 24 states. Word has length 74 [2018-10-27 04:13:15,695 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-27 04:13:15,696 INFO L225 Difference]: With dead ends: 84 [2018-10-27 04:13:15,696 INFO L226 Difference]: Without dead ends: 79 [2018-10-27 04:13:15,697 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 172 GetRequests, 126 SyntacticMatches, 2 SemanticMatches, 44 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 16.4s TimeCoverageRelationStatistics Valid=573, Invalid=1496, Unknown=1, NotChecked=0, Total=2070 [2018-10-27 04:13:15,697 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 79 states. [2018-10-27 04:13:15,700 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 79 to 78. [2018-10-27 04:13:15,700 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 78 states. [2018-10-27 04:13:15,701 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 78 states to 78 states and 78 transitions. [2018-10-27 04:13:15,701 INFO L78 Accepts]: Start accepts. Automaton has 78 states and 78 transitions. Word has length 74 [2018-10-27 04:13:15,701 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-27 04:13:15,701 INFO L481 AbstractCegarLoop]: Abstraction has 78 states and 78 transitions. [2018-10-27 04:13:15,701 INFO L482 AbstractCegarLoop]: Interpolant automaton has 24 states. [2018-10-27 04:13:15,701 INFO L276 IsEmpty]: Start isEmpty. Operand 78 states and 78 transitions. [2018-10-27 04:13:15,702 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 78 [2018-10-27 04:13:15,702 INFO L367 BasicCegarLoop]: Found error trace [2018-10-27 04:13:15,702 INFO L375 BasicCegarLoop]: trace histogram [23, 22, 22, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-27 04:13:15,702 INFO L424 AbstractCegarLoop]: === Iteration 31 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-27 04:13:15,702 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-27 04:13:15,702 INFO L82 PathProgramCache]: Analyzing trace with hash -499371138, now seen corresponding path program 22 times [2018-10-27 04:13:15,702 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-27 04:13:15,703 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 04:13:15,703 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-27 04:13:15,703 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 04:13:15,703 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-27 04:13:15,713 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-27 04:13:16,571 INFO L134 CoverageAnalysis]: Checked inductivity of 737 backedges. 0 proven. 737 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:13:16,571 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-27 04:13:16,571 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-10-27 04:13:16,571 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-10-27 04:13:16,571 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-10-27 04:13:16,571 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-27 04:13:16,571 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/z3 Starting monitored process 30 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 30 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-27 04:13:16,579 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-27 04:13:16,579 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-10-27 04:13:16,600 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-27 04:13:16,602 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-27 04:13:16,633 INFO L134 CoverageAnalysis]: Checked inductivity of 737 backedges. 0 proven. 737 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 04:13:16,633 INFO L316 TraceCheckSpWp]: Computing backward predicates... Received shutdown request... [2018-10-27 04:13:18,648 WARN L187 SmtUtils]: Removed 1 from assertion stack [2018-10-27 04:13:18,648 INFO L177 TraceCheckSpWp]: Timeout while computing interpolants [2018-10-27 04:13:18,848 WARN L522 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 30 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-27 04:13:18,849 WARN L550 AbstractCegarLoop]: Verification canceled [2018-10-27 04:13:18,854 WARN L205 ceAbstractionStarter]: Timeout [2018-10-27 04:13:18,854 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 27.10 04:13:18 BoogieIcfgContainer [2018-10-27 04:13:18,854 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2018-10-27 04:13:18,855 INFO L168 Benchmark]: Toolchain (without parser) took 276807.02 ms. Allocated memory was 1.5 GB in the beginning and 2.5 GB in the end (delta: 942.1 MB). Free memory was 1.4 GB in the beginning and 1.8 GB in the end (delta: -312.1 MB). Peak memory consumption was 630.0 MB. Max. memory is 7.1 GB. [2018-10-27 04:13:18,856 INFO L168 Benchmark]: CDTParser took 0.20 ms. Allocated memory is still 1.5 GB. Free memory is still 1.5 GB. There was no memory consumed. Max. memory is 7.1 GB. [2018-10-27 04:13:18,857 INFO L168 Benchmark]: CACSL2BoogieTranslator took 266.74 ms. Allocated memory is still 1.5 GB. Free memory was 1.4 GB in the beginning and 1.4 GB in the end (delta: 10.6 MB). Peak memory consumption was 10.6 MB. Max. memory is 7.1 GB. [2018-10-27 04:13:18,857 INFO L168 Benchmark]: Boogie Procedure Inliner took 18.96 ms. Allocated memory is still 1.5 GB. Free memory is still 1.4 GB. There was no memory consumed. Max. memory is 7.1 GB. [2018-10-27 04:13:18,858 INFO L168 Benchmark]: Boogie Preprocessor took 21.69 ms. Allocated memory is still 1.5 GB. Free memory is still 1.4 GB. There was no memory consumed. Max. memory is 7.1 GB. [2018-10-27 04:13:18,858 INFO L168 Benchmark]: RCFGBuilder took 315.88 ms. Allocated memory was 1.5 GB in the beginning and 2.3 GB in the end (delta: 759.7 MB). Free memory was 1.4 GB in the beginning and 2.2 GB in the end (delta: -810.5 MB). Peak memory consumption was 26.5 MB. Max. memory is 7.1 GB. [2018-10-27 04:13:18,859 INFO L168 Benchmark]: TraceAbstraction took 276179.00 ms. Allocated memory was 2.3 GB in the beginning and 2.5 GB in the end (delta: 182.5 MB). Free memory was 2.2 GB in the beginning and 1.8 GB in the end (delta: 487.8 MB). Peak memory consumption was 670.3 MB. Max. memory is 7.1 GB. [2018-10-27 04:13:18,864 INFO L336 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.20 ms. Allocated memory is still 1.5 GB. Free memory is still 1.5 GB. There was no memory consumed. Max. memory is 7.1 GB. * CACSL2BoogieTranslator took 266.74 ms. Allocated memory is still 1.5 GB. Free memory was 1.4 GB in the beginning and 1.4 GB in the end (delta: 10.6 MB). Peak memory consumption was 10.6 MB. Max. memory is 7.1 GB. * Boogie Procedure Inliner took 18.96 ms. Allocated memory is still 1.5 GB. Free memory is still 1.4 GB. There was no memory consumed. Max. memory is 7.1 GB. * Boogie Preprocessor took 21.69 ms. Allocated memory is still 1.5 GB. Free memory is still 1.4 GB. There was no memory consumed. Max. memory is 7.1 GB. * RCFGBuilder took 315.88 ms. Allocated memory was 1.5 GB in the beginning and 2.3 GB in the end (delta: 759.7 MB). Free memory was 1.4 GB in the beginning and 2.2 GB in the end (delta: -810.5 MB). Peak memory consumption was 26.5 MB. Max. memory is 7.1 GB. * TraceAbstraction took 276179.00 ms. Allocated memory was 2.3 GB in the beginning and 2.5 GB in the end (delta: 182.5 MB). Free memory was 2.2 GB in the beginning and 1.8 GB in the end (delta: 487.8 MB). Peak memory consumption was 670.3 MB. Max. memory is 7.1 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [Line: 5]: Timeout (TraceAbstraction) Unable to prove that call of __VERIFIER_error() unreachable (line 5). Cancelled while BasicCegarLoop was analyzing trace of length 78 with TraceHistMax 23,while TraceCheckSpWp was constructing backward predicates,while PredicateUnifier was unifying predicates,while SimplifyDDAWithTimeout was simplifying term of DAG size 7. - StatisticsResult: Ultimate Automizer benchmark data CFG has 4 procedures, 19 locations, 1 error locations. TIMEOUT Result, 276.1s OverallTime, 31 OverallIterations, 23 TraceHistogramMax, 10.1s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 589 SDtfs, 32 SDslu, 5786 SDs, 0 SdLazy, 8358 SolverSat, 5 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 6.6s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 2458 GetRequests, 1832 SyntacticMatches, 64 SemanticMatches, 562 ConstructedPredicates, 2 IntricatePredicates, 0 DeprecatedPredicates, 48 ImplicationChecksByTransitivity, 137.2s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=78occurred in iteration=30, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 1.2s AbstIntTime, 3 AbstIntIterations, 0 AbstIntStrong, NaN AbsIntWeakeningRatio, NaN AbsIntAvgWeakeningVarsNumRemoved, NaN AbsIntAvgWeakenedConjuncts, 0.0s DumpTime, AutomataMinimizationStatistics: 0.1s AutomataMinimizationTime, 30 MinimizatonAttempts, 32 StatesRemovedByMinimization, 28 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 118.3s SatisfiabilityAnalysisTime, 141.6s InterpolantComputationTime, 2137 NumberOfCodeBlocks, 2131 NumberOfCodeBlocksAsserted, 150 NumberOfCheckSat, 3109 ConstructedInterpolants, 2 QuantifiedInterpolants, 888927 SizeOfPredicates, 33 NumberOfNonLiveVariables, 2173 ConjunctsInSsa, 577 ConjunctsInUnsatCore, 86 InterpolantComputations, 7 PerfectInterpolantSequences, 107/15558 InterpolantCoveringCapability, InvariantSynthesisStatistics: No data available, InterpolantConsolidationStatistics: No data available, ReuseStatistics: No data available RESULT: Ultimate could not prove your program: Timeout Completed graceful shutdown