The AETG System

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. 23, NO. 7, JULY 1997437

The AETG System: An Approach to Testing

Based on Combinatorial Design

David M. Cohen, Member, IEEE Computer Society, Siddhartha R. Dalal, Member, IEEE

Michael L. Fredman, and Gardner C. Patton

Abstract—This paper describes a new approach to testing that uses combinatorial designs to generate tests that cover the pair-wise, triple, or n-way combinations of a system’s test parameters. These are the parameters that determine the system’s test

scenarios. Examples are system configuration parameters, user inputs and other external events. We implemented this new methodin the AETG system. The AETG system uses new combinatorial algorithms to generate test sets that cover all valid n-way

parameter combinations. The size of an AETG test set grows logarithmically in the number of test parameters. This allows testers todefine test models with dozens of parameters. The AETG system is used in a variety of applications for unit, system, and

interoperability testing. It has generated both high-level test plans and detailed test cases. In several applications, it greatly reducedthe cost of test plan development.

Index Terms—Testing, combinatorial designs, experimental designs, orthogonal arrays.

—————————— 3 ——————————

1INTRODUCTION

T

ESTING is an important but expensive part of the soft-

ware development process. Much research has beenaimed at reducing its cost. This paper describes a new ap-proach to testing that uses combinatorial designs to gener-ate efficient test sets. We implemented this method at Bell-core in the AETG system, which is used in Bellcore [8], [4],[5], [3], [6] and several of its clients [2] for unit, system, andinteroperability testing.

In this new approach, the tester first identifies parame-ters that define the space of possible test scenarios. For ex-ample, the parameters to test adding records to a data basesystem would describe the records that can be added in atransaction. The tester then uses combinatorial designs tocreate a test plan that “covers” all pair-wise, triple, or n-way combinations of the test parameters.

The motivation is two fold. First, there are many systemswhere troublesome faults are caused by the interaction of afew test parameters. A test plan should ideally cover thoseinteractions. The second is that the number of tests requiredto cover all n-way parameter combinations, for fixed n,grows logarithmically in the number of parameters. Thus,testers can define test models that have dozens of parame-ters and that still require only a small number of test cases.This gives testers the freedom to define models with

¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥

? D.M. Cohen is with the IDA Center for Computing Sciences, 17100Science Dr., Bowie, MD 20715. E-mail: dmcohen@http://wendang.chazidian.com.

? S.R. Dalal and G.C. Patton are with Bellcore, 445 South St. Morristown,NJ 07960. E-mail: {sid, gcp}@http://wendang.chazidian.com.

? M.L. Fredman is with the Department of Computer Science, RutgersUniversity, Busch Campus–Hill Center, New Brunswick, NJ 08903. E-mail: fredman@cs.rutgers.edu.

Please address all product inquiries about the AETG System to S.R. Dalal, Bell-core, 445 South St., Morristown, NJ 07960. The AETG System is covered byUnited States Patent 5,542,043.

Manuscript received 22 Aug. 1995; revised 2 Feb. 1997.Recommended for acceptance by R. Hamlet.

For information on obtaining reprints of this article, please send e-mail to:tse@http://wendang.chazidian.com, and reference IEEECS Log Number 103736.

enough detail to capture the semantics of the system undertest accurately. They don’t have to worry that refining amodel by adding one more test parameter will cause thenumber of tests to explode. Models with 80 and more pa-rameters are common.

We did some experiments to test the effectiveness ofAETG tests. In one experiment, we found faults in previ-ously tested modules from two releases of a Bellcore sys-tem, System A. In another, we measured the code coveragegiven by AETG tests for several Unix commands and sev-eral modules from System A. The pair-wise AETG test setsgave good code coverage for both examples.

The AETG system is used in a variety of applications.This paper describes two sample applications. In one, itdesigned a high-level test plan for the telephone 800 servicesoftware. In the other, it created detailed test cases for anATM network performance monitoring system. Designinggood test plans for these systems by hand would usuallyrequire one or two months. The AETG system reduced thetime to one or two weeks.

This paper reports on the AETG system. The next sectionmotivates the basic paradigm with an example. Section 3proves that the number of tests required by the combinato-rial design approach grows logarithmically in the numberof test parameters. Section 4 gives a heuristic algorithm togenerate tests. Section 5 gives an overview of the AETGinput language. Sections 6 and 7 describe the experimentswe did concerning effectiveness and two sample applica-tions. Section 8 concerns related work.

