Yesterday, I started reading Using Production Grammar for Software Testing (UPGS) for Emin Sirer and N. Bershad (found on ModelBasedTesting site), the authors describes a method for generating test automaton based on "inversed" grammars. Following their ideas, I have designed a little framework, the Production Grammar Framework for .NET (PGF).

Introduction

In this blog, I will present a framework for defining and executing production grammars. The production grammars described in UPGS are very similar to classic "LALR" grammars, in terms of understanding and semantics. The difference is that production grammars reversed the work of grammar, since they are used to produce output instead of analyse input.

Production grammars can do anything, ranging form generating data, piloting your application and generating test case, ... Since we are looking at testing applications, here are a few application that we will be interrested on:

• manipulate the Implementation Under Test (IUT),
• generate test case that manipulate the IUT. In this case, the grammar is a code generator,
• if you want to test IUT against input data, generate a wide range of possible inputs,
• etc...

Oracle problem

"Production grammars are well-suited for test generation not only because they can create diverse test cases effectively, but also because they can provide guidance on how the test cases they generate ought to behave. It is often hard to determine the correct system behavior for automatically generated test cases -- a fundamental difficulty known as the oracle problem. In the worst case, automated test generation may require reverse engineering and manual examination to determine the expected behavior of the system on the given test input."  The authors propose two ways of dealing with the oracle problem:

• comparing difference with another implementation,
• generating verification code along with the test code.

Since the PGF is based .NET code, you can theoretically add any verification code and if available, compare with any other implementation. This will be illustrated in the example

What is a Production Grammar:

"A production grammar is a collection of non-terminal rules to terminal rules that resembles a regular parsing grammar, but is used “in reverse.” That is, instead of parsing a sequence of tokens into higher level constructs, a production grammar generates a stream of tokens from a set of non-terminals that specify the overall structure of the stream".

Let's see that on a simple example. Consider the following comma separated list of names:

John,Paul,Marc

An valid EBNF grammar to parse this stream would be ([A-Z] designs capital letters, [a-z] lower case letters, + one or more occurence, * zero or more occurence):

name := [A-Z] [a-z]+
names := name (',' name)*

In the case of production grammar, we want to create that list of name. In C#, a possible implementation of the production grammar would be as follows:

public class NamesGrammar
{
   public string Name()
   {
        int count = nextRandom(); // gets a random int
        return getUpper() + getLowerString(count); // getUpper return upper case, getLowerString returns lower cased string
   }
   public string Names()
   {
        int count = nextRandom();
        string names = Name();
        for(int i=0;i!=count;++i)
           names += ',' + Name();
        return names;
   }
}

The example will generate a list name when the Names method is called, we have production :). This is just a dummy example, it is 100% hard-coded and very difficult to maintain. 

Production Grammar Framework

Before starting to work on an example (guess which), let us define important notations/interfaces of the PGF:

• a rule (IRule) is an object that produce something. A rule can be terminal, it does not have any sub-rules, or non-terminal. Example of non-terminal rule is the + operator, terminal rule would be writing a string to a stream.
• a production (IProduction) represents a production process (you can think of it as batch). It is passed on between the rules and can be stored to transmit the context or finish production,
• Each time a rule wants to produce, it asks the production for a production token (IProductionToken). If the request is succesfull, the production goes on; otherwise, the production finishes. Using this mechanism, you can easily design production that will stop on a finite number of rule production.
• a grammar (IGrammar) encapsultates a start rule and is used to launch the production process,

Those 5 interfaces form the kernel of the PGF, the rest of the framework is built on top and around them to help the user implement grammars.

The working example: a Stack

In order to crystilase the ideas presented here, we will consider the problem of testing a Stack (as in Test Driven Developement in .NET). A simple unbounded stack can be formalized by the following interface:

public interface IStack
{
    void Push(Object);
    Object Pop();
    Object Peek(); // equivalent to Pop() in TDD
    bool IsEmpty {get;}
}

The grammar

Before writing down the grammar in C#, it is useful to formalize it in a "pseudo" EBNF-like notation. In this example, there are 3 terminals: Push, Pop, Peek (we omit IsEmpty for now):

push := stack.Push(...)
pop := stack.Pop()
peek := stack.Peek()

 Since Pop and Peek can throw if the stack is empty, we create a special non-terminal rule  that guards production agains a specific exception type. This gives us the 2 following non-terminal rules:

gardedPop := gard( pop, InvalidOperationException )
gardedPeek := gard( peek, InvalidOperationException )

Of course, we need to be able to decided wheter we want to execute the guarded rule or the non guarded. Again, we define a new non-terminal rule that works as a "if-then-else". This gives us 1 more non-terminal rule:

nonEmpty := push | pop | peek
empty := push | gardedPop | guardedPeek
stackRule := if(isEmpty) { empty } else { nonEmpty }

The final step is to decide how many execution we want. Since we can break the production at the IProduction level, we go for infinite:

stackGrammar := stackRule*

The full grammar can be summarized as

push := stack.Push(...)
pop := stack.Pop()
peek := stack.Peek()
gardedPop := gard( pop, InvalidOperationException )
gardedPeek := gard( peek, InvalidOperationException )
nonEmpty := push | pop | peek
empty := push | gardedPop | guardedPeek
stackRule := if(isEmpty) { empty } else { nonEmpty }
stackGrammar := stackRule*

At this point, we have define a grammar for piloting the stack written in a "pseudo"-EBNF language. The simplicity of the notation let us concentrate on the problem and not on the tool to solve it. However, as it is, the grammar is pretty much useless, since it is missing verification code. We will see that the verification code can be easily added while writing the grammar in C#.

Rewriting the grammar in C# with PGF

The PGF contains a bunch of built-in non-terminal rules and helpers that will help you translate a grammar into functional C# code. In this example, we will encapsulate the grammar in a StackFixture class that contains a stack field:

public class StackFixture 
{
    private Stack stack = new Stack();
}

Step 1: Creating the terminal methods

Following the way we constructed the grammar, we begin by defining the terminals. The easiests solution is to define one method for each terminal and then wrap it into a IRule. For example, the push terminal is implemented as follows:

public class StackFixture 
{
    private Stack stack = new Stack();
    private IRule push;

    public void Push()
    {
        this.stack.Push(null);
    }

    public void CreateGrammar()
    {
        this.push = Rules.Method(new DefaultMethodDelegate(this.Push));
    }
}

We have added 3 things: a IRule field member to store the "push" terminal, a Push method that actually pushes something on the tested stack and a CreateRules method that will be used to creates the grammar. The Rules.Method is a static helper class that encapsulate the call to a member method into a rule. The same operation can be repeated for pop and peek.

Step 2: Adding code for the Oracle problem

In order to be able to verify assertion on the fixture, we need to solve the Oracle problem. For this specifiy case, we can do the Comparaison testing approach where we execute the operations on another implementation and verify that outputs are different (NC, not NSC). 

public class StackFixture 
{
    private ArrayList list = new ArrayList();
    private Stack stack = new Stack();
    private IRule push;

    public void Push()
    {
        this.stack.Push(null);
        this.list.Add(null);
        Assert.AreEqual(list.Count==0, stack.IsEmpty);
        Assert.AreEqual(list[list.Count-1], stack.Peek());
    }
    ...
}

Step 3: Creating the non-terminal rules

From this step, the PGF provides the "classic" non-terminal rules and helper classes to create them (Rules) that makes the rest of the implementation straightforward:

public class StackFixture
{
    ...
    IRule push, pop, peek;
    IRule guardedPop, guardedPeek;
    IRule empty, nonEmpty;
    IRule stackRule;
    IRule stackGrammar;
    ...

    // returns true if stack is empty
    public bool IsEmpty()
    {
         return this.stack.IsEmpty;
    }

    public void CreateGrammar()
    {
        push = Rules.Method(new DefaultMethodDelegate(Push));
        pop = Rules.Method(new DefaultMethodDelegate(Pop));
        peek = Rules.Method(new DefaultMethodDelegate(Peek));

        guardedPop = Rules.Guard( pop, typeof(InvalidOperationException) ); // gard( pop, InvalidOperationException)
        guardedPeek = Rules.Guard( peek, typeof(InvalidOperationException) );// gard( pop, InvalidOperationException)

        nonEmpty = Rules.Alt( push, pop, peek); // push | pop | peek
        empty = Rules.Alt( push, guardedPop, guardedPeek);
 
        stackRule = Rules.If(new ConditionDelegate(IsEmpty), empty, nonEmpty); // if(IsEmtpy) empty else nonEmpty

        stackGrammar = Rules.Kleene(stackRule); // stackRule*
    }
}

Step 4: Creating a grammar and executing a production

In order to simplify our lives, we make StackFixture inherit from the Grammar class (which implement IGrammar) provided by the PGF. This class takes care of setting up the production factory and launching productions. Of course, this part of the framework can be easily customized and extended to plugin into your existing test automaton (MbUnit, NUnit, csUnit, ...).

public class StackFixture : Grammar
{
    public StackFixture()
    { 
        this.CreateRules();
    }
    public void CreateRules()
    {
        ...
        // required for Grammar
        this.StartRule = this.stackGrammar;
    }
}

A production can then be executed by launching the Produce method:

StackFixture fixture =new StackFixture();
fixture.Produce();

Conlusion

Production Grammar Framework is an effective tool to create and implement production grammar. Production grammar are used to model the complex behavior of application and automate the creation of complex test case. In fact, you could easily reuse your existing Unit Test cases with a production grammar! Of course, PGF will be part of MbUnit in the next release. Moreover, since the "hard" work is done by the machine, you can expect to get much better code coverage using Production Grammar (or MBT) than with classical unit tesing.

Future directions and the quizz

This post is already long so I will stop here. However, you can start to think about other interresting use of this technique:

• database testing,
• data generation for user input testing,
• unit test case generation using CodeDom,
• etc...

The quizz question: How does this relates to model based testing ?