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.epf -i ../../../trunk/examples/svcomp/loops-crafted-1/Mono6_false-unreach-call1.c -------------------------------------------------------------------------------- This is Ultimate 0.1.23-df4b876 [2018-11-07 05:11:13,744 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-11-07 05:11:13,747 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-11-07 05:11:13,765 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-11-07 05:11:13,765 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-11-07 05:11:13,767 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-11-07 05:11:13,768 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-11-07 05:11:13,770 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-11-07 05:11:13,773 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-11-07 05:11:13,780 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-11-07 05:11:13,782 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-11-07 05:11:13,782 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-11-07 05:11:13,783 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-11-07 05:11:13,784 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-11-07 05:11:13,785 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-11-07 05:11:13,788 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-11-07 05:11:13,789 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-11-07 05:11:13,791 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-11-07 05:11:13,796 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-11-07 05:11:13,801 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-11-07 05:11:13,803 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-11-07 05:11:13,805 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-11-07 05:11:13,808 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-11-07 05:11:13,808 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-11-07 05:11:13,808 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-11-07 05:11:13,809 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-11-07 05:11:13,810 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-11-07 05:11:13,811 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-11-07 05:11:13,813 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-11-07 05:11:13,814 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-11-07 05:11:13,816 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-11-07 05:11:13,817 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-11-07 05:11:13,817 INFO L177 SettingsManager]: ReqParser provides no preferences, ignoring... [2018-11-07 05:11:13,817 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-11-07 05:11:13,820 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-11-07 05:11:13,821 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-11-07 05:11:13,821 INFO L98 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/default/taipan/svcomp-Reach-64bit-Taipan_Default.epf [2018-11-07 05:11:13,845 INFO L110 SettingsManager]: Loading preferences was successful [2018-11-07 05:11:13,845 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-11-07 05:11:13,846 INFO L131 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2018-11-07 05:11:13,846 INFO L133 SettingsManager]: * User list type=DISABLED [2018-11-07 05:11:13,846 INFO L133 SettingsManager]: * calls to implemented procedures=false [2018-11-07 05:11:13,847 INFO L131 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2018-11-07 05:11:13,847 INFO L133 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2018-11-07 05:11:13,847 INFO L133 SettingsManager]: * Abstract domain=CompoundDomain [2018-11-07 05:11:13,847 INFO L133 SettingsManager]: * Log string format=TERM [2018-11-07 05:11:13,847 INFO L133 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2018-11-07 05:11:13,850 INFO L133 SettingsManager]: * Use the RCFG-of-the-future interface=true [2018-11-07 05:11:13,850 INFO L133 SettingsManager]: * Interval Domain=false [2018-11-07 05:11:13,851 INFO L131 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2018-11-07 05:11:13,851 INFO L133 SettingsManager]: * Overapproximate operations on floating types=true [2018-11-07 05:11:13,851 INFO L133 SettingsManager]: * Check division by zero=IGNORE [2018-11-07 05:11:13,852 INFO L133 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2018-11-07 05:11:13,852 INFO L133 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2018-11-07 05:11:13,852 INFO L133 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2018-11-07 05:11:13,852 INFO L133 SettingsManager]: * Check if freed pointer was valid=false [2018-11-07 05:11:13,852 INFO L133 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2018-11-07 05:11:13,854 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-11-07 05:11:13,854 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-11-07 05:11:13,854 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-11-07 05:11:13,854 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-11-07 05:11:13,855 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-11-07 05:11:13,855 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-11-07 05:11:13,855 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-11-07 05:11:13,855 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-11-07 05:11:13,855 INFO L133 SettingsManager]: * Trace refinement strategy=TAIPAN [2018-11-07 05:11:13,856 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-11-07 05:11:13,856 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-11-07 05:11:13,856 INFO L133 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2018-11-07 05:11:13,856 INFO L133 SettingsManager]: * To the following directory=dump/ [2018-11-07 05:11:13,856 INFO L133 SettingsManager]: * Abstract interpretation Mode=USE_PREDICATES [2018-11-07 05:11:13,902 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2018-11-07 05:11:13,915 INFO L258 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-11-07 05:11:13,919 INFO L214 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2018-11-07 05:11:13,921 INFO L271 PluginConnector]: Initializing CDTParser... [2018-11-07 05:11:13,921 INFO L276 PluginConnector]: CDTParser initialized [2018-11-07 05:11:13,922 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-07 05:11:13,984 INFO L218 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/13aed5542/d8b1d375fb7a416f874708a5216aa836/FLAG909fe42e2 [2018-11-07 05:11:14,406 INFO L298 CDTParser]: Found 1 translation units. [2018-11-07 05:11:14,407 INFO L158 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/loops-crafted-1/Mono6_false-unreach-call1.c [2018-11-07 05:11:14,413 INFO L346 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/13aed5542/d8b1d375fb7a416f874708a5216aa836/FLAG909fe42e2 [2018-11-07 05:11:14,428 INFO L354 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/13aed5542/d8b1d375fb7a416f874708a5216aa836 [2018-11-07 05:11:14,439 INFO L296 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2018-11-07 05:11:14,441 INFO L131 ToolchainWalker]: Walking toolchain with 5 elements. [2018-11-07 05:11:14,441 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2018-11-07 05:11:14,442 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2018-11-07 05:11:14,447 INFO L276 PluginConnector]: CACSL2BoogieTranslator initialized [2018-11-07 05:11:14,448 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 07.11 05:11:14" (1/1) ... [2018-11-07 05:11:14,450 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@5c4e72cb and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.11 05:11:14, skipping insertion in model container [2018-11-07 05:11:14,451 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 07.11 05:11:14" (1/1) ... [2018-11-07 05:11:14,462 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2018-11-07 05:11:14,484 INFO L174 MainTranslator]: Built tables and reachable declarations [2018-11-07 05:11:14,710 INFO L202 PostProcessor]: Analyzing one entry point: main [2018-11-07 05:11:14,714 INFO L189 MainTranslator]: Completed pre-run [2018-11-07 05:11:14,735 INFO L202 PostProcessor]: Analyzing one entry point: main [2018-11-07 05:11:14,752 INFO L193 MainTranslator]: Completed translation [2018-11-07 05:11:14,753 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.11 05:11:14 WrapperNode [2018-11-07 05:11:14,753 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2018-11-07 05:11:14,754 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2018-11-07 05:11:14,754 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2018-11-07 05:11:14,754 INFO L276 PluginConnector]: Boogie Procedure Inliner initialized [2018-11-07 05:11:14,763 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.11 05:11:14" (1/1) ... [2018-11-07 05:11:14,768 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.11 05:11:14" (1/1) ... [2018-11-07 05:11:14,773 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2018-11-07 05:11:14,773 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2018-11-07 05:11:14,773 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2018-11-07 05:11:14,774 INFO L276 PluginConnector]: Boogie Preprocessor initialized [2018-11-07 05:11:14,781 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.11 05:11:14" (1/1) ... [2018-11-07 05:11:14,782 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.11 05:11:14" (1/1) ... [2018-11-07 05:11:14,782 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.11 05:11:14" (1/1) ... [2018-11-07 05:11:14,783 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.11 05:11:14" (1/1) ... [2018-11-07 05:11:14,786 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.11 05:11:14" (1/1) ... [2018-11-07 05:11:14,790 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.11 05:11:14" (1/1) ... [2018-11-07 05:11:14,791 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.11 05:11:14" (1/1) ... [2018-11-07 05:11:14,793 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2018-11-07 05:11:14,793 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2018-11-07 05:11:14,793 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2018-11-07 05:11:14,793 INFO L276 PluginConnector]: RCFGBuilder initialized [2018-11-07 05:11:14,794 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.11 05:11:14" (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-07 05:11:14,923 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2018-11-07 05:11:14,923 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2018-11-07 05:11:14,923 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2018-11-07 05:11:14,924 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2018-11-07 05:11:14,924 INFO L130 BoogieDeclarations]: Found specification of procedure main [2018-11-07 05:11:14,924 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2018-11-07 05:11:14,924 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2018-11-07 05:11:14,924 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2018-11-07 05:11:15,166 INFO L276 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2018-11-07 05:11:15,170 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 07.11 05:11:15 BoogieIcfgContainer [2018-11-07 05:11:15,170 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2018-11-07 05:11:15,171 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2018-11-07 05:11:15,171 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2018-11-07 05:11:15,175 INFO L276 PluginConnector]: TraceAbstraction initialized [2018-11-07 05:11:15,175 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 07.11 05:11:14" (1/3) ... [2018-11-07 05:11:15,176 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6b250b78 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 07.11 05:11:15, skipping insertion in model container [2018-11-07 05:11:15,176 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.11 05:11:14" (2/3) ... [2018-11-07 05:11:15,177 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6b250b78 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 07.11 05:11:15, skipping insertion in model container [2018-11-07 05:11:15,177 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 07.11 05:11:15" (3/3) ... [2018-11-07 05:11:15,179 INFO L112 eAbstractionObserver]: Analyzing ICFG Mono6_false-unreach-call1.c [2018-11-07 05:11:15,191 INFO L136 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-11-07 05:11:15,203 INFO L148 ceAbstractionStarter]: Appying trace abstraction to program that has 1 error locations. [2018-11-07 05:11:15,228 INFO L257 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2018-11-07 05:11:15,270 INFO L382 AbstractCegarLoop]: Interprodecural is true [2018-11-07 05:11:15,270 INFO L383 AbstractCegarLoop]: Hoare is true [2018-11-07 05:11:15,270 INFO L384 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-11-07 05:11:15,270 INFO L385 AbstractCegarLoop]: Backedges is STRAIGHT_LINE [2018-11-07 05:11:15,271 INFO L386 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-11-07 05:11:15,271 INFO L387 AbstractCegarLoop]: Difference is false [2018-11-07 05:11:15,271 INFO L388 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-11-07 05:11:15,271 INFO L393 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-11-07 05:11:15,298 INFO L276 IsEmpty]: Start isEmpty. Operand 21 states. [2018-11-07 05:11:15,305 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 11 [2018-11-07 05:11:15,305 INFO L367 BasicCegarLoop]: Found error trace [2018-11-07 05:11:15,306 INFO L375 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-07 05:11:15,309 INFO L423 AbstractCegarLoop]: === Iteration 1 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-07 05:11:15,315 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-07 05:11:15,316 INFO L82 PathProgramCache]: Analyzing trace with hash -2008095039, now seen corresponding path program 1 times [2018-11-07 05:11:15,318 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-07 05:11:15,375 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:11:15,376 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-07 05:11:15,376 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:11:15,376 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-07 05:11:15,403 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-07 05:11:15,429 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-07 05:11:15,431 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-11-07 05:11:15,431 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2018-11-07 05:11:15,431 INFO L258 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-11-07 05:11:15,435 INFO L459 AbstractCegarLoop]: Interpolant automaton has 2 states [2018-11-07 05:11:15,447 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2018-11-07 05:11:15,447 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2018-11-07 05:11:15,450 INFO L87 Difference]: Start difference. First operand 21 states. Second operand 2 states. [2018-11-07 05:11:15,470 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-07 05:11:15,470 INFO L93 Difference]: Finished difference Result 33 states and 37 transitions. [2018-11-07 05:11:15,471 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2018-11-07 05:11:15,472 INFO L78 Accepts]: Start accepts. Automaton has 2 states. Word has length 10 [2018-11-07 05:11:15,472 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-07 05:11:15,481 INFO L225 Difference]: With dead ends: 33 [2018-11-07 05:11:15,481 INFO L226 Difference]: Without dead ends: 14 [2018-11-07 05:11:15,484 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-07 05:11:15,500 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 14 states. [2018-11-07 05:11:15,519 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 14 to 14. [2018-11-07 05:11:15,520 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 14 states. [2018-11-07 05:11:15,521 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 14 states to 14 states and 15 transitions. [2018-11-07 05:11:15,524 INFO L78 Accepts]: Start accepts. Automaton has 14 states and 15 transitions. Word has length 10 [2018-11-07 05:11:15,525 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-07 05:11:15,525 INFO L480 AbstractCegarLoop]: Abstraction has 14 states and 15 transitions. [2018-11-07 05:11:15,525 INFO L481 AbstractCegarLoop]: Interpolant automaton has 2 states. [2018-11-07 05:11:15,525 INFO L276 IsEmpty]: Start isEmpty. Operand 14 states and 15 transitions. [2018-11-07 05:11:15,526 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2018-11-07 05:11:15,526 INFO L367 BasicCegarLoop]: Found error trace [2018-11-07 05:11:15,529 INFO L375 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-07 05:11:15,529 INFO L423 AbstractCegarLoop]: === Iteration 2 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-07 05:11:15,530 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-07 05:11:15,530 INFO L82 PathProgramCache]: Analyzing trace with hash 1715940768, now seen corresponding path program 1 times [2018-11-07 05:11:15,530 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-07 05:11:15,531 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:11:15,531 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-07 05:11:15,532 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:11:15,532 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-07 05:11:15,573 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-07 05:11:15,787 WARN L179 SmtUtils]: Spent 110.00 ms on a formula simplification that was a NOOP. DAG size: 9 [2018-11-07 05:11:15,875 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-07 05:11:15,877 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-11-07 05:11:15,877 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2018-11-07 05:11:15,878 INFO L258 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-11-07 05:11:15,879 INFO L459 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-11-07 05:11:15,879 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-11-07 05:11:15,879 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2018-11-07 05:11:15,880 INFO L87 Difference]: Start difference. First operand 14 states and 15 transitions. Second operand 5 states. [2018-11-07 05:11:15,958 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-07 05:11:15,958 INFO L93 Difference]: Finished difference Result 27 states and 31 transitions. [2018-11-07 05:11:15,959 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-11-07 05:11:15,959 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 11 [2018-11-07 05:11:15,960 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-07 05:11:15,960 INFO L225 Difference]: With dead ends: 27 [2018-11-07 05:11:15,960 INFO L226 Difference]: Without dead ends: 18 [2018-11-07 05:11:15,962 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2018-11-07 05:11:15,962 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 18 states. [2018-11-07 05:11:15,967 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 18 to 17. [2018-11-07 05:11:15,968 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 17 states. [2018-11-07 05:11:15,969 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 17 states to 17 states and 18 transitions. [2018-11-07 05:11:15,969 INFO L78 Accepts]: Start accepts. Automaton has 17 states and 18 transitions. Word has length 11 [2018-11-07 05:11:15,970 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-07 05:11:15,970 INFO L480 AbstractCegarLoop]: Abstraction has 17 states and 18 transitions. [2018-11-07 05:11:15,970 INFO L481 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-11-07 05:11:15,970 INFO L276 IsEmpty]: Start isEmpty. Operand 17 states and 18 transitions. [2018-11-07 05:11:15,971 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2018-11-07 05:11:15,971 INFO L367 BasicCegarLoop]: Found error trace [2018-11-07 05:11:15,972 INFO L375 BasicCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-07 05:11:15,972 INFO L423 AbstractCegarLoop]: === Iteration 3 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-07 05:11:15,972 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-07 05:11:15,973 INFO L82 PathProgramCache]: Analyzing trace with hash 1048902920, now seen corresponding path program 1 times [2018-11-07 05:11:15,973 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-07 05:11:15,974 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:11:15,974 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-07 05:11:15,974 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:11:15,974 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-07 05:11:15,989 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-07 05:11:16,207 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-07 05:11:16,207 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:11:16,208 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-07 05:11:16,209 INFO L200 CegarAbsIntRunner]: Running AI on error trace of length 16 with the following transitions: [2018-11-07 05:11:16,211 INFO L202 CegarAbsIntRunner]: [0], [4], [8], [12], [14], [19], [21], [28], [31], [33], [39], [40], [41], [43] [2018-11-07 05:11:16,267 INFO L148 AbstractInterpreter]: Using domain PoormanAbstractDomain with backing domain CompoundDomain [CongruenceDomain, OctagonDomain] [2018-11-07 05:11:16,267 INFO L101 FixpointEngine]: Starting fixpoint engine with domain PoormanAbstractDomain (maxUnwinding=3, maxParallelStates=2) [2018-11-07 05:11:16,381 WARN L79 EvaluatorLogger]: Possible loss of precision. Operator ARITHMOD has no precise implementation. [2018-11-07 05:11:16,930 INFO L263 AbstractInterpreter]: Some error location(s) were reachable [2018-11-07 05:11:16,932 INFO L272 AbstractInterpreter]: Visited 14 different actions 270 times. Merged at 5 different actions 148 times. Widened at 1 different actions 26 times. Found 1 fixpoints after 1 different actions. Largest state had 4 variables. [2018-11-07 05:11:16,955 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-07 05:11:16,956 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: Unknown [2018-11-07 05:11:16,957 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:11:16,957 INFO L194 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-07 05:11:16,970 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-07 05:11:16,970 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-11-07 05:11:16,989 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-07 05:11:16,996 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-07 05:11:17,257 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-07 05:11:17,258 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-07 05:11:17,342 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-07 05:11:17,362 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-07 05:11:17,362 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 4, 4] total 9 [2018-11-07 05:11:17,363 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-07 05:11:17,363 INFO L459 AbstractCegarLoop]: Interpolant automaton has 7 states [2018-11-07 05:11:17,363 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2018-11-07 05:11:17,364 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=46, Unknown=0, NotChecked=0, Total=72 [2018-11-07 05:11:17,364 INFO L87 Difference]: Start difference. First operand 17 states and 18 transitions. Second operand 7 states. [2018-11-07 05:11:17,427 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-07 05:11:17,427 INFO L93 Difference]: Finished difference Result 31 states and 35 transitions. [2018-11-07 05:11:17,427 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-11-07 05:11:17,428 INFO L78 Accepts]: Start accepts. Automaton has 7 states. Word has length 15 [2018-11-07 05:11:17,428 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-07 05:11:17,429 INFO L225 Difference]: With dead ends: 31 [2018-11-07 05:11:17,429 INFO L226 Difference]: Without dead ends: 22 [2018-11-07 05:11:17,430 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 34 GetRequests, 27 SyntacticMatches, 0 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=26, Invalid=46, Unknown=0, NotChecked=0, Total=72 [2018-11-07 05:11:17,430 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 22 states. [2018-11-07 05:11:17,434 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 22 to 21. [2018-11-07 05:11:17,434 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 21 states. [2018-11-07 05:11:17,435 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 21 states to 21 states and 22 transitions. [2018-11-07 05:11:17,435 INFO L78 Accepts]: Start accepts. Automaton has 21 states and 22 transitions. Word has length 15 [2018-11-07 05:11:17,436 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-07 05:11:17,436 INFO L480 AbstractCegarLoop]: Abstraction has 21 states and 22 transitions. [2018-11-07 05:11:17,436 INFO L481 AbstractCegarLoop]: Interpolant automaton has 7 states. [2018-11-07 05:11:17,436 INFO L276 IsEmpty]: Start isEmpty. Operand 21 states and 22 transitions. [2018-11-07 05:11:17,437 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2018-11-07 05:11:17,437 INFO L367 BasicCegarLoop]: Found error trace [2018-11-07 05:11:17,437 INFO L375 BasicCegarLoop]: trace histogram [3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-07 05:11:17,437 INFO L423 AbstractCegarLoop]: === Iteration 4 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-07 05:11:17,438 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-07 05:11:17,438 INFO L82 PathProgramCache]: Analyzing trace with hash 452778096, now seen corresponding path program 2 times [2018-11-07 05:11:17,438 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-07 05:11:17,439 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:11:17,439 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-07 05:11:17,439 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:11:17,439 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-07 05:11:17,453 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-07 05:11:17,705 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-07 05:11:17,706 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:11:17,706 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-07 05:11:17,706 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-11-07 05:11:17,706 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-11-07 05:11:17,706 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:11:17,707 INFO L194 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-07 05:11:17,724 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-11-07 05:11:17,725 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST2 (IT: FPandBP) [2018-11-07 05:11:17,742 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 1 check-sat command(s) [2018-11-07 05:11:17,743 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-11-07 05:11:17,745 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-07 05:11:18,052 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-07 05:11:18,052 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-07 05:11:18,265 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-07 05:11:18,290 INFO L312 seRefinementStrategy]: Constructing automaton from 2 perfect and 1 imperfect interpolant sequences. [2018-11-07 05:11:18,290 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [6, 6] imperfect sequences [6] total 14 [2018-11-07 05:11:18,290 INFO L258 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-11-07 05:11:18,291 INFO L459 AbstractCegarLoop]: Interpolant automaton has 6 states [2018-11-07 05:11:18,291 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2018-11-07 05:11:18,292 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=29, Invalid=153, Unknown=0, NotChecked=0, Total=182 [2018-11-07 05:11:18,292 INFO L87 Difference]: Start difference. First operand 21 states and 22 transitions. Second operand 6 states. [2018-11-07 05:11:18,713 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-07 05:11:18,713 INFO L93 Difference]: Finished difference Result 30 states and 32 transitions. [2018-11-07 05:11:18,714 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-11-07 05:11:18,714 INFO L78 Accepts]: Start accepts. Automaton has 6 states. Word has length 19 [2018-11-07 05:11:18,715 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-07 05:11:18,715 INFO L225 Difference]: With dead ends: 30 [2018-11-07 05:11:18,716 INFO L226 Difference]: Without dead ends: 25 [2018-11-07 05:11:18,716 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 45 GetRequests, 31 SyntacticMatches, 0 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=41, Invalid=199, Unknown=0, NotChecked=0, Total=240 [2018-11-07 05:11:18,716 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 25 states. [2018-11-07 05:11:18,720 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 25 to 25. [2018-11-07 05:11:18,720 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 25 states. [2018-11-07 05:11:18,721 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 25 states to 25 states and 27 transitions. [2018-11-07 05:11:18,722 INFO L78 Accepts]: Start accepts. Automaton has 25 states and 27 transitions. Word has length 19 [2018-11-07 05:11:18,722 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-07 05:11:18,722 INFO L480 AbstractCegarLoop]: Abstraction has 25 states and 27 transitions. [2018-11-07 05:11:18,722 INFO L481 AbstractCegarLoop]: Interpolant automaton has 6 states. [2018-11-07 05:11:18,722 INFO L276 IsEmpty]: Start isEmpty. Operand 25 states and 27 transitions. [2018-11-07 05:11:18,723 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2018-11-07 05:11:18,723 INFO L367 BasicCegarLoop]: Found error trace [2018-11-07 05:11:18,723 INFO L375 BasicCegarLoop]: trace histogram [4, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-07 05:11:18,723 INFO L423 AbstractCegarLoop]: === Iteration 5 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-07 05:11:18,724 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-07 05:11:18,724 INFO L82 PathProgramCache]: Analyzing trace with hash 671507994, now seen corresponding path program 1 times [2018-11-07 05:11:18,724 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-07 05:11:18,725 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:11:18,725 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-11-07 05:11:18,725 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:11:18,725 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-07 05:11:18,738 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-07 05:11:18,924 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-07 05:11:18,924 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:11:18,925 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-07 05:11:18,925 INFO L200 CegarAbsIntRunner]: Running AI on error trace of length 24 with the following transitions: [2018-11-07 05:11:18,925 INFO L202 CegarAbsIntRunner]: [0], [4], [8], [12], [14], [17], [19], [21], [28], [31], [33], [39], [40], [41], [43] [2018-11-07 05:11:18,926 INFO L148 AbstractInterpreter]: Using domain PoormanAbstractDomain with backing domain CompoundDomain [CongruenceDomain, OctagonDomain] [2018-11-07 05:11:18,927 INFO L101 FixpointEngine]: Starting fixpoint engine with domain PoormanAbstractDomain (maxUnwinding=3, maxParallelStates=2) [2018-11-07 05:11:18,932 WARN L79 EvaluatorLogger]: Possible loss of precision. Operator ARITHMOD has no precise implementation. [2018-11-07 05:11:19,407 INFO L263 AbstractInterpreter]: Some error location(s) were reachable [2018-11-07 05:11:19,408 INFO L272 AbstractInterpreter]: Visited 15 different actions 392 times. Merged at 6 different actions 207 times. Widened at 1 different actions 32 times. Found 36 fixpoints after 3 different actions. Largest state had 5 variables. [2018-11-07 05:11:19,446 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-07 05:11:19,446 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: Unknown [2018-11-07 05:11:19,447 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:11:19,447 INFO L194 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-07 05:11:19,461 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-07 05:11:19,462 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-11-07 05:11:19,486 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-07 05:11:19,488 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-07 05:11:19,504 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-07 05:11:19,505 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-07 05:11:19,603 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-07 05:11:19,622 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-07 05:11:19,622 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 5, 5] total 9 [2018-11-07 05:11:19,622 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-07 05:11:19,623 INFO L459 AbstractCegarLoop]: Interpolant automaton has 6 states [2018-11-07 05:11:19,623 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2018-11-07 05:11:19,624 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=42, Unknown=0, NotChecked=0, Total=72 [2018-11-07 05:11:19,624 INFO L87 Difference]: Start difference. First operand 25 states and 27 transitions. Second operand 6 states. [2018-11-07 05:11:19,846 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-07 05:11:19,846 INFO L93 Difference]: Finished difference Result 39 states and 43 transitions. [2018-11-07 05:11:19,847 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-11-07 05:11:19,847 INFO L78 Accepts]: Start accepts. Automaton has 6 states. Word has length 23 [2018-11-07 05:11:19,848 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-07 05:11:19,848 INFO L225 Difference]: With dead ends: 39 [2018-11-07 05:11:19,848 INFO L226 Difference]: Without dead ends: 30 [2018-11-07 05:11:19,849 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-07 05:11:19,849 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 30 states. [2018-11-07 05:11:19,853 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 30 to 29. [2018-11-07 05:11:19,854 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 29 states. [2018-11-07 05:11:19,855 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 29 states to 29 states and 31 transitions. [2018-11-07 05:11:19,855 INFO L78 Accepts]: Start accepts. Automaton has 29 states and 31 transitions. Word has length 23 [2018-11-07 05:11:19,855 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-07 05:11:19,855 INFO L480 AbstractCegarLoop]: Abstraction has 29 states and 31 transitions. [2018-11-07 05:11:19,855 INFO L481 AbstractCegarLoop]: Interpolant automaton has 6 states. [2018-11-07 05:11:19,856 INFO L276 IsEmpty]: Start isEmpty. Operand 29 states and 31 transitions. [2018-11-07 05:11:19,856 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2018-11-07 05:11:19,856 INFO L367 BasicCegarLoop]: Found error trace [2018-11-07 05:11:19,857 INFO L375 BasicCegarLoop]: trace histogram [5, 4, 4, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-07 05:11:19,857 INFO L423 AbstractCegarLoop]: === Iteration 6 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-07 05:11:19,857 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-07 05:11:19,857 INFO L82 PathProgramCache]: Analyzing trace with hash 1681938818, now seen corresponding path program 2 times [2018-11-07 05:11:19,857 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-07 05:11:19,858 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:11:19,859 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-07 05:11:19,859 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:11:19,859 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-07 05:11:19,868 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-07 05:11:20,156 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-07 05:11:20,156 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:11:20,156 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-07 05:11:20,157 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-11-07 05:11:20,157 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-11-07 05:11:20,157 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:11:20,157 INFO L194 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-07 05:11:20,166 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-11-07 05:11:20,167 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST2 (IT: FPandBP) [2018-11-07 05:11:20,185 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 2 check-sat command(s) [2018-11-07 05:11:20,185 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-11-07 05:11:20,187 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-07 05:11:20,348 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-07 05:11:20,349 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-07 05:11:20,553 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-07 05:11:20,573 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-07 05:11:20,573 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 17 [2018-11-07 05:11:20,573 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-07 05:11:20,574 INFO L459 AbstractCegarLoop]: Interpolant automaton has 12 states [2018-11-07 05:11:20,574 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2018-11-07 05:11:20,574 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=42, Invalid=230, Unknown=0, NotChecked=0, Total=272 [2018-11-07 05:11:20,576 INFO L87 Difference]: Start difference. First operand 29 states and 31 transitions. Second operand 12 states. [2018-11-07 05:11:20,984 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-07 05:11:20,985 INFO L93 Difference]: Finished difference Result 50 states and 56 transitions. [2018-11-07 05:11:20,985 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-11-07 05:11:20,985 INFO L78 Accepts]: Start accepts. Automaton has 12 states. Word has length 27 [2018-11-07 05:11:20,985 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-07 05:11:20,986 INFO L225 Difference]: With dead ends: 50 [2018-11-07 05:11:20,986 INFO L226 Difference]: Without dead ends: 38 [2018-11-07 05:11:20,987 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 67 GetRequests, 45 SyntacticMatches, 1 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 34 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=87, Invalid=419, Unknown=0, NotChecked=0, Total=506 [2018-11-07 05:11:20,987 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 38 states. [2018-11-07 05:11:20,992 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 38 to 37. [2018-11-07 05:11:20,993 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 37 states. [2018-11-07 05:11:20,994 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 37 states to 37 states and 40 transitions. [2018-11-07 05:11:20,994 INFO L78 Accepts]: Start accepts. Automaton has 37 states and 40 transitions. Word has length 27 [2018-11-07 05:11:20,994 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-07 05:11:20,994 INFO L480 AbstractCegarLoop]: Abstraction has 37 states and 40 transitions. [2018-11-07 05:11:20,995 INFO L481 AbstractCegarLoop]: Interpolant automaton has 12 states. [2018-11-07 05:11:20,995 INFO L276 IsEmpty]: Start isEmpty. Operand 37 states and 40 transitions. [2018-11-07 05:11:20,996 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2018-11-07 05:11:20,996 INFO L367 BasicCegarLoop]: Found error trace [2018-11-07 05:11:20,996 INFO L375 BasicCegarLoop]: trace histogram [7, 6, 6, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-07 05:11:20,996 INFO L423 AbstractCegarLoop]: === Iteration 7 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-07 05:11:20,996 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-07 05:11:20,997 INFO L82 PathProgramCache]: Analyzing trace with hash 1459820948, now seen corresponding path program 3 times [2018-11-07 05:11:20,997 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-07 05:11:20,998 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:11:20,998 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-11-07 05:11:20,998 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:11:20,998 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-07 05:11:21,010 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-07 05:11:21,245 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-07 05:11:21,245 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:11:21,246 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-07 05:11:21,246 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-11-07 05:11:21,246 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-11-07 05:11:21,246 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:11:21,246 INFO L194 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-07 05:11:21,264 INFO L103 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-11-07 05:11:21,264 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder TERMS_WITH_SMALL_CONSTANTS_FIRST (IT: FPandBP) [2018-11-07 05:11:21,281 INFO L249 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-11-07 05:11:21,281 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-11-07 05:11:21,283 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-07 05:11:21,304 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-07 05:11:21,304 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-07 05:11:21,409 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-07 05:11:21,430 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-07 05:11:21,430 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 7, 7] total 14 [2018-11-07 05:11:21,430 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-07 05:11:21,431 INFO L459 AbstractCegarLoop]: Interpolant automaton has 9 states [2018-11-07 05:11:21,431 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2018-11-07 05:11:21,431 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=66, Invalid=116, Unknown=0, NotChecked=0, Total=182 [2018-11-07 05:11:21,432 INFO L87 Difference]: Start difference. First operand 37 states and 40 transitions. Second operand 9 states. [2018-11-07 05:11:21,637 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-07 05:11:21,638 INFO L93 Difference]: Finished difference Result 59 states and 66 transitions. [2018-11-07 05:11:21,639 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-11-07 05:11:21,640 INFO L78 Accepts]: Start accepts. Automaton has 9 states. Word has length 35 [2018-11-07 05:11:21,640 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-07 05:11:21,640 INFO L225 Difference]: With dead ends: 59 [2018-11-07 05:11:21,641 INFO L226 Difference]: Without dead ends: 46 [2018-11-07 05:11:21,641 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-07 05:11:21,642 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 46 states. [2018-11-07 05:11:21,647 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 46 to 45. [2018-11-07 05:11:21,647 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 45 states. [2018-11-07 05:11:21,648 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 45 states to 45 states and 48 transitions. [2018-11-07 05:11:21,648 INFO L78 Accepts]: Start accepts. Automaton has 45 states and 48 transitions. Word has length 35 [2018-11-07 05:11:21,648 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-07 05:11:21,648 INFO L480 AbstractCegarLoop]: Abstraction has 45 states and 48 transitions. [2018-11-07 05:11:21,648 INFO L481 AbstractCegarLoop]: Interpolant automaton has 9 states. [2018-11-07 05:11:21,648 INFO L276 IsEmpty]: Start isEmpty. Operand 45 states and 48 transitions. [2018-11-07 05:11:21,649 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2018-11-07 05:11:21,650 INFO L367 BasicCegarLoop]: Found error trace [2018-11-07 05:11:21,650 INFO L375 BasicCegarLoop]: trace histogram [9, 8, 8, 6, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-07 05:11:21,650 INFO L423 AbstractCegarLoop]: === Iteration 8 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-07 05:11:21,650 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-07 05:11:21,650 INFO L82 PathProgramCache]: Analyzing trace with hash -149334940, now seen corresponding path program 4 times [2018-11-07 05:11:21,651 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-07 05:11:21,651 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:11:21,652 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-11-07 05:11:21,652 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:11:21,652 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-07 05:11:21,664 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-07 05:11:21,920 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-07 05:11:21,921 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:11:21,921 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-07 05:11:21,921 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-11-07 05:11:21,921 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-11-07 05:11:21,921 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:11:21,921 INFO L194 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-07 05:11:21,930 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-07 05:11:21,931 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-11-07 05:11:21,951 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-07 05:11:21,954 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-07 05:11:21,972 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-07 05:11:21,973 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-07 05:11:22,148 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-07 05:11:22,168 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-07 05:11:22,168 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 9, 9] total 18 [2018-11-07 05:11:22,168 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-07 05:11:22,169 INFO L459 AbstractCegarLoop]: Interpolant automaton has 11 states [2018-11-07 05:11:22,169 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2018-11-07 05:11:22,170 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=104, Invalid=202, Unknown=0, NotChecked=0, Total=306 [2018-11-07 05:11:22,170 INFO L87 Difference]: Start difference. First operand 45 states and 48 transitions. Second operand 11 states. [2018-11-07 05:11:22,618 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-07 05:11:22,618 INFO L93 Difference]: Finished difference Result 67 states and 74 transitions. [2018-11-07 05:11:22,620 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-11-07 05:11:22,621 INFO L78 Accepts]: Start accepts. Automaton has 11 states. Word has length 43 [2018-11-07 05:11:22,621 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-07 05:11:22,622 INFO L225 Difference]: With dead ends: 67 [2018-11-07 05:11:22,622 INFO L226 Difference]: Without dead ends: 54 [2018-11-07 05:11:22,622 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-07 05:11:22,622 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states. [2018-11-07 05:11:22,630 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 53. [2018-11-07 05:11:22,630 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 53 states. [2018-11-07 05:11:22,631 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 53 states to 53 states and 56 transitions. [2018-11-07 05:11:22,632 INFO L78 Accepts]: Start accepts. Automaton has 53 states and 56 transitions. Word has length 43 [2018-11-07 05:11:22,632 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-07 05:11:22,632 INFO L480 AbstractCegarLoop]: Abstraction has 53 states and 56 transitions. [2018-11-07 05:11:22,632 INFO L481 AbstractCegarLoop]: Interpolant automaton has 11 states. [2018-11-07 05:11:22,632 INFO L276 IsEmpty]: Start isEmpty. Operand 53 states and 56 transitions. [2018-11-07 05:11:22,633 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 52 [2018-11-07 05:11:22,634 INFO L367 BasicCegarLoop]: Found error trace [2018-11-07 05:11:22,634 INFO L375 BasicCegarLoop]: trace histogram [11, 10, 10, 8, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-07 05:11:22,634 INFO L423 AbstractCegarLoop]: === Iteration 9 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-07 05:11:22,634 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-07 05:11:22,634 INFO L82 PathProgramCache]: Analyzing trace with hash 435142452, now seen corresponding path program 5 times [2018-11-07 05:11:22,634 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-07 05:11:22,635 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:11:22,635 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-07 05:11:22,635 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:11:22,636 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-07 05:11:22,646 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-07 05:11:22,858 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-07 05:11:22,859 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:11:22,859 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-07 05:11:22,859 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-11-07 05:11:22,859 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-11-07 05:11:22,859 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:11:22,859 INFO L194 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-07 05:11:22,869 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-11-07 05:11:22,869 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST2 (IT: FPandBP) [2018-11-07 05:11:22,882 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2018-11-07 05:11:22,882 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-11-07 05:11:22,885 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-07 05:11:23,452 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-07 05:11:23,453 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-07 05:11:23,981 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-07 05:11:24,015 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-07 05:11:24,015 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 9, 9] total 27 [2018-11-07 05:11:24,015 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-07 05:11:24,018 INFO L459 AbstractCegarLoop]: Interpolant automaton has 20 states [2018-11-07 05:11:24,019 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2018-11-07 05:11:24,019 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=92, Invalid=610, Unknown=0, NotChecked=0, Total=702 [2018-11-07 05:11:24,020 INFO L87 Difference]: Start difference. First operand 53 states and 56 transitions. Second operand 20 states. [2018-11-07 05:11:24,473 WARN L179 SmtUtils]: Spent 106.00 ms on a formula simplification that was a NOOP. DAG size: 11 [2018-11-07 05:11:25,335 WARN L179 SmtUtils]: Spent 121.00 ms on a formula simplification that was a NOOP. DAG size: 11 [2018-11-07 05:11:26,162 WARN L179 SmtUtils]: Spent 118.00 ms on a formula simplification that was a NOOP. DAG size: 11 [2018-11-07 05:11:26,897 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-07 05:11:26,898 INFO L93 Difference]: Finished difference Result 83 states and 92 transitions. [2018-11-07 05:11:26,898 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2018-11-07 05:11:26,898 INFO L78 Accepts]: Start accepts. Automaton has 20 states. Word has length 51 [2018-11-07 05:11:26,899 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-07 05:11:26,900 INFO L225 Difference]: With dead ends: 83 [2018-11-07 05:11:26,900 INFO L226 Difference]: Without dead ends: 67 [2018-11-07 05:11:26,902 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 127 GetRequests, 89 SyntacticMatches, 1 SemanticMatches, 37 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 123 ImplicationChecksByTransitivity, 2.1s TimeCoverageRelationStatistics Valid=207, Invalid=1275, Unknown=0, NotChecked=0, Total=1482 [2018-11-07 05:11:26,902 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 67 states. [2018-11-07 05:11:26,908 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 67 to 65. [2018-11-07 05:11:26,909 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 65 states. [2018-11-07 05:11:26,909 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 65 states to 65 states and 69 transitions. [2018-11-07 05:11:26,910 INFO L78 Accepts]: Start accepts. Automaton has 65 states and 69 transitions. Word has length 51 [2018-11-07 05:11:26,910 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-07 05:11:26,910 INFO L480 AbstractCegarLoop]: Abstraction has 65 states and 69 transitions. [2018-11-07 05:11:26,910 INFO L481 AbstractCegarLoop]: Interpolant automaton has 20 states. [2018-11-07 05:11:26,910 INFO L276 IsEmpty]: Start isEmpty. Operand 65 states and 69 transitions. [2018-11-07 05:11:26,911 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 64 [2018-11-07 05:11:26,911 INFO L367 BasicCegarLoop]: Found error trace [2018-11-07 05:11:26,911 INFO L375 BasicCegarLoop]: trace histogram [14, 13, 13, 10, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-07 05:11:26,912 INFO L423 AbstractCegarLoop]: === Iteration 10 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-07 05:11:26,912 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-07 05:11:26,912 INFO L82 PathProgramCache]: Analyzing trace with hash -1361248850, now seen corresponding path program 6 times [2018-11-07 05:11:26,912 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-07 05:11:26,913 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:11:26,913 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-11-07 05:11:26,914 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:11:26,914 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-07 05:11:26,927 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-07 05:11:27,430 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-07 05:11:27,430 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:11:27,430 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-07 05:11:27,430 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-11-07 05:11:27,431 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-11-07 05:11:27,431 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:11:27,431 INFO L194 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-07 05:11:27,453 INFO L103 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-11-07 05:11:27,453 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder TERMS_WITH_SMALL_CONSTANTS_FIRST (IT: FPandBP) [2018-11-07 05:11:27,481 INFO L249 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-11-07 05:11:27,481 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-11-07 05:11:27,485 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-07 05:11:27,511 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-07 05:11:27,511 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-07 05:11:27,896 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-07 05:11:27,916 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-07 05:11:27,916 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 13, 13] total 27 [2018-11-07 05:11:27,916 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-07 05:11:27,917 INFO L459 AbstractCegarLoop]: Interpolant automaton has 16 states [2018-11-07 05:11:27,917 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2018-11-07 05:11:27,918 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=218, Invalid=484, Unknown=0, NotChecked=0, Total=702 [2018-11-07 05:11:27,919 INFO L87 Difference]: Start difference. First operand 65 states and 69 transitions. Second operand 16 states. [2018-11-07 05:11:28,346 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-07 05:11:28,347 INFO L93 Difference]: Finished difference Result 95 states and 105 transitions. [2018-11-07 05:11:28,347 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2018-11-07 05:11:28,347 INFO L78 Accepts]: Start accepts. Automaton has 16 states. Word has length 63 [2018-11-07 05:11:28,348 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-07 05:11:28,349 INFO L225 Difference]: With dead ends: 95 [2018-11-07 05:11:28,349 INFO L226 Difference]: Without dead ends: 78 [2018-11-07 05:11:28,350 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 142 GetRequests, 115 SyntacticMatches, 2 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=218, Invalid=484, Unknown=0, NotChecked=0, Total=702 [2018-11-07 05:11:28,350 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 78 states. [2018-11-07 05:11:28,356 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 78 to 77. [2018-11-07 05:11:28,356 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 77 states. [2018-11-07 05:11:28,357 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 77 states to 77 states and 81 transitions. [2018-11-07 05:11:28,357 INFO L78 Accepts]: Start accepts. Automaton has 77 states and 81 transitions. Word has length 63 [2018-11-07 05:11:28,357 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-07 05:11:28,357 INFO L480 AbstractCegarLoop]: Abstraction has 77 states and 81 transitions. [2018-11-07 05:11:28,358 INFO L481 AbstractCegarLoop]: Interpolant automaton has 16 states. [2018-11-07 05:11:28,358 INFO L276 IsEmpty]: Start isEmpty. Operand 77 states and 81 transitions. [2018-11-07 05:11:28,359 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 76 [2018-11-07 05:11:28,359 INFO L367 BasicCegarLoop]: Found error trace [2018-11-07 05:11:28,359 INFO L375 BasicCegarLoop]: trace histogram [17, 16, 16, 13, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-07 05:11:28,359 INFO L423 AbstractCegarLoop]: === Iteration 11 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-07 05:11:28,359 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-07 05:11:28,359 INFO L82 PathProgramCache]: Analyzing trace with hash -1880071194, now seen corresponding path program 7 times [2018-11-07 05:11:28,360 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-07 05:11:28,360 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:11:28,361 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-11-07 05:11:28,361 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:11:28,361 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-07 05:11:28,372 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-07 05:11:28,709 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-07 05:11:28,709 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:11:28,710 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-07 05:11:28,710 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-11-07 05:11:28,710 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-11-07 05:11:28,710 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:11:28,710 INFO L194 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-07 05:11:28,720 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-07 05:11:28,721 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-11-07 05:11:28,750 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-07 05:11:28,753 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-07 05:11:28,837 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-07 05:11:28,838 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-07 05:11:29,551 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-07 05:11:29,577 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-07 05:11:29,577 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 16, 16] total 33 [2018-11-07 05:11:29,577 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-07 05:11:29,578 INFO L459 AbstractCegarLoop]: Interpolant automaton has 19 states [2018-11-07 05:11:29,578 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2018-11-07 05:11:29,578 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=317, Invalid=739, Unknown=0, NotChecked=0, Total=1056 [2018-11-07 05:11:29,579 INFO L87 Difference]: Start difference. First operand 77 states and 81 transitions. Second operand 19 states. [2018-11-07 05:11:30,411 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-07 05:11:30,411 INFO L93 Difference]: Finished difference Result 107 states and 117 transitions. [2018-11-07 05:11:30,411 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2018-11-07 05:11:30,412 INFO L78 Accepts]: Start accepts. Automaton has 19 states. Word has length 75 [2018-11-07 05:11:30,412 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-07 05:11:30,413 INFO L225 Difference]: With dead ends: 107 [2018-11-07 05:11:30,414 INFO L226 Difference]: Without dead ends: 90 [2018-11-07 05:11:30,415 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 169 GetRequests, 136 SyntacticMatches, 2 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=317, Invalid=739, Unknown=0, NotChecked=0, Total=1056 [2018-11-07 05:11:30,415 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 90 states. [2018-11-07 05:11:30,421 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 90 to 89. [2018-11-07 05:11:30,421 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 89 states. [2018-11-07 05:11:30,422 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 89 states to 89 states and 93 transitions. [2018-11-07 05:11:30,422 INFO L78 Accepts]: Start accepts. Automaton has 89 states and 93 transitions. Word has length 75 [2018-11-07 05:11:30,423 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-07 05:11:30,423 INFO L480 AbstractCegarLoop]: Abstraction has 89 states and 93 transitions. [2018-11-07 05:11:30,423 INFO L481 AbstractCegarLoop]: Interpolant automaton has 19 states. [2018-11-07 05:11:30,423 INFO L276 IsEmpty]: Start isEmpty. Operand 89 states and 93 transitions. [2018-11-07 05:11:30,424 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 88 [2018-11-07 05:11:30,424 INFO L367 BasicCegarLoop]: Found error trace [2018-11-07 05:11:30,424 INFO L375 BasicCegarLoop]: trace histogram [20, 19, 19, 16, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-07 05:11:30,425 INFO L423 AbstractCegarLoop]: === Iteration 12 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-07 05:11:30,425 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-07 05:11:30,425 INFO L82 PathProgramCache]: Analyzing trace with hash -842779106, now seen corresponding path program 8 times [2018-11-07 05:11:30,425 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-07 05:11:30,426 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:11:30,426 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-07 05:11:30,426 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:11:30,426 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-07 05:11:30,438 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-07 05:11:30,924 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-07 05:11:30,925 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:11:30,925 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-07 05:11:30,925 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-11-07 05:11:30,925 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-11-07 05:11:30,925 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:11:30,925 INFO L194 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-07 05:11:30,935 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-11-07 05:11:30,935 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST2 (IT: FPandBP) [2018-11-07 05:11:30,952 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2018-11-07 05:11:30,953 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-11-07 05:11:30,955 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-07 05:11:31,221 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-07 05:11:31,222 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-07 05:11:31,823 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-07 05:11:31,842 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-07 05:11:31,843 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 9, 9] total 36 [2018-11-07 05:11:31,843 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-07 05:11:31,843 INFO L459 AbstractCegarLoop]: Interpolant automaton has 29 states [2018-11-07 05:11:31,844 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 29 interpolants. [2018-11-07 05:11:31,844 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=107, Invalid=1153, Unknown=0, NotChecked=0, Total=1260 [2018-11-07 05:11:31,844 INFO L87 Difference]: Start difference. First operand 89 states and 93 transitions. Second operand 29 states. [2018-11-07 05:11:32,878 WARN L179 SmtUtils]: Spent 107.00 ms on a formula simplification that was a NOOP. DAG size: 11 [2018-11-07 05:11:34,616 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-07 05:11:34,617 INFO L93 Difference]: Finished difference Result 126 states and 138 transitions. [2018-11-07 05:11:34,617 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 28 states. [2018-11-07 05:11:34,617 INFO L78 Accepts]: Start accepts. Automaton has 29 states. Word has length 87 [2018-11-07 05:11:34,618 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-07 05:11:34,618 INFO L225 Difference]: With dead ends: 126 [2018-11-07 05:11:34,618 INFO L226 Difference]: Without dead ends: 106 [2018-11-07 05:11:34,620 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 217 GetRequests, 161 SyntacticMatches, 1 SemanticMatches, 55 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 239 ImplicationChecksByTransitivity, 1.9s TimeCoverageRelationStatistics Valid=312, Invalid=2880, Unknown=0, NotChecked=0, Total=3192 [2018-11-07 05:11:34,620 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 106 states. [2018-11-07 05:11:34,627 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 106 to 105. [2018-11-07 05:11:34,627 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 105 states. [2018-11-07 05:11:34,629 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 105 states to 105 states and 110 transitions. [2018-11-07 05:11:34,629 INFO L78 Accepts]: Start accepts. Automaton has 105 states and 110 transitions. Word has length 87 [2018-11-07 05:11:34,629 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-07 05:11:34,629 INFO L480 AbstractCegarLoop]: Abstraction has 105 states and 110 transitions. [2018-11-07 05:11:34,629 INFO L481 AbstractCegarLoop]: Interpolant automaton has 29 states. [2018-11-07 05:11:34,629 INFO L276 IsEmpty]: Start isEmpty. Operand 105 states and 110 transitions. [2018-11-07 05:11:34,631 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 104 [2018-11-07 05:11:34,631 INFO L367 BasicCegarLoop]: Found error trace [2018-11-07 05:11:34,631 INFO L375 BasicCegarLoop]: trace histogram [24, 23, 23, 19, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-07 05:11:34,631 INFO L423 AbstractCegarLoop]: === Iteration 13 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-07 05:11:34,631 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-07 05:11:34,632 INFO L82 PathProgramCache]: Analyzing trace with hash 2089000704, now seen corresponding path program 9 times [2018-11-07 05:11:34,632 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-07 05:11:34,633 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:11:34,633 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-11-07 05:11:34,633 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:11:34,633 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-07 05:11:34,646 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-07 05:11:35,553 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-07 05:11:35,553 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:11:35,553 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-07 05:11:35,553 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-11-07 05:11:35,553 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-11-07 05:11:35,554 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:11:35,554 INFO L194 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-07 05:11:35,565 INFO L103 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-11-07 05:11:35,565 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder TERMS_WITH_SMALL_CONSTANTS_FIRST (IT: FPandBP) [2018-11-07 05:11:35,601 INFO L249 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-11-07 05:11:35,602 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-11-07 05:11:35,605 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-07 05:11:35,669 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-07 05:11:35,669 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-07 05:11:36,704 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-07 05:11:36,724 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-07 05:11:36,729 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [26, 22, 22] total 46 [2018-11-07 05:11:36,729 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-07 05:11:36,729 INFO L459 AbstractCegarLoop]: Interpolant automaton has 26 states [2018-11-07 05:11:36,730 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2018-11-07 05:11:36,731 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=592, Invalid=1478, Unknown=0, NotChecked=0, Total=2070 [2018-11-07 05:11:36,731 INFO L87 Difference]: Start difference. First operand 105 states and 110 transitions. Second operand 26 states. [2018-11-07 05:11:37,790 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-07 05:11:37,790 INFO L93 Difference]: Finished difference Result 143 states and 156 transitions. [2018-11-07 05:11:37,790 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 25 states. [2018-11-07 05:11:37,791 INFO L78 Accepts]: Start accepts. Automaton has 26 states. Word has length 103 [2018-11-07 05:11:37,791 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-07 05:11:37,792 INFO L225 Difference]: With dead ends: 143 [2018-11-07 05:11:37,793 INFO L226 Difference]: Without dead ends: 122 [2018-11-07 05:11:37,794 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-07 05:11:37,794 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 122 states. [2018-11-07 05:11:37,801 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 122 to 121. [2018-11-07 05:11:37,802 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 121 states. [2018-11-07 05:11:37,803 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 121 states to 121 states and 126 transitions. [2018-11-07 05:11:37,803 INFO L78 Accepts]: Start accepts. Automaton has 121 states and 126 transitions. Word has length 103 [2018-11-07 05:11:37,803 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-07 05:11:37,804 INFO L480 AbstractCegarLoop]: Abstraction has 121 states and 126 transitions. [2018-11-07 05:11:37,804 INFO L481 AbstractCegarLoop]: Interpolant automaton has 26 states. [2018-11-07 05:11:37,804 INFO L276 IsEmpty]: Start isEmpty. Operand 121 states and 126 transitions. [2018-11-07 05:11:37,805 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 120 [2018-11-07 05:11:37,805 INFO L367 BasicCegarLoop]: Found error trace [2018-11-07 05:11:37,806 INFO L375 BasicCegarLoop]: trace histogram [28, 27, 27, 23, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-07 05:11:37,806 INFO L423 AbstractCegarLoop]: === Iteration 14 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-07 05:11:37,806 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-07 05:11:37,806 INFO L82 PathProgramCache]: Analyzing trace with hash -303598432, now seen corresponding path program 10 times [2018-11-07 05:11:37,806 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-07 05:11:37,807 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:11:37,807 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-11-07 05:11:37,807 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:11:37,807 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-07 05:11:37,821 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-07 05:11:38,533 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-07 05:11:38,534 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:11:38,534 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-07 05:11:38,534 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-11-07 05:11:38,534 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-11-07 05:11:38,534 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:11:38,534 INFO L194 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-07 05:11:38,543 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-07 05:11:38,544 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-11-07 05:11:38,578 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-07 05:11:38,581 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-07 05:11:38,632 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-07 05:11:38,633 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-07 05:11:40,859 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-07 05:11:40,894 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-07 05:11:40,894 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [30, 26, 26] total 54 [2018-11-07 05:11:40,895 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-07 05:11:40,895 INFO L459 AbstractCegarLoop]: Interpolant automaton has 30 states [2018-11-07 05:11:40,896 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 30 interpolants. [2018-11-07 05:11:40,899 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=804, Invalid=2058, Unknown=0, NotChecked=0, Total=2862 [2018-11-07 05:11:40,901 INFO L87 Difference]: Start difference. First operand 121 states and 126 transitions. Second operand 30 states. [2018-11-07 05:11:42,598 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-07 05:11:42,598 INFO L93 Difference]: Finished difference Result 159 states and 172 transitions. [2018-11-07 05:11:42,598 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 29 states. [2018-11-07 05:11:42,598 INFO L78 Accepts]: Start accepts. Automaton has 30 states. Word has length 119 [2018-11-07 05:11:42,599 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-07 05:11:42,600 INFO L225 Difference]: With dead ends: 159 [2018-11-07 05:11:42,600 INFO L226 Difference]: Without dead ends: 138 [2018-11-07 05:11:42,601 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 268 GetRequests, 214 SyntacticMatches, 2 SemanticMatches, 52 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 2.7s TimeCoverageRelationStatistics Valid=804, Invalid=2058, Unknown=0, NotChecked=0, Total=2862 [2018-11-07 05:11:42,601 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 138 states. [2018-11-07 05:11:42,609 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 138 to 137. [2018-11-07 05:11:42,609 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 137 states. [2018-11-07 05:11:42,611 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 137 states to 137 states and 142 transitions. [2018-11-07 05:11:42,611 INFO L78 Accepts]: Start accepts. Automaton has 137 states and 142 transitions. Word has length 119 [2018-11-07 05:11:42,611 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-07 05:11:42,611 INFO L480 AbstractCegarLoop]: Abstraction has 137 states and 142 transitions. [2018-11-07 05:11:42,611 INFO L481 AbstractCegarLoop]: Interpolant automaton has 30 states. [2018-11-07 05:11:42,612 INFO L276 IsEmpty]: Start isEmpty. Operand 137 states and 142 transitions. [2018-11-07 05:11:42,613 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 136 [2018-11-07 05:11:42,613 INFO L367 BasicCegarLoop]: Found error trace [2018-11-07 05:11:42,614 INFO L375 BasicCegarLoop]: trace histogram [32, 31, 31, 27, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-07 05:11:42,614 INFO L423 AbstractCegarLoop]: === Iteration 15 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-07 05:11:42,614 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-07 05:11:42,614 INFO L82 PathProgramCache]: Analyzing trace with hash -114554304, now seen corresponding path program 11 times [2018-11-07 05:11:42,614 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-07 05:11:42,615 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:11:42,615 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-07 05:11:42,615 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:11:42,615 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-07 05:11:42,630 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-07 05:11:44,029 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-07 05:11:44,030 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:11:44,030 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-07 05:11:44,030 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-11-07 05:11:44,030 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-11-07 05:11:44,030 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:11:44,030 INFO L194 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-07 05:11:44,039 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-11-07 05:11:44,039 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST2 (IT: FPandBP) [2018-11-07 05:12:15,612 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 7 check-sat command(s) [2018-11-07 05:12:15,612 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-11-07 05:12:15,967 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-07 05:12:17,123 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-07 05:12:17,123 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-07 05:12:31,053 INFO L134 CoverageAnalysis]: Checked inductivity of 1922 backedges. 0 proven. 434 refuted. 3 times theorem prover too weak. 1485 trivial. 0 not checked. [2018-11-07 05:12:31,072 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-07 05:12:31,073 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [34, 12, 12] total 54 [2018-11-07 05:12:31,073 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-07 05:12:31,073 INFO L459 AbstractCegarLoop]: Interpolant automaton has 44 states [2018-11-07 05:12:31,074 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 44 interpolants. [2018-11-07 05:12:31,075 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=225, Invalid=2631, Unknown=6, NotChecked=0, Total=2862 [2018-11-07 05:12:31,075 INFO L87 Difference]: Start difference. First operand 137 states and 142 transitions. Second operand 44 states. [2018-11-07 05:12:35,262 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-07 05:12:35,262 INFO L93 Difference]: Finished difference Result 183 states and 198 transitions. [2018-11-07 05:12:35,263 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 44 states. [2018-11-07 05:12:35,263 INFO L78 Accepts]: Start accepts. Automaton has 44 states. Word has length 135 [2018-11-07 05:12:35,263 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-07 05:12:35,264 INFO L225 Difference]: With dead ends: 183 [2018-11-07 05:12:35,264 INFO L226 Difference]: Without dead ends: 159 [2018-11-07 05:12:35,268 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 338 GetRequests, 251 SyntacticMatches, 1 SemanticMatches, 86 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 670 ImplicationChecksByTransitivity, 17.2s TimeCoverageRelationStatistics Valid=657, Invalid=6993, Unknown=6, NotChecked=0, Total=7656 [2018-11-07 05:12:35,269 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 159 states. [2018-11-07 05:12:35,275 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 159 to 157. [2018-11-07 05:12:35,275 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 157 states. [2018-11-07 05:12:35,277 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 157 states to 157 states and 162 transitions. [2018-11-07 05:12:35,277 INFO L78 Accepts]: Start accepts. Automaton has 157 states and 162 transitions. Word has length 135 [2018-11-07 05:12:35,277 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-07 05:12:35,277 INFO L480 AbstractCegarLoop]: Abstraction has 157 states and 162 transitions. [2018-11-07 05:12:35,277 INFO L481 AbstractCegarLoop]: Interpolant automaton has 44 states. [2018-11-07 05:12:35,277 INFO L276 IsEmpty]: Start isEmpty. Operand 157 states and 162 transitions. [2018-11-07 05:12:35,284 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 156 [2018-11-07 05:12:35,284 INFO L367 BasicCegarLoop]: Found error trace [2018-11-07 05:12:35,285 INFO L375 BasicCegarLoop]: trace histogram [37, 36, 36, 31, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-07 05:12:35,285 INFO L423 AbstractCegarLoop]: === Iteration 16 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-07 05:12:35,285 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-07 05:12:35,285 INFO L82 PathProgramCache]: Analyzing trace with hash -1133922934, now seen corresponding path program 12 times [2018-11-07 05:12:35,285 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-07 05:12:35,286 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:12:35,286 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-11-07 05:12:35,286 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:12:35,286 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-07 05:12:35,303 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-07 05:12:36,183 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-07 05:12:36,183 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:12:36,184 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-07 05:12:36,184 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-11-07 05:12:36,184 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-11-07 05:12:36,184 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:12:36,184 INFO L194 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-07 05:12:36,198 INFO L103 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-11-07 05:12:36,199 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder TERMS_WITH_SMALL_CONSTANTS_FIRST (IT: FPandBP) [2018-11-07 05:12:36,240 INFO L249 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-11-07 05:12:36,241 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-11-07 05:12:36,244 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-07 05:12:36,291 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-07 05:12:36,291 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-07 05:12:38,827 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-07 05:12:38,847 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-07 05:12:38,847 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [39, 34, 34] total 71 [2018-11-07 05:12:38,847 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-07 05:12:38,848 INFO L459 AbstractCegarLoop]: Interpolant automaton has 39 states [2018-11-07 05:12:38,848 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 39 interpolants. [2018-11-07 05:12:38,850 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1359, Invalid=3611, Unknown=0, NotChecked=0, Total=4970 [2018-11-07 05:12:38,850 INFO L87 Difference]: Start difference. First operand 157 states and 162 transitions. Second operand 39 states. [2018-11-07 05:12:41,284 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-07 05:12:41,284 INFO L93 Difference]: Finished difference Result 203 states and 217 transitions. [2018-11-07 05:12:41,285 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 38 states. [2018-11-07 05:12:41,285 INFO L78 Accepts]: Start accepts. Automaton has 39 states. Word has length 155 [2018-11-07 05:12:41,285 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-07 05:12:41,286 INFO L225 Difference]: With dead ends: 203 [2018-11-07 05:12:41,286 INFO L226 Difference]: Without dead ends: 178 [2018-11-07 05:12:41,288 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-07 05:12:41,289 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 178 states. [2018-11-07 05:12:41,294 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 178 to 177. [2018-11-07 05:12:41,295 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 177 states. [2018-11-07 05:12:41,296 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 177 states to 177 states and 182 transitions. [2018-11-07 05:12:41,296 INFO L78 Accepts]: Start accepts. Automaton has 177 states and 182 transitions. Word has length 155 [2018-11-07 05:12:41,296 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-07 05:12:41,297 INFO L480 AbstractCegarLoop]: Abstraction has 177 states and 182 transitions. [2018-11-07 05:12:41,297 INFO L481 AbstractCegarLoop]: Interpolant automaton has 39 states. [2018-11-07 05:12:41,297 INFO L276 IsEmpty]: Start isEmpty. Operand 177 states and 182 transitions. [2018-11-07 05:12:41,299 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 176 [2018-11-07 05:12:41,299 INFO L367 BasicCegarLoop]: Found error trace [2018-11-07 05:12:41,299 INFO L375 BasicCegarLoop]: trace histogram [42, 41, 41, 36, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-07 05:12:41,299 INFO L423 AbstractCegarLoop]: === Iteration 17 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-07 05:12:41,299 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-07 05:12:41,300 INFO L82 PathProgramCache]: Analyzing trace with hash -718034286, now seen corresponding path program 13 times [2018-11-07 05:12:41,300 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-07 05:12:41,301 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:12:41,301 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-11-07 05:12:41,301 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:12:41,301 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-07 05:12:41,320 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-07 05:12:43,148 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-07 05:12:43,149 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:12:43,149 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-07 05:12:43,149 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-11-07 05:12:43,149 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-11-07 05:12:43,149 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:12:43,149 INFO L194 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-07 05:12:43,158 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-07 05:12:43,158 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-11-07 05:12:43,195 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-07 05:12:43,199 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-07 05:12:43,281 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-07 05:12:43,282 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-07 05:12:47,451 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-07 05:12:47,471 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-07 05:12:47,471 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [44, 39, 39] total 81 [2018-11-07 05:12:47,471 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-07 05:12:47,471 INFO L459 AbstractCegarLoop]: Interpolant automaton has 44 states [2018-11-07 05:12:47,472 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 44 interpolants. [2018-11-07 05:12:47,473 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1754, Invalid=4726, Unknown=0, NotChecked=0, Total=6480 [2018-11-07 05:12:47,474 INFO L87 Difference]: Start difference. First operand 177 states and 182 transitions. Second operand 44 states. [2018-11-07 05:12:50,842 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-07 05:12:50,843 INFO L93 Difference]: Finished difference Result 223 states and 237 transitions. [2018-11-07 05:12:50,843 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 43 states. [2018-11-07 05:12:50,843 INFO L78 Accepts]: Start accepts. Automaton has 44 states. Word has length 175 [2018-11-07 05:12:50,844 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-07 05:12:50,846 INFO L225 Difference]: With dead ends: 223 [2018-11-07 05:12:50,846 INFO L226 Difference]: Without dead ends: 198 [2018-11-07 05:12:50,849 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 394 GetRequests, 313 SyntacticMatches, 2 SemanticMatches, 79 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 5.7s TimeCoverageRelationStatistics Valid=1754, Invalid=4726, Unknown=0, NotChecked=0, Total=6480 [2018-11-07 05:12:50,850 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 198 states. [2018-11-07 05:12:50,855 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 198 to 197. [2018-11-07 05:12:50,855 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 197 states. [2018-11-07 05:12:50,856 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 197 states to 197 states and 202 transitions. [2018-11-07 05:12:50,857 INFO L78 Accepts]: Start accepts. Automaton has 197 states and 202 transitions. Word has length 175 [2018-11-07 05:12:50,857 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-07 05:12:50,857 INFO L480 AbstractCegarLoop]: Abstraction has 197 states and 202 transitions. [2018-11-07 05:12:50,857 INFO L481 AbstractCegarLoop]: Interpolant automaton has 44 states. [2018-11-07 05:12:50,857 INFO L276 IsEmpty]: Start isEmpty. Operand 197 states and 202 transitions. [2018-11-07 05:12:50,859 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 196 [2018-11-07 05:12:50,859 INFO L367 BasicCegarLoop]: Found error trace [2018-11-07 05:12:50,859 INFO L375 BasicCegarLoop]: trace histogram [47, 46, 46, 41, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-07 05:12:50,859 INFO L423 AbstractCegarLoop]: === Iteration 18 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-07 05:12:50,860 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-07 05:12:50,860 INFO L82 PathProgramCache]: Analyzing trace with hash 2000210842, now seen corresponding path program 14 times [2018-11-07 05:12:50,860 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-07 05:12:50,860 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:12:50,861 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-07 05:12:50,861 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:12:50,861 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-07 05:12:50,882 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-07 05:12:52,570 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-07 05:12:52,570 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:12:52,570 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-07 05:12:52,570 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-11-07 05:12:52,570 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-11-07 05:12:52,571 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:12:52,571 INFO L194 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-07 05:12:52,580 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-11-07 05:12:52,580 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST2 (IT: FPandBP) [2018-11-07 05:13:07,974 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 7 check-sat command(s) [2018-11-07 05:13:07,974 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-11-07 05:13:08,258 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-07 05:13:09,405 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-07 05:13:09,406 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-07 05:13:21,170 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-07 05:13:21,192 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-07 05:13:21,192 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [49, 13, 13] total 71 [2018-11-07 05:13:21,192 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-07 05:13:21,193 INFO L459 AbstractCegarLoop]: Interpolant automaton has 60 states [2018-11-07 05:13:21,193 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 60 interpolants. [2018-11-07 05:13:21,194 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=304, Invalid=4665, Unknown=1, NotChecked=0, Total=4970 [2018-11-07 05:13:21,195 INFO L87 Difference]: Start difference. First operand 197 states and 202 transitions. Second operand 60 states. [2018-11-07 05:13:28,448 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-07 05:13:28,448 INFO L93 Difference]: Finished difference Result 250 states and 266 transitions. [2018-11-07 05:13:28,448 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 60 states. [2018-11-07 05:13:28,448 INFO L78 Accepts]: Start accepts. Automaton has 60 states. Word has length 195 [2018-11-07 05:13:28,449 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-07 05:13:28,450 INFO L225 Difference]: With dead ends: 250 [2018-11-07 05:13:28,451 INFO L226 Difference]: Without dead ends: 222 [2018-11-07 05:13:28,452 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 488 GetRequests, 369 SyntacticMatches, 1 SemanticMatches, 118 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1312 ImplicationChecksByTransitivity, 15.9s TimeCoverageRelationStatistics Valid=979, Invalid=13300, Unknown=1, NotChecked=0, Total=14280 [2018-11-07 05:13:28,453 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 222 states. [2018-11-07 05:13:28,458 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 222 to 221. [2018-11-07 05:13:28,459 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 221 states. [2018-11-07 05:13:28,460 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 221 states to 221 states and 226 transitions. [2018-11-07 05:13:28,460 INFO L78 Accepts]: Start accepts. Automaton has 221 states and 226 transitions. Word has length 195 [2018-11-07 05:13:28,460 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-07 05:13:28,460 INFO L480 AbstractCegarLoop]: Abstraction has 221 states and 226 transitions. [2018-11-07 05:13:28,460 INFO L481 AbstractCegarLoop]: Interpolant automaton has 60 states. [2018-11-07 05:13:28,461 INFO L276 IsEmpty]: Start isEmpty. Operand 221 states and 226 transitions. [2018-11-07 05:13:28,462 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 220 [2018-11-07 05:13:28,462 INFO L367 BasicCegarLoop]: Found error trace [2018-11-07 05:13:28,462 INFO L375 BasicCegarLoop]: trace histogram [53, 52, 52, 46, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-07 05:13:28,462 INFO L423 AbstractCegarLoop]: === Iteration 19 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-07 05:13:28,462 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-07 05:13:28,463 INFO L82 PathProgramCache]: Analyzing trace with hash -808108724, now seen corresponding path program 15 times [2018-11-07 05:13:28,463 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-07 05:13:28,464 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:13:28,464 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-11-07 05:13:28,464 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:13:28,464 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-07 05:13:28,488 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-07 05:13:30,361 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-07 05:13:30,362 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:13:30,362 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-07 05:13:30,362 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-11-07 05:13:30,362 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-11-07 05:13:30,362 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:13:30,362 INFO L194 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-07 05:13:30,371 INFO L103 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-11-07 05:13:30,371 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder TERMS_WITH_SMALL_CONSTANTS_FIRST (IT: FPandBP) [2018-11-07 05:13:30,418 INFO L249 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-11-07 05:13:30,418 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-11-07 05:13:30,422 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-07 05:13:30,492 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-07 05:13:30,492 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-07 05:13:35,831 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-07 05:13:35,851 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-07 05:13:35,852 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [55, 49, 49] total 102 [2018-11-07 05:13:35,852 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-07 05:13:35,852 INFO L459 AbstractCegarLoop]: Interpolant automaton has 55 states [2018-11-07 05:13:35,853 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 55 interpolants. [2018-11-07 05:13:35,854 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=2744, Invalid=7558, Unknown=0, NotChecked=0, Total=10302 [2018-11-07 05:13:35,854 INFO L87 Difference]: Start difference. First operand 221 states and 226 transitions. Second operand 55 states. [2018-11-07 05:13:40,793 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-07 05:13:40,794 INFO L93 Difference]: Finished difference Result 275 states and 290 transitions. [2018-11-07 05:13:40,794 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 54 states. [2018-11-07 05:13:40,794 INFO L78 Accepts]: Start accepts. Automaton has 55 states. Word has length 219 [2018-11-07 05:13:40,795 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-07 05:13:40,797 INFO L225 Difference]: With dead ends: 275 [2018-11-07 05:13:40,797 INFO L226 Difference]: Without dead ends: 246 [2018-11-07 05:13:40,798 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 493 GetRequests, 391 SyntacticMatches, 2 SemanticMatches, 100 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 6.9s TimeCoverageRelationStatistics Valid=2744, Invalid=7558, Unknown=0, NotChecked=0, Total=10302 [2018-11-07 05:13:40,798 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 246 states. [2018-11-07 05:13:40,805 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 246 to 245. [2018-11-07 05:13:40,805 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 245 states. [2018-11-07 05:13:40,806 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 245 states to 245 states and 250 transitions. [2018-11-07 05:13:40,806 INFO L78 Accepts]: Start accepts. Automaton has 245 states and 250 transitions. Word has length 219 [2018-11-07 05:13:40,806 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-07 05:13:40,807 INFO L480 AbstractCegarLoop]: Abstraction has 245 states and 250 transitions. [2018-11-07 05:13:40,807 INFO L481 AbstractCegarLoop]: Interpolant automaton has 55 states. [2018-11-07 05:13:40,807 INFO L276 IsEmpty]: Start isEmpty. Operand 245 states and 250 transitions. [2018-11-07 05:13:40,808 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 244 [2018-11-07 05:13:40,808 INFO L367 BasicCegarLoop]: Found error trace [2018-11-07 05:13:40,808 INFO L375 BasicCegarLoop]: trace histogram [59, 58, 58, 52, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-07 05:13:40,808 INFO L423 AbstractCegarLoop]: === Iteration 20 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-07 05:13:40,809 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-07 05:13:40,809 INFO L82 PathProgramCache]: Analyzing trace with hash -1414173252, now seen corresponding path program 16 times [2018-11-07 05:13:40,809 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-07 05:13:40,810 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:13:40,810 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-11-07 05:13:40,810 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:13:40,810 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-07 05:13:40,836 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-07 05:13:42,737 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-07 05:13:42,737 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:13:42,737 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-07 05:13:42,737 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-11-07 05:13:42,738 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-11-07 05:13:42,738 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:13:42,738 INFO L194 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-07 05:13:42,747 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-07 05:13:42,747 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-11-07 05:13:42,794 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-07 05:13:42,798 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-07 05:13:42,930 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-07 05:13:42,930 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-07 05:13:49,298 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-07 05:13:49,318 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-07 05:13:49,318 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [61, 55, 55] total 114 [2018-11-07 05:13:49,318 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-07 05:13:49,319 INFO L459 AbstractCegarLoop]: Interpolant automaton has 61 states [2018-11-07 05:13:49,319 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 61 interpolants. [2018-11-07 05:13:49,320 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=3410, Invalid=9472, Unknown=0, NotChecked=0, Total=12882 [2018-11-07 05:13:49,320 INFO L87 Difference]: Start difference. First operand 245 states and 250 transitions. Second operand 61 states. [2018-11-07 05:13:55,361 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-07 05:13:55,361 INFO L93 Difference]: Finished difference Result 299 states and 314 transitions. [2018-11-07 05:13:55,362 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 60 states. [2018-11-07 05:13:55,362 INFO L78 Accepts]: Start accepts. Automaton has 61 states. Word has length 243 [2018-11-07 05:13:55,362 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-07 05:13:55,364 INFO L225 Difference]: With dead ends: 299 [2018-11-07 05:13:55,364 INFO L226 Difference]: Without dead ends: 270 [2018-11-07 05:13:55,365 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 547 GetRequests, 433 SyntacticMatches, 2 SemanticMatches, 112 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 8.0s TimeCoverageRelationStatistics Valid=3410, Invalid=9472, Unknown=0, NotChecked=0, Total=12882 [2018-11-07 05:13:55,366 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 270 states. [2018-11-07 05:13:55,373 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 270 to 269. [2018-11-07 05:13:55,373 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 269 states. [2018-11-07 05:13:55,374 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 269 states to 269 states and 274 transitions. [2018-11-07 05:13:55,374 INFO L78 Accepts]: Start accepts. Automaton has 269 states and 274 transitions. Word has length 243 [2018-11-07 05:13:55,375 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-07 05:13:55,375 INFO L480 AbstractCegarLoop]: Abstraction has 269 states and 274 transitions. [2018-11-07 05:13:55,375 INFO L481 AbstractCegarLoop]: Interpolant automaton has 61 states. [2018-11-07 05:13:55,375 INFO L276 IsEmpty]: Start isEmpty. Operand 269 states and 274 transitions. [2018-11-07 05:13:55,377 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 268 [2018-11-07 05:13:55,377 INFO L367 BasicCegarLoop]: Found error trace [2018-11-07 05:13:55,377 INFO L375 BasicCegarLoop]: trace histogram [65, 64, 64, 58, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-07 05:13:55,377 INFO L423 AbstractCegarLoop]: === Iteration 21 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-07 05:13:55,377 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-07 05:13:55,378 INFO L82 PathProgramCache]: Analyzing trace with hash -886616532, now seen corresponding path program 17 times [2018-11-07 05:13:55,378 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-07 05:13:55,378 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:13:55,378 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-07 05:13:55,379 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:13:55,379 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-07 05:13:55,408 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-07 05:13:58,413 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-07 05:13:58,413 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:13:58,413 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-07 05:13:58,413 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-11-07 05:13:58,413 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-11-07 05:13:58,413 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:13:58,414 INFO L194 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-07 05:13:58,425 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-11-07 05:13:58,425 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST2 (IT: FPandBP) [2018-11-07 05:14:39,318 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 9 check-sat command(s) [2018-11-07 05:14:39,318 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-11-07 05:14:40,155 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-07 05:14:46,507 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-07 05:14:46,508 INFO L316 TraceCheckSpWp]: Computing backward predicates... Received shutdown request... [2018-11-07 05:15:41,603 WARN L187 SmtUtils]: Removed 1 from assertion stack [2018-11-07 05:15:41,603 INFO L177 TraceCheckSpWp]: Timeout while computing interpolants [2018-11-07 05:15:41,804 WARN L521 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 20 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-11-07 05:15:41,804 WARN L549 AbstractCegarLoop]: Verification canceled [2018-11-07 05:15:41,810 WARN L205 ceAbstractionStarter]: Timeout [2018-11-07 05:15:41,810 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 07.11 05:15:41 BoogieIcfgContainer [2018-11-07 05:15:41,810 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2018-11-07 05:15:41,811 INFO L168 Benchmark]: Toolchain (without parser) took 267371.67 ms. Allocated memory was 1.6 GB in the beginning and 2.5 GB in the end (delta: 900.7 MB). Free memory was 1.4 GB in the beginning and 1.8 GB in the end (delta: -365.0 MB). Peak memory consumption was 535.8 MB. Max. memory is 7.1 GB. [2018-11-07 05:15:41,812 INFO L168 Benchmark]: CDTParser took 0.20 ms. Allocated memory is still 1.6 GB. Free memory is still 1.5 GB. There was no memory consumed. Max. memory is 7.1 GB. [2018-11-07 05:15:41,813 INFO L168 Benchmark]: CACSL2BoogieTranslator took 311.76 ms. Allocated memory is still 1.6 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-07 05:15:41,813 INFO L168 Benchmark]: Boogie Procedure Inliner took 19.40 ms. Allocated memory is still 1.6 GB. Free memory is still 1.4 GB. There was no memory consumed. Max. memory is 7.1 GB. [2018-11-07 05:15:41,814 INFO L168 Benchmark]: Boogie Preprocessor took 19.56 ms. Allocated memory is still 1.6 GB. Free memory is still 1.4 GB. There was no memory consumed. Max. memory is 7.1 GB. [2018-11-07 05:15:41,814 INFO L168 Benchmark]: RCFGBuilder took 377.35 ms. Allocated memory was 1.6 GB in the beginning and 2.3 GB in the end (delta: 759.2 MB). Free memory was 1.4 GB in the beginning and 2.2 GB in the end (delta: -813.0 MB). Peak memory consumption was 26.4 MB. Max. memory is 7.1 GB. [2018-11-07 05:15:41,815 INFO L168 Benchmark]: TraceAbstraction took 266639.21 ms. Allocated memory was 2.3 GB in the beginning and 2.5 GB in the end (delta: 141.6 MB). Free memory was 2.2 GB in the beginning and 1.8 GB in the end (delta: 437.4 MB). Peak memory consumption was 579.0 MB. Max. memory is 7.1 GB. [2018-11-07 05:15:41,819 INFO L336 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.20 ms. Allocated memory is still 1.6 GB. Free memory is still 1.5 GB. There was no memory consumed. Max. memory is 7.1 GB. * CACSL2BoogieTranslator took 311.76 ms. Allocated memory is still 1.6 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 19.40 ms. Allocated memory is still 1.6 GB. Free memory is still 1.4 GB. There was no memory consumed. Max. memory is 7.1 GB. * Boogie Preprocessor took 19.56 ms. Allocated memory is still 1.6 GB. Free memory is still 1.4 GB. There was no memory consumed. Max. memory is 7.1 GB. * RCFGBuilder took 377.35 ms. Allocated memory was 1.6 GB in the beginning and 2.3 GB in the end (delta: 759.2 MB). Free memory was 1.4 GB in the beginning and 2.2 GB in the end (delta: -813.0 MB). Peak memory consumption was 26.4 MB. Max. memory is 7.1 GB. * TraceAbstraction took 266639.21 ms. Allocated memory was 2.3 GB in the beginning and 2.5 GB in the end (delta: 141.6 MB). Free memory was 2.2 GB in the beginning and 1.8 GB in the end (delta: 437.4 MB). Peak memory consumption was 579.0 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 PredicateUnifier was unifying predicates,while SimplifyDDAWithTimeout was simplifying term of DAG size 25. - StatisticsResult: Ultimate Automizer benchmark data CFG has 4 procedures, 21 locations, 1 error locations. TIMEOUT Result, 266.5s OverallTime, 21 OverallIterations, 65 TraceHistogramMax, 39.8s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 650 SDtfs, 1221 SDslu, 18397 SDs, 0 SdLazy, 49086 SolverSat, 400 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 28.5s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 4146 GetRequests, 3230 SyntacticMatches, 28 SemanticMatches, 888 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2405 ImplicationChecksByTransitivity, 71.1s 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, 1.2s 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, 47.6s SatisfiabilityAnalysisTime, 69.7s InterpolantComputationTime, 3585 NumberOfCodeBlocks, 3213 NumberOfCodeBlocksAsserted, 62 NumberOfCheckSat, 5311 ConstructedInterpolants, 452 QuantifiedInterpolants, 6626339 SizeOfPredicates, 39 NumberOfNonLiveVariables, 2113 ConjunctsInSsa, 630 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