1Presented at the 1999 International Conference on Testing Computer SoftwareGraph Theory Techniques in Model-Based Testing Harry RobinsonSemantic Platforms Test GroupMicrosoft [email protected] 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.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.2What’s Modeling?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 modelWe 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, 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.3What’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 TheoryGraph 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 GraphsA 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.4So what does all this have to do with the Cost of Delivering Mail in China?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