2THE BASIC COMBINATORIAL DESIGN PARADIGM

Consider the problem of testing a telephone switch’s abilityto place telephone calls. Table 1 shows four parameters thatdefine a very simple test model. The Call Type parametertells the type of call. Its values are Local, Long Distance,

0098-5589/97/$10.00 © 1997 IEEE

438IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. 23, NO. 7, JULY 1997and International. The Billing parameter says who pays for

the call. Its values are Caller (for bill to caller), Collect, and

800. The Access parameter tells how the calling party’s

phone is connected to the switch. The options considered in

this simple model are Loop, ISDN line, and a PBX trunk.

The final parameter, Status, tells whether or not the call was

successful or failed either because the calling party’s phone

was busy or the call was blocked in the phone network.

Since each different combination of parameter values

determines a different test scenario, and each of the four

parameters has three values, the table defines a total of 34 =

81 different scenarios. Suppose for argument’s sake that 81

tests is too many as each individual test is expensive. Then

one alternative would be to select a default value for each

parameter and then vary one parameter in each test until all

the parameter values are covered. Table 2 shows the re-

sulting test set. It has nine tests instead of the 81 required

for exhaustively testing all possible parameter combina-

tions. However, although it covers all individual parameter

values, it covers only 30 of the 9 ?? 6 = 54 possible pair-wise

interactions between the test parameters.

The test plan shown in Table 3 also has nine test cases

but, unlike the default test plan in Table 2, it covers every

pair-wise combination of parameter values. This test plan

was constructed using a well-known combinatorial design

based on the projective plane [12]. Since 2/3 of the calls in

this test plan do not complete successfully, this plan does

not reflect the system’s normal operational profile. In many

applications, a significant number of faults are caused by

parameter interactions that occur in atypical, yet realistic,

situations [4], [22]. A comprehensive test should also cover

these interactions. Since the combinatorial design method

covers them very efficiently, testers who feel that the test

plan should reflect the operational profile can use the com-

binatorial design method to complement tests derived from

the operational profile.

Suppose that the test model had 13 parameters instead

of 9 and that each had three values, say 0, 1, and 2. Then

there are 313 = 1,594,323 possible parameter combinations.

The default method for this configuration requires 27 test

cases and covers (13 ?? 12/2) + 26 ?? 12 = 390 of the (13 ?? 12

/2) ?? 9 = 702 possible pair-wise parameter combinations.

Table 4 [7] shows 15 tests that cover all pair-wise parameter

combinations. In general, default testing for n parameters

with three values each requires 2 ?? n + 1 tests and covers

5/9 of the pair-wise parameter combinations while pair-

wise testing requires 4 ?? log2 n tests and covers all the pair-

wise combinations. For example, for n = 40, exhaustive

testing requires 340 = 1.2 ?? 1019 tests and default testing 81

tests. Pair-wise testing requires only 21 tests.

In the next section, we show that the number of test cases

required to test all pair-wise or n-way parameter combina-

tions grows logarithmically in the number of parameters.

3LOGARITHMIC GROWTH FOR n-WAY INTERACTION

TESTING

We now show that the number of tests for n-way coverage

for fixed n grows logarithmically in the number of pa-rameters. For ease of notation, we state the proof for pair-wise coverage, i.e., for n = 2. The logarithmic growth fol-lows from the following.TABLE 1PARAMETERS FOR PLACING A TELEPHONE C

ALLTABLE 2DEFAULT TEST CASES FOR PLACING A PHONE CALLTABLE 3P

AIR-WISE TEST CASES FOR PLACING A PHONE CALLTABLE 4FIFTEEN

TEST CASES FOR 13 PARAMETERSWITH THREE VALUES EACH

COHEN ET AL.: THE AETG SYSTEM: AN APPROACH TO TESTING BASED ON COMBINATORIAL DESIGN439

THEOREM. Given a system with k parameters, each of which has l

values, suppose that r test cases have already been chosenand that the number of uncovered pairs isa test case that covers at least N/l2

N. Then there is

new pairs.PROOF. Consider the set

U = {(t, p): where t is a test case and p is a pair covered by t}.Since there are k parameters, each test case t covers k(k ?? 1)/2pairs. Thus, each test case t appears in U with k(k ?? 1)/2 dif-ferent pairs p. Since each parameter has l values, each pair p

