java -Xmx6000000000 -jar ./plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data ./data --generate-csv --csv-dir ../../../releaseScripts/default/UAutomizer-linux/csv -tc ../../../trunk/examples/toolchains/AutomizerC.xml -s ../../../trunk/examples/settings/ai/eq-bench/mempurity-32bit-Automizer_Camel+AI_EQ.epf -i ../../../trunk/examples/svcomp/memsafety/lockfree-3.3_false-valid-memtrack.i -------------------------------------------------------------------------------- This is Ultimate 0.1.23-2f49842 [2018-01-20 21:58:39,749 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-01-20 21:58:39,751 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-01-20 21:58:39,767 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-01-20 21:58:39,767 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-01-20 21:58:39,768 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-01-20 21:58:39,770 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-01-20 21:58:39,772 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-01-20 21:58:39,774 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-01-20 21:58:39,775 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-01-20 21:58:39,776 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-01-20 21:58:39,777 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-01-20 21:58:39,778 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-01-20 21:58:39,779 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-01-20 21:58:39,780 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-01-20 21:58:39,783 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-01-20 21:58:39,785 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-01-20 21:58:39,788 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-01-20 21:58:39,789 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-01-20 21:58:39,791 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-01-20 21:58:39,793 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-01-20 21:58:39,793 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-01-20 21:58:39,794 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-01-20 21:58:39,795 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-01-20 21:58:39,796 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-01-20 21:58:39,797 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-01-20 21:58:39,797 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-01-20 21:58:39,798 INFO L177 SettingsManager]: PEA to Boogie provides no preferences, ignoring... [2018-01-20 21:58:39,798 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-01-20 21:58:39,798 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-01-20 21:58:39,799 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-01-20 21:58:39,800 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/ai/eq-bench/mempurity-32bit-Automizer_Camel+AI_EQ.epf [2018-01-20 21:58:39,810 INFO L110 SettingsManager]: Loading preferences was successful [2018-01-20 21:58:39,810 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-01-20 21:58:39,811 INFO L131 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2018-01-20 21:58:39,811 INFO L133 SettingsManager]: * to procedures, called more than once=true [2018-01-20 21:58:39,811 INFO L131 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2018-01-20 21:58:39,811 INFO L133 SettingsManager]: * Abstract domain for RCFG-of-the-future=VPDomain [2018-01-20 21:58:39,812 INFO L133 SettingsManager]: * Use the RCFG-of-the-future interface=true [2018-01-20 21:58:39,812 INFO L131 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2018-01-20 21:58:39,812 INFO L133 SettingsManager]: * sizeof long=4 [2018-01-20 21:58:39,813 INFO L133 SettingsManager]: * Check unreachability of error function in SV-COMP mode=false [2018-01-20 21:58:39,813 INFO L133 SettingsManager]: * Check allocation purity=true [2018-01-20 21:58:39,813 INFO L133 SettingsManager]: * Overapproximate operations on floating types=true [2018-01-20 21:58:39,813 INFO L133 SettingsManager]: * sizeof POINTER=4 [2018-01-20 21:58:39,813 INFO L133 SettingsManager]: * Check division by zero=IGNORE [2018-01-20 21:58:39,814 INFO L133 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2018-01-20 21:58:39,814 INFO L133 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2018-01-20 21:58:39,814 INFO L133 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2018-01-20 21:58:39,814 INFO L133 SettingsManager]: * sizeof long double=12 [2018-01-20 21:58:39,814 INFO L133 SettingsManager]: * Check if freed pointer was valid=false [2018-01-20 21:58:39,815 INFO L133 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2018-01-20 21:58:39,815 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-01-20 21:58:39,815 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-01-20 21:58:39,815 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-01-20 21:58:39,815 INFO L133 SettingsManager]: * Add additional assume for each assert=false [2018-01-20 21:58:39,816 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-01-20 21:58:39,816 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-01-20 21:58:39,816 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-01-20 21:58:39,816 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-01-20 21:58:39,816 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-01-20 21:58:39,817 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-01-20 21:58:39,817 INFO L133 SettingsManager]: * Stop after first violation was found=false [2018-01-20 21:58:39,817 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-01-20 21:58:39,817 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-01-20 21:58:39,817 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-01-20 21:58:39,817 INFO L133 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2018-01-20 21:58:39,818 INFO L131 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2018-01-20 21:58:39,819 INFO L133 SettingsManager]: * TransformationType=HEAP_SEPARATOR [2018-01-20 21:58:39,855 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2018-01-20 21:58:39,868 INFO L266 ainManager$Toolchain]: [Toolchain 1]: Parser(s) successfully initialized [2018-01-20 21:58:39,873 INFO L222 ainManager$Toolchain]: [Toolchain 1]: Toolchain data selected. [2018-01-20 21:58:39,874 INFO L271 PluginConnector]: Initializing CDTParser... [2018-01-20 21:58:39,875 INFO L276 PluginConnector]: CDTParser initialized [2018-01-20 21:58:39,875 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/memsafety/lockfree-3.3_false-valid-memtrack.i [2018-01-20 21:58:40,052 INFO L304 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2018-01-20 21:58:40,057 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2018-01-20 21:58:40,058 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2018-01-20 21:58:40,059 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2018-01-20 21:58:40,066 INFO L276 PluginConnector]: CACSL2BoogieTranslator initialized [2018-01-20 21:58:40,068 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 20.01 09:58:40" (1/1) ... [2018-01-20 21:58:40,072 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@4454cf94 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.01 09:58:40, skipping insertion in model container [2018-01-20 21:58:40,072 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 20.01 09:58:40" (1/1) ... [2018-01-20 21:58:40,094 INFO L153 Dispatcher]: Using SV-COMP mode [2018-01-20 21:58:40,137 INFO L153 Dispatcher]: Using SV-COMP mode [2018-01-20 21:58:40,285 INFO L450 PostProcessor]: Settings: Checked method=main [2018-01-20 21:58:40,306 INFO L450 PostProcessor]: Settings: Checked method=main [2018-01-20 21:58:40,316 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.01 09:58:40 WrapperNode [2018-01-20 21:58:40,316 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2018-01-20 21:58:40,317 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2018-01-20 21:58:40,317 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2018-01-20 21:58:40,317 INFO L276 PluginConnector]: Boogie Preprocessor initialized [2018-01-20 21:58:40,331 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.01 09:58:40" (1/1) ... [2018-01-20 21:58:40,331 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.01 09:58:40" (1/1) ... [2018-01-20 21:58:40,340 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.01 09:58:40" (1/1) ... [2018-01-20 21:58:40,340 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.01 09:58:40" (1/1) ... [2018-01-20 21:58:40,345 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.01 09:58:40" (1/1) ... [2018-01-20 21:58:40,349 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.01 09:58:40" (1/1) ... [2018-01-20 21:58:40,350 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.01 09:58:40" (1/1) ... [2018-01-20 21:58:40,352 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2018-01-20 21:58:40,352 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2018-01-20 21:58:40,353 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2018-01-20 21:58:40,353 INFO L276 PluginConnector]: RCFGBuilder initialized [2018-01-20 21:58:40,353 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.01 09:58:40" (1/1) ... No working directory specified, using /storage/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-01-20 21:58:40,403 INFO L136 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2018-01-20 21:58:40,404 INFO L136 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2018-01-20 21:58:40,404 INFO L136 BoogieDeclarations]: Found implementation of procedure push [2018-01-20 21:58:40,404 INFO L136 BoogieDeclarations]: Found implementation of procedure pop [2018-01-20 21:58:40,404 INFO L136 BoogieDeclarations]: Found implementation of procedure main [2018-01-20 21:58:40,404 INFO L128 BoogieDeclarations]: Found specification of procedure write~int [2018-01-20 21:58:40,405 INFO L128 BoogieDeclarations]: Found specification of procedure read~int [2018-01-20 21:58:40,405 INFO L128 BoogieDeclarations]: Found specification of procedure write~$Pointer$ [2018-01-20 21:58:40,405 INFO L128 BoogieDeclarations]: Found specification of procedure read~$Pointer$ [2018-01-20 21:58:40,405 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.free [2018-01-20 21:58:40,405 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2018-01-20 21:58:40,405 INFO L128 BoogieDeclarations]: Found specification of procedure #Ultimate.alloc [2018-01-20 21:58:40,405 INFO L128 BoogieDeclarations]: Found specification of procedure malloc [2018-01-20 21:58:40,406 INFO L128 BoogieDeclarations]: Found specification of procedure free [2018-01-20 21:58:40,406 INFO L128 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2018-01-20 21:58:40,406 INFO L128 BoogieDeclarations]: Found specification of procedure push [2018-01-20 21:58:40,406 INFO L128 BoogieDeclarations]: Found specification of procedure pop [2018-01-20 21:58:40,406 INFO L128 BoogieDeclarations]: Found specification of procedure main [2018-01-20 21:58:40,406 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2018-01-20 21:58:40,407 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2018-01-20 21:58:40,705 INFO L257 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2018-01-20 21:58:40,705 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.01 09:58:40 BoogieIcfgContainer [2018-01-20 21:58:40,706 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2018-01-20 21:58:40,706 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2018-01-20 21:58:40,706 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2018-01-20 21:58:40,708 INFO L276 PluginConnector]: TraceAbstraction initialized [2018-01-20 21:58:40,708 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 20.01 09:58:40" (1/3) ... [2018-01-20 21:58:40,709 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5385e2 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 20.01 09:58:40, skipping insertion in model container [2018-01-20 21:58:40,710 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.01 09:58:40" (2/3) ... [2018-01-20 21:58:40,710 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5385e2 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 20.01 09:58:40, skipping insertion in model container [2018-01-20 21:58:40,710 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.01 09:58:40" (3/3) ... [2018-01-20 21:58:40,712 INFO L105 eAbstractionObserver]: Analyzing ICFG lockfree-3.3_false-valid-memtrack.i [2018-01-20 21:58:40,722 INFO L130 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-01-20 21:58:40,731 INFO L142 ceAbstractionStarter]: Appying trace abstraction to program that has 5 error locations. [2018-01-20 21:58:40,774 INFO L322 AbstractCegarLoop]: Interprodecural is true [2018-01-20 21:58:40,774 INFO L323 AbstractCegarLoop]: Hoare is true [2018-01-20 21:58:40,774 INFO L324 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-01-20 21:58:40,774 INFO L325 AbstractCegarLoop]: Backedges is TWOTRACK [2018-01-20 21:58:40,774 INFO L326 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-01-20 21:58:40,775 INFO L327 AbstractCegarLoop]: Difference is false [2018-01-20 21:58:40,775 INFO L328 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-01-20 21:58:40,775 INFO L333 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == popErr0EnsuresViolation======== [2018-01-20 21:58:40,776 INFO L87 2NestedWordAutomaton]: Mode: main mode - execution starts in main procedure [2018-01-20 21:58:40,797 INFO L276 IsEmpty]: Start isEmpty. Operand 62 states. [2018-01-20 21:58:40,804 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2018-01-20 21:58:40,805 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 21:58:40,806 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-20 21:58:40,806 INFO L371 AbstractCegarLoop]: === Iteration 1 === [popErr0EnsuresViolation]=== [2018-01-20 21:58:40,810 INFO L82 PathProgramCache]: Analyzing trace with hash 816843792, now seen corresponding path program 1 times [2018-01-20 21:58:40,811 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 21:58:40,812 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 21:58:40,856 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:58:40,857 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 21:58:40,857 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:58:40,933 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 21:58:40,943 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 21:58:41,005 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-20 21:58:41,008 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-20 21:58:41,008 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [1] imperfect sequences [] total 1 [2018-01-20 21:58:41,009 INFO L409 AbstractCegarLoop]: Interpolant automaton has 2 states [2018-01-20 21:58:41,021 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2018-01-20 21:58:41,021 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2018-01-20 21:58:41,023 INFO L87 Difference]: Start difference. First operand 62 states. Second operand 2 states. [2018-01-20 21:58:41,119 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 21:58:41,120 INFO L93 Difference]: Finished difference Result 75 states and 95 transitions. [2018-01-20 21:58:41,120 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2018-01-20 21:58:41,121 INFO L78 Accepts]: Start accepts. Automaton has 2 states. Word has length 14 [2018-01-20 21:58:41,121 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 21:58:41,127 INFO L225 Difference]: With dead ends: 75 [2018-01-20 21:58:41,127 INFO L226 Difference]: Without dead ends: 0 [2018-01-20 21:58:41,130 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 1 GetRequests, 1 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-01-20 21:58:41,142 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 0 states. [2018-01-20 21:58:41,147 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 0 to 0. [2018-01-20 21:58:41,148 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 0 states. [2018-01-20 21:58:41,148 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 0 states to 0 states and 0 transitions. [2018-01-20 21:58:41,149 INFO L78 Accepts]: Start accepts. Automaton has 0 states and 0 transitions. Word has length 14 [2018-01-20 21:58:41,149 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 21:58:41,150 INFO L432 AbstractCegarLoop]: Abstraction has 0 states and 0 transitions. [2018-01-20 21:58:41,150 INFO L433 AbstractCegarLoop]: Interpolant automaton has 2 states. [2018-01-20 21:58:41,150 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2018-01-20 21:58:41,150 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2018-01-20 21:58:41,153 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends 0 states and 0 transitions. [2018-01-20 21:58:41,175 INFO L401 ceAbstractionStarter]: For program point L681(line 681) no Hoare annotation was computed. [2018-01-20 21:58:41,176 INFO L401 ceAbstractionStarter]: For program point L680(line 680) no Hoare annotation was computed. [2018-01-20 21:58:41,176 INFO L401 ceAbstractionStarter]: For program point popEXIT(lines 660 687) no Hoare annotation was computed. [2018-01-20 21:58:41,176 INFO L401 ceAbstractionStarter]: For program point L663(lines 663 686) no Hoare annotation was computed. [2018-01-20 21:58:41,176 INFO L404 ceAbstractionStarter]: At program point popENTRY(lines 660 687) the Hoare annotation is: true [2018-01-20 21:58:41,176 INFO L401 ceAbstractionStarter]: For program point L682(line 682) no Hoare annotation was computed. [2018-01-20 21:58:41,177 INFO L401 ceAbstractionStarter]: For program point L667(line 667) no Hoare annotation was computed. [2018-01-20 21:58:41,177 INFO L401 ceAbstractionStarter]: For program point L672'(line 672) no Hoare annotation was computed. [2018-01-20 21:58:41,177 INFO L401 ceAbstractionStarter]: For program point L664(line 664) no Hoare annotation was computed. [2018-01-20 21:58:41,177 INFO L401 ceAbstractionStarter]: For program point L682'(line 682) no Hoare annotation was computed. [2018-01-20 21:58:41,177 INFO L401 ceAbstractionStarter]: For program point L668(lines 668 669) no Hoare annotation was computed. [2018-01-20 21:58:41,177 INFO L401 ceAbstractionStarter]: For program point L674(line 674) no Hoare annotation was computed. [2018-01-20 21:58:41,177 INFO L401 ceAbstractionStarter]: For program point L672(line 672) no Hoare annotation was computed. [2018-01-20 21:58:41,178 INFO L401 ceAbstractionStarter]: For program point L671(line 671) no Hoare annotation was computed. [2018-01-20 21:58:41,178 INFO L401 ceAbstractionStarter]: For program point L675(lines 675 678) no Hoare annotation was computed. [2018-01-20 21:58:41,178 INFO L401 ceAbstractionStarter]: For program point L675''(lines 675 678) no Hoare annotation was computed. [2018-01-20 21:58:41,178 INFO L401 ceAbstractionStarter]: For program point L681'(line 681) no Hoare annotation was computed. [2018-01-20 21:58:41,178 INFO L401 ceAbstractionStarter]: For program point popErr0EnsuresViolation(lines 660 687) no Hoare annotation was computed. [2018-01-20 21:58:41,178 INFO L401 ceAbstractionStarter]: For program point ULTIMATE.initErr0EnsuresViolation(lines 1 707) no Hoare annotation was computed. [2018-01-20 21:58:41,178 INFO L401 ceAbstractionStarter]: For program point ULTIMATE.initEXIT(lines 1 707) no Hoare annotation was computed. [2018-01-20 21:58:41,179 INFO L404 ceAbstractionStarter]: At program point ULTIMATE.initENTRY(lines 1 707) the Hoare annotation is: true [2018-01-20 21:58:41,179 INFO L401 ceAbstractionStarter]: For program point ULTIMATE.initFINAL(lines 1 707) no Hoare annotation was computed. [2018-01-20 21:58:41,179 INFO L404 ceAbstractionStarter]: At program point ULTIMATE.startENTRY(lines 1 707) the Hoare annotation is: true [2018-01-20 21:58:41,179 INFO L401 ceAbstractionStarter]: For program point ULTIMATE.startFINAL(lines 1 707) no Hoare annotation was computed. [2018-01-20 21:58:41,179 INFO L404 ceAbstractionStarter]: At program point L1(lines 1 707) the Hoare annotation is: true [2018-01-20 21:58:41,179 INFO L401 ceAbstractionStarter]: For program point ULTIMATE.startErr0EnsuresViolation(lines 1 707) no Hoare annotation was computed. [2018-01-20 21:58:41,180 INFO L401 ceAbstractionStarter]: For program point ULTIMATE.startEXIT(lines 1 707) no Hoare annotation was computed. [2018-01-20 21:58:41,180 INFO L404 ceAbstractionStarter]: At program point L694'(line 694) the Hoare annotation is: true [2018-01-20 21:58:41,180 INFO L401 ceAbstractionStarter]: For program point L690'(line 690) no Hoare annotation was computed. [2018-01-20 21:58:41,180 INFO L401 ceAbstractionStarter]: For program point L697'(line 697) no Hoare annotation was computed. [2018-01-20 21:58:41,180 INFO L401 ceAbstractionStarter]: For program point L696'''(lines 696 700) no Hoare annotation was computed. [2018-01-20 21:58:41,180 INFO L401 ceAbstractionStarter]: For program point L690'''(line 690) no Hoare annotation was computed. [2018-01-20 21:58:41,180 INFO L401 ceAbstractionStarter]: For program point mainErr0EnsuresViolation(lines 688 707) no Hoare annotation was computed. [2018-01-20 21:58:41,181 INFO L404 ceAbstractionStarter]: At program point L692(line 692) the Hoare annotation is: true [2018-01-20 21:58:41,181 INFO L401 ceAbstractionStarter]: For program point L691(lines 691 694) no Hoare annotation was computed. [2018-01-20 21:58:41,181 INFO L401 ceAbstractionStarter]: For program point L690(lines 690 695) no Hoare annotation was computed. [2018-01-20 21:58:41,181 INFO L401 ceAbstractionStarter]: For program point L696(lines 696 700) no Hoare annotation was computed. [2018-01-20 21:58:41,181 INFO L401 ceAbstractionStarter]: For program point L696''(lines 696 700) no Hoare annotation was computed. [2018-01-20 21:58:41,181 INFO L404 ceAbstractionStarter]: At program point L694(line 694) the Hoare annotation is: true [2018-01-20 21:58:41,182 INFO L401 ceAbstractionStarter]: For program point mainFINAL(lines 688 707) no Hoare annotation was computed. [2018-01-20 21:58:41,182 INFO L401 ceAbstractionStarter]: For program point L698(line 698) no Hoare annotation was computed. [2018-01-20 21:58:41,182 INFO L401 ceAbstractionStarter]: For program point L697(line 697) no Hoare annotation was computed. [2018-01-20 21:58:41,182 INFO L401 ceAbstractionStarter]: For program point mainEXIT(lines 688 707) no Hoare annotation was computed. [2018-01-20 21:58:41,182 INFO L401 ceAbstractionStarter]: For program point L698'(line 698) no Hoare annotation was computed. [2018-01-20 21:58:41,182 INFO L401 ceAbstractionStarter]: For program point L640(line 640) no Hoare annotation was computed. [2018-01-20 21:58:41,182 INFO L401 ceAbstractionStarter]: For program point L644(line 644) no Hoare annotation was computed. [2018-01-20 21:58:41,182 INFO L401 ceAbstractionStarter]: For program point L643(line 643) no Hoare annotation was computed. [2018-01-20 21:58:41,183 INFO L401 ceAbstractionStarter]: For program point L647''(lines 647 650) no Hoare annotation was computed. [2018-01-20 21:58:41,183 INFO L401 ceAbstractionStarter]: For program point L647(lines 647 650) no Hoare annotation was computed. [2018-01-20 21:58:41,183 INFO L401 ceAbstractionStarter]: For program point L646(line 646) no Hoare annotation was computed. [2018-01-20 21:58:41,183 INFO L401 ceAbstractionStarter]: For program point L633'(line 633) no Hoare annotation was computed. [2018-01-20 21:58:41,183 INFO L404 ceAbstractionStarter]: At program point pushENTRY(lines 629 656) the Hoare annotation is: true [2018-01-20 21:58:41,183 INFO L401 ceAbstractionStarter]: For program point L652(line 652) no Hoare annotation was computed. [2018-01-20 21:58:41,183 INFO L401 ceAbstractionStarter]: For program point pushErr0EnsuresViolation(lines 629 656) no Hoare annotation was computed. [2018-01-20 21:58:41,184 INFO L401 ceAbstractionStarter]: For program point L634(line 634) no Hoare annotation was computed. [2018-01-20 21:58:41,184 INFO L401 ceAbstractionStarter]: For program point L633(line 633) no Hoare annotation was computed. [2018-01-20 21:58:41,184 INFO L401 ceAbstractionStarter]: For program point L632(line 632) no Hoare annotation was computed. [2018-01-20 21:58:41,184 INFO L401 ceAbstractionStarter]: For program point L631(lines 631 655) no Hoare annotation was computed. [2018-01-20 21:58:41,184 INFO L401 ceAbstractionStarter]: For program point L638(line 638) no Hoare annotation was computed. [2018-01-20 21:58:41,184 INFO L401 ceAbstractionStarter]: For program point pushEXIT(lines 629 656) no Hoare annotation was computed. [2018-01-20 21:58:41,184 INFO L401 ceAbstractionStarter]: For program point L637(line 637) no Hoare annotation was computed. [2018-01-20 21:58:41,185 INFO L401 ceAbstractionStarter]: For program point L634'(line 634) no Hoare annotation was computed. [2018-01-20 21:58:41,189 INFO L322 AbstractCegarLoop]: Interprodecural is true [2018-01-20 21:58:41,189 INFO L323 AbstractCegarLoop]: Hoare is true [2018-01-20 21:58:41,189 INFO L324 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-01-20 21:58:41,189 INFO L325 AbstractCegarLoop]: Backedges is TWOTRACK [2018-01-20 21:58:41,189 INFO L326 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-01-20 21:58:41,189 INFO L327 AbstractCegarLoop]: Difference is false [2018-01-20 21:58:41,189 INFO L328 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-01-20 21:58:41,190 INFO L333 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == ULTIMATE.initErr0EnsuresViolation======== [2018-01-20 21:58:41,190 INFO L87 2NestedWordAutomaton]: Mode: main mode - execution starts in main procedure [2018-01-20 21:58:41,192 INFO L276 IsEmpty]: Start isEmpty. Operand 62 states. [2018-01-20 21:58:41,193 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 4 [2018-01-20 21:58:41,193 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 21:58:41,193 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1] [2018-01-20 21:58:41,193 INFO L371 AbstractCegarLoop]: === Iteration 1 === [ULTIMATE.initErr0EnsuresViolation]=== [2018-01-20 21:58:41,193 INFO L82 PathProgramCache]: Analyzing trace with hash 169454, now seen corresponding path program 1 times [2018-01-20 21:58:41,193 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 21:58:41,194 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 21:58:41,195 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:58:41,195 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 21:58:41,195 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:58:41,208 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2018-01-20 21:58:41,221 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2018-01-20 21:58:41,245 INFO L381 BasicCegarLoop]: Counterexample might be feasible [2018-01-20 21:58:41,254 WARN L343 cessorBacktranslator]: Generated EnsuresSpecification ensures #valid == old(#valid); is not ensure(true) [2018-01-20 21:58:41,266 INFO L322 AbstractCegarLoop]: Interprodecural is true [2018-01-20 21:58:41,266 INFO L323 AbstractCegarLoop]: Hoare is true [2018-01-20 21:58:41,266 INFO L324 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-01-20 21:58:41,266 INFO L325 AbstractCegarLoop]: Backedges is TWOTRACK [2018-01-20 21:58:41,266 INFO L326 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-01-20 21:58:41,266 INFO L327 AbstractCegarLoop]: Difference is false [2018-01-20 21:58:41,267 INFO L328 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-01-20 21:58:41,267 INFO L333 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == ULTIMATE.startErr0EnsuresViolation======== [2018-01-20 21:58:41,267 INFO L87 2NestedWordAutomaton]: Mode: main mode - execution starts in main procedure [2018-01-20 21:58:41,269 INFO L276 IsEmpty]: Start isEmpty. Operand 62 states. [2018-01-20 21:58:41,270 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2018-01-20 21:58:41,270 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 21:58:41,270 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-20 21:58:41,270 INFO L371 AbstractCegarLoop]: === Iteration 1 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-20 21:58:41,271 INFO L82 PathProgramCache]: Analyzing trace with hash 1316586551, now seen corresponding path program 1 times [2018-01-20 21:58:41,271 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 21:58:41,271 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 21:58:41,272 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:58:41,272 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 21:58:41,272 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:58:41,289 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 21:58:41,290 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 21:58:41,308 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-20 21:58:41,308 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-20 21:58:41,308 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2018-01-20 21:58:41,309 INFO L409 AbstractCegarLoop]: Interpolant automaton has 2 states [2018-01-20 21:58:41,309 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2018-01-20 21:58:41,309 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2018-01-20 21:58:41,309 INFO L87 Difference]: Start difference. First operand 62 states. Second operand 2 states. [2018-01-20 21:58:41,315 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 21:58:41,315 INFO L93 Difference]: Finished difference Result 75 states and 95 transitions. [2018-01-20 21:58:41,316 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2018-01-20 21:58:41,316 INFO L78 Accepts]: Start accepts. Automaton has 2 states. Word has length 11 [2018-01-20 21:58:41,316 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 21:58:41,324 INFO L225 Difference]: With dead ends: 75 [2018-01-20 21:58:41,324 INFO L226 Difference]: Without dead ends: 57 [2018-01-20 21:58:41,325 INFO L525 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-01-20 21:58:41,325 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 57 states. [2018-01-20 21:58:41,341 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 57 to 57. [2018-01-20 21:58:41,341 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 57 states. [2018-01-20 21:58:41,343 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 57 states to 57 states and 74 transitions. [2018-01-20 21:58:41,343 INFO L78 Accepts]: Start accepts. Automaton has 57 states and 74 transitions. Word has length 11 [2018-01-20 21:58:41,343 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 21:58:41,343 INFO L432 AbstractCegarLoop]: Abstraction has 57 states and 74 transitions. [2018-01-20 21:58:41,344 INFO L433 AbstractCegarLoop]: Interpolant automaton has 2 states. [2018-01-20 21:58:41,344 INFO L276 IsEmpty]: Start isEmpty. Operand 57 states and 74 transitions. [2018-01-20 21:58:41,345 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2018-01-20 21:58:41,345 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 21:58:41,345 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-20 21:58:41,345 INFO L371 AbstractCegarLoop]: === Iteration 2 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-20 21:58:41,345 INFO L82 PathProgramCache]: Analyzing trace with hash -2092868013, now seen corresponding path program 1 times [2018-01-20 21:58:41,346 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 21:58:41,346 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 21:58:41,347 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:58:41,347 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 21:58:41,347 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:58:41,364 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 21:58:41,365 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 21:58:41,390 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-20 21:58:41,390 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-20 21:58:41,391 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-01-20 21:58:41,392 INFO L409 AbstractCegarLoop]: Interpolant automaton has 3 states [2018-01-20 21:58:41,393 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2018-01-20 21:58:41,393 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-01-20 21:58:41,393 INFO L87 Difference]: Start difference. First operand 57 states and 74 transitions. Second operand 3 states. [2018-01-20 21:58:41,413 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 21:58:41,413 INFO L93 Difference]: Finished difference Result 69 states and 87 transitions. [2018-01-20 21:58:41,414 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-01-20 21:58:41,414 INFO L78 Accepts]: Start accepts. Automaton has 3 states. Word has length 15 [2018-01-20 21:58:41,414 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 21:58:41,415 INFO L225 Difference]: With dead ends: 69 [2018-01-20 21:58:41,415 INFO L226 Difference]: Without dead ends: 58 [2018-01-20 21:58:41,417 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-01-20 21:58:41,417 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 58 states. [2018-01-20 21:58:41,423 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 58 to 58. [2018-01-20 21:58:41,423 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 58 states. [2018-01-20 21:58:41,425 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 58 states to 58 states and 75 transitions. [2018-01-20 21:58:41,425 INFO L78 Accepts]: Start accepts. Automaton has 58 states and 75 transitions. Word has length 15 [2018-01-20 21:58:41,425 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 21:58:41,426 INFO L432 AbstractCegarLoop]: Abstraction has 58 states and 75 transitions. [2018-01-20 21:58:41,426 INFO L433 AbstractCegarLoop]: Interpolant automaton has 3 states. [2018-01-20 21:58:41,426 INFO L276 IsEmpty]: Start isEmpty. Operand 58 states and 75 transitions. [2018-01-20 21:58:41,427 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2018-01-20 21:58:41,427 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 21:58:41,427 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-20 21:58:41,427 INFO L371 AbstractCegarLoop]: === Iteration 3 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-20 21:58:41,428 INFO L82 PathProgramCache]: Analyzing trace with hash 1392752657, now seen corresponding path program 1 times [2018-01-20 21:58:41,428 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 21:58:41,428 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 21:58:41,429 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:58:41,429 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 21:58:41,429 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:58:41,451 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2018-01-20 21:58:41,470 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2018-01-20 21:58:41,480 INFO L381 BasicCegarLoop]: Counterexample might be feasible [2018-01-20 21:58:41,491 WARN L343 cessorBacktranslator]: Generated EnsuresSpecification ensures #valid == old(#valid); is not ensure(true) [2018-01-20 21:58:41,498 WARN L343 cessorBacktranslator]: Generated EnsuresSpecification ensures #valid == old(#valid); is not ensure(true) [2018-01-20 21:58:41,500 WARN L343 cessorBacktranslator]: Generated EnsuresSpecification ensures #valid == old(#valid); is not ensure(true) [2018-01-20 21:58:41,512 INFO L322 AbstractCegarLoop]: Interprodecural is true [2018-01-20 21:58:41,512 INFO L323 AbstractCegarLoop]: Hoare is true [2018-01-20 21:58:41,512 INFO L324 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-01-20 21:58:41,512 INFO L325 AbstractCegarLoop]: Backedges is TWOTRACK [2018-01-20 21:58:41,512 INFO L326 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-01-20 21:58:41,512 INFO L327 AbstractCegarLoop]: Difference is false [2018-01-20 21:58:41,512 INFO L328 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-01-20 21:58:41,513 INFO L333 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == mainErr0EnsuresViolation======== [2018-01-20 21:58:41,513 INFO L87 2NestedWordAutomaton]: Mode: main mode - execution starts in main procedure [2018-01-20 21:58:41,514 INFO L276 IsEmpty]: Start isEmpty. Operand 62 states. [2018-01-20 21:58:41,515 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 10 [2018-01-20 21:58:41,515 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 21:58:41,515 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-20 21:58:41,515 INFO L371 AbstractCegarLoop]: === Iteration 1 === [mainErr0EnsuresViolation]=== [2018-01-20 21:58:41,516 INFO L82 PathProgramCache]: Analyzing trace with hash 1784608256, now seen corresponding path program 1 times [2018-01-20 21:58:41,516 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 21:58:41,516 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 21:58:41,517 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:58:41,517 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 21:58:41,517 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:58:41,527 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 21:58:41,528 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 21:58:41,538 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-20 21:58:41,538 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-20 21:58:41,538 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2018-01-20 21:58:41,539 INFO L409 AbstractCegarLoop]: Interpolant automaton has 2 states [2018-01-20 21:58:41,539 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2018-01-20 21:58:41,539 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2018-01-20 21:58:41,539 INFO L87 Difference]: Start difference. First operand 62 states. Second operand 2 states. [2018-01-20 21:58:41,544 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 21:58:41,544 INFO L93 Difference]: Finished difference Result 75 states and 95 transitions. [2018-01-20 21:58:41,544 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2018-01-20 21:58:41,545 INFO L78 Accepts]: Start accepts. Automaton has 2 states. Word has length 9 [2018-01-20 21:58:41,545 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 21:58:41,546 INFO L225 Difference]: With dead ends: 75 [2018-01-20 21:58:41,546 INFO L226 Difference]: Without dead ends: 55 [2018-01-20 21:58:41,547 INFO L525 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-01-20 21:58:41,547 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 55 states. [2018-01-20 21:58:41,552 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 55 to 55. [2018-01-20 21:58:41,552 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 55 states. [2018-01-20 21:58:41,554 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 55 states to 55 states and 72 transitions. [2018-01-20 21:58:41,554 INFO L78 Accepts]: Start accepts. Automaton has 55 states and 72 transitions. Word has length 9 [2018-01-20 21:58:41,554 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 21:58:41,554 INFO L432 AbstractCegarLoop]: Abstraction has 55 states and 72 transitions. [2018-01-20 21:58:41,554 INFO L433 AbstractCegarLoop]: Interpolant automaton has 2 states. [2018-01-20 21:58:41,554 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 72 transitions. [2018-01-20 21:58:41,555 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 14 [2018-01-20 21:58:41,555 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 21:58:41,555 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-20 21:58:41,555 INFO L371 AbstractCegarLoop]: === Iteration 2 === [mainErr0EnsuresViolation]=== [2018-01-20 21:58:41,556 INFO L82 PathProgramCache]: Analyzing trace with hash 1548658460, now seen corresponding path program 1 times [2018-01-20 21:58:41,556 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 21:58:41,556 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 21:58:41,557 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:58:41,557 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 21:58:41,557 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:58:41,565 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 21:58:41,566 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 21:58:41,602 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-20 21:58:41,602 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-20 21:58:41,602 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-01-20 21:58:41,602 INFO L409 AbstractCegarLoop]: Interpolant automaton has 3 states [2018-01-20 21:58:41,603 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2018-01-20 21:58:41,603 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-01-20 21:58:41,603 INFO L87 Difference]: Start difference. First operand 55 states and 72 transitions. Second operand 3 states. [2018-01-20 21:58:41,626 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 21:58:41,626 INFO L93 Difference]: Finished difference Result 65 states and 83 transitions. [2018-01-20 21:58:41,626 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-01-20 21:58:41,627 INFO L78 Accepts]: Start accepts. Automaton has 3 states. Word has length 13 [2018-01-20 21:58:41,627 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 21:58:41,628 INFO L225 Difference]: With dead ends: 65 [2018-01-20 21:58:41,628 INFO L226 Difference]: Without dead ends: 56 [2018-01-20 21:58:41,629 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-01-20 21:58:41,629 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 56 states. [2018-01-20 21:58:41,634 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 56 to 56. [2018-01-20 21:58:41,634 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 56 states. [2018-01-20 21:58:41,635 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 56 states to 56 states and 73 transitions. [2018-01-20 21:58:41,635 INFO L78 Accepts]: Start accepts. Automaton has 56 states and 73 transitions. Word has length 13 [2018-01-20 21:58:41,636 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 21:58:41,636 INFO L432 AbstractCegarLoop]: Abstraction has 56 states and 73 transitions. [2018-01-20 21:58:41,636 INFO L433 AbstractCegarLoop]: Interpolant automaton has 3 states. [2018-01-20 21:58:41,636 INFO L276 IsEmpty]: Start isEmpty. Operand 56 states and 73 transitions. [2018-01-20 21:58:41,636 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 14 [2018-01-20 21:58:41,637 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 21:58:41,637 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-20 21:58:41,637 INFO L371 AbstractCegarLoop]: === Iteration 3 === [mainErr0EnsuresViolation]=== [2018-01-20 21:58:41,637 INFO L82 PathProgramCache]: Analyzing trace with hash 1605916762, now seen corresponding path program 1 times [2018-01-20 21:58:41,637 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 21:58:41,637 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 21:58:41,638 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:58:41,638 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 21:58:41,638 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:58:41,649 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 21:58:41,650 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 21:58:41,675 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-20 21:58:41,675 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-20 21:58:41,675 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2018-01-20 21:58:41,675 INFO L409 AbstractCegarLoop]: Interpolant automaton has 3 states [2018-01-20 21:58:41,676 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2018-01-20 21:58:41,676 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-01-20 21:58:41,676 INFO L87 Difference]: Start difference. First operand 56 states and 73 transitions. Second operand 3 states. [2018-01-20 21:58:41,716 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 21:58:41,717 INFO L93 Difference]: Finished difference Result 65 states and 82 transitions. [2018-01-20 21:58:41,717 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-01-20 21:58:41,717 INFO L78 Accepts]: Start accepts. Automaton has 3 states. Word has length 13 [2018-01-20 21:58:41,717 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 21:58:41,718 INFO L225 Difference]: With dead ends: 65 [2018-01-20 21:58:41,719 INFO L226 Difference]: Without dead ends: 62 [2018-01-20 21:58:41,719 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-01-20 21:58:41,719 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 62 states. [2018-01-20 21:58:41,724 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 62 to 58. [2018-01-20 21:58:41,725 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 58 states. [2018-01-20 21:58:41,726 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 58 states to 58 states and 75 transitions. [2018-01-20 21:58:41,726 INFO L78 Accepts]: Start accepts. Automaton has 58 states and 75 transitions. Word has length 13 [2018-01-20 21:58:41,726 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 21:58:41,726 INFO L432 AbstractCegarLoop]: Abstraction has 58 states and 75 transitions. [2018-01-20 21:58:41,727 INFO L433 AbstractCegarLoop]: Interpolant automaton has 3 states. [2018-01-20 21:58:41,727 INFO L276 IsEmpty]: Start isEmpty. Operand 58 states and 75 transitions. [2018-01-20 21:58:41,728 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2018-01-20 21:58:41,728 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 21:58:41,728 INFO L322 BasicCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-20 21:58:41,728 INFO L371 AbstractCegarLoop]: === Iteration 4 === [mainErr0EnsuresViolation]=== [2018-01-20 21:58:41,728 INFO L82 PathProgramCache]: Analyzing trace with hash 1614897922, now seen corresponding path program 1 times [2018-01-20 21:58:41,729 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 21:58:41,729 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 21:58:41,730 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:58:41,730 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 21:58:41,730 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:58:41,741 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 21:58:41,742 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 21:58:41,786 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-20 21:58:41,786 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-20 21:58:41,786 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-01-20 21:58:41,787 INFO L409 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-01-20 21:58:41,787 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-01-20 21:58:41,787 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-01-20 21:58:41,787 INFO L87 Difference]: Start difference. First operand 58 states and 75 transitions. Second operand 4 states. [2018-01-20 21:58:41,853 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 21:58:41,853 INFO L93 Difference]: Finished difference Result 114 states and 149 transitions. [2018-01-20 21:58:41,854 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-01-20 21:58:41,854 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 19 [2018-01-20 21:58:41,854 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 21:58:41,856 INFO L225 Difference]: With dead ends: 114 [2018-01-20 21:58:41,856 INFO L226 Difference]: Without dead ends: 100 [2018-01-20 21:58:41,857 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-01-20 21:58:41,857 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 100 states. [2018-01-20 21:58:41,871 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 100 to 95. [2018-01-20 21:58:41,871 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 95 states. [2018-01-20 21:58:41,872 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 95 states to 95 states and 129 transitions. [2018-01-20 21:58:41,872 INFO L78 Accepts]: Start accepts. Automaton has 95 states and 129 transitions. Word has length 19 [2018-01-20 21:58:41,873 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 21:58:41,873 INFO L432 AbstractCegarLoop]: Abstraction has 95 states and 129 transitions. [2018-01-20 21:58:41,873 INFO L433 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-01-20 21:58:41,873 INFO L276 IsEmpty]: Start isEmpty. Operand 95 states and 129 transitions. [2018-01-20 21:58:41,875 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2018-01-20 21:58:41,876 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 21:58:41,876 INFO L322 BasicCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-20 21:58:41,876 INFO L371 AbstractCegarLoop]: === Iteration 5 === [mainErr0EnsuresViolation]=== [2018-01-20 21:58:41,876 INFO L82 PathProgramCache]: Analyzing trace with hash -302614467, now seen corresponding path program 1 times [2018-01-20 21:58:41,876 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 21:58:41,877 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 21:58:41,877 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:58:41,878 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 21:58:41,878 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:58:41,894 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 21:58:41,895 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 21:58:42,018 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-01-20 21:58:42,019 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-20 21:58:42,019 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2018-01-20 21:58:42,019 INFO L409 AbstractCegarLoop]: Interpolant automaton has 7 states [2018-01-20 21:58:42,019 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2018-01-20 21:58:42,019 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=12, Invalid=30, Unknown=0, NotChecked=0, Total=42 [2018-01-20 21:58:42,020 INFO L87 Difference]: Start difference. First operand 95 states and 129 transitions. Second operand 7 states. [2018-01-20 21:58:42,415 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 21:58:42,416 INFO L93 Difference]: Finished difference Result 227 states and 312 transitions. [2018-01-20 21:58:42,416 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-01-20 21:58:42,416 INFO L78 Accepts]: Start accepts. Automaton has 7 states. Word has length 37 [2018-01-20 21:58:42,417 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 21:58:42,419 INFO L225 Difference]: With dead ends: 227 [2018-01-20 21:58:42,420 INFO L226 Difference]: Without dead ends: 174 [2018-01-20 21:58:42,421 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 13 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=39, Invalid=93, Unknown=0, NotChecked=0, Total=132 [2018-01-20 21:58:42,421 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 174 states. [2018-01-20 21:58:42,441 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 174 to 150. [2018-01-20 21:58:42,441 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 150 states. [2018-01-20 21:58:42,443 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 150 states to 150 states and 207 transitions. [2018-01-20 21:58:42,443 INFO L78 Accepts]: Start accepts. Automaton has 150 states and 207 transitions. Word has length 37 [2018-01-20 21:58:42,444 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 21:58:42,444 INFO L432 AbstractCegarLoop]: Abstraction has 150 states and 207 transitions. [2018-01-20 21:58:42,444 INFO L433 AbstractCegarLoop]: Interpolant automaton has 7 states. [2018-01-20 21:58:42,444 INFO L276 IsEmpty]: Start isEmpty. Operand 150 states and 207 transitions. [2018-01-20 21:58:42,446 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 48 [2018-01-20 21:58:42,446 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 21:58:42,447 INFO L322 BasicCegarLoop]: trace histogram [3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-20 21:58:42,447 INFO L371 AbstractCegarLoop]: === Iteration 6 === [mainErr0EnsuresViolation]=== [2018-01-20 21:58:42,447 INFO L82 PathProgramCache]: Analyzing trace with hash 1718063660, now seen corresponding path program 1 times [2018-01-20 21:58:42,448 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 21:58:42,448 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 21:58:42,449 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:58:42,449 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 21:58:42,449 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:58:42,479 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 21:58:42,480 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 21:58:42,602 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 2 proven. 18 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-20 21:58:42,603 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-20 21:58:42,603 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/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-01-20 21:58:42,615 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 21:58:42,692 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 21:58:42,700 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-20 21:58:42,948 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 15 proven. 3 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-01-20 21:58:42,970 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-20 21:58:42,970 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 8] total 16 [2018-01-20 21:58:42,970 INFO L409 AbstractCegarLoop]: Interpolant automaton has 16 states [2018-01-20 21:58:42,971 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2018-01-20 21:58:42,971 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=31, Invalid=209, Unknown=0, NotChecked=0, Total=240 [2018-01-20 21:58:42,971 INFO L87 Difference]: Start difference. First operand 150 states and 207 transitions. Second operand 16 states. [2018-01-20 21:58:45,827 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 21:58:45,827 INFO L93 Difference]: Finished difference Result 1079 states and 1600 transitions. [2018-01-20 21:58:45,827 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 95 states. [2018-01-20 21:58:45,827 INFO L78 Accepts]: Start accepts. Automaton has 16 states. Word has length 47 [2018-01-20 21:58:45,828 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 21:58:45,834 INFO L225 Difference]: With dead ends: 1079 [2018-01-20 21:58:45,834 INFO L226 Difference]: Without dead ends: 937 [2018-01-20 21:58:45,841 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 171 GetRequests, 67 SyntacticMatches, 0 SemanticMatches, 104 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4378 ImplicationChecksByTransitivity, 1.6s TimeCoverageRelationStatistics Valid=1600, Invalid=9530, Unknown=0, NotChecked=0, Total=11130 [2018-01-20 21:58:45,842 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 937 states. [2018-01-20 21:58:45,909 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 937 to 363. [2018-01-20 21:58:45,910 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 363 states. [2018-01-20 21:58:45,913 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 363 states to 363 states and 515 transitions. [2018-01-20 21:58:45,914 INFO L78 Accepts]: Start accepts. Automaton has 363 states and 515 transitions. Word has length 47 [2018-01-20 21:58:45,914 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 21:58:45,914 INFO L432 AbstractCegarLoop]: Abstraction has 363 states and 515 transitions. [2018-01-20 21:58:45,914 INFO L433 AbstractCegarLoop]: Interpolant automaton has 16 states. [2018-01-20 21:58:45,914 INFO L276 IsEmpty]: Start isEmpty. Operand 363 states and 515 transitions. [2018-01-20 21:58:45,918 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 74 [2018-01-20 21:58:45,918 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 21:58:45,918 INFO L322 BasicCegarLoop]: trace histogram [5, 5, 4, 4, 4, 4, 4, 4, 4, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-20 21:58:45,918 INFO L371 AbstractCegarLoop]: === Iteration 7 === [mainErr0EnsuresViolation]=== [2018-01-20 21:58:45,918 INFO L82 PathProgramCache]: Analyzing trace with hash -1650249222, now seen corresponding path program 1 times [2018-01-20 21:58:45,919 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 21:58:45,919 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 21:58:45,920 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:58:45,920 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 21:58:45,920 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:58:45,936 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 21:58:45,937 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 21:58:46,043 INFO L134 CoverageAnalysis]: Checked inductivity of 83 backedges. 22 proven. 16 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2018-01-20 21:58:46,043 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-20 21:58:46,043 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/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-01-20 21:58:46,051 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 21:58:46,126 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 21:58:46,132 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-20 21:58:46,189 INFO L134 CoverageAnalysis]: Checked inductivity of 83 backedges. 38 proven. 0 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2018-01-20 21:58:46,223 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2018-01-20 21:58:46,223 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [7] imperfect sequences [7] total 9 [2018-01-20 21:58:46,224 INFO L409 AbstractCegarLoop]: Interpolant automaton has 9 states [2018-01-20 21:58:46,224 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2018-01-20 21:58:46,224 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=54, Unknown=0, NotChecked=0, Total=72 [2018-01-20 21:58:46,224 INFO L87 Difference]: Start difference. First operand 363 states and 515 transitions. Second operand 9 states. [2018-01-20 21:58:46,582 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 21:58:46,583 INFO L93 Difference]: Finished difference Result 876 states and 1273 transitions. [2018-01-20 21:58:46,585 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-01-20 21:58:46,585 INFO L78 Accepts]: Start accepts. Automaton has 9 states. Word has length 73 [2018-01-20 21:58:46,585 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 21:58:46,588 INFO L225 Difference]: With dead ends: 876 [2018-01-20 21:58:46,588 INFO L226 Difference]: Without dead ends: 518 [2018-01-20 21:58:46,590 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 89 GetRequests, 76 SyntacticMatches, 1 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=51, Invalid=131, Unknown=0, NotChecked=0, Total=182 [2018-01-20 21:58:46,590 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 518 states. [2018-01-20 21:58:46,619 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 518 to 478. [2018-01-20 21:58:46,620 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 478 states. [2018-01-20 21:58:46,623 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 478 states to 478 states and 685 transitions. [2018-01-20 21:58:46,624 INFO L78 Accepts]: Start accepts. Automaton has 478 states and 685 transitions. Word has length 73 [2018-01-20 21:58:46,624 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 21:58:46,624 INFO L432 AbstractCegarLoop]: Abstraction has 478 states and 685 transitions. [2018-01-20 21:58:46,624 INFO L433 AbstractCegarLoop]: Interpolant automaton has 9 states. [2018-01-20 21:58:46,624 INFO L276 IsEmpty]: Start isEmpty. Operand 478 states and 685 transitions. [2018-01-20 21:58:46,627 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 75 [2018-01-20 21:58:46,627 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 21:58:46,627 INFO L322 BasicCegarLoop]: trace histogram [5, 5, 4, 4, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-20 21:58:46,627 INFO L371 AbstractCegarLoop]: === Iteration 8 === [mainErr0EnsuresViolation]=== [2018-01-20 21:58:46,628 INFO L82 PathProgramCache]: Analyzing trace with hash -1980963244, now seen corresponding path program 1 times [2018-01-20 21:58:46,628 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 21:58:46,628 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 21:58:46,629 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:58:46,629 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 21:58:46,629 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:58:46,640 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 21:58:46,642 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 21:58:46,719 INFO L134 CoverageAnalysis]: Checked inductivity of 64 backedges. 19 proven. 0 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2018-01-20 21:58:46,719 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-20 21:58:46,719 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2018-01-20 21:58:46,720 INFO L409 AbstractCegarLoop]: Interpolant automaton has 7 states [2018-01-20 21:58:46,720 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2018-01-20 21:58:46,720 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=12, Invalid=30, Unknown=0, NotChecked=0, Total=42 [2018-01-20 21:58:46,720 INFO L87 Difference]: Start difference. First operand 478 states and 685 transitions. Second operand 7 states. [2018-01-20 21:58:46,932 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 21:58:46,932 INFO L93 Difference]: Finished difference Result 1385 states and 2113 transitions. [2018-01-20 21:58:46,933 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-01-20 21:58:46,933 INFO L78 Accepts]: Start accepts. Automaton has 7 states. Word has length 74 [2018-01-20 21:58:46,933 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 21:58:46,938 INFO L225 Difference]: With dead ends: 1385 [2018-01-20 21:58:46,938 INFO L226 Difference]: Without dead ends: 912 [2018-01-20 21:58:46,940 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 13 GetRequests, 4 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=34, Invalid=76, Unknown=0, NotChecked=0, Total=110 [2018-01-20 21:58:46,940 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 912 states. [2018-01-20 21:58:46,998 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 912 to 752. [2018-01-20 21:58:46,998 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 752 states. [2018-01-20 21:58:47,003 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 752 states to 752 states and 1082 transitions. [2018-01-20 21:58:47,003 INFO L78 Accepts]: Start accepts. Automaton has 752 states and 1082 transitions. Word has length 74 [2018-01-20 21:58:47,003 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 21:58:47,003 INFO L432 AbstractCegarLoop]: Abstraction has 752 states and 1082 transitions. [2018-01-20 21:58:47,004 INFO L433 AbstractCegarLoop]: Interpolant automaton has 7 states. [2018-01-20 21:58:47,004 INFO L276 IsEmpty]: Start isEmpty. Operand 752 states and 1082 transitions. [2018-01-20 21:58:47,006 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 84 [2018-01-20 21:58:47,006 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 21:58:47,007 INFO L322 BasicCegarLoop]: trace histogram [6, 6, 5, 5, 5, 5, 5, 5, 5, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-20 21:58:47,007 INFO L371 AbstractCegarLoop]: === Iteration 9 === [mainErr0EnsuresViolation]=== [2018-01-20 21:58:47,007 INFO L82 PathProgramCache]: Analyzing trace with hash 787103849, now seen corresponding path program 2 times [2018-01-20 21:58:47,007 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 21:58:47,007 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 21:58:47,008 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:58:47,008 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 21:58:47,008 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:58:47,021 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 21:58:47,022 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 21:58:47,177 INFO L134 CoverageAnalysis]: Checked inductivity of 127 backedges. 40 proven. 73 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2018-01-20 21:58:47,177 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-20 21:58:47,177 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/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-01-20 21:58:47,184 INFO L101 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-01-20 21:58:47,222 INFO L201 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-20 21:58:47,268 INFO L214 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-20 21:58:47,276 INFO L239 tOrderPrioritization]: Conjunction of SSA is unsat [2018-01-20 21:58:47,282 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-20 21:58:47,426 INFO L134 CoverageAnalysis]: Checked inductivity of 127 backedges. 79 proven. 3 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2018-01-20 21:58:47,462 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-20 21:58:47,462 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 8] total 17 [2018-01-20 21:58:47,463 INFO L409 AbstractCegarLoop]: Interpolant automaton has 17 states [2018-01-20 21:58:47,463 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2018-01-20 21:58:47,463 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=239, Unknown=0, NotChecked=0, Total=272 [2018-01-20 21:58:47,463 INFO L87 Difference]: Start difference. First operand 752 states and 1082 transitions. Second operand 17 states. [2018-01-20 21:58:51,911 WARN L146 SmtUtils]: Spent 215ms on a formula simplification. DAG size of input: 27 DAG size of output 25 [2018-01-20 21:58:52,185 WARN L146 SmtUtils]: Spent 162ms on a formula simplification. DAG size of input: 24 DAG size of output 22 [2018-01-20 21:58:55,543 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 21:58:55,543 INFO L93 Difference]: Finished difference Result 5302 states and 8432 transitions. [2018-01-20 21:58:55,543 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 135 states. [2018-01-20 21:58:55,544 INFO L78 Accepts]: Start accepts. Automaton has 17 states. Word has length 83 [2018-01-20 21:58:55,544 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 21:58:55,565 INFO L225 Difference]: With dead ends: 5302 [2018-01-20 21:58:55,565 INFO L226 Difference]: Without dead ends: 4555 [2018-01-20 21:58:55,574 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 316 GetRequests, 170 SyntacticMatches, 0 SemanticMatches, 146 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8914 ImplicationChecksByTransitivity, 5.0s TimeCoverageRelationStatistics Valid=2873, Invalid=18883, Unknown=0, NotChecked=0, Total=21756 [2018-01-20 21:58:55,576 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 4555 states. [2018-01-20 21:58:55,769 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 4555 to 3144. [2018-01-20 21:58:55,769 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 3144 states. [2018-01-20 21:58:55,780 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3144 states to 3144 states and 4486 transitions. [2018-01-20 21:58:55,780 INFO L78 Accepts]: Start accepts. Automaton has 3144 states and 4486 transitions. Word has length 83 [2018-01-20 21:58:55,780 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 21:58:55,780 INFO L432 AbstractCegarLoop]: Abstraction has 3144 states and 4486 transitions. [2018-01-20 21:58:55,781 INFO L433 AbstractCegarLoop]: Interpolant automaton has 17 states. [2018-01-20 21:58:55,781 INFO L276 IsEmpty]: Start isEmpty. Operand 3144 states and 4486 transitions. [2018-01-20 21:58:55,786 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 87 [2018-01-20 21:58:55,786 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 21:58:55,787 INFO L322 BasicCegarLoop]: trace histogram [6, 6, 5, 5, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-20 21:58:55,787 INFO L371 AbstractCegarLoop]: === Iteration 10 === [mainErr0EnsuresViolation]=== [2018-01-20 21:58:55,787 INFO L82 PathProgramCache]: Analyzing trace with hash 1494721301, now seen corresponding path program 1 times [2018-01-20 21:58:55,787 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 21:58:55,787 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 21:58:55,788 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:58:55,788 INFO L99 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-01-20 21:58:55,788 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:58:55,797 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 21:58:55,798 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 21:58:55,929 INFO L134 CoverageAnalysis]: Checked inductivity of 94 backedges. 25 proven. 5 refuted. 0 times theorem prover too weak. 64 trivial. 0 not checked. [2018-01-20 21:58:55,930 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-20 21:58:55,930 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/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-01-20 21:58:55,939 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 21:58:56,006 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 21:58:56,012 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-20 21:58:56,189 INFO L134 CoverageAnalysis]: Checked inductivity of 94 backedges. 30 proven. 0 refuted. 0 times theorem prover too weak. 64 trivial. 0 not checked. [2018-01-20 21:58:56,211 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2018-01-20 21:58:56,211 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [7] imperfect sequences [7] total 9 [2018-01-20 21:58:56,211 INFO L409 AbstractCegarLoop]: Interpolant automaton has 9 states [2018-01-20 21:58:56,212 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2018-01-20 21:58:56,212 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=54, Unknown=0, NotChecked=0, Total=72 [2018-01-20 21:58:56,212 INFO L87 Difference]: Start difference. First operand 3144 states and 4486 transitions. Second operand 9 states. [2018-01-20 21:58:56,525 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 21:58:56,525 INFO L93 Difference]: Finished difference Result 6836 states and 9969 transitions. [2018-01-20 21:58:56,525 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-01-20 21:58:56,525 INFO L78 Accepts]: Start accepts. Automaton has 9 states. Word has length 86 [2018-01-20 21:58:56,526 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 21:58:56,542 INFO L225 Difference]: With dead ends: 6836 [2018-01-20 21:58:56,543 INFO L226 Difference]: Without dead ends: 3697 [2018-01-20 21:58:56,552 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 101 GetRequests, 89 SyntacticMatches, 1 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=45, Invalid=111, Unknown=0, NotChecked=0, Total=156 [2018-01-20 21:58:56,554 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 3697 states. [2018-01-20 21:58:56,832 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 3697 to 3144. [2018-01-20 21:58:56,832 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 3144 states. [2018-01-20 21:58:56,842 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3144 states to 3144 states and 4486 transitions. [2018-01-20 21:58:56,843 INFO L78 Accepts]: Start accepts. Automaton has 3144 states and 4486 transitions. Word has length 86 [2018-01-20 21:58:56,843 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 21:58:56,843 INFO L432 AbstractCegarLoop]: Abstraction has 3144 states and 4486 transitions. [2018-01-20 21:58:56,843 INFO L433 AbstractCegarLoop]: Interpolant automaton has 9 states. [2018-01-20 21:58:56,844 INFO L276 IsEmpty]: Start isEmpty. Operand 3144 states and 4486 transitions. [2018-01-20 21:58:56,852 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 88 [2018-01-20 21:58:56,852 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 21:58:56,852 INFO L322 BasicCegarLoop]: trace histogram [6, 6, 5, 5, 5, 5, 5, 5, 5, 4, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-20 21:58:56,852 INFO L371 AbstractCegarLoop]: === Iteration 11 === [mainErr0EnsuresViolation]=== [2018-01-20 21:58:56,853 INFO L82 PathProgramCache]: Analyzing trace with hash 1024435374, now seen corresponding path program 1 times [2018-01-20 21:58:56,853 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 21:58:56,853 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 21:58:56,854 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:58:56,854 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 21:58:56,854 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:58:56,865 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 21:58:56,866 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 21:58:56,973 INFO L134 CoverageAnalysis]: Checked inductivity of 132 backedges. 28 proven. 21 refuted. 0 times theorem prover too weak. 83 trivial. 0 not checked. [2018-01-20 21:58:56,974 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-20 21:58:56,974 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/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-01-20 21:58:56,983 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 21:58:57,064 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 21:58:57,070 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-20 21:58:57,116 INFO L134 CoverageAnalysis]: Checked inductivity of 132 backedges. 49 proven. 0 refuted. 0 times theorem prover too weak. 83 trivial. 0 not checked. [2018-01-20 21:58:57,152 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2018-01-20 21:58:57,152 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [7] imperfect sequences [7] total 9 [2018-01-20 21:58:57,153 INFO L409 AbstractCegarLoop]: Interpolant automaton has 9 states [2018-01-20 21:58:57,153 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2018-01-20 21:58:57,153 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=54, Unknown=0, NotChecked=0, Total=72 [2018-01-20 21:58:57,153 INFO L87 Difference]: Start difference. First operand 3144 states and 4486 transitions. Second operand 9 states. [2018-01-20 21:58:57,613 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 21:58:57,613 INFO L93 Difference]: Finished difference Result 5258 states and 7573 transitions. [2018-01-20 21:58:57,614 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-01-20 21:58:57,614 INFO L78 Accepts]: Start accepts. Automaton has 9 states. Word has length 87 [2018-01-20 21:58:57,614 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 21:58:57,629 INFO L225 Difference]: With dead ends: 5258 [2018-01-20 21:58:57,629 INFO L226 Difference]: Without dead ends: 3673 [2018-01-20 21:58:57,635 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 103 GetRequests, 90 SyntacticMatches, 1 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=51, Invalid=131, Unknown=0, NotChecked=0, Total=182 [2018-01-20 21:58:57,637 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 3673 states. [2018-01-20 21:58:57,862 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 3673 to 3550. [2018-01-20 21:58:57,862 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 3550 states. [2018-01-20 21:58:57,869 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3550 states to 3550 states and 5100 transitions. [2018-01-20 21:58:57,870 INFO L78 Accepts]: Start accepts. Automaton has 3550 states and 5100 transitions. Word has length 87 [2018-01-20 21:58:57,870 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 21:58:57,870 INFO L432 AbstractCegarLoop]: Abstraction has 3550 states and 5100 transitions. [2018-01-20 21:58:57,870 INFO L433 AbstractCegarLoop]: Interpolant automaton has 9 states. [2018-01-20 21:58:57,870 INFO L276 IsEmpty]: Start isEmpty. Operand 3550 states and 5100 transitions. [2018-01-20 21:58:57,876 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 89 [2018-01-20 21:58:57,876 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 21:58:57,876 INFO L322 BasicCegarLoop]: trace histogram [6, 6, 5, 5, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-20 21:58:57,876 INFO L371 AbstractCegarLoop]: === Iteration 12 === [mainErr0EnsuresViolation]=== [2018-01-20 21:58:57,876 INFO L82 PathProgramCache]: Analyzing trace with hash 160797049, now seen corresponding path program 1 times [2018-01-20 21:58:57,876 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 21:58:57,877 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 21:58:57,877 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:58:57,877 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 21:58:57,877 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:58:57,887 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 21:58:57,888 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 21:58:58,127 INFO L134 CoverageAnalysis]: Checked inductivity of 93 backedges. 25 proven. 4 refuted. 0 times theorem prover too weak. 64 trivial. 0 not checked. [2018-01-20 21:58:58,127 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-20 21:58:58,127 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/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-01-20 21:58:58,141 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 21:58:58,209 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 21:58:58,214 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-20 21:58:58,282 WARN L1029 $PredicateComparison]: unable to prove that (exists ((|push_#t~malloc2.base| Int)) (and (<= (select |c_old(#valid)| |push_#t~malloc2.base|) 0) (= |c_#valid| (store |c_old(#valid)| |push_#t~malloc2.base| 1)))) is different from true [2018-01-20 21:58:58,297 INFO L134 CoverageAnalysis]: Checked inductivity of 93 backedges. 28 proven. 0 refuted. 0 times theorem prover too weak. 65 trivial. 0 not checked. [2018-01-20 21:58:58,331 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2018-01-20 21:58:58,331 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [4] imperfect sequences [8] total 10 [2018-01-20 21:58:58,332 INFO L409 AbstractCegarLoop]: Interpolant automaton has 10 states [2018-01-20 21:58:58,332 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2018-01-20 21:58:58,333 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=21, Invalid=54, Unknown=1, NotChecked=14, Total=90 [2018-01-20 21:58:58,333 INFO L87 Difference]: Start difference. First operand 3550 states and 5100 transitions. Second operand 10 states. [2018-01-20 21:58:58,931 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 21:58:58,931 INFO L93 Difference]: Finished difference Result 8706 states and 13158 transitions. [2018-01-20 21:58:58,932 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2018-01-20 21:58:58,932 INFO L78 Accepts]: Start accepts. Automaton has 10 states. Word has length 88 [2018-01-20 21:58:58,932 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 21:58:58,954 INFO L225 Difference]: With dead ends: 8706 [2018-01-20 21:58:58,954 INFO L226 Difference]: Without dead ends: 4831 [2018-01-20 21:58:58,967 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 104 GetRequests, 91 SyntacticMatches, 0 SemanticMatches, 13 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 19 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=43, Invalid=140, Unknown=3, NotChecked=24, Total=210 [2018-01-20 21:58:58,971 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 4831 states. [2018-01-20 21:58:59,304 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 4831 to 4394. [2018-01-20 21:58:59,304 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 4394 states. [2018-01-20 21:58:59,313 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 4394 states to 4394 states and 6385 transitions. [2018-01-20 21:58:59,313 INFO L78 Accepts]: Start accepts. Automaton has 4394 states and 6385 transitions. Word has length 88 [2018-01-20 21:58:59,313 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 21:58:59,313 INFO L432 AbstractCegarLoop]: Abstraction has 4394 states and 6385 transitions. [2018-01-20 21:58:59,313 INFO L433 AbstractCegarLoop]: Interpolant automaton has 10 states. [2018-01-20 21:58:59,314 INFO L276 IsEmpty]: Start isEmpty. Operand 4394 states and 6385 transitions. [2018-01-20 21:58:59,319 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 91 [2018-01-20 21:58:59,320 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 21:58:59,320 INFO L322 BasicCegarLoop]: trace histogram [6, 6, 5, 5, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-20 21:58:59,320 INFO L371 AbstractCegarLoop]: === Iteration 13 === [mainErr0EnsuresViolation]=== [2018-01-20 21:58:59,320 INFO L82 PathProgramCache]: Analyzing trace with hash -2024113882, now seen corresponding path program 1 times [2018-01-20 21:58:59,320 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 21:58:59,320 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 21:58:59,321 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:58:59,321 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 21:58:59,321 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:58:59,341 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 21:58:59,342 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 21:58:59,687 INFO L134 CoverageAnalysis]: Checked inductivity of 97 backedges. 38 proven. 41 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2018-01-20 21:58:59,688 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-20 21:58:59,688 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/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-01-20 21:58:59,695 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 21:58:59,755 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 21:58:59,758 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-20 21:59:00,020 INFO L134 CoverageAnalysis]: Checked inductivity of 97 backedges. 48 proven. 3 refuted. 0 times theorem prover too weak. 46 trivial. 0 not checked. [2018-01-20 21:59:00,041 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-20 21:59:00,041 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 6] total 15 [2018-01-20 21:59:00,042 INFO L409 AbstractCegarLoop]: Interpolant automaton has 15 states [2018-01-20 21:59:00,042 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2018-01-20 21:59:00,042 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=28, Invalid=182, Unknown=0, NotChecked=0, Total=210 [2018-01-20 21:59:00,042 INFO L87 Difference]: Start difference. First operand 4394 states and 6385 transitions. Second operand 15 states. [2018-01-20 21:59:02,867 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 21:59:02,868 INFO L93 Difference]: Finished difference Result 16377 states and 25815 transitions. [2018-01-20 21:59:02,868 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 58 states. [2018-01-20 21:59:02,868 INFO L78 Accepts]: Start accepts. Automaton has 15 states. Word has length 90 [2018-01-20 21:59:02,868 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 21:59:02,925 INFO L225 Difference]: With dead ends: 16377 [2018-01-20 21:59:02,925 INFO L226 Difference]: Without dead ends: 12378 [2018-01-20 21:59:02,952 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 197 GetRequests, 128 SyntacticMatches, 0 SemanticMatches, 69 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1474 ImplicationChecksByTransitivity, 1.7s TimeCoverageRelationStatistics Valid=937, Invalid=4033, Unknown=0, NotChecked=0, Total=4970 [2018-01-20 21:59:02,961 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 12378 states. [2018-01-20 21:59:03,877 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 12378 to 10054. [2018-01-20 21:59:03,877 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 10054 states. [2018-01-20 21:59:03,898 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10054 states to 10054 states and 14764 transitions. [2018-01-20 21:59:03,899 INFO L78 Accepts]: Start accepts. Automaton has 10054 states and 14764 transitions. Word has length 90 [2018-01-20 21:59:03,899 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 21:59:03,899 INFO L432 AbstractCegarLoop]: Abstraction has 10054 states and 14764 transitions. [2018-01-20 21:59:03,899 INFO L433 AbstractCegarLoop]: Interpolant automaton has 15 states. [2018-01-20 21:59:03,899 INFO L276 IsEmpty]: Start isEmpty. Operand 10054 states and 14764 transitions. [2018-01-20 21:59:03,906 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 91 [2018-01-20 21:59:03,906 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 21:59:03,907 INFO L322 BasicCegarLoop]: trace histogram [6, 6, 5, 5, 5, 5, 5, 5, 5, 4, 4, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-20 21:59:03,907 INFO L371 AbstractCegarLoop]: === Iteration 14 === [mainErr0EnsuresViolation]=== [2018-01-20 21:59:03,907 INFO L82 PathProgramCache]: Analyzing trace with hash 507171894, now seen corresponding path program 1 times [2018-01-20 21:59:03,907 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 21:59:03,907 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 21:59:03,908 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:59:03,908 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 21:59:03,908 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:59:03,919 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 21:59:03,920 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 21:59:04,099 INFO L134 CoverageAnalysis]: Checked inductivity of 138 backedges. 71 proven. 22 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2018-01-20 21:59:04,099 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-20 21:59:04,099 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/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-01-20 21:59:04,104 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 21:59:04,153 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 21:59:04,156 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-20 21:59:04,217 INFO L134 CoverageAnalysis]: Checked inductivity of 138 backedges. 79 proven. 12 refuted. 0 times theorem prover too weak. 47 trivial. 0 not checked. [2018-01-20 21:59:04,237 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-20 21:59:04,237 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 9] total 15 [2018-01-20 21:59:04,238 INFO L409 AbstractCegarLoop]: Interpolant automaton has 15 states [2018-01-20 21:59:04,238 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2018-01-20 21:59:04,238 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=35, Invalid=175, Unknown=0, NotChecked=0, Total=210 [2018-01-20 21:59:04,238 INFO L87 Difference]: Start difference. First operand 10054 states and 14764 transitions. Second operand 15 states. [2018-01-20 21:59:06,787 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 21:59:06,787 INFO L93 Difference]: Finished difference Result 34700 states and 57428 transitions. [2018-01-20 21:59:06,787 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 33 states. [2018-01-20 21:59:06,788 INFO L78 Accepts]: Start accepts. Automaton has 15 states. Word has length 90 [2018-01-20 21:59:06,788 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 21:59:06,886 INFO L225 Difference]: With dead ends: 34700 [2018-01-20 21:59:06,886 INFO L226 Difference]: Without dead ends: 23471 [2018-01-20 21:59:06,926 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 139 GetRequests, 101 SyntacticMatches, 0 SemanticMatches, 38 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 366 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=292, Invalid=1268, Unknown=0, NotChecked=0, Total=1560 [2018-01-20 21:59:06,941 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 23471 states. [2018-01-20 21:59:08,020 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 23471 to 14718. [2018-01-20 21:59:08,021 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 14718 states. [2018-01-20 21:59:08,049 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 14718 states to 14718 states and 21754 transitions. [2018-01-20 21:59:08,050 INFO L78 Accepts]: Start accepts. Automaton has 14718 states and 21754 transitions. Word has length 90 [2018-01-20 21:59:08,050 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 21:59:08,050 INFO L432 AbstractCegarLoop]: Abstraction has 14718 states and 21754 transitions. [2018-01-20 21:59:08,050 INFO L433 AbstractCegarLoop]: Interpolant automaton has 15 states. [2018-01-20 21:59:08,050 INFO L276 IsEmpty]: Start isEmpty. Operand 14718 states and 21754 transitions. [2018-01-20 21:59:08,140 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 108 [2018-01-20 21:59:08,140 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 21:59:08,140 INFO L322 BasicCegarLoop]: trace histogram [7, 7, 6, 6, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-20 21:59:08,141 INFO L371 AbstractCegarLoop]: === Iteration 15 === [mainErr0EnsuresViolation]=== [2018-01-20 21:59:08,141 INFO L82 PathProgramCache]: Analyzing trace with hash 671709488, now seen corresponding path program 1 times [2018-01-20 21:59:08,141 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 21:59:08,141 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 21:59:08,142 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:59:08,142 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 21:59:08,142 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:59:08,153 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 21:59:08,154 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 21:59:08,316 INFO L134 CoverageAnalysis]: Checked inductivity of 146 backedges. 57 proven. 31 refuted. 0 times theorem prover too weak. 58 trivial. 0 not checked. [2018-01-20 21:59:08,316 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-20 21:59:08,316 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/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-01-20 21:59:08,323 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 21:59:08,384 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 21:59:08,388 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-20 21:59:08,425 INFO L134 CoverageAnalysis]: Checked inductivity of 146 backedges. 64 proven. 3 refuted. 0 times theorem prover too weak. 79 trivial. 0 not checked. [2018-01-20 21:59:08,459 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-20 21:59:08,459 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 4] total 10 [2018-01-20 21:59:08,459 INFO L409 AbstractCegarLoop]: Interpolant automaton has 10 states [2018-01-20 21:59:08,459 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2018-01-20 21:59:08,460 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=73, Unknown=0, NotChecked=0, Total=90 [2018-01-20 21:59:08,460 INFO L87 Difference]: Start difference. First operand 14718 states and 21754 transitions. Second operand 10 states. [2018-01-20 21:59:13,241 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 21:59:13,241 INFO L93 Difference]: Finished difference Result 89092 states and 133872 transitions. [2018-01-20 21:59:13,242 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 33 states. [2018-01-20 21:59:13,242 INFO L78 Accepts]: Start accepts. Automaton has 10 states. Word has length 107 [2018-01-20 21:59:13,242 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 21:59:13,472 INFO L225 Difference]: With dead ends: 89092 [2018-01-20 21:59:13,472 INFO L226 Difference]: Without dead ends: 74379 [2018-01-20 21:59:13,514 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 161 GetRequests, 126 SyntacticMatches, 0 SemanticMatches, 35 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 280 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=272, Invalid=1060, Unknown=0, NotChecked=0, Total=1332 [2018-01-20 21:59:13,548 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 74379 states. [2018-01-20 21:59:18,297 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 74379 to 71089. [2018-01-20 21:59:18,297 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 71089 states. [2018-01-20 21:59:18,481 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 71089 states to 71089 states and 105835 transitions. [2018-01-20 21:59:18,482 INFO L78 Accepts]: Start accepts. Automaton has 71089 states and 105835 transitions. Word has length 107 [2018-01-20 21:59:18,482 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 21:59:18,482 INFO L432 AbstractCegarLoop]: Abstraction has 71089 states and 105835 transitions. [2018-01-20 21:59:18,482 INFO L433 AbstractCegarLoop]: Interpolant automaton has 10 states. [2018-01-20 21:59:18,482 INFO L276 IsEmpty]: Start isEmpty. Operand 71089 states and 105835 transitions. [2018-01-20 21:59:18,497 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 108 [2018-01-20 21:59:18,497 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 21:59:18,498 INFO L322 BasicCegarLoop]: trace histogram [7, 7, 6, 6, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-20 21:59:18,498 INFO L371 AbstractCegarLoop]: === Iteration 16 === [mainErr0EnsuresViolation]=== [2018-01-20 21:59:18,498 INFO L82 PathProgramCache]: Analyzing trace with hash -1515124594, now seen corresponding path program 1 times [2018-01-20 21:59:18,498 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 21:59:18,498 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 21:59:18,499 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:59:18,499 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 21:59:18,499 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:59:18,525 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 21:59:18,526 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 21:59:18,980 INFO L134 CoverageAnalysis]: Checked inductivity of 146 backedges. 2 proven. 117 refuted. 0 times theorem prover too weak. 27 trivial. 0 not checked. [2018-01-20 21:59:18,981 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-20 21:59:18,981 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/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-01-20 21:59:18,986 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 21:59:19,046 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 21:59:19,049 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-20 21:59:19,129 INFO L134 CoverageAnalysis]: Checked inductivity of 146 backedges. 67 proven. 13 refuted. 0 times theorem prover too weak. 66 trivial. 0 not checked. [2018-01-20 21:59:19,150 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-20 21:59:19,150 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 9] total 19 [2018-01-20 21:59:19,151 INFO L409 AbstractCegarLoop]: Interpolant automaton has 19 states [2018-01-20 21:59:19,151 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2018-01-20 21:59:19,151 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=38, Invalid=304, Unknown=0, NotChecked=0, Total=342 [2018-01-20 21:59:19,151 INFO L87 Difference]: Start difference. First operand 71089 states and 105835 transitions. Second operand 19 states. Received shutdown request... [2018-01-20 21:59:21,877 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 62 states. [2018-01-20 21:59:21,878 WARN L491 AbstractCegarLoop]: Verification canceled [2018-01-20 21:59:21,880 INFO L322 AbstractCegarLoop]: Interprodecural is true [2018-01-20 21:59:21,880 INFO L323 AbstractCegarLoop]: Hoare is true [2018-01-20 21:59:21,880 INFO L324 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-01-20 21:59:21,880 INFO L325 AbstractCegarLoop]: Backedges is TWOTRACK [2018-01-20 21:59:21,880 INFO L326 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-01-20 21:59:21,880 INFO L327 AbstractCegarLoop]: Difference is false [2018-01-20 21:59:21,880 INFO L328 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-01-20 21:59:21,880 INFO L333 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == pushErr0EnsuresViolation======== [2018-01-20 21:59:21,880 INFO L87 2NestedWordAutomaton]: Mode: main mode - execution starts in main procedure [2018-01-20 21:59:21,881 INFO L276 IsEmpty]: Start isEmpty. Operand 62 states. [2018-01-20 21:59:21,882 WARN L491 AbstractCegarLoop]: Verification canceled [2018-01-20 21:59:21,883 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 20.01 09:59:21 BoogieIcfgContainer [2018-01-20 21:59:21,883 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2018-01-20 21:59:21,884 INFO L168 Benchmark]: Toolchain (without parser) took 41831.09 ms. Allocated memory was 304.1 MB in the beginning and 1.6 GB in the end (delta: 1.3 GB). Free memory was 261.4 MB in the beginning and 131.6 MB in the end (delta: 129.8 MB). Peak memory consumption was 1.4 GB. Max. memory is 5.3 GB. [2018-01-20 21:59:21,885 INFO L168 Benchmark]: CDTParser took 0.14 ms. Allocated memory is still 304.1 MB. Free memory is still 267.4 MB. There was no memory consumed. Max. memory is 5.3 GB. [2018-01-20 21:59:21,886 INFO L168 Benchmark]: CACSL2BoogieTranslator took 258.26 ms. Allocated memory is still 304.1 MB. Free memory was 261.4 MB in the beginning and 249.4 MB in the end (delta: 12.0 MB). Peak memory consumption was 12.0 MB. Max. memory is 5.3 GB. [2018-01-20 21:59:21,886 INFO L168 Benchmark]: Boogie Preprocessor took 35.18 ms. Allocated memory is still 304.1 MB. Free memory was 249.4 MB in the beginning and 247.4 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 5.3 GB. [2018-01-20 21:59:21,886 INFO L168 Benchmark]: RCFGBuilder took 353.18 ms. Allocated memory is still 304.1 MB. Free memory was 247.4 MB in the beginning and 224.8 MB in the end (delta: 22.6 MB). Peak memory consumption was 22.6 MB. Max. memory is 5.3 GB. [2018-01-20 21:59:21,887 INFO L168 Benchmark]: TraceAbstraction took 41176.80 ms. Allocated memory was 304.1 MB in the beginning and 1.6 GB in the end (delta: 1.3 GB). Free memory was 224.8 MB in the beginning and 131.6 MB in the end (delta: 93.2 MB). Peak memory consumption was 1.4 GB. Max. memory is 5.3 GB. [2018-01-20 21:59:21,889 INFO L344 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.14 ms. Allocated memory is still 304.1 MB. Free memory is still 267.4 MB. There was no memory consumed. Max. memory is 5.3 GB. * CACSL2BoogieTranslator took 258.26 ms. Allocated memory is still 304.1 MB. Free memory was 261.4 MB in the beginning and 249.4 MB in the end (delta: 12.0 MB). Peak memory consumption was 12.0 MB. Max. memory is 5.3 GB. * Boogie Preprocessor took 35.18 ms. Allocated memory is still 304.1 MB. Free memory was 249.4 MB in the beginning and 247.4 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 5.3 GB. * RCFGBuilder took 353.18 ms. Allocated memory is still 304.1 MB. Free memory was 247.4 MB in the beginning and 224.8 MB in the end (delta: 22.6 MB). Peak memory consumption was 22.6 MB. Max. memory is 5.3 GB. * TraceAbstraction took 41176.80 ms. Allocated memory was 304.1 MB in the beginning and 1.6 GB in the end (delta: 1.3 GB). Free memory was 224.8 MB in the beginning and 131.6 MB in the end (delta: 93.2 MB). Peak memory consumption was 1.4 GB. Max. memory is 5.3 GB. * Results from de.uni_freiburg.informatik.ultimate.boogie.preprocessor: - GenericResult: Unfinished Backtranslation Generated EnsuresSpecification ensures #valid == old(#valid); is not ensure(true) - GenericResult: Unfinished Backtranslation Generated EnsuresSpecification ensures #valid == old(#valid); is not ensure(true) - GenericResult: Unfinished Backtranslation Generated EnsuresSpecification ensures #valid == old(#valid); is not ensure(true) - GenericResult: Unfinished Backtranslation Generated EnsuresSpecification ensures #valid == old(#valid); is not ensure(true) * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - PositiveResult [Line: 660]: all allocated memory was freed For all program executions holds that all allocated memory was freed at this location - StatisticsResult: Ultimate Automizer benchmark data for error location: popErr0EnsuresViolation CFG has 5 procedures, 62 locations, 5 error locations. SAFE Result, 0.4s OverallTime, 1 OverallIterations, 1 TraceHistogramMax, 0.1s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 78 SDtfs, 0 SDslu, 0 SDs, 0 SdLazy, 0 SolverSat, 0 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 0.0s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 1 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=62occurred in iteration=0, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s AbstIntTime, 0 AbstIntIterations, 0 AbstIntStrong, NaN AbsIntWeakeningRatio, NaN AbsIntAvgWeakeningVarsNumRemoved, NaN AbsIntAvgWeakenedConjuncts, AutomataMinimizationStatistics: 0.0s AutomataMinimizationTime, 1 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: 0.0s HoareAnnotationTime, 8 LocationsWithAnnotation, 8 PreInvPairs, 8 NumberOfFragments, 8 HoareAnnotationTreeSize, 8 FomulaSimplifications, 0 FormulaSimplificationTreeSizeReduction, 0.0s HoareSimplificationTime, 8 FomulaSimplificationsInter, 0 FormulaSimplificationTreeSizeReductionInter, 0.0s HoareSimplificationTimeInter, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.0s SatisfiabilityAnalysisTime, 0.0s InterpolantComputationTime, 14 NumberOfCodeBlocks, 14 NumberOfCodeBlocksAsserted, 1 NumberOfCheckSat, 13 ConstructedInterpolants, 0 QuantifiedInterpolants, 169 SizeOfPredicates, 0 NumberOfNonLiveVariables, 0 ConjunctsInSsa, 0 ConjunctsInUnsatCore, 1 InterpolantComputations, 1 PerfectInterpolantSequences, 0/0 InterpolantCoveringCapability, InvariantSynthesisStatistics: No data available, InterpolantConsolidationStatistics: No data available, REUSE_STATISTICS: No data available - CounterExampleResult [Line: 1]: not all allocated memory was freed not all allocated memory was freed We found a FailurePath: [L625] int pc1 = 1; [L626] int pc4 = 1; [L624] struct cell *S; [L627] static struct cell *t1 = ((void *)0); [L628] static struct cell *x1 = ((void *)0); [L657] struct cell* garbage; [L658] static struct cell *t4 = ((void *)0); [L659] static struct cell *x4 = ((void *)0); [L662] static int res4; VAL [\old(garbage)=17, \old(garbage)=15, \old(pc1)=7, \old(pc4)=11, \old(res4)=5, \old(S)=3, \old(S)=9, \old(t1)=12, \old(t1)=8, \old(t4)=4, \old(t4)=16, \old(x1)=1, \old(x1)=14, \old(x4)=6, \old(x4)=13, garbage={0:0}, pc1=1, pc4=1, res4=0, S={0:0}, t1={0:0}, t4={0:0}, x1={0:0}, x4={0:0}] - StatisticsResult: Ultimate Automizer benchmark data for error location: ULTIMATE.initErr0EnsuresViolation CFG has 5 procedures, 62 locations, 5 error locations. UNSAFE Result, 0.0s OverallTime, 1 OverallIterations, 1 TraceHistogramMax, 0.0s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: No data available, PredicateUnifierStatistics: No data available, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=62occurred in iteration=0, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s AbstIntTime, 0 AbstIntIterations, 0 AbstIntStrong, NaN AbsIntWeakeningRatio, NaN AbsIntAvgWeakeningVarsNumRemoved, NaN AbsIntAvgWeakenedConjuncts, AutomataMinimizationStatistics: No data available, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.0s SatisfiabilityAnalysisTime, 0.0s InterpolantComputationTime, 3 NumberOfCodeBlocks, 3 NumberOfCodeBlocksAsserted, 1 NumberOfCheckSat, 0 ConstructedInterpolants, 0 QuantifiedInterpolants, 0 SizeOfPredicates, 0 NumberOfNonLiveVariables, 0 ConjunctsInSsa, 0 ConjunctsInUnsatCore, 0 InterpolantComputations, 0 PerfectInterpolantSequences, 0/0 InterpolantCoveringCapability, InvariantSynthesisStatistics: No data available, InterpolantConsolidationStatistics: No data available, REUSE_STATISTICS: No data available - CounterExampleResult [Line: 1]: not all allocated memory was freed not all allocated memory was freed We found a FailurePath: [L625] int pc1 = 1; [L626] int pc4 = 1; [L624] struct cell *S; [L627] static struct cell *t1 = ((void *)0); [L628] static struct cell *x1 = ((void *)0); [L657] struct cell* garbage; [L658] static struct cell *t4 = ((void *)0); [L659] static struct cell *x4 = ((void *)0); [L662] static int res4; VAL [\old(garbage)=0, \old(garbage)=0, \old(pc1)=1, \old(pc4)=1, \old(res4)=0, \old(S)=0, \old(S)=0, \old(t1)=0, \old(t1)=0, \old(t4)=0, \old(t4)=0, \old(x1)=0, \old(x1)=0, \old(x4)=0, \old(x4)=0, garbage={0:0}, pc1=1, pc4=1, res4=0, S={0:0}, t1={0:0}, t4={0:0}, x1={0:0}, x4={0:0}] [L690] S || 1 != pc1 || __VERIFIER_nondet_int() [L690] S || 1 != pc1 || __VERIFIER_nondet_int() VAL [\old(garbage)=0, \old(garbage)=0, \old(pc1)=1, \old(pc4)=1, \old(res4)=0, \old(S)=0, \old(S)=0, \old(t1)=0, \old(t1)=0, \old(t4)=0, \old(t4)=0, \old(x1)=0, \old(x1)=0, \old(x4)=0, \old(x4)=0, __VERIFIER_nondet_int()=0, garbage={0:0}, pc1=1, pc4=1, res4=0, S={0:0}, S || 1 != pc1 || __VERIFIER_nondet_int()=0, t1={0:0}, t4={0:0}, x1={0:0}, x4={0:0}] [L690] COND FALSE !(S || 1 != pc1 || __VERIFIER_nondet_int()) [L696] COND FALSE !(\read(*garbage)) VAL [\old(garbage)=0, \old(garbage)=0, \old(pc1)=1, \old(pc4)=1, \old(res4)=0, \old(S)=0, \old(S)=0, \old(t1)=0, \old(t1)=0, \old(t4)=0, \old(t4)=0, \old(x1)=0, \old(x1)=0, \old(x4)=0, \old(x4)=0, garbage={0:0}, pc1=1, pc4=1, res4=0, S={0:0}, t1={0:0}, t4={0:0}, x1={0:0}, x4={0:0}] [L701] S = ((void *)0) [L702] t1 = ((void *)0) [L703] x1 = ((void *)0) [L704] t4 = ((void *)0) [L705] x4 = ((void *)0) [L706] return !!garbage; VAL [garbage={0:0}, pc1=1, pc4=1, res4=0, S={0:0}, t1={0:0}, t4={0:0}, x1={0:0}, x4={0:0}] - StatisticsResult: Ultimate Automizer benchmark data for error location: ULTIMATE.startErr0EnsuresViolation CFG has 5 procedures, 62 locations, 5 error locations. UNSAFE Result, 0.2s OverallTime, 3 OverallIterations, 1 TraceHistogramMax, 0.0s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 151 SDtfs, 0 SDslu, 69 SDs, 0 SdLazy, 5 SolverSat, 0 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 0.0s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 5 GetRequests, 4 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=62occurred in iteration=0, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s AbstIntTime, 0 AbstIntIterations, 0 AbstIntStrong, NaN AbsIntWeakeningRatio, NaN AbsIntAvgWeakeningVarsNumRemoved, NaN AbsIntAvgWeakenedConjuncts, AutomataMinimizationStatistics: 0.0s AutomataMinimizationTime, 2 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.0s SatisfiabilityAnalysisTime, 0.0s InterpolantComputationTime, 41 NumberOfCodeBlocks, 41 NumberOfCodeBlocksAsserted, 3 NumberOfCheckSat, 24 ConstructedInterpolants, 0 QuantifiedInterpolants, 296 SizeOfPredicates, 0 NumberOfNonLiveVariables, 0 ConjunctsInSsa, 0 ConjunctsInUnsatCore, 2 InterpolantComputations, 2 PerfectInterpolantSequences, 0/0 InterpolantCoveringCapability, InvariantSynthesisStatistics: No data available, InterpolantConsolidationStatistics: No data available, REUSE_STATISTICS: No data available - TimeoutResultAtElement [Line: 688]: Timeout (TraceAbstraction) Unable to prove that all allocated memory was freed (line 688). Cancelled while BasicCegarLoop was constructing difference of abstraction (71089states) and interpolant automaton (currently 62 states, 19 states before enhancement), while PredicateComparison was comparing new predicate (quantifier-free) to 79 known predicates. - StatisticsResult: Ultimate Automizer benchmark data for error location: mainErr0EnsuresViolation CFG has 5 procedures, 62 locations, 5 error locations. TIMEOUT Result, 40.3s OverallTime, 16 OverallIterations, 7 TraceHistogramMax, 26.9s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 1302 SDtfs, 10240 SDslu, 4101 SDs, 0 SdLazy, 8269 SolverSat, 3311 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 7.0s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 1606 GetRequests, 1061 SyntacticMatches, 3 SemanticMatches, 541 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 17467 ImplicationChecksByTransitivity, 12.6s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=71089occurred in iteration=15, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s AbstIntTime, 0 AbstIntIterations, 0 AbstIntStrong, NaN AbsIntWeakeningRatio, NaN AbsIntAvgWeakeningVarsNumRemoved, NaN AbsIntAvgWeakenedConjuncts, AutomataMinimizationStatistics: 8.3s AutomataMinimizationTime, 15 MinimizatonAttempts, 17698 StatesRemovedByMinimization, 13 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.2s SsaConstructionTime, 0.6s SatisfiabilityAnalysisTime, 3.5s InterpolantComputationTime, 1881 NumberOfCodeBlocks, 1881 NumberOfCodeBlocksAsserted, 27 NumberOfCheckSat, 1855 ConstructedInterpolants, 4 QuantifiedInterpolants, 406877 SizeOfPredicates, 36 NumberOfNonLiveVariables, 5809 ConjunctsInSsa, 84 ConjunctsInUnsatCore, 26 InterpolantComputations, 10 PerfectInterpolantSequences, 1839/2224 InterpolantCoveringCapability, InvariantSynthesisStatistics: No data available, InterpolantConsolidationStatistics: No data available, REUSE_STATISTICS: No data available - TimeoutResultAtElement [Line: 629]: Timeout (TraceAbstraction) Unable to prove that all allocated memory was freed (line 629). Cancelled while IsEmpty was searching accepting run (input had 62 states). - StatisticsResult: Ultimate Automizer benchmark data for error location: pushErr0EnsuresViolation CFG has 5 procedures, 62 locations, 5 error locations. TIMEOUT Result, 0.0s OverallTime, 0 OverallIterations, 0 TraceHistogramMax, 0.0s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: No data available, PredicateUnifierStatistics: No data available, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=62occurred in iteration=0, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s AbstIntTime, 0 AbstIntIterations, 0 AbstIntStrong, NaN AbsIntWeakeningRatio, NaN AbsIntAvgWeakeningVarsNumRemoved, NaN AbsIntAvgWeakenedConjuncts, AutomataMinimizationStatistics: No data available, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: No data available, REUSE_STATISTICS: No data available RESULT: Ultimate proved your program to be incorrect! Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/lockfree-3.3_false-valid-memtrack.i_mempurity-32bit-Automizer_Camel+AI_EQ.epf_AutomizerC.xml/Csv-Benchmark-0-2018-01-20_21-59-21-898.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/lockfree-3.3_false-valid-memtrack.i_mempurity-32bit-Automizer_Camel+AI_EQ.epf_AutomizerC.xml/Csv-TraceAbstractionBenchmarks-0-2018-01-20_21-59-21-898.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/lockfree-3.3_false-valid-memtrack.i_mempurity-32bit-Automizer_Camel+AI_EQ.epf_AutomizerC.xml/Csv-TraceAbstractionBenchmarks-1-2018-01-20_21-59-21-898.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/lockfree-3.3_false-valid-memtrack.i_mempurity-32bit-Automizer_Camel+AI_EQ.epf_AutomizerC.xml/Csv-TraceAbstractionBenchmarks-2-2018-01-20_21-59-21-898.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/lockfree-3.3_false-valid-memtrack.i_mempurity-32bit-Automizer_Camel+AI_EQ.epf_AutomizerC.xml/Csv-TraceAbstractionBenchmarks-3-2018-01-20_21-59-21-898.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/lockfree-3.3_false-valid-memtrack.i_mempurity-32bit-Automizer_Camel+AI_EQ.epf_AutomizerC.xml/Csv-TraceAbstractionBenchmarks-4-2018-01-20_21-59-21-898.csv Completed graceful shutdown