JWalk
Look Inside JWalk

JWalk is for Java programmers, who work in agile software development teams. That is, you prefer to design by prototyping code, and you're not afraid to change the codebase frequently. You may avoid formal design and specification, but would still like to have guarantees on the quality of your tested code.

You may rely on regression testing, in which you hand-craft tests for the current version of your code. But you find that writing tests that cover all aspects of your code becomes increasingly tedious, and you miss some cases. Furthermore, your test suites rapidly grow out of date, so you spend as much time fixing tests as you do fixing bugs in your code.

How does JWalk Help?

Test automation is a much-hyped concept, but sometimes refers only to running all your test scripts automatically. This hardly addresses any of the difficult tasks in software testing! JWalk automates much more of the testing process, taking more of the burden away from the programmer:

• JWalk assumes that the code is a flawed, partly reliable expression of the design intent, yet good enough to start testing;

• JWalk generates minimal test suites that cover the states of the tested code automatically, something that testers find hard to do;

• JWalk makes better use of the human-in-the-loop, by prompting for confirmation of selected test outcomes, and automatically testing the rest.

Systematic Testing

Human test-authors can usually identify positive tests for what they expect to see, such as successfully issuing a Loan of a Book to a Borrower. But they are not good at identifying negative tests for things they do not expect to see, such as discharging the same Loan twice! What should even happen in this case?

JWalk's systematic testing explores the constructors and methods of the test class exhaustively. Each unique test sequence consists of a constructor call, followed by one or more method invocations. Eventually, every possible interleaved combination of methods is explored - in both expected and unexpected orders.

JWalk populates each sequence with a predictable set of input arguments, so that the same states are recognised if they are seen again.  This allows the tool to prune redundant tests.

JWalk performs all testing internally within the tool.  That is, it does not export test suites.  This is because it expects the test class to evolve rapidly, so saved tests rapidly go out of date.  JWalk regenerates the tests on each execution.

JWalk saves an oracle file when asked to VALIDATE the behaviour of the test class.  This file is a simple text file encoding the pass or fail results of test sequences.  These were either confirmed by the tester, or predicted by the tool.

JWalk can then detect whether a modified test class deviates from a previously-trained oracle.

Protocol Exploration

The exhaustive testing of interleaved methods is called protocol exploration.  This creates test suites of increasing length that execute the test class's public methods in all interleaved combinations. 

JWalk exploring all interleaved methods of a Stack

The figure above shows JWalk exercising a Stack class, interleaving all of its methods, to a bounded depth of 7 methods.  The results pane highlights Test Cycle #4, which shows all permutations of test sequences of length 4.  In protocol exploration:

• the same method may be invoked more than once, at any position in the sequence;

• the results are evaluated as NORMAL or EXCEPTION, depending on whether execution was nominal or raised an exception;

• the final state of the target Stack is compared with its previous states, reporting whether this was unchanged, or reentrant (returning to a visited state).

Protocol exploration is computationally expensive in the number of paths (see figure).  JWalk mitigates this slightly by terminating paths that end in exceptions, since the same exception will be raised at this point, in any future extension of the same path. 

Algebraic Exploration

JWalk exploring all algebraic constructions of a Stack

The figure above shows JWalk exploring all the algebraic constructions of a Stack, to a bounded depth of 3 methods.  In algebraic exploration:

• the prefix of every test sequence consists of the primitive method push() that takes the Stack into a new state.

• Every method is evaluated for each unique prefix, including observers isFull(), isEmpty() and transformer pop().

• Paths ending in observer-methods are then terminated because they did not change the target's state.

• Paths ending in transformer-methods are also terminated because they returned the target to a previous state.

This pruning is admissible (safe), because a shorter sequence already exists in the test suite that reaches the same state.

Algebraic exploration is computationally cheap in the number of paths explored (see figure).  Altogether, JWalk terminates paths ending in exceptions, observers and transformers, such that only those paths consisting of primitive methods are extended in longer tests.

State-Space Exploration

State-space exploration is sometimes useful if the test class exists in a number of high-level states, and the tester wishes to explore its behaviour exhaustively in each state.

For JWalk to detect high-level states, the test class must supply one or more state predicates.  These are methods with no argument and a boolean result.  Stack has two such methods:

• isEmpty() - true when the target Stack is empty

• isFull() - true when the target is full (with five elements)

JWalk discovering the Empty, Default, Full states of a Stack

The figure above shows that JWalk discovered three high-level states for the Stack.  These are:

• Empty - when isEmpty() is true, but isFull() is false;

• Full - when isFull() is true, but isEmpty() is false;

• Default - when both predicates are false.

JWalk failed to find a state in which both predicates were true, so it concluded correctly that the two predicates are not independent (they both measure the stack-counter).

JWalk exploring all transition-pairs in every Stack state

The figure above shows JWalk exercising all transition-pairs in every high-level state of the Stack.  The results pane highlights the Full: Test Cycle #1, which displays the results of executing every single method in the Full state.

State-space exploration can be computationally expensive, and produces many more results (count the number of tabs in the results pane).

Things to Try