Model based testing

Presented at the 1999 International Conference on Testing Computer Software

Graph Theory Techniques in Model-Based Testing

Harry Robinson Semantic Platforms Test Group Microsoft Corporation
harryr@microsoft.com

Abstract
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 manydifferent 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 individuallycrafted 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 thesechallenges by generating tests from explicit descriptions of the application. It is easier, therefore, to generate and maintain useful, flexible tests. 1

What’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 stategraph, 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, asshown 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 dotesting. (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 thespecifications 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.

2

What’s Graph Theory?
Graph theory has nothing to do with graph paper or x- and y-axes. Graph theory is an area ofmathematics 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...