appears in U with lk??2

different test cases.

Now, consider the subset V of (t, p) such that the testcase t is not one of the r already selected test cases and thepair p is not covered by any of the selected test cases. Wewill prove the theorem by counting the cardinality of V intwo different ways.

For any (t, p) in V, since the pair p is not covered, no testcase that contains p is among the already selected test cases.

Thus, p appears in V with lk??2

different test cases t, i.e., there

are lk??2

different test cases t such that (t, p) is in V. Thus, ifthe number of uncovered pairs is N, the cardinality of V is

N×lk?2

.

Card(V)=N×lk?2

For each unselected test case t, let mt be the number ofnew pairs covered by t. Let mt be 0 if t is one of the r se-lected test cases. Then t appears in V mt times. Thus,

Card(V)=

Σtmt

Now let m be the largest of the mt. To prove the theorem,

we must show that m is at least N/l2

. Since the total num-ber of possible test cases is lk, we have the following ine-quality:

Card(V)=

Σtmt≤m×lk.

Thus, N×lk?2≤m×lk, or

N/l2

≤m.

We proved the theorem by showing that at each step in

generating a test set, there is a test case that covers 1/l2

ofthe remaining pairs. Now consider a greedy algorithm thatat each step chooses a test case that covers the most uncov-ered pairs. Let N be the number of pairs at the start. Sincethere are k fields with l values each, N = k(k ?? 1)/2 ?? http://wendang.chazidian.coming the greedy algorithm, after r test cases have beenchosen, the number of remaining pairs is

N′≤N×(1?1/l2)r.

Thus, if r > ??log(N) / log(1 ?? 1/l2

) then N′ < 1 and all thepairs have been covered. Using the approximation that

log(1 ?? 1/l2) = ??1/l2

, we get that the greedy algorithmcovers all pairs when

r>l2×log(N)≥l2×(log(k(k?1)/2)+2log(l).

This shows that the number of test cases required by thegreedy algorithm grows at most logarithmically in k andquadratically in l. Gargano, Körner, and Vaccaro haveshown [11] that for very large values of k, the number oftest cases n satisfies

n~

l

log2k.Their results are nonconstructive and it seems unlikely thatthe linear growth in l is true for moderate values of k.

4A HEURISTIC ALGORITHM

The proof of logarithmic growth for the greedy algorithmassumes that at each stage it is possible to find a test casethat covers the maximum number of uncovered pairs. Sincethere can be many possible test cases, it is not always com-putationally possible to find an optimal test case. We nowoutline a random greedy algorithm we developed. Againfor simplicity of notation we state the algorithm for pair-wise coverage.

Assume that we have a system with k test parameters andthat the ith parameter has li different values. Assume that wehave already selected r test cases. We select the r + 1 by firstgenerating M different candidate test cases and then choos-ing one that covers the most new pairs. Each candidate testcase is selected by the following greedy algorithm:

1) Choose a parameter f and a value l for f such that thatparameter value appears in the greatest number ofuncovered pairs.

2) Let f1 = f. Then choose a random order for the re-maining parameters. Then, we have an order for all kparameters f1, ?? fk.

3) Assume that values have been selected for parametersf1, ??, fj. For 1 ?? i ?? j, let the selected value for fi becalled vi. Then, choose a value vj+1 for fj+1 as follows.For each possible value v for fj, find the number ofnew pairs in the set of pairs {?? j}. Then, let vfj+1 = v and fi = vi for 1 ?? ij+1 be one of the values that appeared inthe greatest number of new pairs.Note that, in this step, each parameter value is con-sidered only once for inclusion in a candidate testcase. Also, that when choosing a value for parameterfj+1, the possible values are compared with only the jvalues already chosen for parameters f1, ??, fj.We did many experiments with this algorithm. When weset M = 50, i.e., when we generated 50 candidate test casesfor each new test case, the number of generated test casesgrew logarithmically in the number of parameters (when allthe parameters had the same number of values). IncreasingM did not dramatically reduce the number of generatedtests. Since the candidate test cases depend on the randomorder selected in Step 2, using a different random seed canproduce a different test set. One useful optimization is togenerate 50 different test sets using 50 different randomseeds and then choose the best among them. This some-times reduces the number of generated tests by 10 to 20percent. There is also a deterministic construction and analternative random algorithm [7] that sometimes generatefewer test cases.

5AETG INPUT LANGUAGE

The basic constructs of the AETG input language are fieldsand relations

. The fields are the system’s test parameters

440IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. 23, NO. 7, JULY 1997and the relations define relationships between the test pa-

rameters. To define a relation, the tester specifies the fields

it contains and a set of valid and invalid values for each

field. A test generated from valid values is a valid test and a

test generated from valid and invalid values is an invalid

test. Invalid tests usually abort before completion because

of some error condition.

Table 5 shows two relations that refine the test model

given in Table 1 in Section 2. The two relations, Relation 1

and Relation 2, have the same four fields: Call Type, Billing,

Access, and Status. Relation 1 defines 2 ?? 33

test scenarios, and relation 2 defines 2 ?? 32 = 54 different = 18 different

test scenarios. Since International isn’t a valid value for Call

Type in relation 1 and 800 isn’t a valid value for Billing in

relation 2, the set of test scenarios defined by Table 5 has

the constraint that the pair (Call Type = International) &

(Billing = 800) is not valid, i.e., that there are no interna-

tional calls to 800 numbers.

TABLE 5T

WO RELATIONS FOR

PLACING A CALL WITH CONSTRAINT

The tester specifies a degree to test for each relation. If the

tester specifies pair-wise testing, the AETG system gener-

ates tests that cover all valid pair-wise combinations of val-

ues of the relation’s fields. This means that for any two

fields f1 and f2 and any values v1 for f1 and v2 for f2, there is

some test in which f1 has the value v1 and f2 has the value v2.

If the tester specifies n-way testing, the AETG system will

generate a test set that covers all n-way parameter combi-

nations for each relation.

The AETG system generates tests for a set of relations by

combining tests for the individual relations. The algorithm

for combining tests insures that for each combined test

there is a set of relations such that the projection of the test

onto the fields in each relation in the set is a test for that

relation. If two relations have no common fields, the com-

bined tests for the two relations are simply concatenations

of tests for each individual relation.

The AETG system generates an invalid test for each invalid

value specified for a field in a relation. A value is an invalid

value only within the context of a relation. A value which is

invalid for a field in one relation may be a valid value for that

field in another relation. To avoid having one invalid value

mask another the AETG system uses only one invalid value

per test case. It creates the test for an invalid value by taking

a valid test for the relation and substituting the invalid value

in place of the field’s valid value in that test.The tester can also guarantee inclusion of their favoritetest cases by specifying them as seed tests or partial seed testsfor a relation. The seed tests are included in the generatedtest set without modification. The partial seed tests are seedtest cases that have fields that have not been assigned val-ues. The AETG system completes the partial test cases byfilling in values for the missing fields.5.1ConstraintsWhile constraints can be expressed using multiple relationsas shown in Table 5, it may be more efficient to expressthem explicitly by using unallowed tests. An unallowed testfor a relation specifies a set of test cases that are not validfor that relation. Table 6 shows a relation with an explicitconstraint. The relation, Relation 3, has the same four fieldsas the two relations in Table 5. It also has the explicit con-straint that any test case with (Call Type = International) &(Billing = 800) is not allowed, independent of the values forthe Access and Status fields (the * in Table 6 is a wild card).Relation 3 defines the same set of possible test scenarios asrelations 1 and 2, but the two AETG inputs are not identical.Since relations 1 and 2 have incompatible values for the CallType field, tests generated for one relation are not valid testsfor the other. Since each relation requires nine tests for pair-wise coverage, the union of the two test sets has 18 tests. Re-lation 3 requires only the 10 tests shown in Table 7.TABLE 6DEFINITION OF RELATION 3TABLE 7TEN TEST CASES FOR RELATION 3Relations 1 and 2 together require more tests than rela-tion 3 because they impose more stringent test require-ments. Relation 1 specifies that the pair (Access = ISDN) &(Status = Busy) is covered in the context of Call Type = (Localor Long Distance) and relation 2 specifies that the pair is

covered in the context of Call Type = International. Conse-

COHEN ET AL.: THE AETG SYSTEM: AN APPROACH TO TESTING BASED ON COMBINATORIAL DESIGN441

quently, the pair is covered twice in the union of the testsets for the two relations, once in each context. However,the pair is covered only once in the test set for relation 3. Arelation specifies not only a set of pairs to be covered butalso a context for those pairs.

