Graph Theory Techniques in Model-Based Testing
By: Harry Robinson
Models are a method of representing software behavior. Graph theory is an area of mathematics that can
help us use this model information to test applications in many different ways. This paper describes
several graph theory techniques, where they came from, and how they can be used to improve software
What’s Wrong with Traditional Software Testing?
Traditional software testing consists of the tester studying the software system and then writing and
executing individual test scenarios that exercise the system. These scenarios are individually crafted and
then can be executed either manually or by some form of capture/playback test tool.
This method of creating and running tests faces at least two large challenges:
First, these traditional tests will suffer badly from the “pesticide paradox” (Beizer, 1990) in which tests
become less and less useful at catching bugs, because the bugs they were intended to catch have been
caught and fixed.
Second, handcrafted test scenarios are static and difficult to change, but the software under test is
dynamically evolving as functions are added and changed. When new features change the appearance
and behavior of the existing software, the tests must be modified to fit. If it is difficult to update the tests, it
will be hard to justify the test maintenance costs.
Model-based testing alleviates these challenges by generating tests from explicit descriptions of the
application. It is easier, therefore, to generate and maintain useful, flexible tests.
Modeling is a way of representing the behavior of a system. Models are simpler than the system they
describe, and they help us understand and predict the system’s behavior.
A common type of model in computing is the state graph, or finite state machine. State graphs are a
useful way to think about software behavior and testing (Beizer 1995). The application begins in some
state (such as “main window displayed”), the user applies an input (“invoke help dialog”) and the software
moves into a new state (“help dialog displayed”).
We use models all the time to understand behavior, as shown in Figure 1. In fact, much software testing
can be viewed as the tester ¡§moving through¡¨ the various states of an application under test and verifying
that each step worked correctly.
What¡¦s Model-Based Testing?
In recent years, there has been a growing movement in software testing to use the information contained
in explicit models of software behavior to make it simpler and cheaper to do testing. (Beizer 1995,
Model-based testing is a black-box technique that offers many advantages over traditional testing:
„h Constructing the behavioral models can begin early in the development cycle.
„h Modeling exposes ambiguities in the specification and design of the software.
„h The model embodies behavioral information that can be re-used in future testing, even when
the specifications change.
„h The model is easier to update than a suite of individual tests.
And, most importantly for the purpose of this paper, a model furnishes information that can be coupled
with graph theory techniques to generate many different test scenarios automatically.
What’s Graph Theory?
Graph theory has nothing to do with graph paper or x- and y-axes. Graph theory is an area of
mathematics that deals with entities (called nodes) and the connections (called links) between
the nodes. For instance, in Figure 1 above, the circles inscribed with “here” and “there” are
nodes; the line labeled “this” is a type of link.
A Quick Tour through Graph Theory
Graph theory began in the Prussian town of Königsberg in 1736. The town was built on both sides of the
Pregel River and on two islands in the middle of the river. On lazy Sunday afternoons, the happy citizens
of Königsberg would stroll across the seven bridges that joined the different parts of the town.
A common pastime during these Sunday strolls was to try to walk across each of the bridges exactly
once, finally returning to one’s starting place. After several years of trying without success, someone
thought to ask mathematician Leonhard Euler (pronounced “oiler”) if he could figure out if such a walk
was even possible.
Euler realized that he could model the Königsberg problem with nodes (labeled A, B, C and D above)
representing the landmasses and links connecting the nodes wherever a bridge connected two
landmasses. Once the problem was distilled down to this essence, Euler could see that the proposed
walk was impossible. The key factor was the number of links attached to each of the nodes.
For a walker to cross every bridge once and return home there must be an even number of links touching
each node. Having an even number of links attached to each node means that every time a walker enters
a node there will be an available link out of that node. In the case of the Königsberg bridges, each of the
four nodes has an odd number of links, so there is no way that a stroller could complete the tour without
crossing some bridges multiple times.
Since that time, a graph that contains only nodes with even numbers of links (which would permit the
walker to complete the desired stroll) has been called an “Euler graph” and the traversal of the various
links is called an “Euler tour”. (Gross and Yellen 1998)
... to read more articles, visit http://sqa.fyicenter.com/art/