java -Xmx8000000000 -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc ../../../trunk/examples/toolchains/AutomizerCInline.xml -s ../../../trunk/examples/settings/default/taipan/svcomp-Reach-64bit-Taipan_Default-INT-LIM.epf -i ../../../trunk/examples/svcomp/loops-crafted-1/Mono6_false-unreach-call1.c -------------------------------------------------------------------------------- This is Ultimate 0.1.23-63daa26 [2018-11-12 20:46:08,466 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-11-12 20:46:08,468 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-11-12 20:46:08,481 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-11-12 20:46:08,482 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-11-12 20:46:08,483 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-11-12 20:46:08,484 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-11-12 20:46:08,487 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-11-12 20:46:08,490 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-11-12 20:46:08,498 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-11-12 20:46:08,499 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-11-12 20:46:08,499 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-11-12 20:46:08,500 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-11-12 20:46:08,503 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-11-12 20:46:08,507 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-11-12 20:46:08,508 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-11-12 20:46:08,509 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-11-12 20:46:08,512 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-11-12 20:46:08,517 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-11-12 20:46:08,520 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-11-12 20:46:08,521 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-11-12 20:46:08,524 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-11-12 20:46:08,528 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-11-12 20:46:08,528 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-11-12 20:46:08,528 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-11-12 20:46:08,530 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-11-12 20:46:08,531 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-11-12 20:46:08,532 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-11-12 20:46:08,533 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-11-12 20:46:08,536 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-11-12 20:46:08,536 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-11-12 20:46:08,537 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-11-12 20:46:08,537 INFO L177 SettingsManager]: ReqParser provides no preferences, ignoring... [2018-11-12 20:46:08,537 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-11-12 20:46:08,538 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-11-12 20:46:08,541 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-11-12 20:46:08,541 INFO L98 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/default/taipan/svcomp-Reach-64bit-Taipan_Default-INT-LIM.epf [2018-11-12 20:46:08,569 INFO L110 SettingsManager]: Loading preferences was successful [2018-11-12 20:46:08,570 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-11-12 20:46:08,571 INFO L131 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2018-11-12 20:46:08,572 INFO L133 SettingsManager]: * User list type=DISABLED [2018-11-12 20:46:08,572 INFO L133 SettingsManager]: * calls to implemented procedures=false [2018-11-12 20:46:08,572 INFO L131 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2018-11-12 20:46:08,572 INFO L133 SettingsManager]: * Maximum recursion depth of evaluation operations=6 [2018-11-12 20:46:08,572 INFO L133 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2018-11-12 20:46:08,573 INFO L133 SettingsManager]: * Octagon Domain=false [2018-11-12 20:46:08,573 INFO L133 SettingsManager]: * Abstract domain=CompoundDomain [2018-11-12 20:46:08,573 INFO L133 SettingsManager]: * Log string format=TERM [2018-11-12 20:46:08,573 INFO L133 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2018-11-12 20:46:08,573 INFO L133 SettingsManager]: * Use the RCFG-of-the-future interface=true [2018-11-12 20:46:08,574 INFO L131 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2018-11-12 20:46:08,574 INFO L133 SettingsManager]: * Overapproximate operations on floating types=true [2018-11-12 20:46:08,575 INFO L133 SettingsManager]: * Check division by zero=IGNORE [2018-11-12 20:46:08,575 INFO L133 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2018-11-12 20:46:08,575 INFO L133 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2018-11-12 20:46:08,575 INFO L133 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2018-11-12 20:46:08,575 INFO L133 SettingsManager]: * Check if freed pointer was valid=false [2018-11-12 20:46:08,577 INFO L133 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2018-11-12 20:46:08,577 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-11-12 20:46:08,578 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-11-12 20:46:08,578 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-11-12 20:46:08,578 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-11-12 20:46:08,578 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-11-12 20:46:08,578 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-11-12 20:46:08,579 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-11-12 20:46:08,579 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-11-12 20:46:08,579 INFO L133 SettingsManager]: * Trace refinement strategy=TAIPAN [2018-11-12 20:46:08,579 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-11-12 20:46:08,579 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-11-12 20:46:08,579 INFO L133 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2018-11-12 20:46:08,580 INFO L133 SettingsManager]: * To the following directory=dump/ [2018-11-12 20:46:08,580 INFO L133 SettingsManager]: * Abstract interpretation Mode=USE_PREDICATES [2018-11-12 20:46:08,640 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2018-11-12 20:46:08,651 INFO L258 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-11-12 20:46:08,654 INFO L214 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2018-11-12 20:46:08,656 INFO L271 PluginConnector]: Initializing CDTParser... [2018-11-12 20:46:08,656 INFO L276 PluginConnector]: CDTParser initialized [2018-11-12 20:46:08,657 INFO L418 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/loops-crafted-1/Mono6_false-unreach-call1.c [2018-11-12 20:46:08,716 INFO L218 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/15c11adef/20053b965fe64955a45b7b71c2d61d52/FLAGcf60815e3 [2018-11-12 20:46:09,151 INFO L298 CDTParser]: Found 1 translation units. [2018-11-12 20:46:09,151 INFO L158 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/loops-crafted-1/Mono6_false-unreach-call1.c [2018-11-12 20:46:09,160 INFO L346 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/15c11adef/20053b965fe64955a45b7b71c2d61d52/FLAGcf60815e3 [2018-11-12 20:46:09,175 INFO L354 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/15c11adef/20053b965fe64955a45b7b71c2d61d52 [2018-11-12 20:46:09,186 INFO L296 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2018-11-12 20:46:09,188 INFO L131 ToolchainWalker]: Walking toolchain with 5 elements. [2018-11-12 20:46:09,189 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2018-11-12 20:46:09,189 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2018-11-12 20:46:09,195 INFO L276 PluginConnector]: CACSL2BoogieTranslator initialized [2018-11-12 20:46:09,196 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 12.11 08:46:09" (1/1) ... [2018-11-12 20:46:09,200 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@5b9ae0cd and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 08:46:09, skipping insertion in model container [2018-11-12 20:46:09,200 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 12.11 08:46:09" (1/1) ... [2018-11-12 20:46:09,212 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2018-11-12 20:46:09,234 INFO L174 MainTranslator]: Built tables and reachable declarations [2018-11-12 20:46:09,479 INFO L201 PostProcessor]: Analyzing one entry point: main [2018-11-12 20:46:09,483 INFO L189 MainTranslator]: Completed pre-run [2018-11-12 20:46:09,502 INFO L201 PostProcessor]: Analyzing one entry point: main [2018-11-12 20:46:09,521 INFO L193 MainTranslator]: Completed translation [2018-11-12 20:46:09,521 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 08:46:09 WrapperNode [2018-11-12 20:46:09,522 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2018-11-12 20:46:09,523 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2018-11-12 20:46:09,523 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2018-11-12 20:46:09,523 INFO L276 PluginConnector]: Boogie Procedure Inliner initialized [2018-11-12 20:46:09,533 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 08:46:09" (1/1) ... [2018-11-12 20:46:09,539 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 08:46:09" (1/1) ... [2018-11-12 20:46:09,544 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2018-11-12 20:46:09,545 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2018-11-12 20:46:09,545 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2018-11-12 20:46:09,545 INFO L276 PluginConnector]: Boogie Preprocessor initialized [2018-11-12 20:46:09,556 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 08:46:09" (1/1) ... [2018-11-12 20:46:09,556 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 08:46:09" (1/1) ... [2018-11-12 20:46:09,557 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 08:46:09" (1/1) ... [2018-11-12 20:46:09,557 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 08:46:09" (1/1) ... [2018-11-12 20:46:09,561 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 08:46:09" (1/1) ... [2018-11-12 20:46:09,567 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 08:46:09" (1/1) ... [2018-11-12 20:46:09,568 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 08:46:09" (1/1) ... [2018-11-12 20:46:09,569 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2018-11-12 20:46:09,570 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2018-11-12 20:46:09,570 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2018-11-12 20:46:09,570 INFO L276 PluginConnector]: RCFGBuilder initialized [2018-11-12 20:46:09,571 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 08:46:09" (1/1) ... No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-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-11-12 20:46:09,694 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2018-11-12 20:46:09,694 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2018-11-12 20:46:09,694 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2018-11-12 20:46:09,694 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2018-11-12 20:46:09,694 INFO L130 BoogieDeclarations]: Found specification of procedure main [2018-11-12 20:46:09,695 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2018-11-12 20:46:09,695 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2018-11-12 20:46:09,695 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2018-11-12 20:46:09,928 INFO L278 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2018-11-12 20:46:09,928 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 12.11 08:46:09 BoogieIcfgContainer [2018-11-12 20:46:09,929 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2018-11-12 20:46:09,930 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2018-11-12 20:46:09,930 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2018-11-12 20:46:09,943 INFO L276 PluginConnector]: TraceAbstraction initialized [2018-11-12 20:46:09,943 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 12.11 08:46:09" (1/3) ... [2018-11-12 20:46:09,945 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5b7cf32e and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 12.11 08:46:09, skipping insertion in model container [2018-11-12 20:46:09,945 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 08:46:09" (2/3) ... [2018-11-12 20:46:09,946 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5b7cf32e and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 12.11 08:46:09, skipping insertion in model container [2018-11-12 20:46:09,946 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 12.11 08:46:09" (3/3) ... [2018-11-12 20:46:09,949 INFO L112 eAbstractionObserver]: Analyzing ICFG Mono6_false-unreach-call1.c [2018-11-12 20:46:09,965 INFO L136 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-11-12 20:46:09,976 INFO L148 ceAbstractionStarter]: Appying trace abstraction to program that has 1 error locations. [2018-11-12 20:46:09,999 INFO L257 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2018-11-12 20:46:10,059 INFO L382 AbstractCegarLoop]: Interprodecural is true [2018-11-12 20:46:10,060 INFO L383 AbstractCegarLoop]: Hoare is true [2018-11-12 20:46:10,060 INFO L384 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-11-12 20:46:10,060 INFO L385 AbstractCegarLoop]: Backedges is STRAIGHT_LINE [2018-11-12 20:46:10,060 INFO L386 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-11-12 20:46:10,060 INFO L387 AbstractCegarLoop]: Difference is false [2018-11-12 20:46:10,061 INFO L388 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-11-12 20:46:10,061 INFO L393 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-11-12 20:46:10,100 INFO L276 IsEmpty]: Start isEmpty. Operand 21 states. [2018-11-12 20:46:10,105 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 11 [2018-11-12 20:46:10,105 INFO L367 BasicCegarLoop]: Found error trace [2018-11-12 20:46:10,106 INFO L375 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-12 20:46:10,108 INFO L423 AbstractCegarLoop]: === Iteration 1 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-12 20:46:10,114 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-12 20:46:10,114 INFO L82 PathProgramCache]: Analyzing trace with hash -2008095039, now seen corresponding path program 1 times [2018-11-12 20:46:10,116 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-12 20:46:10,164 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:46:10,164 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-12 20:46:10,164 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:46:10,165 INFO L286 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-12 20:46:10,192 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-12 20:46:10,222 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-11-12 20:46:10,224 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-11-12 20:46:10,224 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2018-11-12 20:46:10,224 INFO L256 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-11-12 20:46:10,229 INFO L459 AbstractCegarLoop]: Interpolant automaton has 2 states [2018-11-12 20:46:10,245 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2018-11-12 20:46:10,245 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2018-11-12 20:46:10,248 INFO L87 Difference]: Start difference. First operand 21 states. Second operand 2 states. [2018-11-12 20:46:10,269 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-12 20:46:10,269 INFO L93 Difference]: Finished difference Result 33 states and 37 transitions. [2018-11-12 20:46:10,269 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2018-11-12 20:46:10,271 INFO L78 Accepts]: Start accepts. Automaton has 2 states. Word has length 10 [2018-11-12 20:46:10,271 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-12 20:46:10,280 INFO L225 Difference]: With dead ends: 33 [2018-11-12 20:46:10,281 INFO L226 Difference]: Without dead ends: 14 [2018-11-12 20:46:10,285 INFO L604 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-11-12 20:46:10,303 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 14 states. [2018-11-12 20:46:10,320 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 14 to 14. [2018-11-12 20:46:10,321 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 14 states. [2018-11-12 20:46:10,322 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 14 states to 14 states and 15 transitions. [2018-11-12 20:46:10,324 INFO L78 Accepts]: Start accepts. Automaton has 14 states and 15 transitions. Word has length 10 [2018-11-12 20:46:10,324 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-12 20:46:10,325 INFO L480 AbstractCegarLoop]: Abstraction has 14 states and 15 transitions. [2018-11-12 20:46:10,325 INFO L481 AbstractCegarLoop]: Interpolant automaton has 2 states. [2018-11-12 20:46:10,325 INFO L276 IsEmpty]: Start isEmpty. Operand 14 states and 15 transitions. [2018-11-12 20:46:10,326 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2018-11-12 20:46:10,326 INFO L367 BasicCegarLoop]: Found error trace [2018-11-12 20:46:10,326 INFO L375 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-12 20:46:10,326 INFO L423 AbstractCegarLoop]: === Iteration 2 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-12 20:46:10,327 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-12 20:46:10,327 INFO L82 PathProgramCache]: Analyzing trace with hash 1715940768, now seen corresponding path program 1 times [2018-11-12 20:46:10,327 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-12 20:46:10,329 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:46:10,329 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-12 20:46:10,329 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:46:10,329 INFO L286 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-12 20:46:10,361 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-12 20:46:10,532 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-11-12 20:46:10,532 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-11-12 20:46:10,533 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2018-11-12 20:46:10,533 INFO L256 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-11-12 20:46:10,534 INFO L459 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-11-12 20:46:10,535 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-11-12 20:46:10,535 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2018-11-12 20:46:10,535 INFO L87 Difference]: Start difference. First operand 14 states and 15 transitions. Second operand 5 states. [2018-11-12 20:46:10,621 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-12 20:46:10,621 INFO L93 Difference]: Finished difference Result 27 states and 31 transitions. [2018-11-12 20:46:10,622 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-11-12 20:46:10,622 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 11 [2018-11-12 20:46:10,622 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-12 20:46:10,623 INFO L225 Difference]: With dead ends: 27 [2018-11-12 20:46:10,623 INFO L226 Difference]: Without dead ends: 18 [2018-11-12 20:46:10,625 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2018-11-12 20:46:10,626 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 18 states. [2018-11-12 20:46:10,632 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 18 to 17. [2018-11-12 20:46:10,632 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 17 states. [2018-11-12 20:46:10,633 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 17 states to 17 states and 18 transitions. [2018-11-12 20:46:10,634 INFO L78 Accepts]: Start accepts. Automaton has 17 states and 18 transitions. Word has length 11 [2018-11-12 20:46:10,634 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-12 20:46:10,635 INFO L480 AbstractCegarLoop]: Abstraction has 17 states and 18 transitions. [2018-11-12 20:46:10,635 INFO L481 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-11-12 20:46:10,635 INFO L276 IsEmpty]: Start isEmpty. Operand 17 states and 18 transitions. [2018-11-12 20:46:10,636 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2018-11-12 20:46:10,636 INFO L367 BasicCegarLoop]: Found error trace [2018-11-12 20:46:10,636 INFO L375 BasicCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-12 20:46:10,636 INFO L423 AbstractCegarLoop]: === Iteration 3 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-12 20:46:10,637 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-12 20:46:10,637 INFO L82 PathProgramCache]: Analyzing trace with hash 1048902920, now seen corresponding path program 1 times [2018-11-12 20:46:10,637 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-12 20:46:10,638 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:46:10,638 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-12 20:46:10,640 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:46:10,640 INFO L286 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-12 20:46:10,671 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-12 20:46:10,893 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-11-12 20:46:10,894 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:46:10,894 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-12 20:46:10,896 INFO L200 CegarAbsIntRunner]: Running AI on error trace of length 16 with the following transitions: [2018-11-12 20:46:10,899 INFO L202 CegarAbsIntRunner]: [0], [4], [8], [12], [14], [19], [21], [28], [31], [33], [39], [40], [41], [43] [2018-11-12 20:46:10,946 INFO L148 AbstractInterpreter]: Using domain PoormanAbstractDomain with backing domain CompoundDomain [CongruenceDomain, IntervalDomain] [2018-11-12 20:46:10,946 INFO L101 FixpointEngine]: Starting fixpoint engine with domain PoormanAbstractDomain (maxUnwinding=3, maxParallelStates=2) [2018-11-12 20:46:11,105 WARN L79 EvaluatorLogger]: Possible loss of precision. Operator ARITHMOD has no precise implementation. [2018-11-12 20:46:11,359 INFO L263 AbstractInterpreter]: Some error location(s) were reachable [2018-11-12 20:46:11,361 INFO L272 AbstractInterpreter]: Visited 14 different actions 78 times. Merged at 5 different actions 38 times. Widened at 1 different actions 4 times. Performed 168 root evaluator evaluations with a maximum evaluation depth of 6. Performed 168 inverse root evaluator evaluations with a maximum inverse evaluation depth of 6. Found 1 fixpoints after 1 different actions. Largest state had 4 variables. [2018-11-12 20:46:11,394 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-12 20:46:11,395 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: Unknown [2018-11-12 20:46:11,395 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:46:11,396 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-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-11-12 20:46:11,410 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-12 20:46:11,410 INFO L286 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-11-12 20:46:11,424 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-12 20:46:11,432 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-12 20:46:11,565 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-11-12 20:46:11,565 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-12 20:46:11,650 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-11-12 20:46:11,670 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-12 20:46:11,671 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 4, 4] total 9 [2018-11-12 20:46:11,671 INFO L249 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-12 20:46:11,671 INFO L459 AbstractCegarLoop]: Interpolant automaton has 7 states [2018-11-12 20:46:11,671 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2018-11-12 20:46:11,673 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=46, Unknown=0, NotChecked=0, Total=72 [2018-11-12 20:46:11,673 INFO L87 Difference]: Start difference. First operand 17 states and 18 transitions. Second operand 7 states. [2018-11-12 20:46:11,858 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-12 20:46:11,858 INFO L93 Difference]: Finished difference Result 31 states and 35 transitions. [2018-11-12 20:46:11,858 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-11-12 20:46:11,859 INFO L78 Accepts]: Start accepts. Automaton has 7 states. Word has length 15 [2018-11-12 20:46:11,859 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-12 20:46:11,860 INFO L225 Difference]: With dead ends: 31 [2018-11-12 20:46:11,860 INFO L226 Difference]: Without dead ends: 22 [2018-11-12 20:46:11,861 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 34 GetRequests, 27 SyntacticMatches, 0 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=26, Invalid=46, Unknown=0, NotChecked=0, Total=72 [2018-11-12 20:46:11,861 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 22 states. [2018-11-12 20:46:11,865 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 22 to 21. [2018-11-12 20:46:11,865 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 21 states. [2018-11-12 20:46:11,866 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 21 states to 21 states and 22 transitions. [2018-11-12 20:46:11,866 INFO L78 Accepts]: Start accepts. Automaton has 21 states and 22 transitions. Word has length 15 [2018-11-12 20:46:11,866 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-12 20:46:11,867 INFO L480 AbstractCegarLoop]: Abstraction has 21 states and 22 transitions. [2018-11-12 20:46:11,867 INFO L481 AbstractCegarLoop]: Interpolant automaton has 7 states. [2018-11-12 20:46:11,867 INFO L276 IsEmpty]: Start isEmpty. Operand 21 states and 22 transitions. [2018-11-12 20:46:11,867 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2018-11-12 20:46:11,868 INFO L367 BasicCegarLoop]: Found error trace [2018-11-12 20:46:11,868 INFO L375 BasicCegarLoop]: trace histogram [3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-12 20:46:11,868 INFO L423 AbstractCegarLoop]: === Iteration 4 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-12 20:46:11,869 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-12 20:46:11,869 INFO L82 PathProgramCache]: Analyzing trace with hash 452778096, now seen corresponding path program 2 times [2018-11-12 20:46:11,869 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-12 20:46:11,870 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:46:11,870 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-12 20:46:11,871 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:46:11,871 INFO L286 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-12 20:46:11,885 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-12 20:46:12,141 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 0 proven. 8 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-11-12 20:46:12,142 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:46:12,142 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-12 20:46:12,142 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-11-12 20:46:12,143 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-11-12 20:46:12,143 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:46:12,143 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-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-11-12 20:46:12,161 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-11-12 20:46:12,162 INFO L286 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST2 (IT: FPandBP) [2018-11-12 20:46:12,186 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 1 check-sat command(s) [2018-11-12 20:46:12,186 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-11-12 20:46:12,189 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-12 20:46:12,535 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2018-11-12 20:46:12,535 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-12 20:46:12,710 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2018-11-12 20:46:12,734 INFO L312 seRefinementStrategy]: Constructing automaton from 2 perfect and 1 imperfect interpolant sequences. [2018-11-12 20:46:12,734 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [6, 6] imperfect sequences [6] total 14 [2018-11-12 20:46:12,734 INFO L256 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-11-12 20:46:12,734 INFO L459 AbstractCegarLoop]: Interpolant automaton has 6 states [2018-11-12 20:46:12,735 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2018-11-12 20:46:12,735 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=29, Invalid=153, Unknown=0, NotChecked=0, Total=182 [2018-11-12 20:46:12,736 INFO L87 Difference]: Start difference. First operand 21 states and 22 transitions. Second operand 6 states. [2018-11-12 20:46:13,170 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-12 20:46:13,170 INFO L93 Difference]: Finished difference Result 30 states and 32 transitions. [2018-11-12 20:46:13,172 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-11-12 20:46:13,173 INFO L78 Accepts]: Start accepts. Automaton has 6 states. Word has length 19 [2018-11-12 20:46:13,173 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-12 20:46:13,174 INFO L225 Difference]: With dead ends: 30 [2018-11-12 20:46:13,174 INFO L226 Difference]: Without dead ends: 25 [2018-11-12 20:46:13,175 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 45 GetRequests, 31 SyntacticMatches, 0 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=41, Invalid=199, Unknown=0, NotChecked=0, Total=240 [2018-11-12 20:46:13,175 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 25 states. [2018-11-12 20:46:13,180 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 25 to 25. [2018-11-12 20:46:13,181 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 25 states. [2018-11-12 20:46:13,182 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 25 states to 25 states and 27 transitions. [2018-11-12 20:46:13,182 INFO L78 Accepts]: Start accepts. Automaton has 25 states and 27 transitions. Word has length 19 [2018-11-12 20:46:13,182 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-12 20:46:13,182 INFO L480 AbstractCegarLoop]: Abstraction has 25 states and 27 transitions. [2018-11-12 20:46:13,183 INFO L481 AbstractCegarLoop]: Interpolant automaton has 6 states. [2018-11-12 20:46:13,183 INFO L276 IsEmpty]: Start isEmpty. Operand 25 states and 27 transitions. [2018-11-12 20:46:13,183 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2018-11-12 20:46:13,184 INFO L367 BasicCegarLoop]: Found error trace [2018-11-12 20:46:13,184 INFO L375 BasicCegarLoop]: trace histogram [4, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-12 20:46:13,184 INFO L423 AbstractCegarLoop]: === Iteration 5 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-12 20:46:13,184 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-12 20:46:13,185 INFO L82 PathProgramCache]: Analyzing trace with hash 671507994, now seen corresponding path program 1 times [2018-11-12 20:46:13,186 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-12 20:46:13,187 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:46:13,187 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-11-12 20:46:13,187 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:46:13,187 INFO L286 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-12 20:46:13,199 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-12 20:46:13,420 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 8 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-11-12 20:46:13,420 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:46:13,421 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-12 20:46:13,421 INFO L200 CegarAbsIntRunner]: Running AI on error trace of length 24 with the following transitions: [2018-11-12 20:46:13,421 INFO L202 CegarAbsIntRunner]: [0], [4], [8], [12], [14], [17], [19], [21], [28], [31], [33], [39], [40], [41], [43] [2018-11-12 20:46:13,423 INFO L148 AbstractInterpreter]: Using domain PoormanAbstractDomain with backing domain CompoundDomain [CongruenceDomain, IntervalDomain] [2018-11-12 20:46:13,423 INFO L101 FixpointEngine]: Starting fixpoint engine with domain PoormanAbstractDomain (maxUnwinding=3, maxParallelStates=2) [2018-11-12 20:46:13,429 WARN L79 EvaluatorLogger]: Possible loss of precision. Operator ARITHMOD has no precise implementation. [2018-11-12 20:46:13,557 INFO L263 AbstractInterpreter]: Some error location(s) were reachable [2018-11-12 20:46:13,557 INFO L272 AbstractInterpreter]: Visited 15 different actions 103 times. Merged at 6 different actions 49 times. Widened at 1 different actions 5 times. Performed 272 root evaluator evaluations with a maximum evaluation depth of 6. Performed 272 inverse root evaluator evaluations with a maximum inverse evaluation depth of 6. Found 9 fixpoints after 3 different actions. Largest state had 5 variables. [2018-11-12 20:46:13,585 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-12 20:46:13,585 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: Unknown [2018-11-12 20:46:13,585 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:46:13,585 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-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-11-12 20:46:13,594 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-12 20:46:13,594 INFO L286 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-11-12 20:46:13,609 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-12 20:46:13,611 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-12 20:46:13,638 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 8 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-11-12 20:46:13,639 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-12 20:46:13,710 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 8 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-11-12 20:46:13,732 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-12 20:46:13,733 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 5, 5] total 9 [2018-11-12 20:46:13,733 INFO L249 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-12 20:46:13,733 INFO L459 AbstractCegarLoop]: Interpolant automaton has 6 states [2018-11-12 20:46:13,734 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2018-11-12 20:46:13,734 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=42, Unknown=0, NotChecked=0, Total=72 [2018-11-12 20:46:13,734 INFO L87 Difference]: Start difference. First operand 25 states and 27 transitions. Second operand 6 states. [2018-11-12 20:46:13,987 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-12 20:46:13,988 INFO L93 Difference]: Finished difference Result 39 states and 43 transitions. [2018-11-12 20:46:13,989 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-11-12 20:46:13,989 INFO L78 Accepts]: Start accepts. Automaton has 6 states. Word has length 23 [2018-11-12 20:46:13,989 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-12 20:46:13,990 INFO L225 Difference]: With dead ends: 39 [2018-11-12 20:46:13,990 INFO L226 Difference]: Without dead ends: 30 [2018-11-12 20:46:13,991 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 52 GetRequests, 43 SyntacticMatches, 2 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=30, Invalid=42, Unknown=0, NotChecked=0, Total=72 [2018-11-12 20:46:13,991 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 30 states. [2018-11-12 20:46:13,995 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 30 to 29. [2018-11-12 20:46:13,996 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 29 states. [2018-11-12 20:46:13,996 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 29 states to 29 states and 31 transitions. [2018-11-12 20:46:13,997 INFO L78 Accepts]: Start accepts. Automaton has 29 states and 31 transitions. Word has length 23 [2018-11-12 20:46:13,997 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-12 20:46:13,997 INFO L480 AbstractCegarLoop]: Abstraction has 29 states and 31 transitions. [2018-11-12 20:46:13,997 INFO L481 AbstractCegarLoop]: Interpolant automaton has 6 states. [2018-11-12 20:46:13,998 INFO L276 IsEmpty]: Start isEmpty. Operand 29 states and 31 transitions. [2018-11-12 20:46:13,998 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2018-11-12 20:46:13,998 INFO L367 BasicCegarLoop]: Found error trace [2018-11-12 20:46:13,999 INFO L375 BasicCegarLoop]: trace histogram [5, 4, 4, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-12 20:46:13,999 INFO L423 AbstractCegarLoop]: === Iteration 6 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-12 20:46:13,999 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-12 20:46:13,999 INFO L82 PathProgramCache]: Analyzing trace with hash 1681938818, now seen corresponding path program 2 times [2018-11-12 20:46:13,999 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-12 20:46:14,000 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:46:14,001 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-12 20:46:14,001 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:46:14,001 INFO L286 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-12 20:46:14,011 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-12 20:46:14,202 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 11 proven. 21 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-11-12 20:46:14,203 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:46:14,203 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-12 20:46:14,203 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-11-12 20:46:14,203 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-11-12 20:46:14,203 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:46:14,203 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-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-11-12 20:46:14,213 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-11-12 20:46:14,213 INFO L286 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST2 (IT: FPandBP) [2018-11-12 20:46:14,225 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 2 check-sat command(s) [2018-11-12 20:46:14,226 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-11-12 20:46:14,228 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-12 20:46:14,397 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 0 proven. 11 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2018-11-12 20:46:14,397 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-12 20:46:14,653 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 0 proven. 11 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2018-11-12 20:46:14,673 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-12 20:46:14,674 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 17 [2018-11-12 20:46:14,674 INFO L249 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-12 20:46:14,674 INFO L459 AbstractCegarLoop]: Interpolant automaton has 12 states [2018-11-12 20:46:14,675 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2018-11-12 20:46:14,675 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=42, Invalid=230, Unknown=0, NotChecked=0, Total=272 [2018-11-12 20:46:14,675 INFO L87 Difference]: Start difference. First operand 29 states and 31 transitions. Second operand 12 states. [2018-11-12 20:46:15,025 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-12 20:46:15,025 INFO L93 Difference]: Finished difference Result 50 states and 56 transitions. [2018-11-12 20:46:15,026 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-11-12 20:46:15,026 INFO L78 Accepts]: Start accepts. Automaton has 12 states. Word has length 27 [2018-11-12 20:46:15,026 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-12 20:46:15,027 INFO L225 Difference]: With dead ends: 50 [2018-11-12 20:46:15,027 INFO L226 Difference]: Without dead ends: 38 [2018-11-12 20:46:15,028 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 67 GetRequests, 45 SyntacticMatches, 1 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 34 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=87, Invalid=419, Unknown=0, NotChecked=0, Total=506 [2018-11-12 20:46:15,029 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 38 states. [2018-11-12 20:46:15,034 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 38 to 37. [2018-11-12 20:46:15,034 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 37 states. [2018-11-12 20:46:15,035 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 37 states to 37 states and 40 transitions. [2018-11-12 20:46:15,036 INFO L78 Accepts]: Start accepts. Automaton has 37 states and 40 transitions. Word has length 27 [2018-11-12 20:46:15,036 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-12 20:46:15,036 INFO L480 AbstractCegarLoop]: Abstraction has 37 states and 40 transitions. [2018-11-12 20:46:15,036 INFO L481 AbstractCegarLoop]: Interpolant automaton has 12 states. [2018-11-12 20:46:15,036 INFO L276 IsEmpty]: Start isEmpty. Operand 37 states and 40 transitions. [2018-11-12 20:46:15,037 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2018-11-12 20:46:15,037 INFO L367 BasicCegarLoop]: Found error trace [2018-11-12 20:46:15,038 INFO L375 BasicCegarLoop]: trace histogram [7, 6, 6, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-12 20:46:15,038 INFO L423 AbstractCegarLoop]: === Iteration 7 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-12 20:46:15,038 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-12 20:46:15,038 INFO L82 PathProgramCache]: Analyzing trace with hash 1459820948, now seen corresponding path program 3 times [2018-11-12 20:46:15,038 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-12 20:46:15,039 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:46:15,039 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-11-12 20:46:15,039 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:46:15,039 INFO L286 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-12 20:46:15,050 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-12 20:46:15,221 INFO L134 CoverageAnalysis]: Checked inductivity of 72 backedges. 17 proven. 55 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-11-12 20:46:15,222 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:46:15,222 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-12 20:46:15,222 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-11-12 20:46:15,222 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-11-12 20:46:15,223 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:46:15,223 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-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-11-12 20:46:15,243 INFO L103 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-11-12 20:46:15,243 INFO L286 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder TERMS_WITH_SMALL_CONSTANTS_FIRST (IT: FPandBP) [2018-11-12 20:46:15,264 INFO L249 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-11-12 20:46:15,265 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-11-12 20:46:15,268 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-12 20:46:15,295 INFO L134 CoverageAnalysis]: Checked inductivity of 72 backedges. 33 proven. 36 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-11-12 20:46:15,296 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-12 20:46:15,529 INFO L134 CoverageAnalysis]: Checked inductivity of 72 backedges. 33 proven. 36 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-11-12 20:46:15,549 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-12 20:46:15,549 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 7, 7] total 14 [2018-11-12 20:46:15,549 INFO L249 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-12 20:46:15,549 INFO L459 AbstractCegarLoop]: Interpolant automaton has 9 states [2018-11-12 20:46:15,550 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2018-11-12 20:46:15,550 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=66, Invalid=116, Unknown=0, NotChecked=0, Total=182 [2018-11-12 20:46:15,550 INFO L87 Difference]: Start difference. First operand 37 states and 40 transitions. Second operand 9 states. [2018-11-12 20:46:15,759 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-12 20:46:15,759 INFO L93 Difference]: Finished difference Result 59 states and 66 transitions. [2018-11-12 20:46:15,761 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-11-12 20:46:15,761 INFO L78 Accepts]: Start accepts. Automaton has 9 states. Word has length 35 [2018-11-12 20:46:15,761 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-12 20:46:15,762 INFO L225 Difference]: With dead ends: 59 [2018-11-12 20:46:15,762 INFO L226 Difference]: Without dead ends: 46 [2018-11-12 20:46:15,763 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 79 GetRequests, 65 SyntacticMatches, 2 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=66, Invalid=116, Unknown=0, NotChecked=0, Total=182 [2018-11-12 20:46:15,763 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 46 states. [2018-11-12 20:46:15,769 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 46 to 45. [2018-11-12 20:46:15,769 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 45 states. [2018-11-12 20:46:15,770 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 45 states to 45 states and 48 transitions. [2018-11-12 20:46:15,770 INFO L78 Accepts]: Start accepts. Automaton has 45 states and 48 transitions. Word has length 35 [2018-11-12 20:46:15,770 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-12 20:46:15,770 INFO L480 AbstractCegarLoop]: Abstraction has 45 states and 48 transitions. [2018-11-12 20:46:15,770 INFO L481 AbstractCegarLoop]: Interpolant automaton has 9 states. [2018-11-12 20:46:15,771 INFO L276 IsEmpty]: Start isEmpty. Operand 45 states and 48 transitions. [2018-11-12 20:46:15,771 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2018-11-12 20:46:15,772 INFO L367 BasicCegarLoop]: Found error trace [2018-11-12 20:46:15,772 INFO L375 BasicCegarLoop]: trace histogram [9, 8, 8, 6, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-12 20:46:15,772 INFO L423 AbstractCegarLoop]: === Iteration 8 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-12 20:46:15,772 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-12 20:46:15,773 INFO L82 PathProgramCache]: Analyzing trace with hash -149334940, now seen corresponding path program 4 times [2018-11-12 20:46:15,773 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-12 20:46:15,774 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:46:15,774 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-11-12 20:46:15,774 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:46:15,774 INFO L286 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-12 20:46:15,787 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-12 20:46:16,061 INFO L134 CoverageAnalysis]: Checked inductivity of 128 backedges. 23 proven. 105 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-11-12 20:46:16,061 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:46:16,061 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-12 20:46:16,062 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-11-12 20:46:16,062 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-11-12 20:46:16,062 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:46:16,062 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-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-11-12 20:46:16,071 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-12 20:46:16,072 INFO L286 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-11-12 20:46:16,084 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-12 20:46:16,087 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-12 20:46:16,113 INFO L134 CoverageAnalysis]: Checked inductivity of 128 backedges. 47 proven. 78 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-11-12 20:46:16,113 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-12 20:46:16,279 INFO L134 CoverageAnalysis]: Checked inductivity of 128 backedges. 47 proven. 78 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-11-12 20:46:16,299 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-12 20:46:16,299 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 9, 9] total 18 [2018-11-12 20:46:16,299 INFO L249 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-12 20:46:16,299 INFO L459 AbstractCegarLoop]: Interpolant automaton has 11 states [2018-11-12 20:46:16,300 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2018-11-12 20:46:16,301 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=104, Invalid=202, Unknown=0, NotChecked=0, Total=306 [2018-11-12 20:46:16,301 INFO L87 Difference]: Start difference. First operand 45 states and 48 transitions. Second operand 11 states. [2018-11-12 20:46:16,633 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-12 20:46:16,633 INFO L93 Difference]: Finished difference Result 67 states and 74 transitions. [2018-11-12 20:46:16,635 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-11-12 20:46:16,635 INFO L78 Accepts]: Start accepts. Automaton has 11 states. Word has length 43 [2018-11-12 20:46:16,636 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-12 20:46:16,637 INFO L225 Difference]: With dead ends: 67 [2018-11-12 20:46:16,637 INFO L226 Difference]: Without dead ends: 54 [2018-11-12 20:46:16,638 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 97 GetRequests, 79 SyntacticMatches, 2 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=104, Invalid=202, Unknown=0, NotChecked=0, Total=306 [2018-11-12 20:46:16,638 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states. [2018-11-12 20:46:16,643 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 53. [2018-11-12 20:46:16,643 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 53 states. [2018-11-12 20:46:16,644 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 53 states to 53 states and 56 transitions. [2018-11-12 20:46:16,645 INFO L78 Accepts]: Start accepts. Automaton has 53 states and 56 transitions. Word has length 43 [2018-11-12 20:46:16,645 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-12 20:46:16,645 INFO L480 AbstractCegarLoop]: Abstraction has 53 states and 56 transitions. [2018-11-12 20:46:16,645 INFO L481 AbstractCegarLoop]: Interpolant automaton has 11 states. [2018-11-12 20:46:16,645 INFO L276 IsEmpty]: Start isEmpty. Operand 53 states and 56 transitions. [2018-11-12 20:46:16,646 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 52 [2018-11-12 20:46:16,646 INFO L367 BasicCegarLoop]: Found error trace [2018-11-12 20:46:16,647 INFO L375 BasicCegarLoop]: trace histogram [11, 10, 10, 8, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-12 20:46:16,647 INFO L423 AbstractCegarLoop]: === Iteration 9 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-12 20:46:16,647 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-12 20:46:16,647 INFO L82 PathProgramCache]: Analyzing trace with hash 435142452, now seen corresponding path program 5 times [2018-11-12 20:46:16,648 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-12 20:46:16,648 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:46:16,649 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-12 20:46:16,649 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:46:16,649 INFO L286 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-12 20:46:16,661 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-12 20:46:16,931 INFO L134 CoverageAnalysis]: Checked inductivity of 200 backedges. 29 proven. 171 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-11-12 20:46:16,932 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:46:16,932 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-12 20:46:16,932 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-11-12 20:46:16,932 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-11-12 20:46:16,932 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:46:16,932 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-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-11-12 20:46:16,941 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-11-12 20:46:16,942 INFO L286 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST2 (IT: FPandBP) [2018-11-12 20:46:16,957 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2018-11-12 20:46:16,957 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-11-12 20:46:16,960 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-12 20:46:17,441 INFO L134 CoverageAnalysis]: Checked inductivity of 200 backedges. 0 proven. 64 refuted. 0 times theorem prover too weak. 136 trivial. 0 not checked. [2018-11-12 20:46:17,441 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-12 20:46:17,898 INFO L134 CoverageAnalysis]: Checked inductivity of 200 backedges. 0 proven. 64 refuted. 0 times theorem prover too weak. 136 trivial. 0 not checked. [2018-11-12 20:46:17,932 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-12 20:46:17,932 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 9, 9] total 27 [2018-11-12 20:46:17,932 INFO L249 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-12 20:46:17,934 INFO L459 AbstractCegarLoop]: Interpolant automaton has 20 states [2018-11-12 20:46:17,934 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2018-11-12 20:46:17,935 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=92, Invalid=610, Unknown=0, NotChecked=0, Total=702 [2018-11-12 20:46:17,935 INFO L87 Difference]: Start difference. First operand 53 states and 56 transitions. Second operand 20 states. [2018-11-12 20:46:19,000 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-12 20:46:19,000 INFO L93 Difference]: Finished difference Result 83 states and 92 transitions. [2018-11-12 20:46:19,001 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2018-11-12 20:46:19,001 INFO L78 Accepts]: Start accepts. Automaton has 20 states. Word has length 51 [2018-11-12 20:46:19,002 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-12 20:46:19,003 INFO L225 Difference]: With dead ends: 83 [2018-11-12 20:46:19,003 INFO L226 Difference]: Without dead ends: 67 [2018-11-12 20:46:19,005 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 127 GetRequests, 89 SyntacticMatches, 1 SemanticMatches, 37 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 123 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=207, Invalid=1275, Unknown=0, NotChecked=0, Total=1482 [2018-11-12 20:46:19,005 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 67 states. [2018-11-12 20:46:19,011 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 67 to 65. [2018-11-12 20:46:19,012 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 65 states. [2018-11-12 20:46:19,013 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 65 states to 65 states and 69 transitions. [2018-11-12 20:46:19,013 INFO L78 Accepts]: Start accepts. Automaton has 65 states and 69 transitions. Word has length 51 [2018-11-12 20:46:19,013 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-12 20:46:19,013 INFO L480 AbstractCegarLoop]: Abstraction has 65 states and 69 transitions. [2018-11-12 20:46:19,013 INFO L481 AbstractCegarLoop]: Interpolant automaton has 20 states. [2018-11-12 20:46:19,014 INFO L276 IsEmpty]: Start isEmpty. Operand 65 states and 69 transitions. [2018-11-12 20:46:19,015 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 64 [2018-11-12 20:46:19,015 INFO L367 BasicCegarLoop]: Found error trace [2018-11-12 20:46:19,015 INFO L375 BasicCegarLoop]: trace histogram [14, 13, 13, 10, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-12 20:46:19,015 INFO L423 AbstractCegarLoop]: === Iteration 10 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-12 20:46:19,015 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-12 20:46:19,016 INFO L82 PathProgramCache]: Analyzing trace with hash -1361248850, now seen corresponding path program 6 times [2018-11-12 20:46:19,016 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-12 20:46:19,017 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:46:19,017 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-11-12 20:46:19,017 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:46:19,017 INFO L286 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-12 20:46:19,029 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-12 20:46:19,319 INFO L134 CoverageAnalysis]: Checked inductivity of 338 backedges. 38 proven. 300 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-11-12 20:46:19,320 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:46:19,320 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-12 20:46:19,320 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-11-12 20:46:19,320 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-11-12 20:46:19,320 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:46:19,321 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-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-11-12 20:46:19,333 INFO L103 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-11-12 20:46:19,333 INFO L286 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder TERMS_WITH_SMALL_CONSTANTS_FIRST (IT: FPandBP) [2018-11-12 20:46:19,350 INFO L249 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-11-12 20:46:19,351 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-11-12 20:46:19,354 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-12 20:46:19,398 INFO L134 CoverageAnalysis]: Checked inductivity of 338 backedges. 118 proven. 210 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-11-12 20:46:19,398 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-12 20:46:21,830 INFO L134 CoverageAnalysis]: Checked inductivity of 338 backedges. 118 proven. 210 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-11-12 20:46:21,852 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-12 20:46:21,852 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 13, 13] total 27 [2018-11-12 20:46:21,852 INFO L249 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-12 20:46:21,852 INFO L459 AbstractCegarLoop]: Interpolant automaton has 16 states [2018-11-12 20:46:21,853 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2018-11-12 20:46:21,853 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=218, Invalid=484, Unknown=0, NotChecked=0, Total=702 [2018-11-12 20:46:21,853 INFO L87 Difference]: Start difference. First operand 65 states and 69 transitions. Second operand 16 states. [2018-11-12 20:46:22,408 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-12 20:46:22,408 INFO L93 Difference]: Finished difference Result 95 states and 105 transitions. [2018-11-12 20:46:22,408 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2018-11-12 20:46:22,409 INFO L78 Accepts]: Start accepts. Automaton has 16 states. Word has length 63 [2018-11-12 20:46:22,409 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-12 20:46:22,410 INFO L225 Difference]: With dead ends: 95 [2018-11-12 20:46:22,410 INFO L226 Difference]: Without dead ends: 78 [2018-11-12 20:46:22,411 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 142 GetRequests, 115 SyntacticMatches, 2 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 2.6s TimeCoverageRelationStatistics Valid=218, Invalid=484, Unknown=0, NotChecked=0, Total=702 [2018-11-12 20:46:22,411 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 78 states. [2018-11-12 20:46:22,418 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 78 to 77. [2018-11-12 20:46:22,418 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 77 states. [2018-11-12 20:46:22,419 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 77 states to 77 states and 81 transitions. [2018-11-12 20:46:22,420 INFO L78 Accepts]: Start accepts. Automaton has 77 states and 81 transitions. Word has length 63 [2018-11-12 20:46:22,420 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-12 20:46:22,420 INFO L480 AbstractCegarLoop]: Abstraction has 77 states and 81 transitions. [2018-11-12 20:46:22,420 INFO L481 AbstractCegarLoop]: Interpolant automaton has 16 states. [2018-11-12 20:46:22,420 INFO L276 IsEmpty]: Start isEmpty. Operand 77 states and 81 transitions. [2018-11-12 20:46:22,421 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 76 [2018-11-12 20:46:22,421 INFO L367 BasicCegarLoop]: Found error trace [2018-11-12 20:46:22,422 INFO L375 BasicCegarLoop]: trace histogram [17, 16, 16, 13, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-12 20:46:22,422 INFO L423 AbstractCegarLoop]: === Iteration 11 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-12 20:46:22,422 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-12 20:46:22,422 INFO L82 PathProgramCache]: Analyzing trace with hash -1880071194, now seen corresponding path program 7 times [2018-11-12 20:46:22,422 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-12 20:46:22,423 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:46:22,423 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-11-12 20:46:22,423 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:46:22,424 INFO L286 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-12 20:46:22,437 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-12 20:46:22,850 INFO L134 CoverageAnalysis]: Checked inductivity of 512 backedges. 47 proven. 465 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-11-12 20:46:22,850 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:46:22,850 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-12 20:46:22,850 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-11-12 20:46:22,851 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-11-12 20:46:22,851 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:46:22,851 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-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-11-12 20:46:22,864 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-12 20:46:22,864 INFO L286 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-11-12 20:46:22,895 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-12 20:46:22,899 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-12 20:46:22,985 INFO L134 CoverageAnalysis]: Checked inductivity of 512 backedges. 151 proven. 351 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-11-12 20:46:22,985 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-12 20:46:23,848 INFO L134 CoverageAnalysis]: Checked inductivity of 512 backedges. 151 proven. 351 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-11-12 20:46:23,869 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-12 20:46:23,870 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 16, 16] total 33 [2018-11-12 20:46:23,870 INFO L249 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-12 20:46:23,870 INFO L459 AbstractCegarLoop]: Interpolant automaton has 19 states [2018-11-12 20:46:23,871 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2018-11-12 20:46:23,871 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=317, Invalid=739, Unknown=0, NotChecked=0, Total=1056 [2018-11-12 20:46:23,872 INFO L87 Difference]: Start difference. First operand 77 states and 81 transitions. Second operand 19 states. [2018-11-12 20:46:24,754 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-12 20:46:24,755 INFO L93 Difference]: Finished difference Result 107 states and 117 transitions. [2018-11-12 20:46:24,755 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2018-11-12 20:46:24,755 INFO L78 Accepts]: Start accepts. Automaton has 19 states. Word has length 75 [2018-11-12 20:46:24,756 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-12 20:46:24,757 INFO L225 Difference]: With dead ends: 107 [2018-11-12 20:46:24,758 INFO L226 Difference]: Without dead ends: 90 [2018-11-12 20:46:24,759 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 169 GetRequests, 136 SyntacticMatches, 2 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=317, Invalid=739, Unknown=0, NotChecked=0, Total=1056 [2018-11-12 20:46:24,759 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 90 states. [2018-11-12 20:46:24,767 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 90 to 89. [2018-11-12 20:46:24,767 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 89 states. [2018-11-12 20:46:24,768 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 89 states to 89 states and 93 transitions. [2018-11-12 20:46:24,769 INFO L78 Accepts]: Start accepts. Automaton has 89 states and 93 transitions. Word has length 75 [2018-11-12 20:46:24,769 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-12 20:46:24,769 INFO L480 AbstractCegarLoop]: Abstraction has 89 states and 93 transitions. [2018-11-12 20:46:24,769 INFO L481 AbstractCegarLoop]: Interpolant automaton has 19 states. [2018-11-12 20:46:24,769 INFO L276 IsEmpty]: Start isEmpty. Operand 89 states and 93 transitions. [2018-11-12 20:46:24,770 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 88 [2018-11-12 20:46:24,771 INFO L367 BasicCegarLoop]: Found error trace [2018-11-12 20:46:24,771 INFO L375 BasicCegarLoop]: trace histogram [20, 19, 19, 16, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-12 20:46:24,771 INFO L423 AbstractCegarLoop]: === Iteration 12 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-12 20:46:24,771 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-12 20:46:24,772 INFO L82 PathProgramCache]: Analyzing trace with hash -842779106, now seen corresponding path program 8 times [2018-11-12 20:46:24,772 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-12 20:46:24,773 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:46:24,773 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-12 20:46:24,773 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:46:24,773 INFO L286 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-12 20:46:24,787 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-12 20:46:25,265 INFO L134 CoverageAnalysis]: Checked inductivity of 722 backedges. 56 proven. 666 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-11-12 20:46:25,266 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:46:25,266 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-12 20:46:25,266 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-11-12 20:46:25,266 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-11-12 20:46:25,266 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:46:25,266 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-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-11-12 20:46:25,275 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-11-12 20:46:25,275 INFO L286 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST2 (IT: FPandBP) [2018-11-12 20:46:25,295 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2018-11-12 20:46:25,295 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-11-12 20:46:25,299 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-12 20:46:25,564 INFO L134 CoverageAnalysis]: Checked inductivity of 722 backedges. 0 proven. 194 refuted. 0 times theorem prover too weak. 528 trivial. 0 not checked. [2018-11-12 20:46:25,564 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-12 20:46:26,007 INFO L134 CoverageAnalysis]: Checked inductivity of 722 backedges. 0 proven. 194 refuted. 0 times theorem prover too weak. 528 trivial. 0 not checked. [2018-11-12 20:46:26,027 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-12 20:46:26,027 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 9, 9] total 36 [2018-11-12 20:46:26,027 INFO L249 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-12 20:46:26,028 INFO L459 AbstractCegarLoop]: Interpolant automaton has 29 states [2018-11-12 20:46:26,028 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 29 interpolants. [2018-11-12 20:46:26,028 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=107, Invalid=1153, Unknown=0, NotChecked=0, Total=1260 [2018-11-12 20:46:26,029 INFO L87 Difference]: Start difference. First operand 89 states and 93 transitions. Second operand 29 states. [2018-11-12 20:46:28,515 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-12 20:46:28,515 INFO L93 Difference]: Finished difference Result 126 states and 138 transitions. [2018-11-12 20:46:28,515 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 28 states. [2018-11-12 20:46:28,515 INFO L78 Accepts]: Start accepts. Automaton has 29 states. Word has length 87 [2018-11-12 20:46:28,516 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-12 20:46:28,517 INFO L225 Difference]: With dead ends: 126 [2018-11-12 20:46:28,517 INFO L226 Difference]: Without dead ends: 106 [2018-11-12 20:46:28,518 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 217 GetRequests, 161 SyntacticMatches, 1 SemanticMatches, 55 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 239 ImplicationChecksByTransitivity, 1.7s TimeCoverageRelationStatistics Valid=312, Invalid=2880, Unknown=0, NotChecked=0, Total=3192 [2018-11-12 20:46:28,518 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 106 states. [2018-11-12 20:46:28,526 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 106 to 105. [2018-11-12 20:46:28,526 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 105 states. [2018-11-12 20:46:28,527 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 105 states to 105 states and 110 transitions. [2018-11-12 20:46:28,528 INFO L78 Accepts]: Start accepts. Automaton has 105 states and 110 transitions. Word has length 87 [2018-11-12 20:46:28,528 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-12 20:46:28,528 INFO L480 AbstractCegarLoop]: Abstraction has 105 states and 110 transitions. [2018-11-12 20:46:28,528 INFO L481 AbstractCegarLoop]: Interpolant automaton has 29 states. [2018-11-12 20:46:28,528 INFO L276 IsEmpty]: Start isEmpty. Operand 105 states and 110 transitions. [2018-11-12 20:46:28,530 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 104 [2018-11-12 20:46:28,530 INFO L367 BasicCegarLoop]: Found error trace [2018-11-12 20:46:28,530 INFO L375 BasicCegarLoop]: trace histogram [24, 23, 23, 19, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-12 20:46:28,531 INFO L423 AbstractCegarLoop]: === Iteration 13 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-12 20:46:28,534 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-12 20:46:28,534 INFO L82 PathProgramCache]: Analyzing trace with hash 2089000704, now seen corresponding path program 9 times [2018-11-12 20:46:28,534 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-12 20:46:28,535 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:46:28,535 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-11-12 20:46:28,535 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:46:28,535 INFO L286 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-12 20:46:28,548 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-12 20:46:29,476 INFO L134 CoverageAnalysis]: Checked inductivity of 1058 backedges. 68 proven. 990 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-11-12 20:46:29,477 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:46:29,477 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-12 20:46:29,477 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-11-12 20:46:29,477 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-11-12 20:46:29,477 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:46:29,477 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-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-11-12 20:46:29,491 INFO L103 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-11-12 20:46:29,491 INFO L286 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder TERMS_WITH_SMALL_CONSTANTS_FIRST (IT: FPandBP) [2018-11-12 20:46:29,537 INFO L249 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-11-12 20:46:29,537 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-11-12 20:46:29,541 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-12 20:46:29,613 INFO L134 CoverageAnalysis]: Checked inductivity of 1058 backedges. 296 proven. 741 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2018-11-12 20:46:29,613 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-12 20:46:30,625 INFO L134 CoverageAnalysis]: Checked inductivity of 1058 backedges. 296 proven. 741 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2018-11-12 20:46:30,644 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-12 20:46:30,645 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [26, 22, 22] total 46 [2018-11-12 20:46:30,645 INFO L249 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-12 20:46:30,645 INFO L459 AbstractCegarLoop]: Interpolant automaton has 26 states [2018-11-12 20:46:30,646 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2018-11-12 20:46:30,647 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=592, Invalid=1478, Unknown=0, NotChecked=0, Total=2070 [2018-11-12 20:46:30,647 INFO L87 Difference]: Start difference. First operand 105 states and 110 transitions. Second operand 26 states. [2018-11-12 20:46:31,693 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-12 20:46:31,694 INFO L93 Difference]: Finished difference Result 143 states and 156 transitions. [2018-11-12 20:46:31,694 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 25 states. [2018-11-12 20:46:31,694 INFO L78 Accepts]: Start accepts. Automaton has 26 states. Word has length 103 [2018-11-12 20:46:31,695 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-12 20:46:31,696 INFO L225 Difference]: With dead ends: 143 [2018-11-12 20:46:31,696 INFO L226 Difference]: Without dead ends: 122 [2018-11-12 20:46:31,698 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 232 GetRequests, 186 SyntacticMatches, 2 SemanticMatches, 44 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 1.8s TimeCoverageRelationStatistics Valid=592, Invalid=1478, Unknown=0, NotChecked=0, Total=2070 [2018-11-12 20:46:31,698 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 122 states. [2018-11-12 20:46:31,704 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 122 to 121. [2018-11-12 20:46:31,704 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 121 states. [2018-11-12 20:46:31,705 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 121 states to 121 states and 126 transitions. [2018-11-12 20:46:31,706 INFO L78 Accepts]: Start accepts. Automaton has 121 states and 126 transitions. Word has length 103 [2018-11-12 20:46:31,706 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-12 20:46:31,706 INFO L480 AbstractCegarLoop]: Abstraction has 121 states and 126 transitions. [2018-11-12 20:46:31,706 INFO L481 AbstractCegarLoop]: Interpolant automaton has 26 states. [2018-11-12 20:46:31,706 INFO L276 IsEmpty]: Start isEmpty. Operand 121 states and 126 transitions. [2018-11-12 20:46:31,708 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 120 [2018-11-12 20:46:31,708 INFO L367 BasicCegarLoop]: Found error trace [2018-11-12 20:46:31,708 INFO L375 BasicCegarLoop]: trace histogram [28, 27, 27, 23, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-12 20:46:31,708 INFO L423 AbstractCegarLoop]: === Iteration 14 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-12 20:46:31,708 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-12 20:46:31,709 INFO L82 PathProgramCache]: Analyzing trace with hash -303598432, now seen corresponding path program 10 times [2018-11-12 20:46:31,709 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-12 20:46:31,709 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:46:31,710 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-11-12 20:46:31,710 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:46:31,710 INFO L286 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-12 20:46:31,724 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-12 20:46:32,392 INFO L134 CoverageAnalysis]: Checked inductivity of 1458 backedges. 80 proven. 1378 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-11-12 20:46:32,393 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:46:32,393 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-12 20:46:32,393 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-11-12 20:46:32,393 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-11-12 20:46:32,393 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:46:32,393 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-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-11-12 20:46:32,402 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-12 20:46:32,403 INFO L286 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-11-12 20:46:32,426 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-12 20:46:32,429 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-12 20:46:32,462 INFO L134 CoverageAnalysis]: Checked inductivity of 1458 backedges. 356 proven. 1081 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2018-11-12 20:46:32,462 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-12 20:46:34,376 INFO L134 CoverageAnalysis]: Checked inductivity of 1458 backedges. 356 proven. 1081 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2018-11-12 20:46:34,403 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-12 20:46:34,404 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [30, 26, 26] total 54 [2018-11-12 20:46:34,404 INFO L249 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-12 20:46:34,404 INFO L459 AbstractCegarLoop]: Interpolant automaton has 30 states [2018-11-12 20:46:34,405 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 30 interpolants. [2018-11-12 20:46:34,406 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=804, Invalid=2058, Unknown=0, NotChecked=0, Total=2862 [2018-11-12 20:46:34,406 INFO L87 Difference]: Start difference. First operand 121 states and 126 transitions. Second operand 30 states. [2018-11-12 20:46:35,923 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-12 20:46:35,924 INFO L93 Difference]: Finished difference Result 159 states and 172 transitions. [2018-11-12 20:46:35,924 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 29 states. [2018-11-12 20:46:35,924 INFO L78 Accepts]: Start accepts. Automaton has 30 states. Word has length 119 [2018-11-12 20:46:35,925 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-12 20:46:35,926 INFO L225 Difference]: With dead ends: 159 [2018-11-12 20:46:35,926 INFO L226 Difference]: Without dead ends: 138 [2018-11-12 20:46:35,927 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 268 GetRequests, 214 SyntacticMatches, 2 SemanticMatches, 52 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 2.4s TimeCoverageRelationStatistics Valid=804, Invalid=2058, Unknown=0, NotChecked=0, Total=2862 [2018-11-12 20:46:35,927 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 138 states. [2018-11-12 20:46:35,934 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 138 to 137. [2018-11-12 20:46:35,934 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 137 states. [2018-11-12 20:46:35,935 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 137 states to 137 states and 142 transitions. [2018-11-12 20:46:35,936 INFO L78 Accepts]: Start accepts. Automaton has 137 states and 142 transitions. Word has length 119 [2018-11-12 20:46:35,936 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-12 20:46:35,936 INFO L480 AbstractCegarLoop]: Abstraction has 137 states and 142 transitions. [2018-11-12 20:46:35,936 INFO L481 AbstractCegarLoop]: Interpolant automaton has 30 states. [2018-11-12 20:46:35,936 INFO L276 IsEmpty]: Start isEmpty. Operand 137 states and 142 transitions. [2018-11-12 20:46:35,938 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 136 [2018-11-12 20:46:35,938 INFO L367 BasicCegarLoop]: Found error trace [2018-11-12 20:46:35,938 INFO L375 BasicCegarLoop]: trace histogram [32, 31, 31, 27, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-12 20:46:35,939 INFO L423 AbstractCegarLoop]: === Iteration 15 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-12 20:46:35,939 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-12 20:46:35,939 INFO L82 PathProgramCache]: Analyzing trace with hash -114554304, now seen corresponding path program 11 times [2018-11-12 20:46:35,939 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-12 20:46:35,940 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:46:35,940 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-12 20:46:35,940 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:46:35,940 INFO L286 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-12 20:46:35,955 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-12 20:46:37,734 INFO L134 CoverageAnalysis]: Checked inductivity of 1922 backedges. 92 proven. 1830 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-11-12 20:46:37,734 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:46:37,734 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-12 20:46:37,734 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-11-12 20:46:37,734 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-11-12 20:46:37,735 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:46:37,735 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-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-11-12 20:46:37,745 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-11-12 20:46:37,745 INFO L286 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST2 (IT: FPandBP) [2018-11-12 20:47:09,311 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 7 check-sat command(s) [2018-11-12 20:47:09,312 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-11-12 20:47:09,667 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-12 20:47:10,765 INFO L134 CoverageAnalysis]: Checked inductivity of 1922 backedges. 0 proven. 437 refuted. 0 times theorem prover too weak. 1485 trivial. 0 not checked. [2018-11-12 20:47:10,765 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-12 20:47:20,904 INFO L134 CoverageAnalysis]: Checked inductivity of 1922 backedges. 0 proven. 437 refuted. 0 times theorem prover too weak. 1485 trivial. 0 not checked. [2018-11-12 20:47:20,924 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-12 20:47:20,924 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [34, 12, 12] total 54 [2018-11-12 20:47:20,925 INFO L249 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-12 20:47:20,925 INFO L459 AbstractCegarLoop]: Interpolant automaton has 44 states [2018-11-12 20:47:20,925 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 44 interpolants. [2018-11-12 20:47:20,926 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=225, Invalid=2635, Unknown=2, NotChecked=0, Total=2862 [2018-11-12 20:47:20,927 INFO L87 Difference]: Start difference. First operand 137 states and 142 transitions. Second operand 44 states. [2018-11-12 20:47:24,958 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-12 20:47:24,958 INFO L93 Difference]: Finished difference Result 183 states and 198 transitions. [2018-11-12 20:47:24,958 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 44 states. [2018-11-12 20:47:24,959 INFO L78 Accepts]: Start accepts. Automaton has 44 states. Word has length 135 [2018-11-12 20:47:24,959 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-12 20:47:24,960 INFO L225 Difference]: With dead ends: 183 [2018-11-12 20:47:24,960 INFO L226 Difference]: Without dead ends: 159 [2018-11-12 20:47:24,964 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 338 GetRequests, 251 SyntacticMatches, 1 SemanticMatches, 86 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 672 ImplicationChecksByTransitivity, 13.7s TimeCoverageRelationStatistics Valid=657, Invalid=6997, Unknown=2, NotChecked=0, Total=7656 [2018-11-12 20:47:24,965 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 159 states. [2018-11-12 20:47:24,972 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 159 to 157. [2018-11-12 20:47:24,972 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 157 states. [2018-11-12 20:47:24,973 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 157 states to 157 states and 162 transitions. [2018-11-12 20:47:24,973 INFO L78 Accepts]: Start accepts. Automaton has 157 states and 162 transitions. Word has length 135 [2018-11-12 20:47:24,974 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-12 20:47:24,974 INFO L480 AbstractCegarLoop]: Abstraction has 157 states and 162 transitions. [2018-11-12 20:47:24,974 INFO L481 AbstractCegarLoop]: Interpolant automaton has 44 states. [2018-11-12 20:47:24,974 INFO L276 IsEmpty]: Start isEmpty. Operand 157 states and 162 transitions. [2018-11-12 20:47:24,976 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 156 [2018-11-12 20:47:24,976 INFO L367 BasicCegarLoop]: Found error trace [2018-11-12 20:47:24,976 INFO L375 BasicCegarLoop]: trace histogram [37, 36, 36, 31, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-12 20:47:24,976 INFO L423 AbstractCegarLoop]: === Iteration 16 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-12 20:47:24,977 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-12 20:47:24,977 INFO L82 PathProgramCache]: Analyzing trace with hash -1133922934, now seen corresponding path program 12 times [2018-11-12 20:47:24,977 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-12 20:47:24,977 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:47:24,978 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-11-12 20:47:24,978 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:47:24,978 INFO L286 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-12 20:47:24,995 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-12 20:47:25,892 INFO L134 CoverageAnalysis]: Checked inductivity of 2592 backedges. 107 proven. 2485 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-11-12 20:47:25,893 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:47:25,893 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-12 20:47:25,893 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-11-12 20:47:25,893 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-11-12 20:47:25,893 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:47:25,893 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-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-11-12 20:47:25,903 INFO L103 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-11-12 20:47:25,903 INFO L286 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder TERMS_WITH_SMALL_CONSTANTS_FIRST (IT: FPandBP) [2018-11-12 20:47:25,945 INFO L249 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-11-12 20:47:25,945 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-11-12 20:47:25,949 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-12 20:47:25,994 INFO L134 CoverageAnalysis]: Checked inductivity of 2592 backedges. 603 proven. 1953 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2018-11-12 20:47:25,995 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-12 20:47:28,491 INFO L134 CoverageAnalysis]: Checked inductivity of 2592 backedges. 603 proven. 1953 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2018-11-12 20:47:28,512 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-12 20:47:28,512 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [39, 34, 34] total 71 [2018-11-12 20:47:28,512 INFO L249 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-12 20:47:28,513 INFO L459 AbstractCegarLoop]: Interpolant automaton has 39 states [2018-11-12 20:47:28,513 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 39 interpolants. [2018-11-12 20:47:28,515 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1359, Invalid=3611, Unknown=0, NotChecked=0, Total=4970 [2018-11-12 20:47:28,515 INFO L87 Difference]: Start difference. First operand 157 states and 162 transitions. Second operand 39 states. [2018-11-12 20:47:31,224 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-12 20:47:31,225 INFO L93 Difference]: Finished difference Result 203 states and 217 transitions. [2018-11-12 20:47:31,225 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 38 states. [2018-11-12 20:47:31,225 INFO L78 Accepts]: Start accepts. Automaton has 39 states. Word has length 155 [2018-11-12 20:47:31,226 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-12 20:47:31,227 INFO L225 Difference]: With dead ends: 203 [2018-11-12 20:47:31,227 INFO L226 Difference]: Without dead ends: 178 [2018-11-12 20:47:31,230 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 349 GetRequests, 278 SyntacticMatches, 2 SemanticMatches, 69 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 3.2s TimeCoverageRelationStatistics Valid=1359, Invalid=3611, Unknown=0, NotChecked=0, Total=4970 [2018-11-12 20:47:31,230 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 178 states. [2018-11-12 20:47:31,235 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 178 to 177. [2018-11-12 20:47:31,236 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 177 states. [2018-11-12 20:47:31,237 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 177 states to 177 states and 182 transitions. [2018-11-12 20:47:31,237 INFO L78 Accepts]: Start accepts. Automaton has 177 states and 182 transitions. Word has length 155 [2018-11-12 20:47:31,237 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-12 20:47:31,237 INFO L480 AbstractCegarLoop]: Abstraction has 177 states and 182 transitions. [2018-11-12 20:47:31,238 INFO L481 AbstractCegarLoop]: Interpolant automaton has 39 states. [2018-11-12 20:47:31,238 INFO L276 IsEmpty]: Start isEmpty. Operand 177 states and 182 transitions. [2018-11-12 20:47:31,240 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 176 [2018-11-12 20:47:31,240 INFO L367 BasicCegarLoop]: Found error trace [2018-11-12 20:47:31,240 INFO L375 BasicCegarLoop]: trace histogram [42, 41, 41, 36, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-12 20:47:31,240 INFO L423 AbstractCegarLoop]: === Iteration 17 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-12 20:47:31,240 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-12 20:47:31,240 INFO L82 PathProgramCache]: Analyzing trace with hash -718034286, now seen corresponding path program 13 times [2018-11-12 20:47:31,241 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-12 20:47:31,241 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:47:31,241 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-11-12 20:47:31,242 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:47:31,242 INFO L286 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-12 20:47:31,260 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-12 20:47:32,639 INFO L134 CoverageAnalysis]: Checked inductivity of 3362 backedges. 122 proven. 3240 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-11-12 20:47:32,640 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:47:32,640 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-12 20:47:32,640 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-11-12 20:47:32,640 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-11-12 20:47:32,640 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:47:32,640 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-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-11-12 20:47:32,648 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-12 20:47:32,649 INFO L286 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-11-12 20:47:32,685 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-12 20:47:32,688 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-12 20:47:32,764 INFO L134 CoverageAnalysis]: Checked inductivity of 3362 backedges. 698 proven. 2628 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2018-11-12 20:47:32,764 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-12 20:47:35,974 INFO L134 CoverageAnalysis]: Checked inductivity of 3362 backedges. 698 proven. 2628 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2018-11-12 20:47:35,993 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-12 20:47:35,994 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [44, 39, 39] total 81 [2018-11-12 20:47:35,994 INFO L249 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-12 20:47:35,994 INFO L459 AbstractCegarLoop]: Interpolant automaton has 44 states [2018-11-12 20:47:35,995 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 44 interpolants. [2018-11-12 20:47:35,996 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1754, Invalid=4726, Unknown=0, NotChecked=0, Total=6480 [2018-11-12 20:47:35,996 INFO L87 Difference]: Start difference. First operand 177 states and 182 transitions. Second operand 44 states. [2018-11-12 20:47:39,306 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-12 20:47:39,306 INFO L93 Difference]: Finished difference Result 223 states and 237 transitions. [2018-11-12 20:47:39,313 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 43 states. [2018-11-12 20:47:39,313 INFO L78 Accepts]: Start accepts. Automaton has 44 states. Word has length 175 [2018-11-12 20:47:39,314 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-12 20:47:39,315 INFO L225 Difference]: With dead ends: 223 [2018-11-12 20:47:39,315 INFO L226 Difference]: Without dead ends: 198 [2018-11-12 20:47:39,317 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 394 GetRequests, 313 SyntacticMatches, 2 SemanticMatches, 79 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 4.3s TimeCoverageRelationStatistics Valid=1754, Invalid=4726, Unknown=0, NotChecked=0, Total=6480 [2018-11-12 20:47:39,318 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 198 states. [2018-11-12 20:47:39,324 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 198 to 197. [2018-11-12 20:47:39,324 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 197 states. [2018-11-12 20:47:39,326 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 197 states to 197 states and 202 transitions. [2018-11-12 20:47:39,326 INFO L78 Accepts]: Start accepts. Automaton has 197 states and 202 transitions. Word has length 175 [2018-11-12 20:47:39,327 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-12 20:47:39,327 INFO L480 AbstractCegarLoop]: Abstraction has 197 states and 202 transitions. [2018-11-12 20:47:39,327 INFO L481 AbstractCegarLoop]: Interpolant automaton has 44 states. [2018-11-12 20:47:39,327 INFO L276 IsEmpty]: Start isEmpty. Operand 197 states and 202 transitions. [2018-11-12 20:47:39,329 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 196 [2018-11-12 20:47:39,329 INFO L367 BasicCegarLoop]: Found error trace [2018-11-12 20:47:39,330 INFO L375 BasicCegarLoop]: trace histogram [47, 46, 46, 41, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-12 20:47:39,330 INFO L423 AbstractCegarLoop]: === Iteration 18 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-12 20:47:39,330 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-12 20:47:39,330 INFO L82 PathProgramCache]: Analyzing trace with hash 2000210842, now seen corresponding path program 14 times [2018-11-12 20:47:39,330 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-12 20:47:39,331 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:47:39,331 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-12 20:47:39,331 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:47:39,331 INFO L286 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-12 20:47:39,356 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-12 20:47:41,070 INFO L134 CoverageAnalysis]: Checked inductivity of 4232 backedges. 137 proven. 4095 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-11-12 20:47:41,070 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:47:41,070 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-12 20:47:41,070 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-11-12 20:47:41,070 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-11-12 20:47:41,070 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:47:41,070 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-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-11-12 20:47:41,078 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-11-12 20:47:41,079 INFO L286 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST2 (IT: FPandBP) [2018-11-12 20:48:14,869 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 7 check-sat command(s) [2018-11-12 20:48:14,869 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-11-12 20:48:14,982 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-12 20:48:15,466 INFO L134 CoverageAnalysis]: Checked inductivity of 4232 backedges. 0 proven. 829 refuted. 0 times theorem prover too weak. 3403 trivial. 0 not checked. [2018-11-12 20:48:15,466 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-12 20:48:17,896 INFO L134 CoverageAnalysis]: Checked inductivity of 4232 backedges. 0 proven. 829 refuted. 0 times theorem prover too weak. 3403 trivial. 0 not checked. [2018-11-12 20:48:17,917 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-12 20:48:17,918 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [49, 11, 11] total 67 [2018-11-12 20:48:17,918 INFO L249 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-12 20:48:17,918 INFO L459 AbstractCegarLoop]: Interpolant automaton has 58 states [2018-11-12 20:48:17,919 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 58 interpolants. [2018-11-12 20:48:17,920 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=216, Invalid=4206, Unknown=0, NotChecked=0, Total=4422 [2018-11-12 20:48:17,920 INFO L87 Difference]: Start difference. First operand 197 states and 202 transitions. Second operand 58 states. [2018-11-12 20:48:25,007 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-12 20:48:25,007 INFO L93 Difference]: Finished difference Result 250 states and 266 transitions. [2018-11-12 20:48:25,008 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 57 states. [2018-11-12 20:48:25,008 INFO L78 Accepts]: Start accepts. Automaton has 58 states. Word has length 195 [2018-11-12 20:48:25,008 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-12 20:48:25,010 INFO L225 Difference]: With dead ends: 250 [2018-11-12 20:48:25,010 INFO L226 Difference]: Without dead ends: 222 [2018-11-12 20:48:25,013 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 487 GetRequests, 373 SyntacticMatches, 1 SemanticMatches, 113 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1167 ImplicationChecksByTransitivity, 5.6s TimeCoverageRelationStatistics Valid=785, Invalid=12325, Unknown=0, NotChecked=0, Total=13110 [2018-11-12 20:48:25,013 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 222 states. [2018-11-12 20:48:25,020 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 222 to 221. [2018-11-12 20:48:25,020 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 221 states. [2018-11-12 20:48:25,021 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 221 states to 221 states and 227 transitions. [2018-11-12 20:48:25,021 INFO L78 Accepts]: Start accepts. Automaton has 221 states and 227 transitions. Word has length 195 [2018-11-12 20:48:25,021 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-12 20:48:25,022 INFO L480 AbstractCegarLoop]: Abstraction has 221 states and 227 transitions. [2018-11-12 20:48:25,022 INFO L481 AbstractCegarLoop]: Interpolant automaton has 58 states. [2018-11-12 20:48:25,022 INFO L276 IsEmpty]: Start isEmpty. Operand 221 states and 227 transitions. [2018-11-12 20:48:25,023 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 220 [2018-11-12 20:48:25,023 INFO L367 BasicCegarLoop]: Found error trace [2018-11-12 20:48:25,023 INFO L375 BasicCegarLoop]: trace histogram [53, 52, 52, 46, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-12 20:48:25,023 INFO L423 AbstractCegarLoop]: === Iteration 19 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-12 20:48:25,024 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-12 20:48:25,024 INFO L82 PathProgramCache]: Analyzing trace with hash -808108724, now seen corresponding path program 15 times [2018-11-12 20:48:25,024 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-12 20:48:25,025 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:48:25,025 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-11-12 20:48:25,025 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:48:25,025 INFO L286 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-12 20:48:25,056 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-12 20:48:27,255 INFO L134 CoverageAnalysis]: Checked inductivity of 5408 backedges. 155 proven. 5253 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-11-12 20:48:27,255 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:48:27,255 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-12 20:48:27,255 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-11-12 20:48:27,255 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-11-12 20:48:27,256 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:48:27,256 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-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-11-12 20:48:27,264 INFO L103 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-11-12 20:48:27,264 INFO L286 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder TERMS_WITH_SMALL_CONSTANTS_FIRST (IT: FPandBP) [2018-11-12 20:48:27,307 INFO L249 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-11-12 20:48:27,308 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-11-12 20:48:27,312 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-12 20:48:27,427 INFO L134 CoverageAnalysis]: Checked inductivity of 5408 backedges. 1075 proven. 4278 refuted. 0 times theorem prover too weak. 55 trivial. 0 not checked. [2018-11-12 20:48:27,428 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-12 20:48:33,587 INFO L134 CoverageAnalysis]: Checked inductivity of 5408 backedges. 1075 proven. 4278 refuted. 0 times theorem prover too weak. 55 trivial. 0 not checked. [2018-11-12 20:48:33,607 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-12 20:48:33,607 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [55, 49, 49] total 102 [2018-11-12 20:48:33,607 INFO L249 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-12 20:48:33,608 INFO L459 AbstractCegarLoop]: Interpolant automaton has 55 states [2018-11-12 20:48:33,608 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 55 interpolants. [2018-11-12 20:48:33,609 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=2744, Invalid=7558, Unknown=0, NotChecked=0, Total=10302 [2018-11-12 20:48:33,609 INFO L87 Difference]: Start difference. First operand 221 states and 227 transitions. Second operand 55 states. [2018-11-12 20:48:38,811 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-12 20:48:38,811 INFO L93 Difference]: Finished difference Result 275 states and 292 transitions. [2018-11-12 20:48:38,812 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 54 states. [2018-11-12 20:48:38,812 INFO L78 Accepts]: Start accepts. Automaton has 55 states. Word has length 219 [2018-11-12 20:48:38,813 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-12 20:48:38,815 INFO L225 Difference]: With dead ends: 275 [2018-11-12 20:48:38,815 INFO L226 Difference]: Without dead ends: 246 [2018-11-12 20:48:38,817 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 493 GetRequests, 391 SyntacticMatches, 2 SemanticMatches, 100 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 8.1s TimeCoverageRelationStatistics Valid=2744, Invalid=7558, Unknown=0, NotChecked=0, Total=10302 [2018-11-12 20:48:38,817 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 246 states. [2018-11-12 20:48:38,823 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 246 to 245. [2018-11-12 20:48:38,824 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 245 states. [2018-11-12 20:48:38,825 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 245 states to 245 states and 251 transitions. [2018-11-12 20:48:38,825 INFO L78 Accepts]: Start accepts. Automaton has 245 states and 251 transitions. Word has length 219 [2018-11-12 20:48:38,825 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-12 20:48:38,825 INFO L480 AbstractCegarLoop]: Abstraction has 245 states and 251 transitions. [2018-11-12 20:48:38,826 INFO L481 AbstractCegarLoop]: Interpolant automaton has 55 states. [2018-11-12 20:48:38,826 INFO L276 IsEmpty]: Start isEmpty. Operand 245 states and 251 transitions. [2018-11-12 20:48:38,827 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 244 [2018-11-12 20:48:38,827 INFO L367 BasicCegarLoop]: Found error trace [2018-11-12 20:48:38,827 INFO L375 BasicCegarLoop]: trace histogram [59, 58, 58, 52, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-12 20:48:38,827 INFO L423 AbstractCegarLoop]: === Iteration 20 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-12 20:48:38,828 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-12 20:48:38,828 INFO L82 PathProgramCache]: Analyzing trace with hash -1414173252, now seen corresponding path program 16 times [2018-11-12 20:48:38,828 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-12 20:48:38,828 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:48:38,829 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-11-12 20:48:38,829 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:48:38,829 INFO L286 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-12 20:48:38,858 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-12 20:48:40,968 INFO L134 CoverageAnalysis]: Checked inductivity of 6728 backedges. 173 proven. 6555 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-11-12 20:48:40,968 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:48:40,968 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-12 20:48:40,968 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-11-12 20:48:40,968 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-11-12 20:48:40,968 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:48:40,969 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-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-11-12 20:48:40,980 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-12 20:48:40,980 INFO L286 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-11-12 20:48:41,032 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-12 20:48:41,036 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-12 20:48:41,173 INFO L134 CoverageAnalysis]: Checked inductivity of 6728 backedges. 1213 proven. 5460 refuted. 0 times theorem prover too weak. 55 trivial. 0 not checked. [2018-11-12 20:48:41,173 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-12 20:48:47,559 INFO L134 CoverageAnalysis]: Checked inductivity of 6728 backedges. 1213 proven. 5460 refuted. 0 times theorem prover too weak. 55 trivial. 0 not checked. [2018-11-12 20:48:47,579 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-12 20:48:47,580 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [61, 55, 55] total 114 [2018-11-12 20:48:47,580 INFO L249 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-12 20:48:47,580 INFO L459 AbstractCegarLoop]: Interpolant automaton has 61 states [2018-11-12 20:48:47,581 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 61 interpolants. [2018-11-12 20:48:47,582 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=3410, Invalid=9472, Unknown=0, NotChecked=0, Total=12882 [2018-11-12 20:48:47,582 INFO L87 Difference]: Start difference. First operand 245 states and 251 transitions. Second operand 61 states. [2018-11-12 20:48:53,582 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-12 20:48:53,583 INFO L93 Difference]: Finished difference Result 299 states and 316 transitions. [2018-11-12 20:48:53,583 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 60 states. [2018-11-12 20:48:53,583 INFO L78 Accepts]: Start accepts. Automaton has 61 states. Word has length 243 [2018-11-12 20:48:53,584 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-12 20:48:53,586 INFO L225 Difference]: With dead ends: 299 [2018-11-12 20:48:53,586 INFO L226 Difference]: Without dead ends: 270 [2018-11-12 20:48:53,587 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 547 GetRequests, 433 SyntacticMatches, 2 SemanticMatches, 112 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 8.2s TimeCoverageRelationStatistics Valid=3410, Invalid=9472, Unknown=0, NotChecked=0, Total=12882 [2018-11-12 20:48:53,587 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 270 states. [2018-11-12 20:48:53,595 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 270 to 269. [2018-11-12 20:48:53,595 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 269 states. [2018-11-12 20:48:53,596 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 269 states to 269 states and 275 transitions. [2018-11-12 20:48:53,596 INFO L78 Accepts]: Start accepts. Automaton has 269 states and 275 transitions. Word has length 243 [2018-11-12 20:48:53,597 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-12 20:48:53,597 INFO L480 AbstractCegarLoop]: Abstraction has 269 states and 275 transitions. [2018-11-12 20:48:53,597 INFO L481 AbstractCegarLoop]: Interpolant automaton has 61 states. [2018-11-12 20:48:53,597 INFO L276 IsEmpty]: Start isEmpty. Operand 269 states and 275 transitions. [2018-11-12 20:48:53,599 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 268 [2018-11-12 20:48:53,599 INFO L367 BasicCegarLoop]: Found error trace [2018-11-12 20:48:53,599 INFO L375 BasicCegarLoop]: trace histogram [65, 64, 64, 58, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-12 20:48:53,599 INFO L423 AbstractCegarLoop]: === Iteration 21 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-12 20:48:53,599 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-12 20:48:53,599 INFO L82 PathProgramCache]: Analyzing trace with hash -886616532, now seen corresponding path program 17 times [2018-11-12 20:48:53,600 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-12 20:48:53,600 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:48:53,600 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-12 20:48:53,600 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:48:53,601 INFO L286 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-12 20:48:53,631 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-12 20:48:57,099 INFO L134 CoverageAnalysis]: Checked inductivity of 8192 backedges. 191 proven. 8001 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-11-12 20:48:57,099 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:48:57,099 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-12 20:48:57,100 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-11-12 20:48:57,100 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-11-12 20:48:57,100 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:48:57,100 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-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-11-12 20:48:57,108 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-11-12 20:48:57,109 INFO L286 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST2 (IT: FPandBP) [2018-11-12 20:49:38,000 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 9 check-sat command(s) [2018-11-12 20:49:38,000 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-11-12 20:49:38,840 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-12 20:49:45,358 INFO L134 CoverageAnalysis]: Checked inductivity of 8192 backedges. 0 proven. 1406 refuted. 0 times theorem prover too weak. 6786 trivial. 0 not checked. [2018-11-12 20:49:45,359 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-12 20:50:05,322 WARN L179 SmtUtils]: Spent 397.00 ms on a formula simplification that was a NOOP. DAG size: 22 Received shutdown request... [2018-11-12 20:50:36,339 INFO L177 TraceCheckSpWp]: Timeout while computing interpolants [2018-11-12 20:50:36,540 WARN L521 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 20 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-11-12 20:50:36,540 WARN L549 AbstractCegarLoop]: Verification canceled [2018-11-12 20:50:36,546 WARN L205 ceAbstractionStarter]: Timeout [2018-11-12 20:50:36,546 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 12.11 08:50:36 BoogieIcfgContainer [2018-11-12 20:50:36,546 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2018-11-12 20:50:36,547 INFO L168 Benchmark]: Toolchain (without parser) took 267359.91 ms. Allocated memory was 1.5 GB in the beginning and 2.5 GB in the end (delta: 964.7 MB). Free memory was 1.4 GB in the beginning and 1.6 GB in the end (delta: -194.5 MB). Peak memory consumption was 770.2 MB. Max. memory is 7.1 GB. [2018-11-12 20:50:36,548 INFO L168 Benchmark]: CDTParser took 0.24 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-11-12 20:50:36,548 INFO L168 Benchmark]: CACSL2BoogieTranslator took 333.00 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-11-12 20:50:36,549 INFO L168 Benchmark]: Boogie Procedure Inliner took 21.84 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-11-12 20:50:36,549 INFO L168 Benchmark]: Boogie Preprocessor took 24.62 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-11-12 20:50:36,550 INFO L168 Benchmark]: RCFGBuilder took 358.76 ms. Allocated memory was 1.5 GB in the beginning and 2.2 GB in the end (delta: 726.7 MB). Free memory was 1.4 GB in the beginning and 2.2 GB in the end (delta: -778.9 MB). Peak memory consumption was 26.1 MB. Max. memory is 7.1 GB. [2018-11-12 20:50:36,551 INFO L168 Benchmark]: TraceAbstraction took 266616.52 ms. Allocated memory was 2.2 GB in the beginning and 2.5 GB in the end (delta: 238.0 MB). Free memory was 2.2 GB in the beginning and 1.6 GB in the end (delta: 573.8 MB). Peak memory consumption was 811.8 MB. Max. memory is 7.1 GB. [2018-11-12 20:50:36,554 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.24 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. * CACSL2BoogieTranslator took 333.00 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 21.84 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 24.62 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 358.76 ms. Allocated memory was 1.5 GB in the beginning and 2.2 GB in the end (delta: 726.7 MB). Free memory was 1.4 GB in the beginning and 2.2 GB in the end (delta: -778.9 MB). Peak memory consumption was 26.1 MB. Max. memory is 7.1 GB. * TraceAbstraction took 266616.52 ms. Allocated memory was 2.2 GB in the beginning and 2.5 GB in the end (delta: 238.0 MB). Free memory was 2.2 GB in the beginning and 1.6 GB in the end (delta: 573.8 MB). Peak memory consumption was 811.8 MB. Max. memory is 7.1 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [Line: 2]: Timeout (TraceAbstraction) Unable to prove that call of __VERIFIER_error() unreachable (line 2). Cancelled while BasicCegarLoop was analyzing trace of length 268 with TraceHistMax 65,while TraceCheckSpWp was constructing backward predicates,while PredicateComparison was comparing new predicate (quantified with 0quantifier alternations) to 95 known predicates. - StatisticsResult: Ultimate Automizer benchmark data CFG has 4 procedures, 21 locations, 1 error locations. TIMEOUT Result, 266.5s OverallTime, 21 OverallIterations, 65 TraceHistogramMax, 37.8s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 652 SDtfs, 1221 SDslu, 18311 SDs, 0 SdLazy, 48940 SolverSat, 398 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 27.6s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 4145 GetRequests, 3234 SyntacticMatches, 28 SemanticMatches, 883 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2262 ImplicationChecksByTransitivity, 57.5s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=269occurred in iteration=20, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.6s AbstIntTime, 2 AbstIntIterations, 0 AbstIntStrong, NaN AbsIntWeakeningRatio, NaN AbsIntAvgWeakeningVarsNumRemoved, NaN AbsIntAvgWeakenedConjuncts, 0.0s DumpTime, AutomataMinimizationStatistics: 0.1s AutomataMinimizationTime, 20 MinimizatonAttempts, 20 StatesRemovedByMinimization, 18 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.1s SsaConstructionTime, 66.0s SatisfiabilityAnalysisTime, 57.4s InterpolantComputationTime, 3585 NumberOfCodeBlocks, 3213 NumberOfCodeBlocksAsserted, 62 NumberOfCheckSat, 5311 ConstructedInterpolants, 456 QuantifiedInterpolants, 6048413 SizeOfPredicates, 39 NumberOfNonLiveVariables, 2113 ConjunctsInSsa, 626 ConjunctsInUnsatCore, 56 InterpolantComputations, 4 PerfectInterpolantSequences, 22021/86376 InterpolantCoveringCapability, InvariantSynthesisStatistics: No data available, InterpolantConsolidationStatistics: No data available, ReuseStatistics: No data available RESULT: Ultimate could not prove your program: Timeout Completed graceful shutdown