In this example, the tester may not care if the pair (Access= ISDN) & (Status = Busy) is covered in both contexts. Inthat case, an alternative semantics would regard the rela-tion as specifying only a set of pairs and not a context. Thetwo specifications would then be equivalent and Table 7would be a test plan for either specification.

A simple test generation algorithm is to first generatetests for one relation and then use them to account for pairsin the other relation. This algorithm however does not gen-erate a minimal test set. For example, consider first cover-ing Relation 1 and then Relation 2. Relation 1 would stillrequire nine test cases and Relation 2 would require twotest cases, one for the pair (Call Type = International) &(Billing = Caller) and one for the pair (Call Type = Interna-tional) & (Billing = Collect). The combined test set wouldthen have 11 test cases. This in one more than the 10 shownin Table 7.

We doubt that testers would prefer as a rule to ignorethe context provided by the relation. Testers often use dif-ferent relations to define different semantic situations. Forexample, they may have one relation to define require-ments to test a line interface card when the line’s protocol isEthernet and another for when the protocol is ATM. Thetester would want to insure that flow control worked inboth environments.

Since the fields in an AETG relation have only a finitenumber of values, the user-interface can translate higher levelconstraints such as x ?? y and x ?? y into the unallowed tests.

5.2Hierarchy and Hierarchical Testing

A system often has several natural degrees of interactionbetween its fields. A few fields might be important and thetester may want to test their interactions with each othermore intensively then their interactions with the rest of thesystem. One option is to have two relations. One whichcontains all the fields and which is tested for pair-wisecombinations and another which contains only the mostimportant fields and which is tested for a high-degree ofinteraction. However, that would be wasteful. A better so-lution is to use a subrelation.

A subrelation is a relation that is used as a part of an-other relation. The tester can put the most important fieldsinto a subrelation and give it a high degree of interactiontesting. The tester can then use the subrelation inside rela-tions that are tested for a lower degree of interaction. Whengenerating tests, the AETG system will first generate teststhat cover the subrelation’s specified degree of interactionand then use those tests as partial seed test cases when gen-erating tests for the containing relation.

6EXPERIMENTS

We did experiments to check the effectiveness of AETG testsets. In one experiment, we tested user interface modulesfrom two releases of a Bellcore system. In another, we

measured code coverage of AETG test sets.

In the first experiment, the AETG system tested mod-ules from two releases of a Bellcore system, System A. Ittested nine modules from the first release and 13 from thesecond. The modules were designed to validate the user’sinput for internal consistency. A validation module usu-ally has from 1,000 to 2,000 lines of C code. In this ex-periment, the testers created the AETG input from themodule’s detailed development requirements. Althoughthe modules had already been tested, the experimentfound problems caused by defects in the code and by de-fects in the requirement’s documents.

shows the number of code defects and the column labeledTable 8 shows the results. The column labeled CodeRequirements shows the number of requirement defects.There are more requirements defects than code defects. Therequirements defects are introduced when the system engi-neers take the high-level user-oriented requirements andwrite detailed development requirements. This process re-quires a great deal of effort and knowledge; faults are oftenintroduced during it. Many of these faults are corrected inthe code later in the development process. Finding anddocumenting them is important since the detailed devel-opment requirements are used for maintenance.

We also measured the code coverage given by AETG testsets. We used the ATAC [15], [23] coverage tool to measurethe block, decision, C-uses and P-uses metrics of AETGtests generated for several Unix commands and severalvalidation modules from System A. The pair-wise AETGtest sets gave over 90 percent block coverage for both appli-cation domains. For example, a set of 29 pair-wise AETGtests gave 90 percent block coverage for the Unix sort com-mand. We also compared pair-wise testing with randominput testing and found that pair-wise testing gave bettercoverage. For the modules from System A, we also foundthat code coverage didn’t increase when we increased frompair-wise testing to testing all valid input combinations.Table 9 has the results for one module. The Unix coverageexperiments are discussed in detail in [5].

Several coverage experiments were done at Nortel byBurr and Young [2]. They also found that the AETG pair-wise test sets gave good coverage in a variety of situations.Of course, it is easy to construct examples where onlyone unique combination of test parameters will trigger afault. However, there is growing evidence that for manyreal-world systems, a large number of faults are triggeredby many parameter combinations. This is an area that mer-its further study.

TABLE 8

DEFECTS FOUND IN TWO RELEASES OF SYSTEM A

TABLE 9

CODE COVERAGE RESULTS FOR MODULE A