Chapter 4
Software Test Data Generation from a Genetic Algorithm

Ken Borgelt

Corporate Software Center, US
Motorola Inc.
1301 E. Algonquin Road
Schaumburg, IL 60196
e-mail: ckb009@email.mot.com

ABSTRACT

The work presented in this chapter investigates how a genetic algorithm may be used to produce software unit test data for use in structural testing. A unit test attempts to execute each line of source code in a software module at least once. It is typically performed using a source level debugger after a software module is written or modified. The particular path taken through the module (and there may be many) is determined by the value of any input data as well as data returned from function calls or other sources. Prior art focuses on configuring a genetic algorithm to identify test data executing a specific path, block of code, or control statement. The approach considered here differs in that its goal is to optimize a population of test data which as a whole provides the desired module coverage. This chapter documents how varying population sizes and a new fitness function influence the formation of a suitable set of test data for a simple software program. The fitness function described here provides improvement over the prior art. The performance gains observed result from making the genetic algorithm aware of the structure of the software module being tested. This work is the first step toward the creation of a software development utility to automatically produce unit test data.

INTRODUCTION

Computer software will continue to increase in size and capability as long as customers press for new features and manufacturers keep designing larger storage devices. This is colloquially known as Parkinson’s Law of Data. Software is also being used more often in mission critical applications and embedded products where error free operation is paramount. At the same time, companies like Motorola are pressing developers to take significant steps to reduce a product’s time-to-market.

Motorola’s Land Mobile Products Sector produces two-way radio based communications systems for municipalities, governments, and utilities. Some land mobile systems, such as those providing state wide coverage for Michigan and Florida, are quite large and complex. Systems are comprised of numerous specialized pieces of equipment. Each of these is an embedded system with at least one microprocessor running software designed to perform some specialized task in the system, such as system control, resource assignment, audio routing, or radio transmit and receive processing. The Repeater Software group produces software for one of these system boxes, an embedded multiprocessor base station. The software used in this product has been developed incrementally over the past seven years by a large number of engineers.

Software that has been maintained over time is commonly called“legacy”code. Adding new features to legacy code is usually the most cost effective way to add new functionality to an older product. This practice is not always painless because it is impossible to anticipate design decisions for features scheduled for development in the distant future. Poor choices early in the development cycle can be difficult to rectify because tight development schedules and overlapping development phases can limit redesign efforts. The result is a poorly designed feature marked by overly complex and error prone software modules. Unit test plans for such modules tend not to be maintained because of their high complexity. Also, developers sometimes do not execute test plans for such modules even when they are available. Instead, developers will test only the functionality they have changed, increasing the risk of not catching a serious problem in the software.

The worst scenario is when a developer modifies a module that is complex enough to impair understanding. The addition of some feature to such a module must be performed so that the existing features continue to work. If the developer breaks one of the older legacy features and does not perform a full unit test, he or she may not find the flaw until system test or later. The worst situation is a bug in software released to customers.