Presented at the 1999 International Conference on Testing Computer Software
Semantic Platforms Test Group
Microsoft Corporation
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 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”).
Figure 1: A user and his model
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.
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, Apfelbaum 1997)
Model-based testing is a black-box technique that offers many advantages over traditional testing:
Constructing the behavioral models can begin early in the development cycle.
Modeling exposes ambiguities in the specification and design of the software.
The model embodies behavioral information that can be re-used in future testing, even when the specifications change.
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.
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.
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.
Figure 2: From Bridges to Graphs
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)
And the citizens of Königsberg evidently had to find some other way to occupy their Sunday afternoons.
In 1962, a mere 226 years after the Königsberg incident, a mathematician named Kwan Mei-Ko asked a sensible follow-up question to the bridge-crossing problem. (Kwan 1962)
Given that it is impossible to cross each bridge exactly once and return to the starting point, what is the minimal amount of re-crossing a walker needs to do?
This is the type of problem a postman faces when delivering mail. Suppose that each of the links in the graph in Figure 3 is a street where mail must be delivered, and each of the nodes is an intersection where the postman can change direction. (Note that the node icons in Figure 3 display the number of links touching the node.) The postman must travel across each link to deliver the mail, but would like to minimize the amount of additional walking (called “deadheading”) that is needed.
Figure 3: A Postman’s Problem and a Postman’s Solution
Kwan’s solution was to treat re-crossing of any link as if it were adding duplicate links to the graph. These “duplicated” links could provide each node in the graph with an even number of attached links. This process is called “Eulerizing” the graph.
Once the graph was Eulerized, one could perform an Euler tour of the resulting modified graph. For example, the postman in Figure 3 could take the following minimal route to deliver his mail:
a b
c b e
f g d
d
repeating only the “b” and “d” segments of his route.
In Kwan’s honor, this problem became known as the “Chinese Postman Problem”.
Several years later, a useful variation on the Chinese Postman Problem asked for the minimal length tour when the links only allow passage in one direction. Since this is the problem faced by street sweepers in the one-way streets of New York, it became known as the New York Street Sweeper Problem. (Beltrami 1977, Bodin & Tucker 1983)
Figure 4: A Street Sweeper’s Problem and a Street Sweeper’s Solution
[Note: Some additional terminology is helpful here: links that can only be crossed in one direction are called arcs. And a graph consisting only of arcs is called a “directed graph” or digraph for short.]
In constructing an Euler tour in the Chinese Postman Problem, we were concerned with the number of links touching each node. In the case of a digraph, an Euler tour must also take account of the direction of the arcs touching each node. To “Eulerize” a digraph, it is necessary have equal numbers of arcs coming into the node and arcs leaving the node.
So, counting every incoming arc as “+1” and every outgoing arc as “-1”, we can calculate the “polarity” of each node in the digraph.
For example, a node with two outgoing arcs and one incoming arc would have a polarity of “ 1 – 2 = -1”.
(Note that the node icons in Figure 4 display each node’s polarity before and after Eulerization.)
To create an Eulerian digraph, we duplicate arcs between positive polarity nodes and negative polarity nodes so that each node ends up with zero polarity. This balancing of incoming and outgoing arcs achieves the same purpose as having even numbers of links in the case of the undirected graph: anyone entering a node via an incoming arc is guaranteed to be able to exit the node on an outgoing arc.
In Figure 4, we duplicated arcs “b”, “e” and “g” to balance the digraph. The street sweeper in Figure 4 can now use the following minimal directed route:
a b
c b f
e g d
e g
repeating only the “b”, “e” and “g” segments of his route.
Suppose you are a tester and you have a behavioral model of some software you would like to test. And suppose further that the model looks like the left hand digraph in Figure 5, where the nodes represent the states of the application and the arcs are the actions you can perform.
One of the first approaches you might think of is to execute every possible action. But how can you do it in an efficient manner? A quick look at the application’s state graph shows you that this is just the New York Street Sweeper Problem in a thin disguise!
Figure 5: A Tester’s Problem and a Tester’s Solution
Since you already have the behavioral model available to you as a graph, you can apply the appropriate graph algorithm to generate an efficient graph traversal automatically. In the example in Figure 5, our tester could test all available actions as follows:
a b
c b f
e g d
e g
Executing every action in the model is nice; it’s like achieving statement coverage when testing code. But since one of the defining characteristics of models is that there are typically a large number of possible “next actions” at every node in the graph, what can we do if we would like to test these combinations of actions? For instance, suppose the tester in Figure 5 wants to make sure to test link combinations such as “b c”, “b f”, and “b g”? A quick look at the sequences we generated shows us that “b g” appears nowhere in our test sequence. This is because the Chinese Postman and its variations guarantee visiting every link, but not every combination of links.
The approach of testing combinations of actions is called “switch cover” in finite state machine testing (Chow 1978). And there is a simple graph theory algorithm known as de Bruijn (pronounced “de-broyn”) sequences that generate the appropriate actions to get switch cover. (Gross and Yellen 1998)
In keeping with graph theory’s colorful nomenclature, de Bruijn sequences are also known as “safecracker sequences” because they describe “the shortest sequence of dial turns … sufficient to try out all combinations of length n.” (Skiena 1998)
The de Bruijn sequence for combinations of length 2 (all pairs of adjacent actions) is generated as follows:
Create a dual graph of the original graph (i.e., a graph in which the arcs of the original graph are converted to nodes)
Everywhere in the original graph that arc 1 is an incoming to a node and arc 2 is outgoing from the same node, create an arc in the dual graph from node 1 to node 2. For instance, in the left hand graph in Figure 6, arc “a” is incoming to the node from which arc “b” is outgoing; therefore in the dual graph (on the right hand side of Figure 6), there is an arc from node “a” to node “b”.
Figure 6 shows the completed dual graph.
Eulerize the dual graph (by duplicating arcs to balance node polarities)
Traverse the Eulerized graph, noting the names of the nodes that you pass.
Figure 6: A Model and its Dual Graph
The generated sequence will be the length 2 switch cover for the graph. (You can see that all 2-link combinations, including “b c”, “b f” and “b g” are generated.)
a b c b f e c b g d e f e g
Suppose you are faced with the following situation when
testing the software modeled in Figure 5:
You have several test machines available.
You have very limited time for testing
Each action in the behavioral model takes an hour to execute (purely for the sake of this discussion)
The application goes to the reset state when it receives input “g”.
Each test machine can run a test scenario from the reset state.
Look again at the Street Sweeper test sequence given for Figure 5:
a b
c b f
e g d
e g
If we divide these actions between two machines at the reset states (i.e., after executing action “g”), we get the following distribution:
