Want to be a testing guru? Use reachability graphs (Part 3)

In the previous post, I showed you how useful reachability graphs can be in documenting almost infinite steps to recreate a bug.

Reachability graphs are really the next step in bug reports, where you not only specify how you exposed a specific bug, step-by-step, but it documents how to recreate the bug in a very terse manner that shows all the relevant abstract states that exposed that bug.

In this post, I want to discuss another feature of reachability graphs that make them more powerful than you think.



Irrelevant states

Notice in the steps I described for the test in the previous post that I did not explicitly prescribe closing the search box when typing in the second address. In fact, I explicitly stated not to close it.

However, what happens if you do? Does the bug still appear? Is the bug related to leaving the box open or the text typed in?

Try this: perform those combinations of steps yourself, and record what you find. Only then, continue reading this post.

Did you try the different steps? Did the bug still appear?

if you study the reachability graph from the previous post, you will notice the following group of nodes and edges, which I have outlined with red in the snapshot below.

Reachability graphs make irrelevant states clear

Reachability graphs make irrelevant states clear


If you tried the different steps yourself, you noticed that it makes absolutely no difference whether or not you close the search box to expose the bug.

In other words, the open/close state of the search box is irrelevant because no matter what you do with it (leave it open or close it), the bug still appears. In other words, any of the two paths in the example above reach the same abstract state: that of the bug being exposed.

The ability to record and expose irrelevant states of the SUT (system under test) is one of the most powerful capabilities of reachability graphs.

This ability to expose irrelevant states is always in the form of the same pattern of edges and nodes, which I call the “bicycle pattern.” That is, whenever you have one node branching into more than one child node (where those children nodes are mutually exclusive, such as a node and its negation) and, in turn, they all eventually reach the same abstract state representing a fault, then you have irrelevant states at hand.

In the snapshot above taken from the example from the previous post, the two irrelevant states are “Search box explicitly/manually closed” and it’s negation, “Search box not explicitly/manually closed.”

I would like to emphasize that this property of reachability graphs holds every time, not just in certain cases. This property of such graphs can be used as a pattern for ruling out irrelevant properties from the search space when, say, you are debugging a problem or testing software.

If you are wondering how this can possibly be the case, I encourage you to read the research paper where I formalize and prove this property.

Further, the property is a necessary criterion in the sense that it does not lead to false positives. That is, it does not declare a property P as relevant to an abstract state when in fact it is not.

I encourage you to use these graphs whenever possible, as I am sure you will find them very useful.

Stay tuned for more examples of reachability graphs and their usage.